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
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.