Merge pull request #16678 from vespa-engine/havardpe/small-vector

small vector

7 files changed, 353 insertions, 0 deletions

diff --git a/vespalib/CMakeLists.txt b/vespalib/CMakeLists.txt
index 6d71b2d05be..2db3c89dfb5 100644
--- a/vespalib/CMakeLists.txt
+++ b/vespalib/CMakeLists.txt
@@ -100,6 +100,7 @@ vespa_define_module(
     src/tests/slime
     src/tests/slime/external_data_value
     src/tests/slime/summary-feature-benchmark
+    src/tests/small_vector
     src/tests/spin_lock
     src/tests/stash
     src/tests/stllike
diff --git a/vespalib/src/tests/small_vector/CMakeLists.txt b/vespalib/src/tests/small_vector/CMakeLists.txt
new file mode 100644
index 00000000000..22bd739ccc8
--- /dev/null
+++ b/vespalib/src/tests/small_vector/CMakeLists.txt
@@ -0,0 +1,9 @@
+# Copyright Verizon Media. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+vespa_add_executable(vespalib_small_vector_test_app TEST
+    SOURCES
+    small_vector_test.cpp
+    DEPENDS
+    vespalib
+    GTest::GTest
+)
+vespa_add_test(NAME vespalib_small_vector_test_app COMMAND vespalib_small_vector_test_app)
diff --git a/vespalib/src/tests/small_vector/small_vector_test.cpp b/vespalib/src/tests/small_vector/small_vector_test.cpp
new file mode 100644
index 00000000000..58779237fd4
--- /dev/null
+++ b/vespalib/src/tests/small_vector/small_vector_test.cpp
@@ -0,0 +1,164 @@
+// Copyright Verizon Media. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+
+#include <vespa/vespalib/util/small_vector.h>
+#include <vespa/vespalib/gtest/gtest.h>
+
+using namespace vespalib;
+
+template <typename T, size_t N>
+void verify(const SmallVector<T,N> &vec, std::vector<uint32_t> expect, size_t expect_capacity = 0) {
+    if (expect_capacity == 0) {
+        expect_capacity = (expect.size() <= N) ? N : roundUp2inN(expect.size());
+    }
+    ASSERT_EQ(vec.size(), expect.size());
+    EXPECT_EQ((vec.size() == 0), vec.empty());
+    EXPECT_EQ(vec.capacity(), expect_capacity);
+    EXPECT_EQ((vec.capacity() <= N), vec.is_local());
+    auto pos = vec.begin();
+    auto end = vec.end();
+    for (size_t i = 0; i < vec.size(); ++i) {
+        EXPECT_EQ(vec[i], expect[i]);
+        ASSERT_TRUE(pos != end);
+        EXPECT_EQ(*pos, expect[i]);
+        ++pos;
+    }
+    EXPECT_EQ(pos, end);
+}
+
+TEST(SmallVectorTest, basic_usage) {
+    SmallVector<uint32_t,4> vec;
+    EXPECT_EQ(sizeof(vec), 32);
+    EXPECT_EQ(vec.capacity(), 4);
+    verify(vec, {});
+    vec.emplace_back(3);
+    verify(vec, {3});
+    vec.emplace_back(5);
+    verify(vec, {3,5});
+    vec.emplace_back(7);
+    verify(vec, {3,5,7});
+    vec.emplace_back(11);
+    verify(vec, {3,5,7,11});
+    vec.emplace_back(13);
+    verify(vec, {3,5,7,11,13});
+    vec.emplace_back(17);
+    verify(vec, {3,5,7,11,13,17});
+    vec.clear();
+    verify(vec, {}, 8);
+}
+
+// not 2^n size struct
+struct MyStruct {
+    uint32_t a;
+    uint32_t b;
+    uint32_t c;
+};
+
+TEST(SmallVectorTest, reserve) {
+    SmallVector<uint32_t,4> vec1;
+    SmallVector<MyStruct,4> vec2;
+    EXPECT_EQ(vec1.capacity(), 4);
+    EXPECT_EQ(vec2.capacity(), 4);
+    vec1.reserve(3);
+    vec2.reserve(3);
+    EXPECT_EQ(vec1.capacity(), 4);
+    EXPECT_EQ(vec2.capacity(), 4);
+    vec1.reserve(6);
+    vec2.reserve(6);
+    EXPECT_EQ(vec1.capacity(), 8);
+    EXPECT_EQ(vec2.capacity(), 10);
+}
+
+TEST(SmallVectorTest, copy_and_assign) {
+    SmallVector<uint32_t,4> vec1;
+    vec1.add(3).add(5).add(7).add(11);
+    SmallVector<uint32_t,4> vec2(vec1);
+    SmallVector<uint32_t,4> vec3;
+    for (size_t i = 0; i < 64; ++i) {
+        vec3.add(123);
+    }
+    vec3 = vec2;
+    verify(vec1, {3,5,7,11});
+    verify(vec2, {3,5,7,11});
+    verify(vec3, {3,5,7,11}, 64);
+}
+
+TEST(SmallVectorTest, unique_pointers_resize_and_move) {
+    SmallVector<std::unique_ptr<uint32_t>,4> vec1;
+    for (size_t i = 0; i < 128; ++i) {
+        vec1.emplace_back(std::make_unique<uint32_t>(i));
+    }
+    ASSERT_EQ(vec1.size(), 128);
+    SmallVector<std::unique_ptr<uint32_t>,4> vec2(std::move(vec1));
+    ASSERT_EQ(vec2.size(), 128);
+    SmallVector<std::unique_ptr<uint32_t>,4> vec3;
+    for (size_t i = 0; i < 256; ++i) {
+        vec3.emplace_back(std::make_unique<uint32_t>(i));
+    }
+    ASSERT_EQ(vec3.size(), 256);
+    vec3 = std::move(vec2);
+    ASSERT_EQ(vec3.size(), 128);
+    auto pos = vec3.begin();
+    auto end = vec3.end();
+    for (size_t i = 0; i < 128; ++i) {
+        EXPECT_EQ(*vec3[i], i);
+        ASSERT_TRUE(pos != end);
+        EXPECT_EQ(**pos, i);
+        ++pos;
+    }
+    EXPECT_EQ(pos, end);
+}
+
+TEST(SmallVectorTest, inplace_edit) {
+    SmallVector<uint32_t,4> vec;
+    vec.add(3).add(5).add(7).add(11);
+    verify(vec, {3,5,7,11});
+    for (auto &x: vec) {
+        x += 1;
+    }
+    verify(vec, {4,6,8,12});
+    vec[1] = 10;
+    vec[3] = 20;
+    verify(vec, {4,10,8,20});
+}
+
+struct MyUInt32 {
+    uint32_t value = 42;
+    operator uint32_t() const { return value; }
+};
+
+TEST(SmallVectorTest, create_with_default_elements) {
+    SmallVector<uint32_t,4> vec1(2);
+    SmallVector<uint32_t,4> vec2(6);
+    SmallVector<MyUInt32,4> vec3(2);
+    SmallVector<MyUInt32,4> vec4(6);
+    verify(vec1, {0, 0});
+    verify(vec2, {0, 0, 0, 0, 0, 0});
+    verify(vec3, {42, 42});
+    verify(vec4, {42, 42, 42, 42, 42, 42});
+}
+
+TEST(SmallVectorTest, create_with_copied_elements) {
+    SmallVector<uint32_t,4> vec1(2, 5);
+    SmallVector<uint32_t,4> vec2(6, 5);
+    SmallVector<MyUInt32,4> vec3(2, MyUInt32{5});
+    SmallVector<MyUInt32,4> vec4(6, MyUInt32{5});
+    verify(vec1, {5, 5});
+    verify(vec2, {5, 5, 5, 5, 5, 5});
+    verify(vec3, {5, 5});
+    verify(vec4, {5, 5, 5, 5, 5, 5});
+}
+
+TEST(SmallVectorTest, create_with_unique_pointers) {
+    SmallVector<std::unique_ptr<uint32_t>,2> vec1(1);
+    SmallVector<std::unique_ptr<uint32_t>,2> vec2(3);
+    EXPECT_EQ(vec1.capacity(), 2);
+    EXPECT_EQ(vec2.capacity(), 4);
+    ASSERT_EQ(vec1.size(), 1);
+    ASSERT_EQ(vec2.size(), 3);
+    EXPECT_TRUE(vec1[0].get() == nullptr);
+    EXPECT_TRUE(vec2[0].get() == nullptr);
+    EXPECT_TRUE(vec2[1].get() == nullptr);
+    EXPECT_TRUE(vec2[2].get() == nullptr);
+}
+
+GTEST_MAIN_RUN_ALL_TESTS()
diff --git a/vespalib/src/vespa/vespalib/util/CMakeLists.txt b/vespalib/src/vespa/vespalib/util/CMakeLists.txt
index 9d250d31563..64c27482e00 100644
--- a/vespalib/src/vespa/vespalib/util/CMakeLists.txt
+++ b/vespalib/src/vespa/vespalib/util/CMakeLists.txt
@@ -51,6 +51,7 @@ vespa_add_library(vespalib_vespalib_util OBJECT
     sig_catch.cpp
     signalhandler.cpp
     simple_thread_bundle.cpp
+    small_vector.cpp
     stash.cpp
     string_hash.cpp
     stringfmt.cpp
diff --git a/vespalib/src/vespa/vespalib/util/small_vector.cpp b/vespalib/src/vespa/vespalib/util/small_vector.cpp
new file mode 100644
index 00000000000..cc2cabdb275
--- /dev/null
+++ b/vespalib/src/vespa/vespalib/util/small_vector.cpp
@@ -0,0 +1,3 @@
+// Copyright Verizon Media. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+
+#include "small_vector.h"
diff --git a/vespalib/src/vespa/vespalib/util/small_vector.h b/vespalib/src/vespa/vespalib/util/small_vector.h
new file mode 100644
index 00000000000..a0e2c621124
--- /dev/null
+++ b/vespalib/src/vespa/vespalib/util/small_vector.h
@@ -0,0 +1,174 @@
+// Copyright Verizon Media. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+
+#pragma once
+
+#include "alloc.h"
+#include "traits.h"
+#include <string.h>
+#include <cstdint>
+#include <cassert>
+#include <memory>
+
+namespace vespalib {
+
+namespace small_vector {
+
+template<typename T, typename... Args>
+void create_at(T *ptr, Args &&...args) {
+    // https://en.cppreference.com/w/cpp/memory/construct_at
+    ::new (const_cast<void*>(static_cast<const volatile void*>(ptr))) T(std::forward<Args>(args)...);
+}
+
+template <typename T>
+void move_objects(T *dst, T *src, uint32_t n) {
+    if constexpr (std::is_trivially_copyable_v<T>) {
+        memcpy(dst, src, n * sizeof(T));
+    } else {
+        for (size_t i = 0; i < n; ++i) {
+            create_at(dst + i, std::move(src[i]));
+        }
+    }
+}
+
+template <typename T>
+void copy_objects(T *dst, const T *src, uint32_t n) {
+    if constexpr (std::is_trivially_copyable_v<T>) {
+        memcpy(dst, src, n * sizeof(T));
+    } else {
+        for (size_t i = 0; i < n; ++i) {
+            create_at(dst + i, src[i]);
+        }
+    }
+}
+
+template <typename T, typename... Args>
+void create_objects(T *dst, uint32_t n, Args &&...args) {
+    for (size_t i = 0; i < n; ++i) {
+        create_at(dst + i, std::forward<Args>(args)...);
+    }
+}
+
+template <typename T>
+void destroy_objects(T *src, uint32_t n) {
+    if (!can_skip_destruction_v<T>) {
+        std::destroy_n(src, n);
+    }
+}
+
+template <typename T>
+std::pair<T*,size_t> alloc_objects(size_t wanted) {
+    size_t mem = roundUp2inN(wanted * sizeof(T));
+    size_t entries = (mem / sizeof(T));
+    mem = (entries * sizeof(T));
+    T *ptr = static_cast<T*>(malloc(mem));
+    assert(ptr != nullptr);
+    return {ptr, entries};
+}
+
+} // namespace small_vector
+
+/**
+ * Simplified vector-like container that has space for some elements
+ * inside the object itself. Intended use is to contain lists of
+ * simple objects/values that are small in both size and number.
+ **/
+template <typename T, size_t N>
+class SmallVector
+{
+private:
+    T *_data;
+    uint32_t _size;
+    uint32_t _capacity;
+    alignas(T) char _space[sizeof(T) * N];
+    constexpr T *local() noexcept { return reinterpret_cast<T*>(_space); }
+    constexpr const T *local() const noexcept { return reinterpret_cast<const T*>(_space); }
+    void expand(size_t wanted) {
+        auto [new_data, new_capacity] = small_vector::alloc_objects<T>(wanted);
+        small_vector::move_objects(new_data, _data, _size);
+        small_vector::destroy_objects(_data, _size);
+        auto old_data = _data;
+        _data = new_data;
+        _capacity = new_capacity;
+        if (old_data != local()) {
+            free(old_data);
+        }
+    }
+public:
+    constexpr SmallVector() noexcept : _data(local()), _size(0), _capacity(N) {
+        static_assert(N > 0);
+    }
+    SmallVector(size_t n) : SmallVector() {
+        reserve(n);
+        small_vector::create_objects(_data, n);
+        _size = n;
+    }
+    SmallVector(size_t n, const T &obj) : SmallVector() {
+        reserve(n);
+        small_vector::create_objects(_data, n, obj);
+        _size = n;
+    }
+    SmallVector(SmallVector &&rhs) : SmallVector() {
+        reserve(rhs._size);
+        small_vector::move_objects(_data, rhs._data, rhs._size);
+        _size = rhs._size;
+    }
+    SmallVector(const SmallVector &rhs) : SmallVector() {
+        reserve(rhs._size);
+        small_vector::copy_objects(_data, rhs._data, rhs._size);
+        _size = rhs._size;
+    }
+    SmallVector &operator=(SmallVector &&rhs) {
+        assert(std::addressof(rhs) != this);
+        clear();
+        reserve(rhs._size);
+        small_vector::move_objects(_data, rhs._data, rhs._size);
+        _size = rhs._size;
+        return *this;
+    }
+    SmallVector &operator=(const SmallVector &rhs) {
+        assert(std::addressof(rhs) != this);
+        clear();
+        reserve(rhs._size);
+        small_vector::copy_objects(_data, rhs._data, rhs._size);
+        _size = rhs._size;
+        return *this;
+    }
+    ~SmallVector() {
+        small_vector::destroy_objects(_data, _size);
+        if (_data != local()) {
+            free(_data);
+        }
+    }
+    bool empty() const { return (_size == 0); }
+    uint32_t size() const { return _size; }
+    uint32_t capacity() const { return _capacity; }
+    bool is_local() const { return (_data == local()); }
+    T *begin() { return _data; }
+    T *end() { return (_data + _size); }
+    const T *begin() const { return _data; }
+    const T *end() const { return (_data + _size); }
+    T &operator[](size_t idx) { return _data[idx]; }
+    const T &operator[](size_t idx) const { return _data[idx]; }
+    void clear() {
+        small_vector::destroy_objects(_data, _size);
+        _size = 0;
+    }
+    void reserve(size_t wanted) {
+        if (__builtin_expect(wanted > _capacity, false)) {
+            expand(wanted);
+        }
+    }
+    template <typename... Args>
+    void emplace_back(Args &&...args) {
+        reserve(_size + 1);
+        small_vector::create_at((_data + _size), std::forward<Args>(args)...);
+        ++_size;
+    }
+    template <typename... Args>
+    SmallVector &add(Args &&...args) {
+        emplace_back(std::forward<Args>(args)...);
+        return *this;
+    }
+};
+
+} // namespace
diff --git a/vespalib/src/vespa/vespalib/util/traits.h b/vespalib/src/vespa/vespalib/util/traits.h
index 7f8945954a8..2f04a679e72 100644
--- a/vespalib/src/vespa/vespalib/util/traits.h
+++ b/vespalib/src/vespa/vespalib/util/traits.h
@@ -36,6 +36,7 @@ struct can_skip_destruction : std::is_trivially_destructible<T> {};
     template <>                                         \
     struct can_skip_destruction<T> : std::true_type {}; \
     }
+template <typename T> constexpr bool can_skip_destruction_v = can_skip_destruction<T>::value;
 
 //-----------------------------------------------------------------------------