diff options
Diffstat (limited to 'vespalib')
-rw-r--r-- | vespalib/CMakeLists.txt | 1 | ||||
-rw-r--r-- | vespalib/src/tests/alloc/alloc_test.cpp | 15 | ||||
-rw-r--r-- | vespalib/src/tests/small_vector/CMakeLists.txt | 9 | ||||
-rw-r--r-- | vespalib/src/tests/small_vector/small_vector_test.cpp | 164 | ||||
-rw-r--r-- | vespalib/src/tests/stllike/hash_test.cpp | 16 | ||||
-rw-r--r-- | vespalib/src/vespa/vespalib/stllike/hash_map.hpp | 2 | ||||
-rw-r--r-- | vespalib/src/vespa/vespalib/stllike/hashtable.hpp | 3 | ||||
-rw-r--r-- | vespalib/src/vespa/vespalib/util/CMakeLists.txt | 2 | ||||
-rw-r--r-- | vespalib/src/vespa/vespalib/util/alloc.h | 6 | ||||
-rw-r--r-- | vespalib/src/vespa/vespalib/util/memoryusage.cpp | 24 | ||||
-rw-r--r-- | vespalib/src/vespa/vespalib/util/memoryusage.h | 13 | ||||
-rw-r--r-- | vespalib/src/vespa/vespalib/util/small_vector.cpp | 3 | ||||
-rw-r--r-- | vespalib/src/vespa/vespalib/util/small_vector.h | 174 | ||||
-rw-r--r-- | vespalib/src/vespa/vespalib/util/traits.h | 1 |
14 files changed, 426 insertions, 7 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/alloc/alloc_test.cpp b/vespalib/src/tests/alloc/alloc_test.cpp index c52170fc8ec..d37abb15c2f 100644 --- a/vespalib/src/tests/alloc/alloc_test.cpp +++ b/vespalib/src/tests/alloc/alloc_test.cpp @@ -47,6 +47,21 @@ TEST("test roundUp2inN") { EXPECT_EQUAL(16u, roundUp2inN(9)); } +TEST("test roundUp2inN elems") { + EXPECT_EQUAL(0u, roundUp2inN(0, 17)); + EXPECT_EQUAL(1u, roundUp2inN(1, 17)); + EXPECT_EQUAL(3u, roundUp2inN(2, 17)); + EXPECT_EQUAL(3u, roundUp2inN(3, 17)); + EXPECT_EQUAL(7u, roundUp2inN(4, 17)); + EXPECT_EQUAL(7u, roundUp2inN(5, 17)); + EXPECT_EQUAL(7u, roundUp2inN(6, 17)); + EXPECT_EQUAL(7u, roundUp2inN(7, 17)); + EXPECT_EQUAL(15u, roundUp2inN(8, 17)); + EXPECT_EQUAL(15u, roundUp2inN(9, 17)); + EXPECT_EQUAL(15u, roundUp2inN(15, 17)); + EXPECT_EQUAL(30u, roundUp2inN(16, 17)); +} + TEST("test basics") { { Alloc h = Alloc::allocHeap(100); 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/tests/stllike/hash_test.cpp b/vespalib/src/tests/stllike/hash_test.cpp index 561c7b34035..59081c0ab73 100644 --- a/vespalib/src/tests/stllike/hash_test.cpp +++ b/vespalib/src/tests/stllike/hash_test.cpp @@ -555,7 +555,7 @@ TEST("test that begin and end are identical with empty hashtables") { EXPECT_TRUE(empty_but_reserved.begin() == empty_but_reserved.end()); } -TEST ("test that large_allocator works fine with std::vector") { +TEST("test that large_allocator works fine with std::vector") { using V = std::vector<uint64_t, allocator_large<uint64_t>>; V a; a.push_back(1); @@ -568,4 +568,18 @@ TEST ("test that large_allocator works fine with std::vector") { ASSERT_EQUAL(b.size(), c.size()); } +TEST("test that hash table clear does not resize hashtable") { + hash_set<int> a(100); + EXPECT_EQUAL(0u, a.size()); + EXPECT_EQUAL(128u, a.capacity()); + for (size_t i(0); i < 100; i++) { + a.insert(i); + } + EXPECT_EQUAL(100u, a.size()); + EXPECT_EQUAL(128u, a.capacity()); + a.clear(); + EXPECT_EQUAL(0u, a.size()); + EXPECT_EQUAL(128u, a.capacity()); +} + TEST_MAIN() { TEST_RUN_ALL(); } diff --git a/vespalib/src/vespa/vespalib/stllike/hash_map.hpp b/vespalib/src/vespa/vespalib/stllike/hash_map.hpp index 900d6ff238d..567893534b0 100644 --- a/vespalib/src/vespa/vespalib/stllike/hash_map.hpp +++ b/vespalib/src/vespa/vespalib/stllike/hash_map.hpp @@ -14,7 +14,7 @@ hash_map<K, V, H, EQ, M>::hash_map() : template <typename K, typename V, typename H, typename EQ, typename M> hash_map<K, V, H, EQ, M>::hash_map(size_t reserveSize) : - _ht(reserveSize) + _ht(reserveSize) { } template <typename K, typename V, typename H, typename EQ, typename M> diff --git a/vespalib/src/vespa/vespalib/stllike/hashtable.hpp b/vespalib/src/vespa/vespalib/stllike/hashtable.hpp index 15510d608da..d80113a8f55 100644 --- a/vespalib/src/vespa/vespalib/stllike/hashtable.hpp +++ b/vespalib/src/vespa/vespalib/stllike/hashtable.hpp @@ -147,7 +147,8 @@ template< typename Key, typename Value, typename Hash, typename Equal, typename void hashtable<Key, Value, Hash, Equal, KeyExtract, Modulator>::clear() { _nodes.clear(); - resize(getTableSize()); + _count = 0; + _nodes.resize(getTableSize()); } template< typename Key, typename Value, typename Hash, typename Equal, typename KeyExtract, typename Modulator > diff --git a/vespalib/src/vespa/vespalib/util/CMakeLists.txt b/vespalib/src/vespa/vespalib/util/CMakeLists.txt index d934a7b38ca..64c27482e00 100644 --- a/vespalib/src/vespa/vespalib/util/CMakeLists.txt +++ b/vespalib/src/vespa/vespalib/util/CMakeLists.txt @@ -31,6 +31,7 @@ vespa_add_library(vespalib_vespalib_util OBJECT left_right_heap.cpp lz4compressor.cpp md5.c + memoryusage.cpp mmap_file_allocator.cpp mmap_file_allocator_factory.cpp printable.cpp @@ -50,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/alloc.h b/vespalib/src/vespa/vespalib/util/alloc.h index 71a3bd2407a..a1bb6af6514 100644 --- a/vespalib/src/vespa/vespalib/util/alloc.h +++ b/vespalib/src/vespa/vespalib/util/alloc.h @@ -80,8 +80,14 @@ private: namespace vespalib { +/// Rounds up to the closest number that is a power of 2 inline size_t roundUp2inN(size_t minimum) { return 2ul << Optimized::msbIdx(minimum - 1); } +/// Rounds minElems up to the closest number where minElems*elemSize is a power of 2 +inline size_t roundUp2inN(size_t minElems, size_t elemSize) { + return roundUp2inN(minElems * elemSize)/elemSize; +} + } diff --git a/vespalib/src/vespa/vespalib/util/memoryusage.cpp b/vespalib/src/vespa/vespalib/util/memoryusage.cpp new file mode 100644 index 00000000000..6d6f93c3be0 --- /dev/null +++ b/vespalib/src/vespa/vespalib/util/memoryusage.cpp @@ -0,0 +1,24 @@ +// Copyright Verizon Media. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. + +#include "memoryusage.h" +#include <vespa/vespalib/stllike/asciistream.h> + +namespace vespalib { + +string +MemoryUsage::toString() const { + vespalib::asciistream os; + os << *this; + return os.str(); +} + +asciistream & +operator << (asciistream & os, const MemoryUsage & usage) { + os << "allocated: " << usage.allocatedBytes(); + os << ", used: " << usage.usedBytes(); + os << ", dead: " << usage.deadBytes(); + os << ", onhold: " << usage.allocatedBytesOnHold(); + return os; +} + +} // namespace vespalib diff --git a/vespalib/src/vespa/vespalib/util/memoryusage.h b/vespalib/src/vespa/vespalib/util/memoryusage.h index 0ab339d1262..cc245ee69e9 100644 --- a/vespalib/src/vespa/vespalib/util/memoryusage.h +++ b/vespalib/src/vespa/vespalib/util/memoryusage.h @@ -1,8 +1,8 @@ -// Copyright 2017 Yahoo Holdings. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +// Copyright Verizon Media. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. #pragma once -#include <cstddef> +#include <vespa/vespalib/stllike/string.h> namespace vespalib { @@ -14,14 +14,14 @@ private: size_t _allocatedBytesOnHold; public: - MemoryUsage() + MemoryUsage() noexcept : _allocatedBytes(0), _usedBytes(0), _deadBytes(0), _allocatedBytesOnHold(0) { } - MemoryUsage(size_t allocated, size_t used, size_t dead, size_t onHold) + MemoryUsage(size_t allocated, size_t used, size_t dead, size_t onHold) noexcept : _allocatedBytes(allocated), _usedBytes(used), _deadBytes(dead), @@ -56,6 +56,11 @@ public: _deadBytes += rhs._deadBytes; _allocatedBytesOnHold += rhs._allocatedBytesOnHold; } + string toString() const; }; +class asciistream; + +asciistream & operator << (asciistream & os, const MemoryUsage & usage); + } // namespace vespalib 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; //----------------------------------------------------------------------------- |