News for hackers. Stuff that matters.

maniccoder

Re:Rpmalloc – A lock-free memory allocator on Monday March 20, 2017 @05:38PM (#13917908)
Thank you for the clarifications, I will definitely improve the documentation w.r.t trouble cases, fragmentation and similar allocators.

The goal is of course not to replace the standard allocator, but rather to offer an alternative for those cases where the standard allocator performs poorly.

Re:Rpmalloc – A lock-free memory allocator on Monday March 20, 2017 @05:14AM (#13912729)
Memory blocks are owned by the span (the page-aligned larger bucket of blocks) they belong to. While a span is in use (at least on block is allocated) it is indeed owned by the heap that allocates the block. When the span is completely freed, ownership is released.

In your case, the block will be marked as free for allocation. If it is the last used block in that span, the span will eventually be returned to the global cache and reused by other heaps/threads when the owner thread ends. If the span is still used, it will remain in the heap until the heap is picked up by another thread. Heaps are reused as threads are joined and created (i.e number of allocated heaps are the maximum number of concurrent threads since process started).

The worst case is that one thread allocates blocks, hands them off to other threads then ends, and that the process never creates additional threads. In this case, the spans will remain mapped and unused. I have planned to allow other threads to pick up and collect spans from unused heaps at some point to solve this.

Re:Rpmalloc – A lock-free memory allocator on Monday March 20, 2017 @04:48AM (#13912639)
There already is a benchmark against glibc single threaded, compile the rpmalloc-benchmark repository linked in the readme and run the runall script. Compare rpmalloc 1 thread case against crt 1 thread (with crt being the C runtime, i.e glibc in this case).

Graphs and analysis for a Linux system will be added soon, but a spoiler:

rpmalloc 22.7m memory ops/CPU second, 26MiB bytes peak, 15% overhead

jemalloc 21.3m memory ops/CPU second, 30MiB bytes peak, 33% overhead

tcmalloc 20.4m memory ops/CPU second, 30MiB bytes peak, 32% overhead

crt 13.5m memory ops/CPU second, 24MiB bytes peak, 7% overhead

rpmalloc is faster and has less overhead than both jemalloc and tcmalloc, and a lot faster than glibc at the cost of extra memory overhead.

The reasoning behind the granularities is that 16 bytes is a reasonable granularity for smaller objects (below 2KiB in size). Medium sized requests (between 2KiB and 32KiB) have a 512 byte granularity, while large requests (up to 2MiB) have a 62KiB granularity.

If you have a suggestion for additional benchmark models I would be happy to add an implementation for it.

Re:Rpmalloc – A lock-free memory allocator on Monday March 20, 2017 @01:41AM (#13911998)
I will look into it
Re:Rpmalloc – A lock-free memory allocator on Sunday March 19, 2017 @04:56PM (#13909580)
Yes, you can (unless you also include the provided malloc.c glue code which provides the malloc family of entry points - only use the rpmalloc.c implementation). However, read the caveat section in the readme if you're on a mmap based system.
Re:Rpmalloc – A lock-free memory allocator on Sunday March 19, 2017 @04:54PM (#13909566)
I'm going to add jemalloc, lockless and scalloc in the benchmark comparisons soon(ish).

Regarding the files, only rpmalloc.[h|c] is needed. The malloc.c file is just for overriding the malloc family of entry points, and provide automatic init/fini glue.

The 16 byte alignment is just a note that all returned blocks are naturally aligned to 16 byte boundaries due to the fact that all size buckets are a multiple of 16 bytes internally. It is needed for SSE instructions, which is why I mention it.

Re:Rpmalloc – A lock-free memory allocator on Sunday March 19, 2017 @04:48PM (#13909546)
It does not, at the moment. Feel free to create an issue about it on the github repo, or even submit a PR if you're feeling creative.
Re:Rpmalloc – A lock-free memory allocator on Sunday March 19, 2017 @04:47PM (#13909537)
What specifically would you like to know? I would be happy to elaborate more in the readme if you can explain in more detail what you mean with "insufficient analysis". The reason I posted about it on twitter in the first place was that I wanted feedback and comments on what to improve.

(Btw, I'm the author of the library)