From 26ad1469b9ff2c3f099128b2b1c3e533c0dde19f Mon Sep 17 00:00:00 2001 From: Håvard Pettersen Date: Wed, 24 Feb 2021 15:21:26 +0000 Subject: small vector --- vespalib/CMakeLists.txt | 1 + vespalib/src/tests/small_vector/CMakeLists.txt | 9 ++ .../src/tests/small_vector/small_vector_test.cpp | 124 +++++++++++++++++ vespalib/src/vespa/vespalib/util/CMakeLists.txt | 1 + vespalib/src/vespa/vespalib/util/small_vector.cpp | 3 + vespalib/src/vespa/vespalib/util/small_vector.h | 155 +++++++++++++++++++++ vespalib/src/vespa/vespalib/util/traits.h | 1 + 7 files changed, 294 insertions(+) create mode 100644 vespalib/src/tests/small_vector/CMakeLists.txt create mode 100644 vespalib/src/tests/small_vector/small_vector_test.cpp create mode 100644 vespalib/src/vespa/vespalib/util/small_vector.cpp create mode 100644 vespalib/src/vespa/vespalib/util/small_vector.h 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..bb9e9faf88d --- /dev/null +++ b/vespalib/src/tests/small_vector/small_vector_test.cpp @@ -0,0 +1,124 @@ +// Copyright Verizon Media. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. + +#include +#include + +using namespace vespalib; + +template +void verify(const SmallVector &vec, std::vector 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 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 vec1; + SmallVector 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 vec1; + vec1.add(3).add(5).add(7).add(11); + SmallVector vec2(vec1); + SmallVector 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,4> vec1; + for (size_t i = 0; i < 128; ++i) { + vec1.emplace_back(std::make_unique(i)); + } + ASSERT_EQ(vec1.size(), 128); + SmallVector,4> vec2(std::move(vec1)); + ASSERT_EQ(vec2.size(), 128); + SmallVector,4> vec3; + for (size_t i = 0; i < 256; ++i) { + vec3.emplace_back(std::make_unique(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 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}); +} + +GTEST_MAIN_RUN_ALL_TESTS() diff --git a/vespalib/src/vespa/vespalib/util/CMakeLists.txt b/vespalib/src/vespa/vespalib/util/CMakeLists.txt index d934a7b38ca..a249659f713 100644 --- a/vespalib/src/vespa/vespalib/util/CMakeLists.txt +++ b/vespalib/src/vespa/vespalib/util/CMakeLists.txt @@ -50,6 +50,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..8fc311c82fc --- /dev/null +++ b/vespalib/src/vespa/vespalib/util/small_vector.h @@ -0,0 +1,155 @@ +// Copyright Verizon Media. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. + +#include "alloc.h" +#include "traits.h" +#include +#include +#include +#include + +namespace vespalib { + +namespace small_vector { + +template +void create_at(T *ptr, Args &&...args) { + // https://en.cppreference.com/w/cpp/memory/construct_at + ::new (const_cast(static_cast(ptr))) T(std::forward(args)...); +} + +template +void move_objects(T *dst, T *src, uint32_t n) { + if constexpr (std::is_trivially_copyable_v) { + memcpy(dst, src, n * sizeof(T)); + } else { + for (size_t i = 0; i < n; ++i) { + create_at(dst + i, std::move(src[i])); + } + } +} + +template +void copy_objects(T *dst, const T *src, uint32_t n) { + if constexpr (std::is_trivially_copyable_v) { + memcpy(dst, src, n * sizeof(T)); + } else { + for (size_t i = 0; i < n; ++i) { + create_at(dst + i, src[i]); + } + } +} + +template +void destroy_objects(T *src, uint32_t n) { + if (!can_skip_destruction_v) { + std::destroy_n(src, n); + } +} + +template +std::pair 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(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 +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(_space); } + constexpr const T *local() const noexcept { return reinterpret_cast(_space); } + void expand(size_t wanted) { + auto [new_data, new_capacity] = small_vector::alloc_objects(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(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 + void emplace_back(Args &&...args) { + reserve(_size + 1); + small_vector::create_at((_data + _size), std::forward(args)...); + ++_size; + } + template + SmallVector &add(Args &&...args) { + emplace_back(std::forward(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 {}; template <> \ struct can_skip_destruction : std::true_type {}; \ } +template constexpr bool can_skip_destruction_v = can_skip_destruction::value; //----------------------------------------------------------------------------- -- cgit v1.2.3 From a2d2dc147c1be738a2a5dfe52857775bcba5e642 Mon Sep 17 00:00:00 2001 From: Håvard Pettersen Date: Fri, 26 Feb 2021 11:11:54 +0000 Subject: update after comments --- .../src/tests/small_vector/small_vector_test.cpp | 44 +++++++++++++++++++++- vespalib/src/vespa/vespalib/util/small_vector.h | 19 ++++++++++ 2 files changed, 61 insertions(+), 2 deletions(-) diff --git a/vespalib/src/tests/small_vector/small_vector_test.cpp b/vespalib/src/tests/small_vector/small_vector_test.cpp index bb9e9faf88d..58779237fd4 100644 --- a/vespalib/src/tests/small_vector/small_vector_test.cpp +++ b/vespalib/src/tests/small_vector/small_vector_test.cpp @@ -5,8 +5,8 @@ using namespace vespalib; -template -void verify(const SmallVector &vec, std::vector expect, size_t expect_capacity = 0) { +template +void verify(const SmallVector &vec, std::vector expect, size_t expect_capacity = 0) { if (expect_capacity == 0) { expect_capacity = (expect.size() <= N) ? N : roundUp2inN(expect.size()); } @@ -121,4 +121,44 @@ TEST(SmallVectorTest, inplace_edit) { 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 vec1(2); + SmallVector vec2(6); + SmallVector vec3(2); + SmallVector 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 vec1(2, 5); + SmallVector vec2(6, 5); + SmallVector vec3(2, MyUInt32{5}); + SmallVector 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,2> vec1(1); + SmallVector,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/small_vector.h b/vespalib/src/vespa/vespalib/util/small_vector.h index 8fc311c82fc..a0e2c621124 100644 --- a/vespalib/src/vespa/vespalib/util/small_vector.h +++ b/vespalib/src/vespa/vespalib/util/small_vector.h @@ -1,5 +1,7 @@ // 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 @@ -39,6 +41,13 @@ void copy_objects(T *dst, const T *src, uint32_t n) { } } +template +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)...); + } +} + template void destroy_objects(T *src, uint32_t n) { if (!can_skip_destruction_v) { @@ -88,6 +97,16 @@ 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); -- cgit v1.2.3