1

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.

closed as primarily opinion-based by gbjbaanb, Bart van Ingen Schenau, AProgrammer, user40980, gnat Jan 22 '15 at 13:10

Many good questions generate some degree of opinion based on expert experience, but answers to this question will tend to be almost entirely based on opinions, rather than facts, references, or specific expertise. If this question can be reworded to fit the rules in the help center, please edit the question.

  • As you say, some widely used allocators are quite scalable without being lock free. Why go the extra mile (and risk regressions in actual performance) to be completely lock-free? – user7043 Jan 22 '15 at 7:43
  • @delnan: Because, citing from Michael's paper "The experimental performance results show that not only is our allocator competitive with some of the best lock-based allocators, but also that it outperforms them, and often by substantial margins, in virtually all cases including under various levels of parallelism and various sharing patterns, and also offers the lowest contention-free latency". So what are some scenarios where performance regression is something to be afraid of, as you say? – Fizz Jan 22 '15 at 7:48
  • But does it beat jemalloc and the TBB allocator? Does it beat the current versions of ptmalloc and Hoard? Allocator performance is very tricky, no single paper can settle it definitely. If Intel wanted to adopt a new allocator, they'd probably run their own extensive benchmark suite and collaborate with important customers to test more real-world programs. There's little incentive to do that if their current allocator scales near-linearly in all applications they care about. (Also, there's more to an allocator than throughput: Fragmentation and metadata overhead also matter.) – user7043 Jan 22 '15 at 7:55
  • @delnan: If what you're trying to say is: lock-free allocators would suck or not provide much benefit compared to current state-of-the-art lock-based allocators, then please provide an answer along those lines, preferably backed by some data. – Fizz Jan 22 '15 at 8:21
  • I'm not saying that. I'm saying that the "not completely lock-free" approaches work well enough that most people aren't out actively looking for more scalable approaches, and that any allocator has to overcome significant hurdles to prove its worth and force itself onto the market. – user7043 Jan 22 '15 at 8:25
4

Here are some possible answers:

  • IBM has patented their lock-free allocator... But then they also support Linux etc., so they might have an incentive to at least provide an implementation. And the XMalloc guys also filed for a patent on theirs. But I haven't [yet] found any patents (or patent applications) for NBmalloc.

  • A more a localized issue is that M. Michael appears to have ceased publishing at IBM right after that paper. I'm not sure if he's still with IBM, but having him leave or switch focus might be a reason why IBM didn't try to productize his allocator, as IBM did with prior Watson/Watson2 allocators that made it into AIX. The other lock-free allocators don't seem to have connections with a big company that could push them into a product.

  • Finally, a more general reason would be the relative ratio of code complexity vs. performance benefits. Quoting from "Proving That Non-Blocking Algorithms Don’t Block" by A. Gotsman et al.

    Non-blocking data structures are generally much more complex than their lock-based counterparts, but can provide better performance in the presence of high contention between threads.

    So, the code complexity would have to be justified by significant payoffs in performance. While some lock-free allocator papers have claimed these... other papers have come up with contrary or wish-wash results. In particular, the Streamflow paper, whose authors reimplemented Michael's algorithm, claim to have beaten it soundly using an allocator that wasn't lock-free. Podolsky's course paper came up only with relatively marginal improvements. So I'm guessing the jury is still out if the lock-free allocators are worth the extra effort.

1

How do you know that lock-free allocators / deallocators are not used? For example, take malloc on MacOS X and iOS. Do you know it's lock free or not? (Their documentation says that calling malloc and free on the same thread in short sequence is very fast, and that's the case that you worry about).

  • Sure there can be closed-sourced systems that use lock-free allocators and never explicitly say what they do use, but that's not real (scientific) information... – Fizz Jan 22 '15 at 9:04
  • To give you a comparison, AIX 7.1 is a lot more open/documented with respect to their allocator(s) internals, but they don't seem to have put into production their own lock-free sauce. – Fizz Jan 22 '15 at 9:18
  • The most recent book on OSX internals I found J. Levin's Mac OS X and iOS Internals: To the Apple's Core (2013) explains the OSX heap allocator (the so-called magazine allocator, in use since Snow Leopard) on p. 139. It is fairly similar to Intel's TBB allocator or IBM's threadcache; there's no mention of it being globally lock-free. – Fizz Jan 22 '15 at 9:35
  • By the way, the term "magazines" points to a similarity with usenix.org/legacy/event/usenix01/bonwick.html – Fizz Jan 22 '15 at 9:50
  • There's an even more detailed (and free!) article on the OS X malloc: cocoawithlove.com/2010/05/look-at-how-malloc-works-on-mac.html – Fizz Jan 22 '15 at 11:49

Not the answer you're looking for? Browse other questions tagged or ask your own question.