1 `folly/PackedSyncPtr.h`
4 A highly specialized data structure consisting of a pointer, a 1-bit
5 spin lock, and a 15-bit integral packed into `sizeof(void*)`.
7 Typical application is for microsharding of many elements within containers.
8 Because there is no memory overhead, an arbitrarily large number of locks can be
9 used to minimize lock contention with no memory penalty. Additionally,
10 excellent cache performance is obtained by storing the lock inline with the
11 pointer (no additional cache miss or false sharing). Finally, because it uses a
12 simple spinlock mechanism, the cost of aqcuiring an uncontended lock is minimal.
17 This is not a "smart" pointer: nothing automagical is going on
18 here. Locking is up to the user. Resource deallocation is up to
19 the user. Locks are never acquired or released outside explicit
20 calls to lock() and unlock().
22 Change the value of the raw pointer with set(), but you must hold
23 the lock when calling this function if multiple threads could be
26 Here is an example of using a PackedSyncPtr to build a synchronized vector with
27 no memory overhead - the spinlock and size are stored in the 16 unused bits of
28 pointer, the rest of which points to the actual data. See
29 `folly/small_vector.h` for a complete implementation of this concept.
34 PackedSyncPtr<T> base;
37 SyncVec() { base.init(); }
39 void push_back(const T& t) {
41 static_cast<T*>(realloc(base.get(), (base.extra() + 1) * sizeof(T))));
42 base[base.extra()] = t;
43 base.setExtra(base.extra() + 1);
63 return base.get() + base.extra();
71 This is using an x64-specific detail about the effective virtual
72 address space. Long story short: the upper two bytes of all our
73 pointers will be zero in reality---and if you have a couple billion
74 such pointers in core, it makes pretty good sense to try to make
75 use of that memory. The exact details can be perused here:
77 [http://en.wikipedia.org/wiki/X86-64#Canonical_form_addresses](http://en.wikipedia.org/wiki/X86-64#Canonical_form_addresses)