X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=folly%2Ftest%2Fsmall_vector_test.cpp;h=cf1642149bab854cd42c25f89fb1386fa050b5ce;hb=cd1bdc912603c0358ba733d379a74ae90ab3a437;hp=18cb57bf4783fe21a2157f216aa0a30e111c5d82;hpb=27494a20393fa45072e7d526d358835f3abe312a;p=folly.git diff --git a/folly/test/small_vector_test.cpp b/folly/test/small_vector_test.cpp index 18cb57bf..cf164214 100644 --- a/folly/test/small_vector_test.cpp +++ b/folly/test/small_vector_test.cpp @@ -1,5 +1,5 @@ /* - * Copyright 2012 Facebook, Inc. + * Copyright 2011-present Facebook, Inc. * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. @@ -14,22 +14,27 @@ * limitations under the License. */ -#include "folly/small_vector.h" +#include +#include -#include -#include -#include #include +#include #include +#include +#include +#include +#include #include -#include "folly/Conv.h" +#include +#include +#include using folly::small_vector; using namespace folly::small_vector_policy; -#if defined(__x86_64__) +#if FOLLY_X64 || FOLLY_PPC64 static_assert(sizeof(small_vector) == 16, "Object size is not what we expect for small_vector"); @@ -50,21 +55,53 @@ static_assert(sizeof(small_vector) == 8 + 1, "small_vector is wrong size"); -static_assert(sizeof(small_vector) == 16, - "OneBitMutex took more space than expected"); - static_assert(sizeof(small_vector) == 10, "Sizeof unexpectedly large"); -static_assert(sizeof(small_vector) == 10, - "Sizeof unexpectedly large"); -static_assert(sizeof(small_vector) == 10, - "Sizeof unexpectedly large"); #endif +static_assert(!FOLLY_IS_TRIVIALLY_COPYABLE(std::unique_ptr), + "std::unique_ptr<> is trivially copyable"); + namespace { +template +using small_sorted_vector_map = folly::sorted_vector_map< + Key, + Value, + std::less, + std::allocator>, + void, + folly::small_vector, N>>; + +template +using noheap_sorted_vector_map = folly::sorted_vector_map< + Key, + Value, + std::less, + std::allocator>, + void, + folly::small_vector< + std::pair, + N, + folly::small_vector_policy::NoHeap>>; + +template +using small_sorted_vector_set = folly::sorted_vector_set< + T, + std::less, + std::allocator, + void, + folly::small_vector>; + +template +using noheap_sorted_vector_set = folly::sorted_vector_set< + T, + std::less, + std::allocator, + void, + folly::small_vector>; + struct NontrivialType { static int ctored; explicit NontrivialType() : a(0) {} @@ -73,9 +110,7 @@ struct NontrivialType { ++ctored; } - NontrivialType(NontrivialType const& s) { - ++ctored; - } + NontrivialType(NontrivialType const& /* s */) { ++ctored; } NontrivialType& operator=(NontrivialType const& o) { a = o.a; @@ -84,8 +119,8 @@ struct NontrivialType { int32_t a; }; -static_assert(!boost::has_trivial_copy::value, - "NontrivialType isn't trivially copyable"); +static_assert(!FOLLY_IS_TRIVIALLY_COPYABLE(NontrivialType), + "NontrivialType is trivially copyable"); int NontrivialType::ctored = 0; @@ -118,7 +153,7 @@ struct Thrower { --alive; } - Thrower& operator=(Thrower const& other) { + Thrower& operator=(Thrower const& /* other */) { EXPECT_EQ(magic, kMagic); MaybeThrow(); return *this; @@ -141,13 +176,16 @@ struct NoncopyableCounter { ~NoncopyableCounter() { --alive; } - NoncopyableCounter(NoncopyableCounter&&) { ++alive; } + NoncopyableCounter(NoncopyableCounter&&) noexcept { ++alive; } NoncopyableCounter(NoncopyableCounter const&) = delete; NoncopyableCounter& operator=(NoncopyableCounter const&) const = delete; NoncopyableCounter& operator=(NoncopyableCounter&&) { return *this; } }; int NoncopyableCounter::alive = 0; +static_assert(!FOLLY_IS_TRIVIALLY_COPYABLE(NoncopyableCounter), + "NoncopyableCounter is trivially copyable"); + // Check that throws don't break the basic guarantee for some cases. // Uses the method for testing exception safety described at // http://www.boost.org/community/exception_safety.html, to force all @@ -161,7 +199,7 @@ struct TestBasicGuarantee { { throwCounter = 1000; for (int i = 0; i < prepopulate; ++i) { - vec.push_back(Thrower()); + vec.emplace_back(); } } @@ -169,14 +207,14 @@ struct TestBasicGuarantee { throwCounter = 1000; } - template + template void operator()(int insertCount, Operation const& op) { bool done = false; std::unique_ptr > workingVec; for (int counter = 1; !done; ++counter) { throwCounter = 1000; - workingVec.reset(new folly::small_vector(vec)); + workingVec = std::make_unique>(vec); throwCounter = counter; EXPECT_EQ(Thrower::alive, prepopulate * 2); try { @@ -198,14 +236,14 @@ struct TestBasicGuarantee { } }; -} +} // namespace TEST(small_vector, BasicGuarantee) { for (int prepop = 1; prepop < 30; ++prepop) { (TestBasicGuarantee(prepop))( // parens or a mildly vexing parse :( 1, [&] (folly::small_vector& v) { - v.push_back(Thrower()); + v.emplace_back(); } ); @@ -234,9 +272,9 @@ TEST(small_vector, BasicGuarantee) { 3, [&] (folly::small_vector& v) { std::vector b; - b.push_back(Thrower()); - b.push_back(Thrower()); - b.push_back(Thrower()); + b.emplace_back(); + b.emplace_back(); + b.emplace_back(); /* * Apparently if you do the following initializer_list instead @@ -253,7 +291,7 @@ TEST(small_vector, BasicGuarantee) { [&] (folly::small_vector& v) { std::vector b; for (int i = 0; i < 6; ++i) { - b.push_back(Thrower()); + b.emplace_back(); } v.insert(v.begin() + 1, b.begin(), b.end()); @@ -271,7 +309,7 @@ TEST(small_vector, BasicGuarantee) { // Run this with. // MALLOC_CONF=prof_leak:true -// LD_PRELOAD=${JEMALLOC_PATH}/lib/libjemalloc.so.1 +// LD_PRELOAD=${JEMALLOC_PATH}/lib/libjemalloc.so.2 // LD_PRELOAD="$LD_PRELOAD:"${UNWIND_PATH}/lib/libunwind.so.7 TEST(small_vector, leak_test) { for (int j = 0; j < 1000; ++j) { @@ -286,7 +324,7 @@ TEST(small_vector, Insert) { folly::small_vector someVec(3, 3); someVec.insert(someVec.begin(), 12, 12); EXPECT_EQ(someVec.size(), 15); - for (int i = 0; i < someVec.size(); ++i) { + for (size_t i = 0; i < someVec.size(); ++i) { if (i < 12) { EXPECT_EQ(someVec[i], 12); } else { @@ -426,7 +464,7 @@ TEST(small_vector, GrowShrinkGrow) { auto capacity = vec.capacity(); auto oldSize = vec.size(); - for (int i = 0; i < oldSize; ++i) { + for (size_t i = 0; i < oldSize; ++i) { vec.erase(vec.begin() + (std::rand() % vec.size())); EXPECT_EQ(vec.capacity(), capacity); } @@ -472,9 +510,10 @@ TEST(small_vector, Iteration) { } TEST(small_vector, NonCopyableType) { - folly::small_vector,2> vec; + folly::small_vector vec; + for (int i = 0; i < 10; ++i) { - vec.emplace(vec.begin(), new std::string("asd")); + vec.emplace(vec.begin(), 13); } EXPECT_EQ(vec.size(), 10); auto vec2 = std::move(vec); @@ -522,7 +561,7 @@ TEST(small_vector, NoHeap) { std::size_t,folly::small_vector_policy::NoHeap> Vector; Vector v; - EXPECT_EQ(v.max_size(), 10); + static_assert(v.max_size() == 10, "max_size is incorrect"); for (int i = 0; i < 10; ++i) { v.push_back(folly::to(i)); @@ -538,10 +577,6 @@ TEST(small_vector, NoHeap) { EXPECT_TRUE(caught); // Check max_size works right with various policy combinations. - folly::small_vector v2; - EXPECT_EQ(v2.max_size(), 32); - folly::small_vector v3; - EXPECT_EQ(v3.max_size(), (1ul << 30) - 1); folly::small_vector v4; EXPECT_EQ(v4.max_size(), (1ul << 31) - 1); @@ -551,7 +586,8 @@ TEST(small_vector, NoHeap) { * pointer. */ folly::small_vector notsosmall; - EXPECT_EQ(notsosmall.max_size(), sizeof(char*)); + static_assert(notsosmall.max_size() == sizeof(char*), + "max_size is incorrect"); caught = false; try { notsosmall.push_back(12); @@ -568,8 +604,6 @@ TEST(small_vector, MaxSize) { EXPECT_EQ(vec.max_size(), 127); folly::small_vector vec2; EXPECT_EQ(vec2.max_size(), (1 << 15) - 1); - folly::small_vector vec3; - EXPECT_EQ(vec3.max_size(), (1 << 14) - 1); } TEST(small_vector, AllHeap) { @@ -594,18 +628,10 @@ TEST(small_vector, AllHeap) { TEST(small_vector, Basic) { typedef folly::small_vector Vector; Vector a; -#ifdef __x86_64__ - a.lock(); - a.unlock(); -#endif - a.push_back(12); EXPECT_EQ(a.front(), 12); EXPECT_EQ(a.size(), 1); @@ -646,7 +672,7 @@ TEST(small_vector, Basic) { } TEST(small_vector, Capacity) { - folly::small_vector vec; + folly::small_vector vec; EXPECT_EQ(vec.size(), 0); EXPECT_EQ(vec.capacity(), 1); @@ -658,8 +684,7 @@ TEST(small_vector, Capacity) { EXPECT_EQ(vec.size(), 2); EXPECT_GT(vec.capacity(), 1); - - folly::small_vector vec2; + folly::small_vector vec2; EXPECT_EQ(vec2.size(), 0); EXPECT_EQ(vec2.capacity(), 2); @@ -672,12 +697,9 @@ TEST(small_vector, Capacity) { EXPECT_EQ(vec2.size(), 3); EXPECT_GT(vec2.capacity(), 2); - // Both have grown by the minimum amount - EXPECT_EQ(vec.capacity(), vec2.capacity()); - // Test capacity heapifying logic folly::small_vector vec3; - const size_t hc_size = 1000000; + const size_t hc_size = 100000; for (size_t i = 0; i < hc_size; ++i) { auto v = (unsigned char)i; vec3.push_back(v); @@ -750,3 +772,313 @@ TEST(small_vector, SelfInsert) { EXPECT_EQ(vec[i], "abc"); } } + +struct CheckedInt { + static const int DEFAULT_VALUE = (int)0xdeadbeef; + CheckedInt(): value(DEFAULT_VALUE) {} + explicit CheckedInt(int value): value(value) {} + CheckedInt(const CheckedInt& rhs, int) : value(rhs.value) {} + CheckedInt(const CheckedInt& rhs): value(rhs.value) {} + CheckedInt(CheckedInt&& rhs) noexcept: value(rhs.value) { + rhs.value = DEFAULT_VALUE; + } + CheckedInt& operator= (const CheckedInt& rhs) { + value = rhs.value; + return *this; + } + CheckedInt& operator= (CheckedInt&& rhs) noexcept { + value = rhs.value; + rhs.value = DEFAULT_VALUE; + return *this; + } + ~CheckedInt() {} + int value; +}; + +TEST(small_vector, ForwardingEmplaceInsideVector) { + folly::small_vector v; + v.push_back(CheckedInt(1)); + for (int i = 1; i < 20; ++i) { + v.emplace_back(v[0], 42); + ASSERT_EQ(1, v.back().value); + } +} + +TEST(small_vector, LVEmplaceInsideVector) { + folly::small_vector v; + v.push_back(CheckedInt(1)); + for (int i = 1; i < 20; ++i) { + v.emplace_back(v[0]); + ASSERT_EQ(1, v.back().value); + } +} + +TEST(small_vector, CLVEmplaceInsideVector) { + folly::small_vector v; + const folly::small_vector& cv = v; + v.push_back(CheckedInt(1)); + for (int i = 1; i < 20; ++i) { + v.emplace_back(cv[0]); + ASSERT_EQ(1, v.back().value); + } +} + +TEST(small_vector, RVEmplaceInsideVector) { + folly::small_vector v; + v.push_back(CheckedInt(0)); + for (int i = 1; i < 20; ++i) { + v[0] = CheckedInt(1); + v.emplace_back(std::move(v[0])); + ASSERT_EQ(1, v.back().value); + } +} + +TEST(small_vector, LVPushValueInsideVector) { + folly::small_vector v; + v.push_back(CheckedInt(1)); + for (int i = 1; i < 20; ++i) { + v.push_back(v[0]); + ASSERT_EQ(1, v.back().value); + } +} + +TEST(small_vector, RVPushValueInsideVector) { + folly::small_vector v; + v.push_back(CheckedInt(0)); + for (int i = 1; i < 20; ++i) { + v[0] = CheckedInt(1); + v.push_back(v[0]); + ASSERT_EQ(1, v.back().value); + } +} + +TEST(small_vector, EmplaceIterCtor) { + std::vector v{new int(1), new int(2)}; + std::vector> uv(v.begin(), v.end()); + + std::vector w{new int(1), new int(2)}; + small_vector> uw(w.begin(), w.end()); +} + +TEST(small_vector, InputIterator) { + std::vector expected{125, 320, 512, 750, 333}; + std::string values = "125 320 512 750 333"; + std::istringstream is1(values); + std::istringstream is2(values); + + std::vector stdV{std::istream_iterator(is1), + std::istream_iterator()}; + ASSERT_EQ(stdV.size(), expected.size()); + for (size_t i = 0; i < expected.size(); i++) { + ASSERT_EQ(stdV[i], expected[i]); + } + + small_vector smallV{std::istream_iterator(is2), + std::istream_iterator()}; + ASSERT_EQ(smallV.size(), expected.size()); + for (size_t i = 0; i < expected.size(); i++) { + ASSERT_EQ(smallV[i], expected[i]); + } +} + +TEST(small_vector, NoCopyCtor) { + struct Test { + Test() = default; + Test(const Test&) = delete; + Test(Test&&) = default; + + int field = 42; + }; + + small_vector test(10); + ASSERT_EQ(test.size(), 10); + for (const auto& element : test) { + EXPECT_EQ(element.field, 42); + } +} + +TEST(small_vector, ZeroInitializable) { + small_vector test(10); + ASSERT_EQ(test.size(), 10); + for (const auto& element : test) { + EXPECT_EQ(element, 0); + } +} + +TEST(small_vector, InsertMoreThanGrowth) { + small_vector test; + test.insert(test.end(), 30, 0); + for (auto element : test) { + EXPECT_EQ(element, 0); + } +} + +TEST(small_vector, EmplaceBackExponentialGrowth) { + small_vector> test; + std::vector capacities; + capacities.push_back(test.capacity()); + for (int i = 0; i < 10000; ++i) { + test.emplace_back(0, 0); + if (test.capacity() != capacities.back()) { + capacities.push_back(test.capacity()); + } + } + EXPECT_LE(capacities.size(), 25); +} + +TEST(small_vector, InsertExponentialGrowth) { + small_vector> test; + std::vector capacities; + capacities.push_back(test.capacity()); + for (int i = 0; i < 10000; ++i) { + test.insert(test.begin(), std::make_pair(0, 0)); + if (test.capacity() != capacities.back()) { + capacities.push_back(test.capacity()); + } + } + EXPECT_LE(capacities.size(), 25); +} + +TEST(small_vector, InsertNExponentialGrowth) { + small_vector test; + std::vector capacities; + capacities.push_back(test.capacity()); + for (int i = 0; i < 10000; ++i) { + test.insert(test.begin(), 100, 0); + if (test.capacity() != capacities.back()) { + capacities.push_back(test.capacity()); + } + } + EXPECT_LE(capacities.size(), 25); +} + +namespace { +struct Counts { + size_t copyCount{0}; + size_t moveCount{0}; +}; + +class Counter { + Counts* counts; + + public: + explicit Counter(Counts& counts) : counts(&counts) {} + Counter(Counter const& other) noexcept : counts(other.counts) { + ++counts->copyCount; + } + Counter(Counter&& other) noexcept : counts(other.counts) { + ++counts->moveCount; + } + Counter& operator=(Counter const& rhs) noexcept { + EXPECT_EQ(counts, rhs.counts); + ++counts->copyCount; + return *this; + } + Counter& operator=(Counter&& rhs) noexcept { + EXPECT_EQ(counts, rhs.counts); + ++counts->moveCount; + return *this; + } +}; +} // namespace + +TEST(small_vector, EmplaceBackEfficiency) { + small_vector test; + Counts counts; + for (size_t i = 1; i <= test.capacity(); ++i) { + test.emplace_back(counts); + EXPECT_EQ(0, counts.copyCount); + EXPECT_EQ(0, counts.moveCount); + } + EXPECT_EQ(test.size(), test.capacity()); + test.emplace_back(counts); + // Every element except the last has to be moved to the new position + EXPECT_EQ(0, counts.copyCount); + EXPECT_EQ(test.size() - 1, counts.moveCount); + EXPECT_LT(test.size(), test.capacity()); +} + +TEST(small_vector, RVPushBackEfficiency) { + small_vector test; + Counts counts; + for (size_t i = 1; i <= test.capacity(); ++i) { + test.push_back(Counter(counts)); + // 1 copy for each push_back() + EXPECT_EQ(0, counts.copyCount); + EXPECT_EQ(i, counts.moveCount); + } + EXPECT_EQ(test.size(), test.capacity()); + test.push_back(Counter(counts)); + // 1 move for each push_back() + // Every element except the last has to be moved to the new position + EXPECT_EQ(0, counts.copyCount); + EXPECT_EQ(test.size() + test.size() - 1, counts.moveCount); + EXPECT_LT(test.size(), test.capacity()); +} + +TEST(small_vector, CLVPushBackEfficiency) { + small_vector test; + Counts counts; + Counter const counter(counts); + for (size_t i = 1; i <= test.capacity(); ++i) { + test.push_back(counter); + // 1 copy for each push_back() + EXPECT_EQ(i, counts.copyCount); + EXPECT_EQ(0, counts.moveCount); + } + EXPECT_EQ(test.size(), test.capacity()); + test.push_back(counter); + // 1 copy for each push_back() + EXPECT_EQ(test.size(), counts.copyCount); + // Every element except the last has to be moved to the new position + EXPECT_EQ(test.size() - 1, counts.moveCount); + EXPECT_LT(test.size(), test.capacity()); +} + +TEST(small_vector, StorageForSortedVectorMap) { + small_sorted_vector_map test; + test.insert(std::make_pair(10, 10)); + EXPECT_EQ(test.size(), 1); + test.insert(std::make_pair(10, 10)); + EXPECT_EQ(test.size(), 1); + test.insert(std::make_pair(20, 10)); + EXPECT_EQ(test.size(), 2); + test.insert(std::make_pair(30, 10)); + EXPECT_EQ(test.size(), 3); +} + +TEST(small_vector, NoHeapStorageForSortedVectorMap) { + noheap_sorted_vector_map test; + test.insert(std::make_pair(10, 10)); + EXPECT_EQ(test.size(), 1); + test.insert(std::make_pair(10, 10)); + EXPECT_EQ(test.size(), 1); + test.insert(std::make_pair(20, 10)); + EXPECT_EQ(test.size(), 2); + EXPECT_THROW(test.insert(std::make_pair(30, 10)), std::length_error); + EXPECT_EQ(test.size(), 2); +} + +TEST(small_vector, StorageForSortedVectorSet) { + small_sorted_vector_set test; + test.insert(10); + EXPECT_EQ(test.size(), 1); + test.insert(10); + EXPECT_EQ(test.size(), 1); + test.insert(20); + EXPECT_EQ(test.size(), 2); + test.insert(30); + EXPECT_EQ(test.size(), 3); +} + +TEST(small_vector, NoHeapStorageForSortedVectorSet) { + noheap_sorted_vector_set test; + test.insert(10); + EXPECT_EQ(test.size(), 1); + test.insert(10); + EXPECT_EQ(test.size(), 1); + test.insert(20); + EXPECT_EQ(test.size(), 2); + EXPECT_THROW(test.insert(30), std::length_error); + EXPECT_EQ(test.size(), 2); +}