Fastest inline-assembly spinlock

sigvardsen picture sigvardsen · Aug 14, 2012 · Viewed 12.4k times · Source

I'm writing a multithreaded application in c++, where performance is critical. I need to use a lot of locking while copying small structures between threads, for this I have chosen to use spinlocks.

I have done some research and speed testing on this and I found that most implementations are roughly equally fast:

  • Microsofts CRITICAL_SECTION, with SpinCount set to 1000, scores about 140 time units
  • Implementing this algorithm with Microsofts InterlockedCompareExchange scores about 95 time units
  • Ive also tried to use some inline assembly with __asm {} using something like this code and it scores about 70 time units, but I am not sure that a proper memory barrier has been created.

Edit: The times given here are the time it takes for 2 threads to lock and unlock the spinlock 1,000,000 times.

I know this isn't a lot of difference but as a spinlock is a heavily used object, one would think that programmers would have agreed on the fastest possible way to make a spinlock. Googling it leads to many different approaches however. I would think this aforementioned method would be the fastest if implemented using inline assembly and using the instruction CMPXCHG8B instead of comparing 32bit registers. Furthermore memory barriers must be taken into account, this could be done by LOCK CMPXHG8B (I think?), which guarantees "exclusive rights" to the shared memory between cores. At last [some suggests] that for busy waits should be accompanied by NOP:REP that would enable Hyper-threading processors to switch to another thread, but I am not sure whether this is true or not?

From my performance-test of different spinlocks, it is seen that there is not much difference, but for purely academic purpose I would like to know which one is fastest. However as I have extremely limited experience in the assembly-language and with memory barriers, I would be happy if someone could write the assembly code for the last example I provided with LOCK CMPXCHG8B and proper memory barriers in the following template:

__asm
{
     spin_lock:
         ;locking code.
     spin_unlock:
         ;unlocking code.
}

Answer

Necrolis picture Necrolis · Aug 16, 2012

Although there is already an accepted answer, there are a few things that where missed that could be used to improve all the answers, taken from this Intel article, all above fast lock implementation:

  1. Spin on a volatile read, not an atomic instruction, this avoids unneeded bus locking, especially on highly contended locks.
  2. Use back-off for highly contested locks
  3. Inline the lock, preferably with intrinsics for compilers where inline asm is detrimental (basically MSVC).