5 ms·

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

by o11c 3y ago

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.

gavinhoward 3y ago
I'm not a contributor to snmalloc or affiliated in any way. 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.
- fanf2 3y ago
  Have you considered using mimalloc? I gather it has a similar design to snmalloc, but mimalloc is written in C.
  - gavinhoward 3y ago
    I did, but I don't want to have a dependency on Microsoft code. 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().
netcoyote 3y ago
Don't all thread implementations leak unfreed memory when a thread exits? 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.
- lights0123 3y ago
  The memory could be freed from another thread with a classical allocator—but this one passes it back to the allocating thread, leaving the question what happens to it?
- deleted 3y ago
  [deleted]
- lelanthran 3y ago
  > Don't all thread implementations leak unfreed memory when a thread exits? 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)
lelanthran 3y ago
> The real question is: how does this deal with freeing allocations from a thread that exited? 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.
mjp41 3y ago
Hi, I am one of the authors of snmalloc. There is a pool of allocators. When a thread exits it returns it to the pool. When a thread is created it first checks the pool for an allocator and uses that in preference to creating a new one. If your application has generally a uniform number of threads over time, then this works well. If you have a spike of threads at start up, then are purely single threaded after that, then this heuristic does not work well. 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.
- menaerus 3y ago
  https://github.com/microsoft/snmalloc#snmalloc https://github.com/microsoft/snmalloc#snmalloc mentions two biggest motivations as: > 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.
  - mjp41 3y ago
    > 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? 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.

by o11c 3y ago

gavinhoward 3y ago

I'm not a contributor to snmalloc or affiliated in any way. 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.

fanf2 3y ago
Have you considered using mimalloc? I gather it has a similar design to snmalloc, but mimalloc is written in C.
- gavinhoward 3y ago
  I did, but I don't want to have a dependency on Microsoft code. 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().

netcoyote 3y ago

Don't all thread implementations leak unfreed memory when a thread exits? 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.

lights0123 3y ago
The memory could be freed from another thread with a classical allocator—but this one passes it back to the allocating thread, leaving the question what happens to it?
deleted 3y ago
[deleted]
lelanthran 3y ago
> Don't all thread implementations leak unfreed memory when a thread exits? 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)

lelanthran 3y ago

> The real question is: how does this deal with freeing allocations from a thread that exited? 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.

mjp41 3y ago

Hi, I am one of the authors of snmalloc. There is a pool of allocators. When a thread exits it returns it to the pool. When a thread is created it first checks the pool for an allocator and uses that in preference to creating a new one. If your application has generally a uniform number of threads over time, then this works well. If you have a spike of threads at start up, then are purely single threaded after that, then this heuristic does not work well. 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.

menaerus 3y ago
https://github.com/microsoft/snmalloc#snmalloc https://github.com/microsoft/snmalloc#snmalloc mentions two biggest motivations as: > 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.
- mjp41 3y ago
  > 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? 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.