SuperMalloc: A Super Fast Multithreaded Malloc for 64-bit Machines

For what it's worth, in my tests, Hoard (http://www.hoard.org, https://github.com/emeryberger/Hoard) significantly outperformed SuperMalloc on a machine without TSX. For example, on a simple microbenchmark that tests scalability, Hoard is 2x faster with one thread, and the gap widens with more threads (Hoard is 3.3x faster with 8 threads, 4x faster with 16 threads).

Code at https://github.com/kuszmaul/SuperMalloc.

Paper seems to be there, too, at https://github.com/kuszmaul/SuperMalloc/blob/master/paper/cp...

Neat, we have multiple allocator authors on this thread! I'm one of the authors of reference [38], Streamflow (http://www.scott-a-s.com/projects/#streamflow). Unlike the other allocators, our code has not been kept updated over the years. So it's very reasonable our allocator is not compared against in the experiments. In any event, the allocator for TBBmalloc shares a lot of design similarity. (It's based on McRT-malloc, which was presented as a paper during the same session as our allocator at ISMM 2006.)

The author of this paper does not use lock-free techniques, which our allocator used - I'm curious if using lock-free algorithms would have changed the author's design, or improved the performance. I do think that despite the similarities that Streamflow has to TBBmalloc, Streamflow is not susceptible to the same kind of memory blowup. The problem, as described in the recent paper:

"TBBmalloc can have an unbounded footprint. One case was documented by [40]. In this case, one thread allocates a large number of objects, and a second thread then frees them, placing them into the first threads foreign block. If the first thread then does not call free(), then the memory will never be removed from the foreign block to be reused. There appears to be no easy fix to this problem in TBBmalloc, since the thread-local locking policy assumes, deep in its design, that every thread calls free() periodically."

Streamflow avoids this problem by putting the remote-free block check on the malloc path. That is, when allocating memory, you always check if other threads remotely freed memory for you. Basically, if you're continually allocating memory, you're also continually checking to see if you should clean your memory that other threads freed for you. You can see this in action: https://github.com/scotts/streamflow/blob/master/streamflow....

All of the above is just to add some background - I look forward to really digging into this paper over the holidays.

(In case anyone actually follows my comments, they may know I currently do research and development for IBM Streams. That has zero relationship to this memory allocator I worked on early in grad school; it's just an odd coincidence of project names.)

Fast, multicore-scalable, low-fragmentation memory allocation through large virtual memory and global data structures [1]

An allocator that is designed for scalability from the ground up. Similar design to Streamflow (based on so-called spans) that eagerly returns memory (latency-aware) and a backend that also makes use of fragmenting virtual memory, which is plentiful available on 64bit systems.

[1]: http://dl.acm.org/citation.cfm?doid=2814270.2814294

I think the significant design decision is that in a 64 bit world, virtual address space is no longer scarce. This allows a simpler implementation, roughly half the code.

The micro benchmarks are great, the whole program level benchmarks show nothing earth shaking. But I'll take ok performance and half the code any day.

SuperMalloc was subject to critique and comparison with Bonwick's Slab Allocator in this excellent talk by Ryan Zezeski: "Memory by the Slab: The Tale of Bonwick's Slab Allocator" video, paper etc: http://paperswelove.org/2015/video/ryan-zezeski-memory-by-th...

"dual licensed" - guaranteed to double your licensing confusion.

Comparison to tcmalloc suspiciously omitted.