Going lock-free has the benefit on any platform (well, any platform with atomic primitives) that you don't have to worry about a thread getting preempted while holding a lock and blocking others indefinitely. However, I think the scalability advantages aren't as evident on today's systems as they will be (or are, in the case of GPUs) on systems with high-tens to hundreds or thousands of hardware threads. The main reason I've found is that most lock-free algorithms I've implemented add significant constant factors over their serial equivalents (often via retries on CAS failure), so you really have to have high access concurrency to make it worth your while.
Going lock-free also tends to force you to use simpler data structures, since you have to figure out how to migrate the data structure from state A to state B via a sequence of very "small" operations (e.g., a CAS or atomic add), making sure that every intermediate state along the way is also valid. This is in contrast to acquiring a (group of) lock(s) and going to town for a lock-based data structure. As evidence of this, being able to figure out a lock-free variant of something like a linked list or skip list --- things which are not considered rocket science in the serial world --- will usually get you a conference or journal paper.
Another reason I don't think we've seen the best of lock-free yet is that most current implementations besides GPUs ride on top of cache coherence; you incur all the overhead of getting the cache line in your local cache, perform the atomic op, then ship it somewhere else. Since the whole raison d'etre of lock-free algorithms is that data operated on atomically tends to be getting hammered by many threads, there's really not much point to shipping it all around the chip; just put some functional units in the last-level cache and keep the data there.
Haven't looked at the Lockless source yet, but locks on the fast path does seem unusual; it seems fairly standard in high-performance allocators to have a per-thread cache of freed blocks, which obviously doesn't need locks.
I'd be interested in a copy of the SFMalloc paper, if it's alright with the authors (email in profile); wasn't able to attend PACT this year to see the talk, but I'm very interested in the work.
Your points are true in general, but memory allocation is a special case.
The main data structures in memory allocators tend to be pretty simple. We got away with using singly-linked lists (FIFO queues) as the only shared data structure that needed to be lock-free. In that case, you trade one lock for one compare-and-swap, so there it's an even trade. The main path of the allocation was free of synchronization.
I also implemented a lock-free radix tree (the original was borrowed from TCMalloc), and you can see multiple compare-and-swap operations in the main routine (https://github.com/scotts/streamflow/blob/master/streamflow....), but they will be hit only rarely.
I applied your reasoning, though. The fast path for allocation and freeing small objects was usually synchronization free, and always lock-free. But I protected my page manager with spin locks. The page manager was responsible for grabbing pages from the OS, giving them back to the OS, and carving out pages for individual threads to use as their backing store for their small object allocations. My rationale was that we would only hit the page manager rarely, and in that case, it would probably be faster to use a spin lock, since I anticipated getting pages from the page manager would usually be uncontended.
But that was back in 2005 and 2006. We only had access to 8 thread machines. The SFMalloc paper makes it lock-free all the way up the stack, and their experiments of up to 48 cores shows significant improvement.
Comments
Going lock-free has the benefit on any platform (well, any platform with atomic primitives) that you don't have to worry about a thread getting preempted while holding a lock and blocking others indefinitely. However, I think the scalability advantages aren't as evident on today's systems as they will be (or are, in the case of GPUs) on systems with high-tens to hundreds or thousands of hardware threads. The main reason I've found is that most lock-free algorithms I've implemented add significant constant factors over their serial equivalents (often via retries on CAS failure), so you really have to have high access concurrency to make it worth your while.
Going lock-free also tends to force you to use simpler data structures, since you have to figure out how to migrate the data structure from state A to state B via a sequence of very "small" operations (e.g., a CAS or atomic add), making sure that every intermediate state along the way is also valid. This is in contrast to acquiring a (group of) lock(s) and going to town for a lock-based data structure. As evidence of this, being able to figure out a lock-free variant of something like a linked list or skip list --- things which are not considered rocket science in the serial world --- will usually get you a conference or journal paper.
Another reason I don't think we've seen the best of lock-free yet is that most current implementations besides GPUs ride on top of cache coherence; you incur all the overhead of getting the cache line in your local cache, perform the atomic op, then ship it somewhere else. Since the whole raison d'etre of lock-free algorithms is that data operated on atomically tends to be getting hammered by many threads, there's really not much point to shipping it all around the chip; just put some functional units in the last-level cache and keep the data there.
Haven't looked at the Lockless source yet, but locks on the fast path does seem unusual; it seems fairly standard in high-performance allocators to have a per-thread cache of freed blocks, which obviously doesn't need locks.
I'd be interested in a copy of the SFMalloc paper, if it's alright with the authors (email in profile); wasn't able to attend PACT this year to see the talk, but I'm very interested in the work.
Your points are true in general, but memory allocation is a special case.
The main data structures in memory allocators tend to be pretty simple. We got away with using singly-linked lists (FIFO queues) as the only shared data structure that needed to be lock-free. In that case, you trade one lock for one compare-and-swap, so there it's an even trade. The main path of the allocation was free of synchronization.
I also implemented a lock-free radix tree (the original was borrowed from TCMalloc), and you can see multiple compare-and-swap operations in the main routine (https://github.com/scotts/streamflow/blob/master/streamflow....), but they will be hit only rarely.
I applied your reasoning, though. The fast path for allocation and freeing small objects was usually synchronization free, and always lock-free. But I protected my page manager with spin locks. The page manager was responsible for grabbing pages from the OS, giving them back to the OS, and carving out pages for individual threads to use as their backing store for their small object allocations. My rationale was that we would only hit the page manager rarely, and in that case, it would probably be faster to use a spin lock, since I anticipated getting pages from the page manager would usually be uncontended.
But that was back in 2005 and 2006. We only had access to 8 thread machines. The SFMalloc paper makes it lock-free all the way up the stack, and their experiments of up to 48 cores shows significant improvement.