In a multithreaded programming environment, lock contention on the heap is often enough a performance bottleneck.Theoretically at least, the cream-of-the-crop solution for this problem is to have the scalable/parallel[izing] allocator be entirely lock-free. However, it seems to me that besides a few research papers (e.g. [1][2][5]), which do contain promising experimental results, entirely lock-free allocators haven't trickled down to production environments. I'd be glad if you could prove me wrong with counter-examples though. So what are the practical reasons for this slow (or non-existent) adoption of lock-free allocators? Note that more widely used scalable allocators like the one from Intel's TBB are not lock-free although they use fine-grained locks (cf p. 315 in [3]).For what's worth, I also found a CMU student project/paper[4], claiming to have implemented a lock-free allocator that is slightly better than [Google's] tcmalloc on up to 64-cores. Another interesting point in that paper is that llalloc in these tests is Lockless Inc.'s LockLess allocator, which isn't 100% lockfree (it has a lock around the global heap). jemalloc and ptmalloc are also benchmarked in there.References:[1] Michael, Maged M. Scalable lock-free dynamic memory allocation. ACM Sigplan Notices 39.6 (2004): 35-46. I found an independent [re]implementation of Michael's algorithm at http://people.cs.vt.edu/~scschnei/streamflow/[2] Huang, Xiaohuang, et al. Xmalloc: A scalable lock-free dynamic memory allocator for many-core machines. Computer and Information Technology (CIT), 2010 IEEE 10th International Conference on. IEEE, 2010. Free version of the paper as MS thesis.[3] Kukanov, Alexey, and Michael J. Voss. The Foundations for Scalable Multi-core Software in Intel Threading Building Blocks. Intel Technology Journal 11.4 (2007).[4] Alex Podolsky, Nah Lock: A Lock-Free Memory Allocator; apparently written in 2013 based on parent directory timestamps and the S13 suffix in the course name.[5] Gidenstam, Anders, Marina Papatriantafilou, and Philippas Tsigas. NBmalloc: Allocating memory in a lock-free manner. Algorithmica 58.2 (2010): 304-338. Source code available for this one.As a footnote, I see there are 4 pending close votes for this question, but I see none for Why have hardware-accelerated vector graphics not taken off?. It would be interesting if someone could explain why a question that could potentially be answered by somewhat objective performance numbers is more opinion based than one where the main factor is the market orientation of 2-3 big companies.
Why don't we see (more) widespread adoption of lock-free dynamic memory allocators?
multithreading;locks;malloc