* `NoHeap` - Avoid the heap entirely. (Throws `std::length_error` if
you would've spilled out of the in-place allocation.)
-* `OneBitMutex` - On x64 platforms, this spends one bit of the
- `size_type` to provide a spin lock that you can use for whatever you
- want.
-
* `<Any integral type>` - customizes the amount of space we spend on
tracking the size of the vector.
// 4-byte size_type.
small_vector<std::unique_ptr<int>, 32, uint32_t> v;
- // A inline vector of up to 256 ints which will not use the
- // heap and comes with a spin lock.
- small_vector<int, 256, NoHeap, OneBitMutex> v;
+ // A inline vector of up to 256 ints which will not use the heap.
+ small_vector<int, 256, NoHeap> v;
// Same as the above, but making the size_type smaller too.
- small_vector<int, 256, NoHeap, uint16_t, OneBitMutex> v;
+ small_vector<int, 256, NoHeap, uint16_t> v;
```
*/
struct NoHeap;
-/*
- * Passing this policy will cause small_vector to provide lock() and
- * unlock() functions using a 1-bit spin lock in the size value.
- *
- * Note that this is intended for a fairly specialized (although
- * strangely common at facebook) use case, where you have billions of
- * vectors in memory where none of them are "hot" and most of them are
- * small. This allows you to get fine-grained locks without spending
- * a lot of memory on mutexes (the alternative of a large hashtable of
- * locks leads to extra cache misses in the lookup path).
- *
- * __x86_64__ only.
- */
-struct OneBitMutex;
-
//////////////////////////////////////////////////////////////////////
} // small_vector_policy
SizeType size_;
};
-#if FOLLY_X64
- template<class SizeType, bool ShouldUseHeap>
- struct OneBitMutexImpl {
- typedef SizeType InternalSizeType;
-
- OneBitMutexImpl() { psl_.init(); }
-
- void lock() const { psl_.lock(); }
- void unlock() const { psl_.unlock(); }
- bool try_lock() const { return psl_.try_lock(); }
-
- protected:
- static bool const kShouldUseHeap = ShouldUseHeap;
-
- static constexpr std::size_t policyMaxSize() {
- return SizeType(~(SizeType(1) << kLockBit | kExternMask));
- }
-
- std::size_t doSize() const {
- return psl_.getData() & ~kExternMask;
- }
-
- std::size_t isExtern() const {
- return psl_.getData() & kExternMask;
- }
-
- void setExtern(bool b) {
- if (b) {
- setSize(SizeType(doSize()) | kExternMask);
- } else {
- setSize(SizeType(doSize()) & ~kExternMask);
- }
- }
-
- void setSize(std::size_t sz) {
- assert(sz < (std::size_t(1) << kLockBit));
- psl_.setData((kExternMask & psl_.getData()) | SizeType(sz));
- }
-
- void swapSizePolicy(OneBitMutexImpl& o) {
- std::swap(psl_, o.psl_);
- }
-
- private:
- static SizeType const kLockBit = sizeof(SizeType) * 8 - 1;
- static SizeType const kExternMask =
- kShouldUseHeap ? SizeType(1) << (sizeof(SizeType) * 8 - 2)
- : 0;
-
- PicoSpinLock<SizeType,kLockBit> psl_;
- };
-#else
- template<class SizeType, bool ShouldUseHeap>
- struct OneBitMutexImpl {
- static_assert(std::is_same<SizeType,void>::value,
- "OneBitMutex only works on x86-64");
- };
-#endif
-
/*
* If you're just trying to use this class, ignore everything about
* this next small_vector_base class thing.
mpl::size<Integrals>::value == 1,
"Multiple size types specified in small_vector<>");
- /*
- * Figure out if we're supposed to supply a one-bit mutex. :)
- */
- typedef typename mpl::count<
- PolicyList,small_vector_policy::OneBitMutex
- >::type HasMutex;
-
- static_assert(HasMutex::value == 0 || HasMutex::value == 1,
- "Multiple copies of small_vector_policy::OneBitMutex "
- "supplied; this is probably a mistake");
-
/*
* Determine whether we should allow spilling to the heap or not.
*/
/*
* Make the real policy base classes.
*/
- typedef typename mpl::if_<
- HasMutex,
- OneBitMutexImpl<SizeType,!HasNoHeap::value>,
- IntegralSizePolicy<SizeType,!HasNoHeap::value>
- >::type ActualSizePolicy;
+ typedef IntegralSizePolicy<SizeType,!HasNoHeap::value>
+ ActualSizePolicy;
/*
* Now inherit from them all. This is done in such a convoluted
8 + 1,
"small_vector<int32_t,1,uint32_t> is wrong size");
-static_assert(sizeof(small_vector<int32_t,1,OneBitMutex>) == 16,
- "OneBitMutex took more space than expected");
-
static_assert(sizeof(small_vector<int16_t,4,uint16_t>) == 10,
"Sizeof unexpectedly large");
-static_assert(sizeof(small_vector<int16_t,4,uint16_t,OneBitMutex>) == 10,
- "Sizeof unexpectedly large");
-static_assert(sizeof(small_vector<int16_t,4,NoHeap,uint16_t,
- OneBitMutex>) == 10,
- "Sizeof unexpectedly large");
#endif
EXPECT_TRUE(caught);
// Check max_size works right with various policy combinations.
- folly::small_vector<std::string,32,uint32_t,NoHeap,OneBitMutex> v2;
- static_assert(v2.max_size() == 32, "max_size is incorrect");
- folly::small_vector<std::string,32,uint32_t,OneBitMutex> v3;
- EXPECT_EQ(v3.max_size(), (1ul << 30) - 1);
folly::small_vector<std::string,32,uint32_t> v4;
EXPECT_EQ(v4.max_size(), (1ul << 31) - 1);
EXPECT_EQ(vec.max_size(), 127);
folly::small_vector<int,2,uint16_t> vec2;
EXPECT_EQ(vec2.max_size(), (1 << 15) - 1);
- folly::small_vector<int,2,uint16_t,OneBitMutex> vec3;
- EXPECT_EQ(vec3.max_size(), (1 << 14) - 1);
}
TEST(small_vector, AllHeap) {
TEST(small_vector, Basic) {
typedef folly::small_vector<int,3,uint32_t
-#if FOLLY_X64
- ,OneBitMutex
-#endif
> Vector;
Vector a;
-#if FOLLY_X64
- a.lock();
- a.unlock();
-#endif
-
a.push_back(12);
EXPECT_EQ(a.front(), 12);
EXPECT_EQ(a.size(), 1);
projects / folly.git / commitdiff