Snmalloc: A Message Passing Allocator

Snmalloc: A Message Passing Allocator
github.com

  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.