The real question is: how does this deal with freeing allocations from a thread that exited?
The implications of thread lifetime seems to be one of the biggest differences between existing allocators.
The implications of thread lifetime seems to be one of the biggest differences between existing allocators.
We have not had complaints about this heuristic, yet. We have a solution that involves marking the remote free queue as sleeping, and a thread that sends to it and observes "sleeping" would then have to do some work for that "sleeping" allocator. This is fairly easy, but I haven't had time to implement it.
> Allocations on one thread are freed by a different thread
I can imagine one use-case for this: a task that is scheduled from and executed by a work-stealing thread-pool can allocate memory in one thread but by design there's no guarantee that the memory will be necessarily freed from that exact thread. Would that be a good use-case for snmalloc?
> Deallocations occur in large batches
This sounds much like a bump allocator use-case but which can do this exact thing by calling a single munmap(addr, len) and unmap multiple allocations all at once.
Yes. A work stealing runtime is a perfect use case for this. Also, cases where you might have a dedicated IO ingress thread that allocates work items, these get picked up by worker threads, and then sent to a dedicated IO egress thread. The ingress thread does a lot of allocation, the egress thread does a lot of deallocation, and the workers do a bit of both. The deallocations typically flow the opposite direction to the work flow, and this works extremely well with snmalloc.
> This sounds much like a bump allocator use-case but which can do this exact thing by calling a single munmap(addr, len) and unmap multiple allocations all at once.
Where suitable bump allocated arena management will be fast, but some times the lifetime are more complex. Certain algorithms for memory management can often release a lot of memory in a batch that is not necessarily allocated in batch, i.e. Lock-free epoch based memory reclamation, or Linux RCU, both batch deciding memory is no longer required. There are also application level things like periodic flushes of a cache/log that can cause batching of deallocations, but are not well suited to bump allocators.
I'm going to reimplement snmalloc in C for my own code.
I'm going to avoid that problem by using structured concurrency. Under my system, threads only get data from threads that are ancestors. (There will be a way of getting data from a non-ancestor, but it will effectively keep the allocating thread alive until the using thread is done.)
The reason I'm going to use snmalloc is because of structured concurrency; it's like it was designed for structured concurrency.
Plus, there are some changes I will make to make my snmalloc/mimalloc clone more friendly to structured concurrency. Nothing major, stuff to mostly deal with realloc().
I assume that they don't release the allocator assigned to a thread when a thread exits, unless that allocator is holding a list of zero allocations.
That sounds like the easiest part of all of this, TBH: A single extra line of code that, after performing an actual deallocation (as opposed to sending a message to perform the deallocation), the allocator checks that it has non-zero allocations, and that the thread still exists, otherwise it deletes itself.
I mean, how would the thread know that the memory needs to be freed? It cannot know that the application hasn't ROT13 encoded the pointer, passed it to another thread, and that thread plans to use the memory.
I'm a bit slow this morning - I don't understand what this is supposed to mean.
To me, it's like saying "don't all functions leak unfreed memory when a function returns" - it's true, but so what? It's always been true.
> I mean, how would the thread know that the memory needs to be freed? It cannot know that the application hasn't ROT13 encoded the pointer, passed it to another thread, and that thread plans to use the memory.
As I understand it, they are using multiple allocators (maybe 1 allocator per thread?), and they store metadata (such as ownership information of the allocated block) during the allocation.
With 1 allocator per thread, each allocation by an allocator maps to a single thread. When a block is to be freed, the allocator for the thread checks the ownership information, and if it is not the owner of that block, sends a request to the thread that is the owner of that block.
This means that even if the thread allocated a block, and let it get used by multiple other threads, they can all call `free` on that block, and the original thread will simply get all the free requests (I assume it will ignore requests for freeing blocks that are already freed).
It all depends on extra metadata stored during allocation, that describes the ownership information of that block.
(Happy to be corrected about any/all of the above)