folly/docs/PackedSyncPtr.md

   1 `folly/PackedSyncPtr.h`
   2 ----------------------
   3
   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*)`.
   6
   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.
  13
  14 ### Usage
  15 ***
  16
  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().
  21
  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
  24 using it.
  25
  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.
  30
  31 ``` Cpp
  32     template<typename T>
  33     class SyncVec {
  34       PackedSyncPtr<T> base;
  35
  36      public:
  37       SyncVec() { base.init(); }
  38
  39       void push_back(const T& t) {
  40         base.set(
  41           static_cast<T*>(realloc(base.get(), (base.extra() + 1) * sizeof(T))));
  42         base[base.extra()] = t;
  43         base.setExtra(base.extra() + 1);
  44       }
  45
  46       size_t size() const {
  47         return base.extra();
  48       }
  49
  50       void lock() {
  51         base.lock();
  52       }
  53
  54       void unlock() {
  55         base.unlock();
  56       }
  57
  58       T* begin() const {
  59         return base.get();
  60       }
  61
  62       T* end() const {
  63         return base.get() + base.extra();
  64       }
  65     };
  66 ```
  67
  68 ### Implementation
  69 ***
  70
  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:
  76
  77 [http://en.wikipedia.org/wiki/X86-64#Canonical_form_addresses](http://en.wikipedia.org/wiki/X86-64#Canonical_form_addresses)