susumu.yata
null+****@clear*****
Fri Nov 30 09:49:01 JST 2012
susumu.yata 2012-11-30 09:49:01 +0900 (Fri, 30 Nov 2012) New Revision: 804617e2223e200ef36a9d8705f8936489538db6 https://github.com/groonga/grnxx/commit/804617e2223e200ef36a9d8705f8936489538db6 Log: Add grnxx::alpha::Vector. grnxx::db::Vector will be replaced after tests and benchmarks. Added files: lib/alpha/vector.cpp lib/alpha/vector.hpp test/test_alpha_vector.cpp Modified files: .gitignore lib/alpha/Makefile.am test/Makefile.am Modified: .gitignore (+1 -0) =================================================================== --- .gitignore 2012-11-29 14:30:23 +0900 (35fcbf1) +++ .gitignore 2012-11-30 09:49:01 +0900 (2d69642) @@ -24,6 +24,7 @@ libtool ltmain.sh missing stamp-h1 +test/test_alpha_vector test/test_backtrace test/test_db_array test/test_db_blob_vector Modified: lib/alpha/Makefile.am (+4 -2) =================================================================== --- lib/alpha/Makefile.am 2012-11-29 14:30:23 +0900 (8044c8d) +++ lib/alpha/Makefile.am 2012-11-30 09:49:01 +0900 (0495d73) @@ -1,8 +1,10 @@ noinst_LTLIBRARIES = libgrnxx_alpha.la libgrnxx_alpha_la_SOURCES = \ - sample.cpp + sample.cpp \ + vector.cpp libgrnxx_alpha_includedir = ${includedir}/grnxx/alpha libgrnxx_alpha_include_HEADERS = \ - sample.hpp + sample.hpp \ + vector.hpp Added: lib/alpha/vector.cpp (+442 -0) 100644 =================================================================== --- /dev/null +++ lib/alpha/vector.cpp 2012-11-30 09:49:01 +0900 (81b5608) @@ -0,0 +1,442 @@ +/* + Copyright (C) 2012 Brazil, Inc. + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public + License as published by the Free Software Foundation; either + version 2.1 of the License, or (at your option) any later version. + + This library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with this library; if not, write to the Free Software + Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA +*/ +#include "vector.hpp" + +#include <vector> + +#include "../exception.hpp" +#include "../lock.hpp" +#include "../logger.hpp" + +namespace grnxx { +namespace alpha { + +VectorCreate VECTOR_CREATE; +VectorOpen VECTOR_OPEN; + +VectorHeader::VectorHeader(const void *default_value, + uint64_t value_size, + uint64_t page_size, + uint64_t table_size, + uint64_t secondary_table_size) + : value_size_(value_size), + page_size_(page_size), + table_size_(table_size), + secondary_table_size_(secondary_table_size), + has_default_value_(default_value ? 1 : 0), + first_table_block_id_(io::BLOCK_INVALID_ID), + secondary_table_block_id_(io::BLOCK_INVALID_ID), + inter_process_mutex_() {} + +StringBuilder &VectorHeader::write_to(StringBuilder &builder) const { + if (!builder) { + return builder; + } + + builder << "{ value_size = " << value_size_ + << ", page_size = " << page_size_ + << ", table_size = " << table_size_ + << ", secondary_table_size = " << secondary_table_size_ + << ", has_default_value = " << has_default_value_ + << ", first_table_block_id = " << first_table_block_id_ + << ", secondary_table_block_id = " << secondary_table_block_id_ + << ", inter_process_mutex = " << inter_process_mutex_; + return builder << " }"; +} + +std::unique_ptr<VectorImpl> VectorImpl::create(io::Pool pool, + const void *default_value, + uint64_t value_size, + uint64_t page_size, + uint64_t table_size, + uint64_t secondary_table_size, + FillPage fill_page) { + std::unique_ptr<VectorImpl> vector(new (std::nothrow) VectorImpl); + if (!vector) { + GRNXX_ERROR() << "new grnxx::io::VectorImpl failed"; + GRNXX_THROW(); + } + vector->create_vector(pool, default_value, value_size, page_size, table_size, + secondary_table_size, fill_page); + return vector; +} + +std::unique_ptr<VectorImpl> VectorImpl::open(io::Pool pool, + uint32_t block_id, + uint64_t value_size, + uint64_t page_size, + uint64_t table_size, + uint64_t secondary_table_size, + FillPage fill_page) { + std::unique_ptr<VectorImpl> vector(new (std::nothrow) VectorImpl); + if (!vector) { + GRNXX_ERROR() << "new grnxx::io::VectorImpl failed"; + GRNXX_THROW(); + } + vector->open_vector(pool, block_id, value_size, page_size, table_size, + secondary_table_size, fill_page); + return vector; +} + +StringBuilder &VectorImpl::write_to(StringBuilder &builder) const { + if (!builder) { + return builder; + } + + builder << "{ pool = " << pool_.path() + << ", block_info = " << *block_info_ + << ", header = " << *header_ + << ", max_page_id = " << max_page_id_ + << ", inter_thread_mutex = " << inter_thread_mutex_; + return builder << " }"; +} + +void VectorImpl::unlink(io::Pool pool, + uint32_t block_id, + uint64_t value_size, + uint64_t page_size, + uint64_t table_size, + uint64_t secondary_table_size) try { + std::vector<uint32_t> block_ids; + + { + std::unique_ptr<VectorImpl> vector = VectorImpl::open( + pool, block_id, value_size, + page_size, table_size, secondary_table_size, nullptr); + const VectorHeader * const header = vector->header_; + + block_ids.push_back(block_id); + + block_ids.push_back(header->first_table_block_id()); + for (uint64_t i = 0; i < header->table_size(); ++i) { + if (vector->first_table_[i] != io::BLOCK_INVALID_ID) { + block_ids.push_back(vector->first_table_[i]); + } + } + + if (header->secondary_table_block_id() != io::BLOCK_INVALID_ID) { + block_ids.push_back(header->secondary_table_block_id()); + uint32_t * const secondary_table = static_cast<uint32_t *>( + pool.get_block_address(header->secondary_table_block_id())); + for (uint64_t i = 0; i < header->secondary_table_size(); ++i) { + if (secondary_table[i] != io::BLOCK_INVALID_ID) { + block_ids.push_back(secondary_table[i]); + uint32_t * const table = static_cast<uint32_t *>( + pool.get_block_address(secondary_table[i])); + for (uint64_t j = 0; j < header->table_size(); ++j) { + if (table[j] != io::BLOCK_INVALID_ID) { + block_ids.push_back(table[j]); + } + } + } + } + } + } + + for (size_t i = 0; i < block_ids.size(); ++i) { + pool.free_block(block_ids[i]); + } +} catch (const std::exception &exception) { + GRNXX_ERROR() << exception; + GRNXX_THROW(); +} + +VectorImpl::VectorImpl() + : pool_(), + fill_page_(nullptr), + block_info_(nullptr), + header_(nullptr), + default_value_(nullptr), + table_size_bits_(0), + table_size_mask_(0), + max_page_id_(0), + first_table_(nullptr), + secondary_table_(nullptr), + secondary_table_cache_(), + first_table_cache_(), + tables_cache_(), + inter_thread_mutex_() {} + +void VectorImpl::create_vector(io::Pool pool, + const void *default_value, + uint64_t value_size, + uint64_t page_size, + uint64_t table_size, + uint64_t secondary_table_size, + FillPage fill_page) { + pool_ = pool; + + std::unique_ptr<void *[]> first_table_cache( + new (std::nothrow) void *[table_size]); + if (!first_table_cache) { + GRNXX_ERROR() << "new void *[" << table_size << "] failed"; + GRNXX_THROW(); + } + + uint64_t header_block_size = sizeof(VectorHeader); + if (default_value) { + header_block_size += value_size; + } + block_info_ = pool_.create_block(header_block_size); + + const io::BlockInfo *first_table_block_info; + try { + first_table_block_info = pool_.create_block(sizeof(uint32_t) * table_size); + } catch (...) { + pool_.free_block(*block_info_); + throw; + } + + void * const block_address = pool_.get_block_address(*block_info_); + header_ = static_cast<VectorHeader *>(block_address); + *header_ = VectorHeader(default_value, value_size, page_size, table_size, + secondary_table_size); + restore_from_header(); + + if (default_value_) { + std::memcpy(default_value_, default_value, + static_cast<size_t>(value_size)); + fill_page_ = fill_page; + } + + header_->set_first_table_block_id(first_table_block_info->id()); + first_table_ = static_cast<uint32_t *>( + pool_.get_block_address(*first_table_block_info)); + first_table_cache_ = std::move(first_table_cache); + for (uint64_t i = 0; i < header_->table_size(); ++i) { + first_table_[i] = io::BLOCK_INVALID_ID; + first_table_cache_[i] = nullptr; + } +} + +void VectorImpl::open_vector(io::Pool pool, + uint32_t block_id, + uint64_t value_size, + uint64_t page_size, + uint64_t table_size, + uint64_t secondary_table_size, + FillPage fill_page) { + pool_ = pool; + + block_info_ = pool_.get_block_info(block_id); + if (block_info_->size() < sizeof(VectorHeader)) { + GRNXX_ERROR() << "invalid argument: block_info = " << *block_info_ + << ", header_size = " << sizeof(VectorHeader); + GRNXX_THROW(); + } + + void * const block_address = pool_.get_block_address(*block_info_); + header_ = static_cast<VectorHeader *>(block_address); + restore_from_header(); + + if (default_value_) { + const uint64_t header_size = sizeof(VectorHeader) + value_size; + if (block_info_->size() < header_size) { + GRNXX_ERROR() << "invalid argument: block_info = " << *block_info_ + << ", header_size = " << header_size; + GRNXX_THROW(); + } + fill_page_ = fill_page; + } + + if (value_size != header_->value_size()) { + GRNXX_ERROR() << "invalid value size: actual = " << header_->value_size() + << ", expected = " << value_size; + GRNXX_THROW(); + } + if (page_size != header_->page_size()) { + GRNXX_ERROR() << "invalid page size: actual = " << header_->page_size() + << ", expected = " << page_size; + GRNXX_THROW(); + } + if (table_size != header_->table_size()) { + GRNXX_ERROR() << "invalid table size: actual = " << header_->table_size() + << ", expected = " << table_size; + GRNXX_THROW(); + } + if (secondary_table_size != header_->secondary_table_size()) { + GRNXX_ERROR() << "invalid secondary table size: actual = " + << header_->secondary_table_size() + << ", expected = " << secondary_table_size; + GRNXX_THROW(); + } + + first_table_ = static_cast<uint32_t *>( + pool_.get_block_address(header_->first_table_block_id())); + + first_table_cache_.reset(new (std::nothrow) void *[header_->table_size()]); + if (!first_table_cache_) { + GRNXX_ERROR() << "new void *[" << header_->table_size() << "] failed"; + GRNXX_THROW(); + } + for (uint64_t i = 0; i < header_->table_size(); ++i) { + first_table_cache_[i] = nullptr; + } +} + +void VectorImpl::restore_from_header() { + if (header_->has_default_value()) { + default_value_ = header_ + 1; + } + table_size_bits_ = bit_scan_reverse(header_->table_size()); + table_size_mask_ = header_->table_size() - 1; + max_page_id_ = header_->table_size() * header_->secondary_table_size() - 1; +} + +void *VectorImpl::get_page_address_on_failure(uint64_t page_id) { + if (page_id < header_->table_size()) { + if (!first_table_cache_[page_id]) { + if (first_table_[page_id] == io::BLOCK_INVALID_ID) { + initialize_page(&first_table_[page_id]); + } + first_table_cache_[page_id] = + pool_.get_block_address(first_table_[page_id]); + } + return first_table_cache_[page_id]; + } + + if (page_id <= max_page_id_) { + if (!tables_cache_) { + if (!secondary_table_cache_) { + if (!secondary_table_) { + if (header_->secondary_table_block_id() == io::BLOCK_INVALID_ID) { + initialize_secondary_table(); + } + secondary_table_ = static_cast<uint32_t *>( + pool_.get_block_address(header_->secondary_table_block_id())); + } + initialize_secondary_table_cache(); + } + initialize_tables_cache(); + } + + const uint64_t table_id = page_id >> table_size_bits_; + std::unique_ptr<void *[]> &table_cache = tables_cache_[table_id]; + if (!table_cache) { + if (secondary_table_[table_id] == io::BLOCK_INVALID_ID) { + initialize_table(&secondary_table_[table_id]); + } + secondary_table_cache_[table_id] = static_cast<uint32_t *>( + pool_.get_block_address(secondary_table_[table_id])); + initialize_table_cache(&table_cache); + } + + page_id &= table_size_mask_; + if (!table_cache[page_id]) { + uint32_t * const table = secondary_table_cache_[table_id]; + if (table[page_id] == io::BLOCK_INVALID_ID) { + initialize_page(&table[page_id]); + } + table_cache[page_id] = pool_.get_block_address(table[page_id]); + } + return table_cache[page_id]; + } + + GRNXX_ERROR() << "invalid argument: page_id = " << page_id + << ": [0, " << max_page_id_ <<']'; + GRNXX_THROW(); +} + +void VectorImpl::initialize_secondary_table() { + Lock lock(mutable_inter_process_mutex()); + if (header_->secondary_table_block_id() == io::BLOCK_INVALID_ID) { + const auto block_info = pool_.create_block( + sizeof(uint32_t) * header_->secondary_table_size()); + uint32_t * const body = static_cast<uint32_t *>( + pool_.get_block_address(*block_info)); + for (uint64_t i = 0; i < header_->secondary_table_size(); ++i) { + body[i] = io::BLOCK_INVALID_ID; + } + header_->set_secondary_table_block_id(block_info->id()); + } +} + +void VectorImpl::initialize_table(uint32_t *table_block_id) { + Lock lock(mutable_inter_process_mutex()); + if (*table_block_id == io::BLOCK_INVALID_ID) { + const auto block_info = pool_.create_block( + sizeof(uint32_t) * header_->table_size()); + uint32_t * const body = static_cast<uint32_t *>( + pool_.get_block_address(*block_info)); + for (uint64_t i = 0; i < header_->table_size(); ++i) { + body[i] = io::BLOCK_INVALID_ID; + } + *table_block_id = block_info->id(); + } +} + +void VectorImpl::initialize_page(uint32_t *page_block_id) { + Lock lock(mutable_inter_process_mutex()); + if (*page_block_id == io::BLOCK_INVALID_ID) { + const io::BlockInfo *block_info = pool_.create_block( + header_->value_size() * header_->page_size()); + if (fill_page_) { + fill_page_(pool_.get_block_address(*block_info), default_value_); + } + *page_block_id = block_info->id(); + } +} + +void VectorImpl::initialize_secondary_table_cache() { + Lock lock(mutable_inter_thread_mutex()); + if (!secondary_table_cache_) { + std::unique_ptr<uint32_t *[]> tables( + new (std::nothrow) uint32_t *[header_->secondary_table_size()]); + if (!tables) { + GRNXX_ERROR() << "new grnxx::uint32_t *[" + << header_->secondary_table_size() << "] failed"; + GRNXX_THROW(); + } + for (uint64_t i = 0; i < header_->secondary_table_size(); ++i) { + tables[i] = nullptr; + } + secondary_table_cache_ = std::move(tables); + } +} + +void VectorImpl::initialize_table_cache( + std::unique_ptr<void *[]> *table_cache) { + Lock lock(mutable_inter_thread_mutex()); + if (!*table_cache) { + std::unique_ptr<void *[]> cache( + new (std::nothrow) void *[header_->table_size()]); + if (!cache) { + GRNXX_ERROR() << "new void *[" << header_->table_size() << "] failed"; + GRNXX_THROW(); + } + for (uint64_t i = 0; i < header_->table_size(); ++i) { + cache[i] = nullptr; + } + *table_cache = std::move(cache); + } +} + +void VectorImpl::initialize_tables_cache() { + Lock lock(mutable_inter_thread_mutex()); + if (!tables_cache_) { + std::unique_ptr<std::unique_ptr<void *[]>[]> cache(new (std::nothrow) + std::unique_ptr<void *[]>[header_->secondary_table_size()]); + for (uint64_t i = 0; i < header_->secondary_table_size(); ++i) { + cache[i] = nullptr; + } + tables_cache_ = std::move(cache); + } +} + +} // namespace alpha +} // namespace grnxx Added: lib/alpha/vector.hpp (+329 -0) 100644 =================================================================== --- /dev/null +++ lib/alpha/vector.hpp 2012-11-30 09:49:01 +0900 (14dbb95) @@ -0,0 +1,329 @@ +/* + Copyright (C) 2012 Brazil, Inc. + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public + License as published by the Free Software Foundation; either + version 2.1 of the License, or (at your option) any later version. + + This library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with this library; if not, write to the Free Software + Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA +*/ +#ifndef GRNXX_ALPHA_VECTOR_HPP +#define GRNXX_ALPHA_VECTOR_HPP + +#include "../io/pool.hpp" + +namespace grnxx { +namespace alpha { + +const uint64_t VECTOR_MIN_PAGE_SIZE = uint64_t(1) << 0; +const uint64_t VECTOR_MAX_PAGE_SIZE = uint64_t(1) << 20; +const uint64_t VECTOR_DEFAULT_PAGE_SIZE = uint64_t(1) << 16; + +const uint64_t VECTOR_MIN_TABLE_SIZE = uint64_t(1) << 10; +const uint64_t VECTOR_MAX_TABLE_SIZE = uint64_t(1) << 20; +const uint64_t VECTOR_DEFAULT_TABLE_SIZE = uint64_t(1) << 12; + +const uint64_t VECTOR_MIN_SECONDARY_TABLE_SIZE = uint64_t(1) << 10; +const uint64_t VECTOR_MAX_SECONDARY_TABLE_SIZE = uint64_t(1) << 20; +const uint64_t VECTOR_DEFAULT_SECONDARY_TABLE_SIZE = uint64_t(1) << 12; + +extern class VectorCreate {} VECTOR_CREATE; +extern class VectorOpen {} VECTOR_OPEN; + +class VectorHeader { + public: + VectorHeader(const void *default_value, + uint64_t value_size, + uint64_t page_size, + uint64_t table_size, + uint64_t secondary_table_size); + + uint64_t value_size() const { + return value_size_; + } + uint64_t page_size() const { + return page_size_; + } + uint64_t table_size() const { + return table_size_; + } + uint64_t secondary_table_size() const { + return secondary_table_size_; + } + bool has_default_value() const { + return has_default_value_ != 0; + } + uint32_t first_table_block_id() const { + return first_table_block_id_; + } + uint32_t secondary_table_block_id() const { + return secondary_table_block_id_; + } + + void set_first_table_block_id(uint32_t value) { + first_table_block_id_ = value; + } + void set_secondary_table_block_id(uint32_t value) { + secondary_table_block_id_ = value; + } + + Mutex *mutable_inter_process_mutex() { + return &inter_process_mutex_; + } + + StringBuilder &write_to(StringBuilder &builder) const; + + private: + uint64_t value_size_; + uint64_t page_size_; + uint64_t table_size_; + uint64_t secondary_table_size_; + uint32_t has_default_value_; + uint32_t first_table_block_id_; + uint32_t secondary_table_block_id_; + Mutex inter_process_mutex_; +}; + +inline StringBuilder &operator<<(StringBuilder &builder, + const VectorHeader &header) { + return header.write_to(builder); +} + +class VectorImpl { + typedef void (*FillPage)(void *page_address, const void *value); + + public: + static std::unique_ptr<VectorImpl> create(io::Pool pool, + const void *default_value, + uint64_t value_size, + uint64_t page_size, + uint64_t table_size, + uint64_t secondary_table_size, + FillPage fill_page); + static std::unique_ptr<VectorImpl> open(io::Pool pool, + uint32_t block_id, + uint64_t value_size, + uint64_t page_size, + uint64_t table_size, + uint64_t secondary_table_size, + FillPage fill_page); + + template <uint64_t PAGE_SIZE, + uint64_t TABLE_SIZE, + uint64_t SECONDARY_TABLE_SIZE> + void *get_page_address(uint64_t page_id) { + if ((page_id < TABLE_SIZE) && first_table_cache_[page_id]) { + return first_table_cache_[page_id]; + } + if ((page_id < (TABLE_SIZE * SECONDARY_TABLE_SIZE)) && tables_cache_) { + const uint64_t table_id = page_id / TABLE_SIZE; + const std::unique_ptr<void *[]> &table_cache = tables_cache_[table_id]; + if (table_cache) { + const uint64_t local_page_id = page_id % TABLE_SIZE; + if (table_cache[local_page_id]) { + return table_cache[local_page_id]; + } + } + } + return get_page_address_on_failure(page_id); + } + + uint32_t block_id() const { + return block_info_->id(); + } + + StringBuilder &write_to(StringBuilder &builder) const; + + static void unlink(io::Pool pool, + uint32_t block_id, + uint64_t value_size, + uint64_t page_size, + uint64_t table_size, + uint64_t secondary_table_size); + + private: + io::Pool pool_; + FillPage fill_page_; + const io::BlockInfo *block_info_; + VectorHeader *header_; + void *default_value_; + uint8_t table_size_bits_; + uint64_t table_size_mask_; + uint64_t max_page_id_; + uint32_t *first_table_; + uint32_t *secondary_table_; + std::unique_ptr<uint32_t *[]> secondary_table_cache_; + std::unique_ptr<void *[]> first_table_cache_; + std::unique_ptr<std::unique_ptr<void *[]>[]> tables_cache_; + Mutex inter_thread_mutex_; + + VectorImpl(); + + void create_vector(io::Pool pool, + const void *default_value, + uint64_t value_size, + uint64_t page_size, + uint64_t table_size, + uint64_t secondary_table_size, + FillPage fill_page); + void open_vector(io::Pool pool, + uint32_t block_id, + uint64_t value_size, + uint64_t page_size, + uint64_t table_size, + uint64_t secondary_table_size, + FillPage fill_page); + void restore_from_header(); + + void *get_page_address_on_failure(uint64_t page_id); + + void initialize_secondary_table(); + void initialize_table(uint32_t *table_block_id); + void initialize_page(uint32_t *page_block_id); + void initialize_secondary_table_cache(); + void initialize_table_cache(std::unique_ptr<void *[]> *table_cache); + void initialize_tables_cache(); + + Mutex *mutable_inter_process_mutex() { + return header_->mutable_inter_process_mutex(); + } + Mutex *mutable_inter_thread_mutex() { + return &inter_thread_mutex_; + } +}; + +inline StringBuilder &operator<<(StringBuilder &builder, + const VectorImpl &vector) { + return vector.write_to(builder); +} + +template <typename T, + uint64_t PAGE_SIZE = VECTOR_DEFAULT_PAGE_SIZE, + uint64_t TABLE_SIZE = VECTOR_DEFAULT_TABLE_SIZE, + uint64_t SECONDARY_TABLE_SIZE = VECTOR_DEFAULT_SECONDARY_TABLE_SIZE> +class Vector { + static_assert(PAGE_SIZE >= VECTOR_MIN_PAGE_SIZE, "too small PAGE_SIZE"); + static_assert(PAGE_SIZE <= VECTOR_MAX_PAGE_SIZE, "too large PAGE_SIZE"); + static_assert((PAGE_SIZE & (PAGE_SIZE - 1)) == 0, + "PAGE_SIZE must be a power of two"); + + static_assert(TABLE_SIZE >= VECTOR_MIN_TABLE_SIZE, "too small TABLE_SIZE"); + static_assert(TABLE_SIZE <= VECTOR_MAX_TABLE_SIZE, "too large TABLE_SIZE"); + static_assert((TABLE_SIZE & (TABLE_SIZE - 1)) == 0, + "TABLE_SIZE must be a power of two"); + + static_assert(SECONDARY_TABLE_SIZE >= VECTOR_MIN_SECONDARY_TABLE_SIZE, + "too small SECONDARY_TABLE_SIZE"); + static_assert(SECONDARY_TABLE_SIZE <= VECTOR_MAX_SECONDARY_TABLE_SIZE, + "too large SECONDARY_TABLE_SIZE"); + static_assert((SECONDARY_TABLE_SIZE & (SECONDARY_TABLE_SIZE - 1)) == 0, + "SECONDARY_TABLE_SIZE must be a power of two"); + + public: + typedef T Value; + + Vector() : impl_() {} + Vector(io::Pool pool, const VectorCreate &) + : impl_(VectorImpl::create(pool, nullptr, sizeof(Value), PAGE_SIZE, + TABLE_SIZE, SECONDARY_TABLE_SIZE, fill_page)) {} + Vector(io::Pool pool, const VectorCreate &, const Value &default_value) + : impl_(VectorImpl::create(pool, &default_value, sizeof(Value), PAGE_SIZE, + TABLE_SIZE, SECONDARY_TABLE_SIZE, fill_page)) {} + Vector(io::Pool pool, const VectorOpen &, uint32_t block_id) + : impl_(VectorImpl::open(pool, block_id, sizeof(Value), PAGE_SIZE, + TABLE_SIZE, SECONDARY_TABLE_SIZE, fill_page)) {} + ~Vector() {} + + Vector(const Vector &vector) : impl_(vector.impl_) {} + Vector &operator=(const Vector &vector) { + impl_ = vector.impl_; + return *this; + } + + Vector(Vector &&vector) : impl_(std::move(vector.impl_)) {} + Vector &operator=(Vector &&vector) { + impl_ = std::move(vector.impl_); + return *this; + } + + GRNXX_EXPLICIT_CONVERSION operator bool() const { + return static_cast<bool>(impl_); + } + + Value &operator[](uint64_t id) { + void * const page_address = + impl_->get_page_address<PAGE_SIZE, TABLE_SIZE, + SECONDARY_TABLE_SIZE>(id / PAGE_SIZE); + return static_cast<T *>(page_address)[id % PAGE_SIZE]; + } + + uint32_t block_id() const { + return impl_->block_id(); + } + + void swap(Vector &rhs) { + impl_.swap(rhs.impl_); + } + + StringBuilder &write_to(StringBuilder &builder) const { + return impl_ ? impl_->write_to(builder) : (builder << "n/a"); + } + + static GRNXX_CONSTEXPR uint64_t value_size() { + return sizeof(Value); + } + static GRNXX_CONSTEXPR uint64_t page_size() { + return PAGE_SIZE; + } + static GRNXX_CONSTEXPR uint64_t table_size() { + return TABLE_SIZE; + } + static GRNXX_CONSTEXPR uint64_t secondary_table_size() { + return SECONDARY_TABLE_SIZE; + } + static GRNXX_CONSTEXPR uint64_t max_id() { + return (PAGE_SIZE * TABLE_SIZE * SECONDARY_TABLE_SIZE) - 1; + } + + static void unlink(io::Pool pool, uint32_t block_id) { + VectorImpl::unlink(pool, block_id, sizeof(Value), + PAGE_SIZE, TABLE_SIZE, SECONDARY_TABLE_SIZE); + } + + private: + std::shared_ptr<VectorImpl> impl_; + + static void fill_page(void *page_address, const void *value) { + Value *values = static_cast<Value *>(page_address); + for (uint64_t i = 0; i < PAGE_SIZE; ++i) { + std::memcpy(&values[i], value, sizeof(Value)); + } + } +}; + +template <typename T, uint64_t PAGE_SIZE, uint64_t TABLE_SIZE, + uint64_t SECONDARY_TABLE_SIZE> +inline void swap(Vector<T, PAGE_SIZE, TABLE_SIZE, SECONDARY_TABLE_SIZE> &lhs, + Vector<T, PAGE_SIZE, TABLE_SIZE, SECONDARY_TABLE_SIZE> &rhs) { + lhs.swap(rhs); +} + +template <typename T, uint64_t PAGE_SIZE, uint64_t TABLE_SIZE, + uint64_t SECONDARY_TABLE_SIZE> +inline StringBuilder &operator<<(StringBuilder &builder, + const Vector<T, PAGE_SIZE, TABLE_SIZE, SECONDARY_TABLE_SIZE> &vector) { + return vector.write_to(builder); +} + +} // namespace alpha +} // namespace grnxx + +#endif // GRNXX_ALPHA_VECTOR_HPP Modified: test/Makefile.am (+4 -0) =================================================================== --- test/Makefile.am 2012-11-29 14:30:23 +0900 (248074b) +++ test/Makefile.am 2012-11-30 09:49:01 +0900 (41f485e) @@ -1,6 +1,7 @@ AM_CXXFLAGS = -I../lib TESTS = \ + test_alpha_vector \ test_backtrace \ test_db_array \ test_db_blob_vector \ @@ -28,6 +29,9 @@ TESTS = \ check_PROGRAMS = $(TESTS) +test_alpha_vector_SOURCES = test_alpha_vector.cpp +test_alpha_vector_LDADD = ../lib/libgrnxx.la + test_backtrace_SOURCES = test_backtrace.cpp test_backtrace_LDADD = ../lib/libgrnxx.la Added: test/test_alpha_vector.cpp (+301 -0) 100644 =================================================================== --- /dev/null +++ test/test_alpha_vector.cpp 2012-11-30 09:49:01 +0900 (a78773f) @@ -0,0 +1,301 @@ +/* + Copyright (C) 2012 Brazil, Inc. + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public + License as published by the Free Software Foundation; either + version 2.1 of the License, or (at your option) any later version. + + This library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with this library; if not, write to the Free Software + Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA +*/ +#include <cassert> +#include <cstdlib> +#include <random> +#include <vector> + +#include "alpha/vector.hpp" +#include "logger.hpp" +#include "time.hpp" + +struct Point { + double x; + double y; +}; + +void test_basics() { + grnxx::io::Pool::unlink_if_exists("temp.grn"); + + grnxx::io::Pool pool("temp.grn", grnxx::io::GRNXX_IO_CREATE); + + grnxx::alpha::Vector<std::uint32_t> vector( + pool, grnxx::alpha::VECTOR_CREATE); + + assert(vector.block_id() == 0); + assert(vector.value_size() == sizeof(std::uint32_t)); + assert(vector.page_size() == grnxx::alpha::VECTOR_DEFAULT_PAGE_SIZE); + assert(vector.table_size() == grnxx::alpha::VECTOR_DEFAULT_TABLE_SIZE); + assert(vector.secondary_table_size() == + grnxx::alpha::VECTOR_DEFAULT_SECONDARY_TABLE_SIZE); + + GRNXX_NOTICE() << "vector = " << vector; + + grnxx::alpha::Vector<std::uint32_t> vector2; + + vector.swap(vector2); + vector2.swap(vector); + + assert(vector.block_id() != grnxx::io::BLOCK_INVALID_ID); + + vector[0] = 1; + vector[1000] = 10; + vector[1000000] = 100; + vector[1000000000] = 1000; + vector[1000000000000ULL] = 10000; + vector[vector.max_id()] = 100000; + + assert(vector[0] == 1); + assert(vector[1000] == 10); + assert(vector[1000000] == 100); + assert(vector[1000000000] == 1000); + assert(vector[1000000000000ULL] == 10000); + assert(vector[vector.max_id()] == 100000); + + const std::uint32_t block_id = vector.block_id(); + + vector = grnxx::alpha::Vector<std::uint32_t>(); + pool = grnxx::io::Pool(); + + pool = grnxx::io::Pool("temp.grn", grnxx::io::GRNXX_IO_OPEN); + + vector = grnxx::alpha::Vector<std::uint32_t>( + pool, grnxx::alpha::VECTOR_OPEN, block_id); + + assert(vector[0] == 1); + assert(vector[1000] == 10); + assert(vector[1000000] == 100); + assert(vector[1000000000] == 1000); + assert(vector[1000000000000ULL] == 10000); + assert(vector[vector.max_id()] == 100000); + + assert(grnxx::atomic_fetch_and_add(1, &vector[0]) == 1); + assert(vector[0] == 2); + + assert(grnxx::atomic_fetch_and_add(10, &vector[0]) == 2); + assert(vector[0] == 12); + + vector = grnxx::alpha::Vector<std::uint32_t>( + pool, grnxx::alpha::VECTOR_CREATE, 56789); + + assert(vector[0] == 56789); + assert(vector[1000] == 56789); + assert(vector[1000000] == 56789); + assert(vector[1000000000] == 56789); + assert(vector[1000000000000ULL] == 56789); + assert(vector[vector.max_id()] == 56789); + + assert(grnxx::atomic_compare_and_swap( + std::uint32_t(56789), std::uint32_t(98765), &vector[0])); + assert(!grnxx::atomic_compare_and_swap( + std::uint32_t(56789), std::uint32_t(98765), &vector[0])); + assert(grnxx::atomic_compare_and_swap( + std::uint32_t(98765), std::uint32_t(56789), &vector[0])); + assert(vector[0] == 56789); + + vector = grnxx::alpha::Vector<std::uint32_t>(); + + grnxx::alpha::Vector<std::uint32_t>::unlink(pool, 0); + + grnxx::alpha::Vector<float> float_vector(pool, grnxx::alpha::VECTOR_CREATE); + + float_vector[0] = 1.0F; + assert(float_vector[0] == 1.0F); + float_vector[1 << 30] = 2.0F; + assert(float_vector[1 << 30] == 2.0F); + + float_vector = grnxx::alpha::Vector<float>(); + + grnxx::alpha::Vector<double> double_vector( + pool, grnxx::alpha::VECTOR_CREATE); + + double_vector[0] = 1.0; + assert(double_vector[0] == 1.0); + double_vector[1 << 30] = 2.0; + assert(double_vector[1 << 30] == 2.0); + + double_vector = grnxx::alpha::Vector<double>(); + + grnxx::alpha::Vector<Point> point_vector(pool, grnxx::alpha::VECTOR_CREATE); + + point_vector[0].x = 123; + point_vector[0].y = 456; + assert(point_vector[0].x == 123); + assert(point_vector[0].y == 456); + + point_vector[1 << 30].x = 987; + point_vector[1 << 30].y = 654; + assert(point_vector[1 << 30].x == 987); + assert(point_vector[1 << 30].y == 654); + + point_vector = grnxx::alpha::Vector<Point>(); + + pool = grnxx::io::Pool(); + grnxx::io::Pool::unlink_if_exists("temp.grn"); +} + +template <typename T> +void test_times() { + enum { VECTOR_SIZE = 1 << 20 }; + + grnxx::io::Pool pool("temp.grn", grnxx::io::GRNXX_IO_TEMPORARY); + + grnxx::alpha::Vector<T> vector(pool, grnxx::alpha::VECTOR_CREATE); + + grnxx::Time start, end; + + std::uint64_t total = 0; + + start = grnxx::Time::now(); + for (std::uint64_t id = 0; id < VECTOR_SIZE; ++id) { + vector[id] = T(0); + } + end = grnxx::Time::now(); + grnxx::Duration set_1st_elapsed = (end - start) / VECTOR_SIZE; + + start = grnxx::Time::now(); + for (std::uint64_t id = 0; id < VECTOR_SIZE; ++id) { + vector[id] = T(1); + } + end = grnxx::Time::now(); + grnxx::Duration set_2nd_elapsed = (end - start) / VECTOR_SIZE; + + start = grnxx::Time::now(); + for (std::uint64_t id = 0; id < VECTOR_SIZE; ++id) { + total += vector[id]; + } + end = grnxx::Time::now(); + grnxx::Duration get_elapsed = (end - start) / VECTOR_SIZE; + + + start = grnxx::Time::now(); + for (std::uint64_t id = vector.max_id() - VECTOR_SIZE + 1; + id <= vector.max_id(); ++id) { + vector[id] = T(0); + } + end = grnxx::Time::now(); + grnxx::Duration ex_set_1st_elapsed = (end - start) / VECTOR_SIZE; + + start = grnxx::Time::now(); + for (std::uint64_t id = vector.max_id() - VECTOR_SIZE + 1; + id <= vector.max_id(); ++id) { + vector[id] = T(1); + } + end = grnxx::Time::now(); + grnxx::Duration ex_set_2nd_elapsed = (end - start) / VECTOR_SIZE; + + start = grnxx::Time::now(); + for (std::uint64_t id = vector.max_id() - VECTOR_SIZE + 1; + id <= vector.max_id(); ++id) { + total += vector[id]; + } + end = grnxx::Time::now(); + grnxx::Duration ex_get_elapsed = (end - start) / VECTOR_SIZE; + + + const std::uint64_t boundary = vector.page_size() * vector.table_size(); + const std::uint64_t range = 1 << 16; + std::uint64_t id_begin = boundary - (range / 2); + std::uint64_t id_end = boundary + (range / 2); + + for (uint64_t id = id_begin; id < id_end; ++id) { + vector[id] = T(0); + } + + std::mt19937 engine; + std::vector<std::uint64_t> ids(VECTOR_SIZE); + for (int i = 0; i < VECTOR_SIZE; ++i) { + ids[i] = id_begin + (engine() % range); + } + + start = grnxx::Time::now(); + for (int i = 0; i < VECTOR_SIZE; ++i) { + vector[ids[i]] = T(0); + } + end = grnxx::Time::now(); + grnxx::Duration boundary_set_1st_elapsed = (end - start) / VECTOR_SIZE; + + start = grnxx::Time::now(); + for (int i = 0; i < VECTOR_SIZE; ++i) { + vector[ids[i]] = T(1); + } + end = grnxx::Time::now(); + grnxx::Duration boundary_set_2nd_elapsed = (end - start) / VECTOR_SIZE; + + start = grnxx::Time::now(); + for (int i = 0; i < VECTOR_SIZE; ++i) { + total += vector[ids[i]]; + } + end = grnxx::Time::now(); + grnxx::Duration boundary_get_elapsed = (end - start) / VECTOR_SIZE; + + const std::uint32_t block_id = vector.block_id(); + vector = grnxx::alpha::Vector<T>(); + + start = grnxx::Time::now(); + grnxx::alpha::Vector<T>::unlink(pool, block_id); + end = grnxx::Time::now(); + grnxx::Duration unlink_elapsed = end - start; + + vector = grnxx::alpha::Vector<T>(pool, grnxx::alpha::VECTOR_CREATE, 0); + + start = grnxx::Time::now(); + for (std::uint64_t id = 0; id < VECTOR_SIZE; ++id) { + vector[id] = T(0); + } + end = grnxx::Time::now(); + grnxx::Duration default_elapsed = (end - start) / VECTOR_SIZE; + + + GRNXX_NOTICE() << "elapsed [ns]: set = " + << set_2nd_elapsed.nanoseconds() << " (" + << set_1st_elapsed.nanoseconds() << ", " + << default_elapsed.nanoseconds() << ')' + << ", get = " + << get_elapsed.nanoseconds() + << ", ex. set = " + << ex_set_2nd_elapsed.nanoseconds() << " (" + << ex_set_1st_elapsed.nanoseconds() << ')' + << ", ex. get = " + << ex_get_elapsed.nanoseconds() + << ", boundary set = " + << boundary_set_2nd_elapsed.nanoseconds() << " (" + << boundary_set_1st_elapsed.nanoseconds() << ')' + << ", boundary get = " + << boundary_get_elapsed.nanoseconds() + << ", unlink = " + << unlink_elapsed.nanoseconds() + << ", total = " + << total; +} + +int main() { + grnxx::Logger::set_flags(grnxx::LOGGER_WITH_ALL | + grnxx::LOGGER_ENABLE_COUT); + grnxx::Logger::set_max_level(grnxx::NOTICE_LOGGER); + + test_basics(); + test_times<std::uint8_t>(); + test_times<std::uint16_t>(); + test_times<std::uint32_t>(); + test_times<std::uint64_t>(); + test_times<float>(); + test_times<double>(); + + return 0; +} -------------- next part -------------- HTML����������������������������...Download