Consider using restartable sequences

[rigtorp]

Restartable sequences is a Linux feature that allows creating wait-free per CPU data structures. You can read more about it here https://lwn.net/Articles/662946/ and here https://www.efficios.com/blog/2019/02/08/linux-restartable-sequences/. You can read about how tcmalloc is using it here https://google.github.io/tcmalloc/design.html. It can be used to move to per CPU arenas instead of per thread arenas.

It might not be a high priority to implement, but I wanted to raise awareness of restartable sequences.

[daanx]

Ah very interesting. I have not seen that before and will take a close look -- it would be great if it can be used to avoid some CAS instructions and find further perf improvements. Thanks for the links!

[rigtorp]

To avoid CAS I think you would need to have approximately N^2 thread free lists, one for each possible pairing of threads. With restartable sequences you can have per cpu free lists. This could lead to less wasted heap space. It's also possible that the N in N^2 becomes small enough (number of CPU cores) that it's feasible to use CAS free spsc queues instead of the current mpsc for cross-thread frees.

Great work creating mimalloc! It's a very promising allocator and good to see some innovation on heap allocators. I particularly like the great huge page support, it's really easy to use: https://rigtorp.se/hugepages/ (Last section, scroll to the end).

[rigtorp]

I found this very detailed explanation on how tcmalloc uses rseq for per cpu free lists: https://google.github.io/tcmalloc/rseq.html