Add class for configuring an array store.

7 files changed, 216 insertions, 0 deletions

diff --git a/searchlib/CMakeLists.txt b/searchlib/CMakeLists.txt
index 0ca4fe41d2e..bb07dc90459 100644
--- a/searchlib/CMakeLists.txt
+++ b/searchlib/CMakeLists.txt
@@ -103,6 +103,7 @@ vespa_define_module(
     src/tests/common/sequencedtaskexecutor
     src/tests/common/summaryfeatures
     src/tests/datastore/array_store
+    src/tests/datastore/array_store_config
     src/tests/datastore/datastore
     src/tests/diskindex/bitvector
     src/tests/diskindex/diskindex
diff --git a/searchlib/src/tests/datastore/array_store_config/CMakeLists.txt b/searchlib/src/tests/datastore/array_store_config/CMakeLists.txt
new file mode 100644
index 00000000000..465e697553a
--- /dev/null
+++ b/searchlib/src/tests/datastore/array_store_config/CMakeLists.txt
@@ -0,0 +1,8 @@
+# Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+vespa_add_executable(searchlib_array_store_config_test_app TEST
+    SOURCES
+    array_store_config_test.cpp
+    DEPENDS
+    searchlib
+)
+vespa_add_test(NAME searchlib_array_store_config_test_app COMMAND searchlib_array_store_config_test_app)
diff --git a/searchlib/src/tests/datastore/array_store_config/FILES b/searchlib/src/tests/datastore/array_store_config/FILES
new file mode 100644
index 00000000000..71f4e3f5b8c
--- /dev/null
+++ b/searchlib/src/tests/datastore/array_store_config/FILES
@@ -0,0 +1 @@
+array_store_config_test.cpp
diff --git a/searchlib/src/tests/datastore/array_store_config/array_store_config_test.cpp b/searchlib/src/tests/datastore/array_store_config/array_store_config_test.cpp
new file mode 100644
index 00000000000..bc7a446b3b4
--- /dev/null
+++ b/searchlib/src/tests/datastore/array_store_config/array_store_config_test.cpp
@@ -0,0 +1,73 @@
+// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+#include <vespa/fastos/fastos.h>
+#include <vespa/log/log.h>
+LOG_SETUP("array_store_config_test");
+#include <vespa/vespalib/testkit/testapp.h>
+#include <vespa/searchlib/datastore/entryref.h>
+#include <vespa/searchlib/datastore/array_store_config.h>
+
+using namespace search::datastore;
+using AllocSpec = ArrayStoreConfig::AllocSpec;
+
+struct Fixture
+{
+    using EntryRefType = EntryRefT<18>;
+    ArrayStoreConfig cfg;
+
+    Fixture(uint32_t maxSmallArraySize,
+            const AllocSpec &defaultSpec)
+        : cfg(maxSmallArraySize, defaultSpec) {}
+
+    Fixture(uint32_t maxSmallArraySize,
+            size_t hugePageSize,
+            size_t smallPageSize,
+            size_t minNumArraysForNewBuffer)
+        : cfg(ArrayStoreConfig::optimizeForHugePage(maxSmallArraySize, hugePageSize, smallPageSize,
+                                                    sizeof(int), EntryRefType::offsetSize(),
+                                                    minNumArraysForNewBuffer)) { }
+    void assertSpec(size_t arraySize, uint32_t numArraysForNewBuffer) {
+        assertSpec(arraySize, AllocSpec(0, EntryRefType::offsetSize(), numArraysForNewBuffer));
+    }
+    void assertSpec(size_t arraySize, const AllocSpec &expSpec) {
+        const ArrayStoreConfig::AllocSpec &actSpec = cfg.specForSize(arraySize);
+        EXPECT_EQUAL(expSpec.minArraysInBuffer, actSpec.minArraysInBuffer);
+        EXPECT_EQUAL(expSpec.maxArraysInBuffer, actSpec.maxArraysInBuffer);
+        EXPECT_EQUAL(expSpec.numArraysForNewBuffer, actSpec.numArraysForNewBuffer);
+    }
+};
+
+constexpr size_t KB = 1024;
+constexpr size_t MB = KB * KB;
+
+TEST_F("require that default allocation spec is given for all array sizes", Fixture(3, AllocSpec(4, 32, 8)))
+{
+    EXPECT_EQUAL(3, f.cfg.maxSmallArraySize());
+    TEST_DO(f.assertSpec(0, AllocSpec(4, 32, 8)));
+    TEST_DO(f.assertSpec(1, AllocSpec(4, 32, 8)));
+    TEST_DO(f.assertSpec(2, AllocSpec(4, 32, 8)));
+    TEST_DO(f.assertSpec(3, AllocSpec(4, 32, 8)));
+}
+
+TEST_F("require that we can generate config optimized for a given huge page", Fixture(1024,
+                                                                                      2 * MB,
+                                                                                      4 * KB,
+                                                                                      8 * KB))
+{
+    EXPECT_EQUAL(1024, f.cfg.maxSmallArraySize());
+    TEST_DO(f.assertSpec(0, 8 * KB)); // large arrays
+    TEST_DO(f.assertSpec(1, 256 * KB));
+    TEST_DO(f.assertSpec(2, 256 * KB));
+    TEST_DO(f.assertSpec(3, 168 * KB));
+    TEST_DO(f.assertSpec(4, 128 * KB));
+    TEST_DO(f.assertSpec(5, 100 * KB));
+    TEST_DO(f.assertSpec(6, 84 * KB));
+
+    TEST_DO(f.assertSpec(32, 16 * KB));
+    TEST_DO(f.assertSpec(33, 12 * KB));
+    TEST_DO(f.assertSpec(42, 12 * KB));
+    TEST_DO(f.assertSpec(43, 8 * KB));
+    TEST_DO(f.assertSpec(1022, 8 * KB));
+    TEST_DO(f.assertSpec(1023, 8 * KB));
+}
+
+TEST_MAIN() { TEST_RUN_ALL(); }
diff --git a/searchlib/src/vespa/searchlib/datastore/CMakeLists.txt b/searchlib/src/vespa/searchlib/datastore/CMakeLists.txt
index 3b67548d719..a54cbc7c479 100644
--- a/searchlib/src/vespa/searchlib/datastore/CMakeLists.txt
+++ b/searchlib/src/vespa/searchlib/datastore/CMakeLists.txt
@@ -1,6 +1,7 @@
 # Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
 vespa_add_library(searchlib_datastore OBJECT
     SOURCES
+    array_store_config.cpp
     buffer_type.cpp
     bufferstate.cpp
     datastore.cpp
diff --git a/searchlib/src/vespa/searchlib/datastore/array_store_config.cpp b/searchlib/src/vespa/searchlib/datastore/array_store_config.cpp
new file mode 100644
index 00000000000..1710e41069b
--- /dev/null
+++ b/searchlib/src/vespa/searchlib/datastore/array_store_config.cpp
@@ -0,0 +1,66 @@
+// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+
+#include <vespa/fastos/fastos.h>
+#include "array_store_config.h"
+
+namespace search {
+namespace datastore {
+
+ArrayStoreConfig::ArrayStoreConfig(size_t maxSmallArraySize, const AllocSpec &defaultSpec)
+    : _allocSpecs()
+{
+    for (size_t i = 0; i < (maxSmallArraySize + 1); ++i) {
+        _allocSpecs.push_back(defaultSpec);
+    }
+}
+
+ArrayStoreConfig::ArrayStoreConfig(const AllocSpecVector &allocSpecs)
+    : _allocSpecs(allocSpecs)
+{
+}
+
+const ArrayStoreConfig::AllocSpec &
+ArrayStoreConfig::specForSize(size_t arraySize) const
+{
+    assert(arraySize < _allocSpecs.size());
+    return _allocSpecs[arraySize];
+}
+
+namespace {
+
+size_t
+capToLimits(size_t value, size_t minLimit, size_t maxLimit)
+{
+    size_t result = std::max(value, minLimit);
+    return std::min(result, maxLimit);
+}
+
+size_t
+alignToSmallPageSize(size_t value, size_t minLimit, size_t smallPageSize)
+{
+    return ((value - minLimit) / smallPageSize) * smallPageSize + minLimit;
+}
+
+}
+
+ArrayStoreConfig
+ArrayStoreConfig::optimizeForHugePage(size_t maxSmallArraySize,
+                                      size_t hugePageSize,
+                                      size_t smallPageSize,
+                                      size_t entrySize,
+                                      size_t maxEntryRefOffset,
+                                      size_t minNumArraysForNewBuffer)
+{
+    AllocSpecVector allocSpecs;
+    allocSpecs.emplace_back(0, maxEntryRefOffset, minNumArraysForNewBuffer); // large array spec;
+    for (size_t arraySize = 1; arraySize <= maxSmallArraySize; ++arraySize) {
+        size_t numArraysForNewBuffer = hugePageSize / (entrySize * arraySize);
+        numArraysForNewBuffer = capToLimits(numArraysForNewBuffer, minNumArraysForNewBuffer, maxEntryRefOffset);
+        numArraysForNewBuffer = alignToSmallPageSize(numArraysForNewBuffer, minNumArraysForNewBuffer, smallPageSize);
+        allocSpecs.emplace_back(0, maxEntryRefOffset, numArraysForNewBuffer);
+    }
+    return ArrayStoreConfig(allocSpecs);
+}
+
+}
+}
diff --git a/searchlib/src/vespa/searchlib/datastore/array_store_config.h b/searchlib/src/vespa/searchlib/datastore/array_store_config.h
new file mode 100644
index 00000000000..6ada8cdae05
--- /dev/null
+++ b/searchlib/src/vespa/searchlib/datastore/array_store_config.h
@@ -0,0 +1,66 @@
+// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+
+#pragma once
+
+namespace search {
+namespace datastore {
+
+/**
+ * Config specifying layout and buffer allocation strategy for an array store.
+ */
+class ArrayStoreConfig
+{
+public:
+    /**
+     * Specification of buffer allocation strategy for arrays of a given size.
+     */
+    struct AllocSpec {
+        // Minimum number of arrays to allocate in a buffer.
+        size_t minArraysInBuffer;
+        // Maximum number of arrays to allocate in a buffer.
+        size_t maxArraysInBuffer;
+        // Number of arrays needed before allocating a new buffer instead of just resizing the first one.
+        size_t numArraysForNewBuffer;
+        AllocSpec(size_t minArraysInBuffer_,
+                  size_t maxArraysInBuffer_,
+                  size_t numArraysForNewBuffer_)
+            : minArraysInBuffer(minArraysInBuffer_),
+              maxArraysInBuffer(maxArraysInBuffer_),
+              numArraysForNewBuffer(numArraysForNewBuffer_) {}
+    };
+
+    using AllocSpecVector = std::vector<AllocSpec>;
+
+private:
+    AllocSpecVector _allocSpecs;
+
+    /**
+     * Setup an array store with arrays of size [1-(allocSpecs.size()-1)] allocated in buffers and
+     * larger arrays are heap allocated. The allocation spec for a given array size is found in the given vector.
+     * Allocation spec for large arrays is located at position 0.
+     */
+    ArrayStoreConfig(const AllocSpecVector &allocSpecs);
+
+public:
+    /**
+     * Setup an array store with arrays of size [1-maxSmallArraySize] allocated in buffers
+     * with the given default allocation spec. Larger arrays are heap allocated.
+     */
+    ArrayStoreConfig(size_t maxSmallArraySize, const AllocSpec &defaultSpec);
+
+    size_t maxSmallArraySize() const { return _allocSpecs.size() - 1; }
+    const AllocSpec &specForSize(size_t arraySize) const;
+
+    /**
+     * Generate a config that is optimized for the given memory huge page size.
+     */
+    static ArrayStoreConfig optimizeForHugePage(size_t maxSmallArraySize,
+                                                size_t hugePageSize,
+                                                size_t smallPageSize,
+                                                size_t entrySize,
+                                                size_t maxEntryRefOffset,
+                                                size_t minNumArraysForNewBuffer);
+};
+
+}
+}