diff options
author | Tor Egge <Tor.Egge@online.no> | 2023-06-14 10:56:21 +0200 |
---|---|---|
committer | Tor Egge <Tor.Egge@online.no> | 2023-06-14 10:56:21 +0200 |
commit | 11496a9a886ae5ce6a0e742674d307b705abd7fd (patch) | |
tree | 82b9cd6630bd2c9df7ce65a0d4cc09a0901385b8 /vespalib/src | |
parent | 086b5e4fdab9d3ca275d87c740108d48945034bb (diff) |
Add DynamicArrayBufferType.
Diffstat (limited to 'vespalib/src')
6 files changed, 437 insertions, 0 deletions
diff --git a/vespalib/src/tests/datastore/dynamic_array_buffer_type/CMakeLists.txt b/vespalib/src/tests/datastore/dynamic_array_buffer_type/CMakeLists.txt new file mode 100644 index 00000000000..02cb0464e7c --- /dev/null +++ b/vespalib/src/tests/datastore/dynamic_array_buffer_type/CMakeLists.txt @@ -0,0 +1,9 @@ +# Copyright Yahoo. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +vespa_add_executable(vespalib_dynamic_array_buffer_type_test_app TEST + SOURCES + dynamic_array_buffer_type_test.cpp + DEPENDS + vespalib + GTest::GTest +) +vespa_add_test(NAME vespalib_dynamic_array_buffer_type_test_app COMMAND vespalib_dynamic_array_buffer_type_test_app) diff --git a/vespalib/src/tests/datastore/dynamic_array_buffer_type/dynamic_array_buffer_type_test.cpp b/vespalib/src/tests/datastore/dynamic_array_buffer_type/dynamic_array_buffer_type_test.cpp new file mode 100644 index 00000000000..d5244ae56aa --- /dev/null +++ b/vespalib/src/tests/datastore/dynamic_array_buffer_type/dynamic_array_buffer_type_test.cpp @@ -0,0 +1,249 @@ +// Copyright Yahoo. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. + +#include <vespa/vespalib/datastore/dynamic_array_buffer_type.hpp> +#include <vespa/vespalib/gtest/gtest.h> +#include <ostream> + +using vespalib::datastore::BufferTypeBase; +using vespalib::datastore::DynamicArrayBufferType; +using vespalib::datastore::EntryCount; + +namespace { + +struct CleanContextBase +{ + std::atomic<size_t> _extra_used_bytes; + std::atomic<size_t> _extra_hold_bytes; + CleanContextBase() + : _extra_used_bytes(0), + _extra_hold_bytes(0) + { + } +}; + +struct MyCleanContext : public CleanContextBase, + public BufferTypeBase::CleanContext +{ + MyCleanContext() + : CleanContextBase(), + BufferTypeBase::CleanContext(_extra_used_bytes, _extra_hold_bytes) + { + } +}; + +struct Counts { + uint32_t _def_constructs; + uint32_t _value_constructs; + uint32_t _copy_constructs; + uint32_t _destructs; + uint32_t _assigns; + + Counts(uint32_t def_constructs, uint32_t value_constructs, uint32_t copy_constructs, uint32_t destructs, uint32_t assigns) + : _def_constructs(def_constructs), + _value_constructs(value_constructs), + _copy_constructs(copy_constructs), + _destructs(destructs), + _assigns(assigns) + { + } + + Counts() + : Counts(0, 0, 0, 0, 0) + { + } + bool operator==(const Counts &rhs) const { + return _def_constructs == rhs._def_constructs && + _value_constructs == rhs._value_constructs && + _copy_constructs == rhs._copy_constructs && + _destructs == rhs._destructs && + _assigns == rhs._assigns; + } +}; + +Counts counts; + +std::ostream& operator<<(std::ostream& os, const Counts& c) { + os << "{def_constructs=" << c._def_constructs << + ", value_constructs=" << c._value_constructs << + ", copy_constructs=" << c._copy_constructs << + ", destructs=" << c._destructs << + ", assigns=" << c._assigns << "}"; + return os; +} + +struct WrapInt32 { + int32_t _v; + + WrapInt32() + : _v(0) + { + ++counts._def_constructs; + } + WrapInt32(int v) + : _v(v) + { + ++counts._value_constructs; + } + WrapInt32(const WrapInt32& rhs) + : _v(rhs._v) + { + ++counts._copy_constructs; + } + WrapInt32& operator=(const WrapInt32& rhs) { + _v = rhs._v; + ++counts._assigns; + return *this; + } + ~WrapInt32() { + ++counts._destructs; + } +}; + +} + +class DynamicArrayBufferTypeTest : public testing::Test +{ +protected: + DynamicArrayBufferTypeTest(); + ~DynamicArrayBufferTypeTest() override; + + using BufferType = DynamicArrayBufferType<WrapInt32>; + + template <typename ElemT> + uint32_t get_entry_size(uint32_t array_size); + + std::vector<int> get_vector(const void *buffer, uint32_t offset, uint32_t array_size); + std::vector<int> get_vector(const void *buffer, uint32_t offset); + std::vector<int> get_max_vector(const void *buffer, uint32_t offset); + void write_entry1(); + + BufferType _buffer_type; + size_t _entry_size; + size_t _buf_size; + std::unique_ptr<char[]> _buf; +}; + +DynamicArrayBufferTypeTest::DynamicArrayBufferTypeTest() + : testing::Test(), + _buffer_type(3, 0, 10, 0, 0.2), + _entry_size(_buffer_type.entry_size()), + _buf_size(2 * _entry_size), + _buf(std::make_unique<char[]>(_buf_size)) +{ + // Call initialize_reserved_entries to force construction of empty element + _buffer_type.initialize_reserved_entries(_buf.get(), 1); + memset(_buf.get(), 55, _buf_size); + // Reset counts after empty element has been constructed + counts = Counts(); +} + +DynamicArrayBufferTypeTest::~DynamicArrayBufferTypeTest() = default; + +template <typename ElemT> +uint32_t +DynamicArrayBufferTypeTest::get_entry_size(uint32_t array_size) +{ + DynamicArrayBufferType<ElemT> my_buffer_type(array_size, 0, 10, 0, 0.2); + return my_buffer_type.entry_size(); +} + +std::vector<int> +DynamicArrayBufferTypeTest::get_vector(const void* buffer, uint32_t offset, uint32_t array_size) +{ + auto e = BufferType::get_entry(buffer, offset, _entry_size); + std::vector<int> result; + for (uint32_t i = 0; i < array_size; ++i) { + result.emplace_back(e[i]._v); + } + return result; +} + +std::vector<int> +DynamicArrayBufferTypeTest::get_vector(const void* buffer, uint32_t offset) +{ + auto e = BufferType::get_entry(buffer, offset, _entry_size); + auto array_size = BufferType::get_dynamic_array_size(e, _entry_size); + EXPECT_GE(_buffer_type.getArraySize(), array_size); + return get_vector(buffer, offset, array_size); +} + +std::vector<int> +DynamicArrayBufferTypeTest::get_max_vector(const void* buffer, uint32_t offset) +{ + auto array_size = _buffer_type.getArraySize(); + return get_vector(buffer, offset, array_size); +} + +void +DynamicArrayBufferTypeTest::write_entry1() +{ + auto e1 = BufferType::get_entry(_buf.get(), 1, _entry_size); + BufferType::set_dynamic_array_size(e1, _entry_size, 2); + new (static_cast<void *>(e1)) WrapInt32(42); + new (static_cast<void *>(e1 + 1)) WrapInt32(47); + new (static_cast<void *>(e1 + 2)) WrapInt32(49); // Not cleaned by clean_hold +} + +TEST_F(DynamicArrayBufferTypeTest, entry_size_is_calculated) +{ + EXPECT_EQ(8, get_entry_size<char>(1)); + EXPECT_EQ(8, get_entry_size<char>(2)); + EXPECT_EQ(8, get_entry_size<char>(3)); + EXPECT_EQ(8, get_entry_size<char>(4)); + EXPECT_EQ(12, get_entry_size<char>(5)); + EXPECT_EQ(8, get_entry_size<int16_t>(1)); + EXPECT_EQ(8, get_entry_size<int16_t>(2)); + EXPECT_EQ(12, get_entry_size<int16_t>(3)); + EXPECT_EQ(8, get_entry_size<int32_t>(1)); + EXPECT_EQ(12, get_entry_size<int32_t>(2)); + EXPECT_EQ(16, get_entry_size<int64_t>(1)); + EXPECT_EQ(24, get_entry_size<int64_t>(2)); + EXPECT_EQ(20, get_entry_size<WrapInt32>(4)); +} + +TEST_F(DynamicArrayBufferTypeTest, initialize_reserved_entries) +{ + _buffer_type.initialize_reserved_entries(_buf.get(), 2); + EXPECT_EQ((std::vector<int>{}), get_vector(_buf.get(), 0)); + EXPECT_EQ((std::vector<int>{}), get_vector(_buf.get(), 1)); + EXPECT_EQ((std::vector<int>{0, 0, 0}), get_max_vector(_buf.get(), 0)); + EXPECT_EQ((std::vector<int>{0, 0, 0}), get_max_vector(_buf.get(), 1)); + EXPECT_EQ(Counts(0, 0, 6, 0, 0), counts); +} + +TEST_F(DynamicArrayBufferTypeTest, fallback_copy) +{ + _buffer_type.initialize_reserved_entries(_buf.get(), 1); + write_entry1(); + EXPECT_EQ(Counts(0, 3, 3, 0, 0), counts); + auto buf2 = std::make_unique<char[]>(_buf_size); + _buffer_type.fallback_copy(buf2.get(), _buf.get(), 2); + EXPECT_EQ((std::vector<int>{}), get_vector(buf2.get(), 0)); + EXPECT_EQ((std::vector<int>{42, 47}), get_vector(buf2.get(), 1)); + EXPECT_EQ((std::vector<int>{0, 0, 0}), get_max_vector(buf2.get(), 0)); + EXPECT_EQ((std::vector<int>{42, 47, 49}), get_max_vector(buf2.get(), 1)); + EXPECT_EQ(Counts(0, 3, 9, 0, 0), counts); +} + +TEST_F(DynamicArrayBufferTypeTest, destroy_entries) +{ + _buffer_type.initialize_reserved_entries(_buf.get(), 2); + write_entry1(); + _buffer_type.destroy_entries(_buf.get(), 2); + EXPECT_EQ(Counts(0, 3, 6, 6, 0), counts); +} + +TEST_F(DynamicArrayBufferTypeTest, clean_hold) +{ + _buffer_type.initialize_reserved_entries(_buf.get(), 1); + write_entry1(); + MyCleanContext clean_context; + _buffer_type.clean_hold(_buf.get(), 1, 1, clean_context); + EXPECT_EQ((std::vector<int>{0, 0}), get_vector(_buf.get(), 1)); + EXPECT_EQ((std::vector<int>{0, 0, 49}), get_max_vector(_buf.get(), 1)); + EXPECT_EQ(Counts(0, 3, 3, 0, 2), counts); + _buffer_type.clean_hold(_buf.get(), 0, 2, clean_context); + EXPECT_EQ(Counts(0, 3, 3, 0, 4), counts); +} + +GTEST_MAIN_RUN_ALL_TESTS() diff --git a/vespalib/src/vespa/vespalib/datastore/CMakeLists.txt b/vespalib/src/vespa/vespalib/datastore/CMakeLists.txt index 1c3b9112dda..8b76c576cf0 100644 --- a/vespalib/src/vespa/vespalib/datastore/CMakeLists.txt +++ b/vespalib/src/vespa/vespalib/datastore/CMakeLists.txt @@ -16,6 +16,7 @@ vespa_add_library(vespalib_vespalib_datastore OBJECT compaction_strategy.cpp datastore.cpp datastorebase.cpp + dynamic_array_buffer_type.cpp entry_ref_filter.cpp entryref.cpp fixed_size_hash_map.cpp diff --git a/vespalib/src/vespa/vespalib/datastore/dynamic_array_buffer_type.cpp b/vespalib/src/vespa/vespalib/datastore/dynamic_array_buffer_type.cpp new file mode 100644 index 00000000000..df2129e8ff2 --- /dev/null +++ b/vespalib/src/vespa/vespalib/datastore/dynamic_array_buffer_type.cpp @@ -0,0 +1,17 @@ +// Copyright Yahoo. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. + +#include "dynamic_array_buffer_type.hpp" + +namespace vespalib::datastore { + +template class DynamicArrayBufferType<char>; +template class DynamicArrayBufferType<int8_t>; +template class DynamicArrayBufferType<int16_t>; +template class DynamicArrayBufferType<int32_t>; +template class DynamicArrayBufferType<int64_t>; +template class DynamicArrayBufferType<float>; +template class DynamicArrayBufferType<double>; +template class DynamicArrayBufferType<AtomicEntryRef>; + +} + diff --git a/vespalib/src/vespa/vespalib/datastore/dynamic_array_buffer_type.h b/vespalib/src/vespa/vespalib/datastore/dynamic_array_buffer_type.h new file mode 100644 index 00000000000..7e2c70b2374 --- /dev/null +++ b/vespalib/src/vespa/vespalib/datastore/dynamic_array_buffer_type.h @@ -0,0 +1,57 @@ +// Copyright Yahoo. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. + +#pragma once + +#include "buffer_type.h" + +namespace vespalib::datastore { + +/** + * Concrete class used to manage allocation and de-allocation of + * elements of type ElemType in data store buffers. + * + * Layout of each entry is: + * + * elements[array_size] - array of elements in entry + * padding - to align entries + * dynamic_array_size - number of array elements that should + * be visible to reader. + */ +template <typename ElemT> +class DynamicArrayBufferType : public BufferTypeBase +{ +public: + using ElemType = ElemT; +protected: + static const ElemType& empty_entry() noexcept; + ElemType* get_entry(void *buffer, size_t offset) noexcept { return get_entry(buffer, offset, entry_size()); } + const ElemType* get_entry(const void *buffer, size_t offset) const noexcept { return get_entry(buffer, offset, entry_size()); } +public: + DynamicArrayBufferType(const DynamicArrayBufferType &rhs) = delete; + DynamicArrayBufferType & operator=(const DynamicArrayBufferType &rhs) = delete; + DynamicArrayBufferType(DynamicArrayBufferType && rhs) noexcept = default; + DynamicArrayBufferType & operator=(DynamicArrayBufferType && rhs) noexcept = default; + DynamicArrayBufferType(uint32_t array_size, uint32_t min_entries, uint32_t max_entries, + uint32_t num_entries_for_new_buffer, float allocGrowFactor) noexcept; + ~DynamicArrayBufferType() override; + void destroy_entries(void* buffer, EntryCount num_entries) override; + void fallback_copy(void* new_buffer, const void* old_buffer, EntryCount num_entries) override; + void initialize_reserved_entries(void* buffer, EntryCount reserved_entries) override; + void clean_hold(void* buffer, size_t offset, EntryCount num_entries, CleanContext cleanCxt) override; + static uint32_t calc_entry_size(uint32_t array_size) noexcept; + static ElemType* get_entry(void* buffer, size_t offset, uint32_t entry_size) noexcept { return reinterpret_cast<ElemType*>(static_cast<char*>(buffer) + offset * entry_size); } + static const ElemType* get_entry(const void* buffer, size_t offset, uint32_t entry_size) noexcept { return reinterpret_cast<const ElemType*>(static_cast<const char*>(buffer) + offset * entry_size); } + static uint32_t get_dynamic_array_size(const void *buffer, uint32_t entry_size) noexcept { return *reinterpret_cast<const uint32_t*>(static_cast<const char*>(buffer) + entry_size - sizeof(uint32_t)); } + static void set_dynamic_array_size(void *buffer, uint32_t entry_size, uint32_t array_size) noexcept { *reinterpret_cast<uint32_t*>(static_cast<char*>(buffer) + entry_size - sizeof(uint32_t)) = array_size; } +}; + +extern template class DynamicArrayBufferType<char>; +extern template class DynamicArrayBufferType<int8_t>; +extern template class DynamicArrayBufferType<int16_t>; +extern template class DynamicArrayBufferType<int32_t>; +extern template class DynamicArrayBufferType<int64_t>; +extern template class DynamicArrayBufferType<float>; +extern template class DynamicArrayBufferType<double>; +extern template class DynamicArrayBufferType<AtomicEntryRef>; + +} diff --git a/vespalib/src/vespa/vespalib/datastore/dynamic_array_buffer_type.hpp b/vespalib/src/vespa/vespalib/datastore/dynamic_array_buffer_type.hpp new file mode 100644 index 00000000000..9085e32db6b --- /dev/null +++ b/vespalib/src/vespa/vespalib/datastore/dynamic_array_buffer_type.hpp @@ -0,0 +1,104 @@ +// Copyright Yahoo. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. + +#pragma once + +#include "dynamic_array_buffer_type.h" +#include "aligner.h" +#include <algorithm> +#include <cassert> + +namespace vespalib::datastore { + +template <typename ElemT> +DynamicArrayBufferType<ElemT>::DynamicArrayBufferType(uint32_t array_size, uint32_t min_entries, uint32_t max_entries, + uint32_t num_entries_for_new_buffer, float allocGrowFactor) noexcept + : BufferTypeBase(calc_entry_size(array_size), array_size, min_entries, max_entries, num_entries_for_new_buffer, allocGrowFactor) +{ } + +template <typename ElemT> +DynamicArrayBufferType<ElemT>::~DynamicArrayBufferType() = default; + +template <typename ElemT> +uint32_t +DynamicArrayBufferType<ElemT>::calc_entry_size(uint32_t array_size) noexcept +{ + Aligner aligner(std::max(alignof(uint32_t), alignof(ElemType))); + return aligner.align(sizeof(ElemType) * array_size + sizeof(uint32_t)); +} + +template <typename ElemT> +void +DynamicArrayBufferType<ElemT>::destroy_entries(void* buffer, EntryCount num_entries) +{ + uint32_t array_size = _arraySize; + for (uint32_t entry_idx = 0; entry_idx < num_entries; ++entry_idx) { + auto e = get_entry(buffer, entry_idx); + for (uint32_t elem_idx = 0; elem_idx < array_size; ++elem_idx) { + e->~ElemType(); + ++e; + } + } +} + +template <typename ElemT> +void +DynamicArrayBufferType<ElemT>::fallback_copy(void* new_buffer, const void* old_buffer, EntryCount num_entries) +{ + uint32_t array_size = _arraySize; + for (uint32_t entry_idx = 0; entry_idx < num_entries; ++entry_idx) { + auto d = get_entry(new_buffer, entry_idx); + auto s = get_entry(old_buffer, entry_idx); + set_dynamic_array_size(d, entry_size(), get_dynamic_array_size(s, entry_size())); + for (uint32_t elem_idx = 0; elem_idx < array_size; ++elem_idx) { + new (static_cast<void*>(d)) ElemType(*s); + ++s; + ++d; + } + } +} + +template <typename ElemT> +void +DynamicArrayBufferType<ElemT>::initialize_reserved_entries(void* buffer, EntryCount reserved_entries) +{ + uint32_t array_size = _arraySize; + const auto& empty = empty_entry(); + for (uint32_t entry_idx = 0; entry_idx < reserved_entries; ++entry_idx) { + auto e = get_entry(buffer, entry_idx); + set_dynamic_array_size(e, entry_size(), 0); + for (uint32_t elem_idx = 0; elem_idx < array_size; ++elem_idx) { + new (static_cast<void*>(e)) ElemType(empty); + ++e; + } + } +} + +template <typename ElemT> +void +DynamicArrayBufferType<ElemT>::clean_hold(void* buffer, size_t offset, EntryCount num_entries, CleanContext) +{ + uint32_t max_array_size = _arraySize; + const auto& empty = empty_entry(); + for (uint32_t entry_idx = 0; entry_idx < num_entries; ++entry_idx) { + auto e = get_entry(buffer, offset + entry_idx); + auto array_size = get_dynamic_array_size(e, entry_size()); + assert(array_size <= max_array_size); + for (uint32_t elem_idx = 0; elem_idx < array_size; ++elem_idx) { + *e = empty; + ++e; + } + } +} + +template <typename ElemT> +const ElemT& +DynamicArrayBufferType<ElemT>::empty_entry() noexcept +{ + // It's possible for ElemType to wrap e.g. an Alloc instance, which has a transitive + // dependency on globally constructed allocator object(s). To avoid issues with global + // construction order, initialize the sentinel on the first access. + static ElemType empty = ElemType(); + return empty; +} + +} |