RWSpinLock.hpp File Reference

ReadWrite lock using spin_lock, copied from Folly library under Apache-2.0 license, see https://github.com/facebook/folly/blob/master/folly/synchronization/RWSpinLock.h. More...

#include <algorithm>
#include <atomic>
#include <thread>
#include "../Common.h"

Go to the source code of this file.

Classes
class	Memory::RWSpinLock
	High-performance read-write-spinlock, see RWSpinLock.hpp for details. More...
class	Memory::RWSpinLock::ReadHolder
	RAII guard for read lock with RWSpinLock::lock_shared() on construction and RWSpinLock::unlock_shared() on destruction. More...
class	Memory::RWSpinLock::UpgradedHolder
	RAII guard for upgrade lock with RWSpinLock::lock_upgrade() on construction and RWSpinLock::unlock_upgrade() on destruction. More...
class	Memory::RWSpinLock::WriteHolder
	RAII guard for write lock with RWSpinLock::lock() on construction and RWSpinLock::unlock() on destruction. More...

Namespaces
namespace	Memory
	Namespace for all classes, typedefs and functions of memory safety. See Memory Safety for more instrucion.

Detailed Description

ReadWrite lock using spin_lock, copied from Folly library under Apache-2.0 license, see https://github.com/facebook/folly/blob/master/folly/synchronization/RWSpinLock.h.

Author

Xin Liu xliux.nosp@m.@fb..nosp@m.com

N.B. You most likely do not want to use RWSpinLock or any other kind of spinlock. Use SharedMutex instead.

In short, spinlocks in preemptive multi-tasking operating systems have serious problems and fast mutexes like SharedMutex are almost certainly the better choice, because letting the OS scheduler put a thread to sleep is better for system responsiveness and throughput than wasting a timeslice repeatedly querying a lock held by a thread that's blocked, and you can't prevent userspace programs blocking.

Spinlocks in an operating system kernel make much more sense than they do in userspace.

---

Read-Write spin lock implementations.

Ref: http://locklessinc.com/articles/locks

Both locks here are faster than pthread_rwlock and have very low overhead (usually 20-30ns). They don't use any system mutexes and are very compact (4/8 bytes), so are suitable for per-instance based locking, particularly when contention is not expected.

For a spinlock, RWSpinLock is a reasonable choice. (See the note about for why a spin lock is frequently a bad idea generally.) RWSpinLock has minimal overhead, and comparable contention performance when the number of competing threads is less than or equal to the number of logical CPUs. Even as the number of threads gets larger, RWSpinLock can still be very competitive in READ, although it is slower on WRITE, and also inherently unfair to writers.

The lock will not grant any new shared (read) accesses while a thread attempting to acquire the lock in write mode is blocked. (That is, if the lock is held in shared mode by N threads, and a thread attempts to acquire it in write mode, no one else can acquire it in shared mode until these N threads release the lock and then the blocked thread acquires and releases the exclusive lock.) This also applies for attempts to reacquire the lock in shared mode by threads that already hold it in shared mode, making the lock non-reentrant.

RWSpinLock handles 2^30 - 1 concurrent readers.

---

Benchmark on (Intel(R) Xeon(R) CPU L5630 @ 2.13GHz) 8 cores(16 HTs)

1. Single thread benchmark (read/write lock + unlock overhead)

   Benchmark	Iters	Total t	t/iter	iter/sec
   * BM_RWSpinLockRead	100000	1.786 ms	17.86 ns	53.4 M
   +30.5% BM_RWSpinLockWrite	100000	2.331 ms	23.31 ns	40.91 M
   + 175% BM_PThreadRWMutexRead	100000	4.917 ms	49.17 ns	19.4 M
   + 166% BM_PThreadRWMutexWrite	100000	4.757 ms	47.57 ns	20.05 M

2. Contention Benchmark (90% read, 10% write)

   Benchmark	hits	average	min	max	sigma
   8 threads
   RWSpinLock Write	142666	220 ns	78 ns	40.8 us	269 ns
   RWSpinLock Read	1282297	222 ns	80 ns	37.7 us	248 ns
   pthread_rwlock_t Write	84248	2.48 us	99 ns	269 us	8.19 us
   pthread_rwlock_t Read	761646	933 ns	101 ns	374 us	3.25 us
   16 threads
   RWSpinLock Write	124236	237 ns	78 ns	261 us	801 ns
   RWSpinLock Read	1115807	236 ns	78 ns	2.27 ms	2.17 us
   pthread_rwlock_t Write	83363	7.12 us	99 ns	785 us	28.1 us
   pthread_rwlock_t Read	754978	2.18 us	101 ns	1.02 ms	14.3 us
   50 threads
   RWSpinLock Write	131142	1.37 us	82 ns	7.53 ms	68.2 us
   RWSpinLock Read	1181240	262 ns	78 ns	6.62 ms	12.7 us
   pthread_rwlock_t Write	80849	112 us	103 ns	4.52 ms	263 us
   pthread_rwlock_t Read	728698	24 us	101 ns	7.28 ms	194 us