Snmalloc: A Message Passing Allocator

Unfortunately, I cannot find any significant code samples for Verona on the website or in the GitHub repo. There are a few types defined in a pretty low-level way:

https://github.com/microsoft/verona/tree/master/std/builtin

Re: Snmalloc: A Message Passing Allocator

#9

Post by Varriount » Thu, Oct 12, 2023, 1:17 AM UTC

ridiculous_fish wrote: post #5

There's lots more details about the design in this PDF: https://alex.shamis.au/files/snmalloc-A-Message-Passing-Allo...

I found this design decision rather odd:

  Allocators may send messages to any other allocator. In a naïve implementation each allocator would keep a queue of batched messages for each other allocator. The number of queues would then either be the dynamically known number of existing threads, or the statically known maximal number of possible threads. The former would require allocation of a dynamically sized structure when handling remote deallocation and slow enqueueing, while the latter would lead to significant wasted space and hard-coded limits. Instead, we adapted ideas from radix trees. Allocators keep a fixed 2k size array of buckets of pending messages, where k in our implementation is 6. Batched messages are inserted into the bucket which corresponds to their destination’s address, modulo the number of buckets. Dispatch of messages takes place by sending all the messages from the same bucket to one allocator, which then responds to those messages for which it is the final destination, and forwards the rest, again according to their destination allocator address, but now shifted right by k bits.

I would think that the overhead of message passing would mean that minimization of the number of messages sent. I wonder how well this technique scales.

Re: Snmalloc: A Message Passing Allocator

#10

Post by gavinhoward » Thu, Oct 12, 2023, 1:48 AM UTC

o11c wrote: post #6

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.

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.