From 5a66f8e7375bafccf365a1448bd2709fea623335 Mon Sep 17 00:00:00 2001 From: Tor Egge Date: Wed, 15 Feb 2023 16:01:58 +0100 Subject: Add exponential array size growth to tensor buffer type mapper. --- .../tensor_buffer_operations_test.cpp | 4 +- .../tensor_buffer_store_test.cpp | 31 +++++++++++++ .../tensor_buffer_type_mapper_test.cpp | 54 ++++++++++++++++++---- .../tensor/serialized_fast_value_attribute.cpp | 2 +- .../searchlib/tensor/tensor_buffer_operations.cpp | 10 ++-- .../searchlib/tensor/tensor_buffer_operations.h | 3 +- .../vespa/searchlib/tensor/tensor_buffer_store.cpp | 12 +++-- .../vespa/searchlib/tensor/tensor_buffer_store.h | 3 ++ .../searchlib/tensor/tensor_buffer_type_mapper.cpp | 29 ++++++++++-- .../searchlib/tensor/tensor_buffer_type_mapper.h | 3 +- .../src/vespa/vespalib/datastore/array_store.h | 2 + .../src/vespa/vespalib/datastore/array_store.hpp | 2 +- .../vespalib/datastore/array_store_type_mapper.h | 1 + 13 files changed, 131 insertions(+), 25 deletions(-) diff --git a/searchlib/src/tests/tensor/tensor_buffer_operations/tensor_buffer_operations_test.cpp b/searchlib/src/tests/tensor/tensor_buffer_operations/tensor_buffer_operations_test.cpp index 9bed7a11bee..321e174862f 100644 --- a/searchlib/src/tests/tensor/tensor_buffer_operations/tensor_buffer_operations_test.cpp +++ b/searchlib/src/tests/tensor/tensor_buffer_operations/tensor_buffer_operations_test.cpp @@ -78,7 +78,7 @@ TensorBufferOperationsTest::get_array_sizes(uint32_t max_subspaces) { std::vector array_sizes; for (uint32_t num_subspaces = 0; num_subspaces < max_subspaces; ++num_subspaces) { - array_sizes.emplace_back(_ops.get_array_size(num_subspaces)); + array_sizes.emplace_back(_ops.get_buffer_size(num_subspaces)); } return array_sizes; } @@ -88,7 +88,7 @@ TensorBufferOperationsTest::store_tensor(const Value& tensor) { EXPECT_EQ(_tensor_type, tensor.type()); uint32_t num_subspaces = tensor.index().size(); - auto array_size = _ops.get_array_size(num_subspaces); + auto array_size = _ops.get_buffer_size(num_subspaces); std::vector buf; buf.resize(array_size); _ops.store_tensor(buf, tensor); diff --git a/searchlib/src/tests/tensor/tensor_buffer_store/tensor_buffer_store_test.cpp b/searchlib/src/tests/tensor/tensor_buffer_store/tensor_buffer_store_test.cpp index ec7fc2334c4..0a69d8149ed 100644 --- a/searchlib/src/tests/tensor/tensor_buffer_store/tensor_buffer_store_test.cpp +++ b/searchlib/src/tests/tensor/tensor_buffer_store/tensor_buffer_store_test.cpp @@ -6,6 +6,8 @@ #include #include #include +#include +#include using search::tensor::TensorBufferStore; using vespalib::datastore::EntryRef; @@ -177,4 +179,33 @@ TEST_F(TensorBufferStoreTest, get_vectors) EXPECT_EQ(0, _store.get_vectors(EntryRef()).subspaces()); } +TEST_F(TensorBufferStoreTest, buffer_handles_range_of_subspaces) +{ + auto offset_bits = TensorBufferStore::get_offset_bits(); + TensorBufferStore store(_tensor_type, {}, 400); + std::vector refs; + vespalib::hash_set buffers; + TensorSpec tensor_spec(tensor_type_spec); + for (uint32_t x = 0; x < 400; ++x) { + vespalib::asciistream x_stream; + x_stream << x; + vespalib::string x_as_string = x_stream.str(); + tensor_spec.add({{"x", x_as_string.c_str()}}, x + 1.5); + auto tensor = value_from_spec(tensor_spec, FastValueBuilderFactory::get()); + EXPECT_EQ(_tensor_type, tensor->type()); + auto ref = store.store_tensor(*tensor); + refs.emplace_back(ref); + auto buffer_id = ref.buffer_id(offset_bits); + buffers.insert(buffer_id); + } + EXPECT_EQ(156u, buffers.size()); + uint32_t x = 0; + for (auto ref : refs) { + auto tensor = store.get_tensor(ref); + ++x; + EXPECT_EQ(x, tensor->index().size()); + EXPECT_EQ(x, store.get_vectors(ref).subspaces()); + } +} + GTEST_MAIN_RUN_ALL_TESTS() diff --git a/searchlib/src/tests/tensor/tensor_buffer_type_mapper/tensor_buffer_type_mapper_test.cpp b/searchlib/src/tests/tensor/tensor_buffer_type_mapper/tensor_buffer_type_mapper_test.cpp index d7eaa6b633d..17612f08271 100644 --- a/searchlib/src/tests/tensor/tensor_buffer_type_mapper/tensor_buffer_type_mapper_test.cpp +++ b/searchlib/src/tests/tensor/tensor_buffer_type_mapper/tensor_buffer_type_mapper_test.cpp @@ -15,14 +15,18 @@ const vespalib::string tensor_type_2d_mixed_spec("tensor(x{},y[2])"); const vespalib::string float_tensor_type_spec("tensor(y{})"); const vespalib::string tensor_type_dense_spec("tensor(x[2])"); +constexpr double grow_factor = 1.02; + struct TestParam { vespalib::string _name; std::vector _array_sizes; + std::vector _large_array_sizes; vespalib::string _tensor_type_spec; - TestParam(vespalib::string name, std::vector array_sizes, const vespalib::string& tensor_type_spec) + TestParam(vespalib::string name, std::vector array_sizes, std::vector large_array_sizes, const vespalib::string& tensor_type_spec) : _name(std::move(name)), _array_sizes(std::move(array_sizes)), + _large_array_sizes(std::move(large_array_sizes)), _tensor_type_spec(tensor_type_spec) { } @@ -49,6 +53,7 @@ protected: TensorBufferTypeMapperTest(); ~TensorBufferTypeMapperTest() override; std::vector get_array_sizes(); + std::vector get_large_array_sizes(); void select_type_ids(); }; @@ -56,7 +61,7 @@ TensorBufferTypeMapperTest::TensorBufferTypeMapperTest() : testing::TestWithParam(), _tensor_type(ValueType::from_spec(GetParam()._tensor_type_spec)), _ops(_tensor_type), - _mapper(GetParam()._array_sizes.size(), &_ops) + _mapper(GetParam()._array_sizes.size(), grow_factor, &_ops) { } @@ -70,11 +75,33 @@ TensorBufferTypeMapperTest::get_array_sizes() for (uint32_t type_id = 1; type_id <= max_small_subspaces_type_id; ++type_id) { auto num_subspaces = type_id - 1; array_sizes.emplace_back(_mapper.get_array_size(type_id)); - EXPECT_EQ(_ops.get_array_size(num_subspaces), array_sizes.back()); + EXPECT_EQ(_ops.get_buffer_size(num_subspaces), array_sizes.back()); } return array_sizes; } +std::vector +TensorBufferTypeMapperTest::get_large_array_sizes() +{ + auto& large_array_sizes = GetParam()._large_array_sizes; + uint32_t max_large = large_array_sizes.size(); + TensorBufferTypeMapper mapper(max_large * 100, grow_factor, &_ops); + std::vector result; + for (uint32_t i = 0; i < max_large; ++i) { + uint32_t type_id = (i + 1) * 100; + auto array_size = mapper.get_array_size(type_id); + result.emplace_back(array_size); + EXPECT_EQ(type_id, mapper.get_type_id(array_size)); + EXPECT_EQ(type_id, mapper.get_type_id(array_size - 1)); + if (array_size == large_array_sizes.back()) { + EXPECT_EQ(0u, mapper.get_type_id(array_size + 1)); + } else { + EXPECT_EQ(type_id + 1, mapper.get_type_id(array_size + 1)); + } + } + return result; +} + void TensorBufferTypeMapperTest::select_type_ids() { @@ -101,11 +128,11 @@ TensorBufferTypeMapperTest::select_type_ids() INSTANTIATE_TEST_SUITE_P(TensorBufferTypeMapperMultiTest, TensorBufferTypeMapperTest, - testing::Values(TestParam("1d", {8, 16, 32, 40, 64}, tensor_type_sparse_spec), - TestParam("1dfloat", {4, 12, 20, 28, 36}, float_tensor_type_spec), - TestParam("2d", {8, 24, 40, 56, 80}, tensor_type_2d_spec), - TestParam("2dmixed", {8, 24, 48, 64, 96}, tensor_type_2d_mixed_spec), - TestParam("dense", {8, 24}, tensor_type_dense_spec)), + testing::Values(TestParam("1d", {8, 16, 32, 40, 64}, {1760, 10880, 76896, 555248, 4020512}, tensor_type_sparse_spec), + TestParam("1dfloat", {4, 12, 20, 28, 36}, {1728, 11104, 79168, 572128, 4143664}, float_tensor_type_spec), + TestParam("2d", {8, 24, 40, 56, 80}, {1600, 9184, 63872, 460416, 3332976}, tensor_type_2d_spec), + TestParam("2dmixed", {8, 24, 48, 64, 96}, {1984, 11472, 79824, 575504, 4166208}, tensor_type_2d_mixed_spec), + TestParam("dense", {8, 24}, {}, tensor_type_dense_spec)), testing::PrintToStringParamName()); TEST_P(TensorBufferTypeMapperTest, array_sizes_are_calculated) @@ -118,4 +145,15 @@ TEST_P(TensorBufferTypeMapperTest, type_ids_are_selected) select_type_ids(); } +TEST_P(TensorBufferTypeMapperTest, large_arrays_grows_exponentially) +{ + EXPECT_EQ(GetParam()._large_array_sizes, get_large_array_sizes()); +} + +TEST_P(TensorBufferTypeMapperTest, avoid_array_size_overflow) +{ + TensorBufferTypeMapper mapper(400, 2.0, &_ops); + EXPECT_GE(30, mapper.get_max_small_array_type_id(1000)); +} + GTEST_MAIN_RUN_ALL_TESTS() diff --git a/searchlib/src/vespa/searchlib/tensor/serialized_fast_value_attribute.cpp b/searchlib/src/vespa/searchlib/tensor/serialized_fast_value_attribute.cpp index c4dd0ef30f0..6612db1d27e 100644 --- a/searchlib/src/vespa/searchlib/tensor/serialized_fast_value_attribute.cpp +++ b/searchlib/src/vespa/searchlib/tensor/serialized_fast_value_attribute.cpp @@ -15,7 +15,7 @@ namespace search::tensor { SerializedFastValueAttribute::SerializedFastValueAttribute(stringref name, const Config &cfg, const NearestNeighborIndexFactory& index_factory) : TensorAttribute(name, cfg, _tensorBufferStore, index_factory), - _tensorBufferStore(cfg.tensorType(), get_memory_allocator(), 1000u) + _tensorBufferStore(cfg.tensorType(), get_memory_allocator(), 400u) { } diff --git a/searchlib/src/vespa/searchlib/tensor/tensor_buffer_operations.cpp b/searchlib/src/vespa/searchlib/tensor/tensor_buffer_operations.cpp index 3a42b47ace3..fcdb9311ec6 100644 --- a/searchlib/src/vespa/searchlib/tensor/tensor_buffer_operations.cpp +++ b/searchlib/src/vespa/searchlib/tensor/tensor_buffer_operations.cpp @@ -110,7 +110,7 @@ TensorBufferOperations::store_tensor(ArrayRef buf, const vespalib::eval::V auto cells_start_offset = aligner.align(labels_end_offset); auto cells_end_offset = cells_start_offset + cells_mem_size; auto store_end = aligner.align(cells_end_offset); - assert(store_end == get_array_size(num_subspaces)); + assert(store_end == get_buffer_size(num_subspaces)); assert(buf.size() >= store_end); *reinterpret_cast(buf.data()) = num_subspaces; auto labels = reinterpret_cast(buf.data() + get_labels_offset()); @@ -137,8 +137,8 @@ TensorBufferOperations::store_tensor(ArrayRef buf, const vespalib::eval::V if (cells_mem_size > 0) { memcpy(buf.data() + cells_start_offset, cells.data, cells_mem_size); } - if (cells_end_offset != store_end) { - memset(buf.data() + cells_end_offset, 0, store_end - cells_end_offset); + if (cells_end_offset != buf.size()) { + memset(buf.data() + cells_end_offset, 0, buf.size() - cells_end_offset); } } @@ -146,7 +146,7 @@ std::unique_ptr TensorBufferOperations::make_fast_view(ConstArrayRef buf, const vespalib::eval::ValueType& tensor_type) const { auto num_subspaces = get_num_subspaces(buf); - assert(buf.size() >= get_array_size(num_subspaces)); + assert(buf.size() >= get_buffer_size(num_subspaces)); ConstArrayRef labels(reinterpret_cast(buf.data() + get_labels_offset()), num_subspaces * _num_mapped_dimensions); auto cells_size = num_subspaces * _subspace_type.size(); auto cells_mem_size = num_subspaces * _subspace_type.mem_size(); // Size measured in bytes @@ -185,7 +185,7 @@ void TensorBufferOperations::encode_stored_tensor(ConstArrayRef buf, const vespalib::eval::ValueType& tensor_type, vespalib::nbostream& target) const { auto num_subspaces = get_num_subspaces(buf); - assert(buf.size() >= get_array_size(num_subspaces)); + assert(buf.size() >= get_buffer_size(num_subspaces)); ConstArrayRef labels(reinterpret_cast(buf.data() + get_labels_offset()), num_subspaces * _num_mapped_dimensions); auto cells_size = num_subspaces * _subspace_type.size(); auto cells_mem_size = num_subspaces * _subspace_type.mem_size(); // Size measured in bytes diff --git a/searchlib/src/vespa/searchlib/tensor/tensor_buffer_operations.h b/searchlib/src/vespa/searchlib/tensor/tensor_buffer_operations.h index 26cf9a429a1..3928b41c2d1 100644 --- a/searchlib/src/vespa/searchlib/tensor/tensor_buffer_operations.h +++ b/searchlib/src/vespa/searchlib/tensor/tensor_buffer_operations.h @@ -80,7 +80,8 @@ class TensorBufferOperations return get_num_subspaces(get_num_subspaces_and_flag(buf)); } public: - size_t get_array_size(uint32_t num_subspaces) const noexcept { + // Size (in bytes) used to serialize tensor with num_subspaces. + size_t get_buffer_size(uint32_t num_subspaces) const noexcept { auto cells_mem_size = get_cells_mem_size(num_subspaces); auto aligner = select_aligner(cells_mem_size); return get_cells_offset(num_subspaces, aligner) + aligner.align(cells_mem_size); diff --git a/searchlib/src/vespa/searchlib/tensor/tensor_buffer_store.cpp b/searchlib/src/vespa/searchlib/tensor/tensor_buffer_store.cpp index 6c2ef698dc0..ff39c33fc5d 100644 --- a/searchlib/src/vespa/searchlib/tensor/tensor_buffer_store.cpp +++ b/searchlib/src/vespa/searchlib/tensor/tensor_buffer_store.cpp @@ -26,6 +26,8 @@ namespace { constexpr float ALLOC_GROW_FACTOR = 0.2; +constexpr double mapper_grow_factor = 1.02; + } TensorBufferStore::TensorBufferStore(const ValueType& tensor_type, std::shared_ptr allocator, uint32_t max_small_subspaces_type_id) @@ -33,11 +35,11 @@ TensorBufferStore::TensorBufferStore(const ValueType& tensor_type, std::shared_p _tensor_type(tensor_type), _ops(_tensor_type), _array_store(ArrayStoreType::optimizedConfigForHugePage(max_small_subspaces_type_id, - TensorBufferTypeMapper(max_small_subspaces_type_id, &_ops), + TensorBufferTypeMapper(max_small_subspaces_type_id, mapper_grow_factor, &_ops), MemoryAllocator::HUGEPAGE_SIZE, MemoryAllocator::PAGE_SIZE, 8_Ki, ALLOC_GROW_FACTOR), - std::move(allocator), TensorBufferTypeMapper(max_small_subspaces_type_id, &_ops)) + std::move(allocator), TensorBufferTypeMapper(max_small_subspaces_type_id, mapper_grow_factor, &_ops)) { } @@ -81,7 +83,11 @@ EntryRef TensorBufferStore::store_tensor(const Value &tensor) { uint32_t num_subspaces = tensor.index().size(); - auto array_size = _ops.get_array_size(num_subspaces); + auto buffer_size = _ops.get_buffer_size(num_subspaces); + auto& mapper = _array_store.get_mapper(); + auto type_id = mapper.get_type_id(buffer_size); + auto array_size = (type_id != 0) ? mapper.get_array_size(type_id) : buffer_size; + assert(array_size >= buffer_size); auto ref = _array_store.allocate(array_size); auto buf = _array_store.get_writable(ref); _ops.store_tensor(buf, tensor); diff --git a/searchlib/src/vespa/searchlib/tensor/tensor_buffer_store.h b/searchlib/src/vespa/searchlib/tensor/tensor_buffer_store.h index ce00977c298..f602836bd32 100644 --- a/searchlib/src/vespa/searchlib/tensor/tensor_buffer_store.h +++ b/searchlib/src/vespa/searchlib/tensor/tensor_buffer_store.h @@ -44,6 +44,9 @@ public: auto buf = _array_store.get(ref); return _ops.get_vectors(buf); } + + // Used by unit test + static constexpr uint32_t get_offset_bits() noexcept { return RefType::offset_bits; } }; } diff --git a/searchlib/src/vespa/searchlib/tensor/tensor_buffer_type_mapper.cpp b/searchlib/src/vespa/searchlib/tensor/tensor_buffer_type_mapper.cpp index b4b0b9bbc79..ce8cc11026c 100644 --- a/searchlib/src/vespa/searchlib/tensor/tensor_buffer_type_mapper.cpp +++ b/searchlib/src/vespa/searchlib/tensor/tensor_buffer_type_mapper.cpp @@ -3,6 +3,8 @@ #include "tensor_buffer_type_mapper.h" #include "tensor_buffer_operations.h" #include +#include +#include namespace search::tensor { @@ -12,15 +14,29 @@ TensorBufferTypeMapper::TensorBufferTypeMapper() { } -TensorBufferTypeMapper::TensorBufferTypeMapper(uint32_t max_small_subspaces_type_id, TensorBufferOperations* ops) +TensorBufferTypeMapper::TensorBufferTypeMapper(uint32_t max_small_subspaces_type_id, double grow_factor, TensorBufferOperations* ops) : _array_sizes(), _ops(ops) { _array_sizes.reserve(max_small_subspaces_type_id + 1); _array_sizes.emplace_back(0); // type id 0 uses LargeSubspacesBufferType + uint32_t num_subspaces = 0; + size_t prev_array_size = 0u; + size_t array_size = 0u; for (uint32_t type_id = 1; type_id <= max_small_subspaces_type_id; ++type_id) { - auto num_subspaces = type_id - 1; - _array_sizes.emplace_back(_ops->get_array_size(num_subspaces)); + if (type_id > 1) { + num_subspaces = std::max(num_subspaces + 1, static_cast(std::floor(num_subspaces * grow_factor))); + } + array_size = _ops->get_buffer_size(num_subspaces); + while (array_size <= prev_array_size) { + ++num_subspaces; + array_size = _ops->get_buffer_size(num_subspaces); + } + if (array_size > std::numeric_limits::max()) { + break; + } + _array_sizes.emplace_back(array_size); + prev_array_size = array_size; } } @@ -44,4 +60,11 @@ TensorBufferTypeMapper::get_array_size(uint32_t type_id) const return _array_sizes[type_id]; } +uint32_t +TensorBufferTypeMapper::get_max_small_array_type_id(uint32_t max_small_array_type_id) const noexcept +{ + auto clamp_type_id = _array_sizes.size() - 1; + return (clamp_type_id < max_small_array_type_id) ? clamp_type_id : max_small_array_type_id; +} + } diff --git a/searchlib/src/vespa/searchlib/tensor/tensor_buffer_type_mapper.h b/searchlib/src/vespa/searchlib/tensor/tensor_buffer_type_mapper.h index 950076c9924..ad2116a429c 100644 --- a/searchlib/src/vespa/searchlib/tensor/tensor_buffer_type_mapper.h +++ b/searchlib/src/vespa/searchlib/tensor/tensor_buffer_type_mapper.h @@ -25,12 +25,13 @@ public: using LargeBufferType = LargeSubspacesBufferType; TensorBufferTypeMapper(); - TensorBufferTypeMapper(uint32_t max_small_subspaces_type_id, TensorBufferOperations* ops); + TensorBufferTypeMapper(uint32_t max_small_subspaces_type_id, double grow_factor, TensorBufferOperations* ops); ~TensorBufferTypeMapper(); uint32_t get_type_id(size_t array_size) const; size_t get_array_size(uint32_t type_id) const; TensorBufferOperations& get_tensor_buffer_operations() const noexcept { return *_ops; } + uint32_t get_max_small_array_type_id(uint32_t max_small_array_type_id) const noexcept; }; } diff --git a/vespalib/src/vespa/vespalib/datastore/array_store.h b/vespalib/src/vespa/vespalib/datastore/array_store.h index c76b71ae34e..9e403a52b44 100644 --- a/vespalib/src/vespa/vespalib/datastore/array_store.h +++ b/vespalib/src/vespa/vespalib/datastore/array_store.h @@ -144,6 +144,8 @@ public: bool has_free_lists_enabled() const { return _store.has_free_lists_enabled(); } bool has_held_buffers() const noexcept { return _store.has_held_buffers(); } + const TypeMapper& get_mapper() const noexcept { return _mapper; } + static ArrayStoreConfig optimizedConfigForHugePage(uint32_t maxSmallArrayTypeId, size_t hugePageSize, size_t smallPageSize, diff --git a/vespalib/src/vespa/vespalib/datastore/array_store.hpp b/vespalib/src/vespa/vespalib/datastore/array_store.hpp index 4276318f993..53b149fda80 100644 --- a/vespalib/src/vespa/vespalib/datastore/array_store.hpp +++ b/vespalib/src/vespa/vespalib/datastore/array_store.hpp @@ -220,7 +220,7 @@ ArrayStore::optimizedConfigForHugePage(uint32_t maxSm size_t minNumArraysForNewBuffer, float allocGrowFactor) { - return ArrayStoreConfig::optimizeForHugePage(maxSmallArrayTypeId, + return ArrayStoreConfig::optimizeForHugePage(mapper.get_max_small_array_type_id(maxSmallArrayTypeId), [&](uint32_t type_id) noexcept { return mapper.get_array_size(type_id); }, hugePageSize, smallPageSize, diff --git a/vespalib/src/vespa/vespalib/datastore/array_store_type_mapper.h b/vespalib/src/vespa/vespalib/datastore/array_store_type_mapper.h index 0fc1073d577..1b1e085ed16 100644 --- a/vespalib/src/vespa/vespalib/datastore/array_store_type_mapper.h +++ b/vespalib/src/vespa/vespalib/datastore/array_store_type_mapper.h @@ -23,6 +23,7 @@ public: uint32_t get_type_id(size_t array_size) const { return array_size; } size_t get_array_size(uint32_t type_id) const { return type_id; } + static uint32_t get_max_small_array_type_id(uint32_t max_small_array_type_id) noexcept { return max_small_array_type_id; } }; } -- cgit v1.2.3