Late, but better than never I thought I would add Julian Bucknalls articles to this list. But he does not have performance numbers. In my testing of his structures the list scaled well compared to locking (very low kernel usage compared to ReaderWriterLock). His blog has a series of articles on lock free structures in … Read more
Say I write some data, and then I write an indication that the data is now ready. It’s imperative that no other thread who sees the indication that the data is ready not see the write of the data itself. So prior writes cannot move past that write. Say I read that some data is … Read more
This queue data structure is not strictly lock-free by what I consider the most reasonable definition. That definition is something like: A structure is lock-free if only if any thread can be indefinitely suspended at any point while still leaving the structure usable by the remaining threads. Of course this implies a suitable definition of … Read more
OPA (Open Portable Atomics) could be a good fit for your needs. https://trac.mcs.anl.gov/projects/openpa/ It provides a consistent C API to common atomic operations across multiple platforms under an MIT-style license. The library is small and certainly meets your size requirements. The current platform list is: GCC inline assembly for x86, x86_64, ia64, PPC 440, and … Read more
I have looked for actual data for the past days, and found nothing. However, I did some research, which compares the cost of atomic ops with the costs of cache misses. The cost of the x86 LOCK prefix, (including lock cmpxchg for atomic CAS), before PentiumPro (as described in the doc), is a memory access … Read more
Short answer is: You cannot. Long answer is: If you are asking this question, you do not probably know enough to be able to create a lock free structure. Creating lock free structures is extremely hard, and only experts in this field can do it. Instead of writing your own, search for an existing implementation. … Read more
It seems like part what you’re really asking is: Why isn’t the lock prefix implicit for cmpxchg with a memory operand, like it is for xchg (since 386)? The simple answer (that others have given) is simply that Intel designed it this way. But this leads to the question: Why did Intel do that? Is … Read more
In a conforming C++11 compiler this is safe [intro.memory] (ยง1.7): A memory location is either an object of scalar type or a maximal sequence of adjacent bit-fields all having non-zero width. […] Two threads of execution (1.10) can update and access separate memory locations without interfering with each other. C11 gives identical guarantees (they even … Read more
Lock free algorithms generally perform more poorly than lock-based algorithms. That’s a key reason they’re not used nearly as frequently. The problem with lock free algorithms is that they maximize contention by allowing contending threads to continue to contend. Locks avoid contention by de-scheduling contending threads. Lock free algorithms, to a first approximation, should only … Read more
Does this imply that, ‘there is no case where using a non-lock-free atomic type would be a better choice over using a lock-free atomic type when the latter is available’ ? (Mainly in terms of performance rather than ease-of-use). No. And that is, in general, not true. Suppose you have two cores and three threads … Read more