Do lock-free algorithms really perform better than their lock-full counterparts?

by

Beyond the simple cases of the InterlockedXxx functions, it seems like
the prevailing pattern with all of these is that they implement their
own locks.

None of the answers here really seem to get to the heart of the difference between a “lock-free” CAS loop and a mutex or spin-lock.

The important difference is that lock-free algorithms are guaranteed to make progress on their own – without the assistance of other threads. With a lock or spin lock, any poor thread that can’t acquire a lock is entirely at the mercy of the thread that owns the lock. The poor thread that can’t acquire the lock can do nothing except wait (either via a busy wait or an OS-assisted sleep).

With lock-free algorithms that loop on a CAS, each thread is guaranteed to make progress regardless of what other contending threads are doing. Each thread is, essentially, in control of its own fate. Yes, it still may have to loop many times, but the number of times it loops is limited by the number of contending threads. It cannot infinitely loop, for the most part. (In practice, it’s possible for live lock to occur due to, e.g. an LL/SC loop that keeps failing due to false sharing) – but again measures can be taken by the thread itself to deal with this – it is not at the mercy of another thread holding a lock.

As for performance, it depends. I’ve seen flagrant examples of lock-free algorithms being totally out-performed by their locking counterparts, even under high-thread contention. On an x86-64 machine running Debian 7, I compared the performance between the C++ Boost.Lockfree queue (based on the Michael/Scott algorithm) and a plain old std::queue surround by an std::mutex. Under high thread contention, the lockfree version was almost twice as slow.

So why is that? Well, the performance of lockfree algorithms ultimately comes down to the implementation details. How does the algorithm avoid ABA? How does it accomplish safe memory reclamation? There are so many variants… tagged pointers, epoch based reclamation, RCU/quiescent state, hazard pointers, general process-wide garbage collection, etc. All these strategies have performance implications, and some also place restrictions on how your application in general can be designed. In general, reference-counting approaches (or tagged pointer approaches) tend to perform poorly, in my experience. But the alternatives can be much more complex to implement, and require a lot more memory-reclamation infrastructure based around thread-local storage or generalized garbage collection.

More Related Contents:

  1. Is it possible to use mutex in multiprocessing case on Linux/UNIX ?
  2. Conditional Variable vs Semaphore
  3. When is a condition variable needed, isn’t a mutex enough?
  4. What happens when different CPU cores write to the same RAM address without synchronization?
  5. How do I run parallel threads of computation on a partitioned array?
  6. What is a race condition?
  7. Synchronizing on String objects in Java
  8. How can I implement ABA counter with c++11 CAS?
  9. How to avoid Not on FX application thread; currentThread = JavaFX Application Thread error?
  10. What is a semaphore?
  11. Lock-free Progress Guarantees in a circular buffer queue
  12. Are C++ Reads and Writes of an int Atomic?
  13. Are Java static initializers thread safe?
  14. What is the Re-entrant lock and concept in general?
  15. Which would be better for concurrent tasks on node.js? Fibers? Web-workers? or Threads?
  16. Asynchronous vs Multithreading – Is there a difference?
  17. How to Multi-thread an Operation Within a Loop in Python
  18. What is the difference between a synchronized method and synchronized block in Java? [duplicate]
  19. How Do I Choose Between the Various Ways to do Threading in Delphi?
  20. Sharing a variable between multiple different threads
  21. How to manage db connections on server?
  22. Can x86 reorder a narrow store with a wider load that fully contains it?
  23. Using HttpContext.Current in WebApi is dangerous because of async
  24. Asynchronous IO in Scala with futures
  25. How do I Understand Read Memory Barriers and Volatile
  26. Canonical way to generate random numbers in Cython
  27. Can a hyper-threaded processor core execute two threads at the exact same time?
  28. Prolog find all paths Implementation
  29. omp parallel vs. omp parallel for
  30. Which is more efficient, basic mutex lock or atomic integer?

Leave a Comment