Mimalloc: Free List Sharding in Action
Created on 2020-07-24T04:01:46.536523
Microsoft shit, but it's actually good.
Designed around a system which uses delayed reference counting.
- Free List: A list of blocks which are currently free.
- Memory Page: A large, contiguous block of memory[1].
- Free List Sharding: Using a separate free list for each memory page.
- Thread Ownership: Each page has a designated thread whom owns it. Non-owner threads can still access memory from the page but have to do it differently.
- Thread Free List: A list of memory blocks which have been freed by threads which do not own the page.
- Thread Local List: A list of memory blocks which have been freed by the thread owning the page.
- No locks are used; all operations are performed atomically. (This is good for systems with many parallel threads.)
Bucketing
Mimalloc is more prone to wasting memory than TLSF or other advanced general allocators.
- Each size class is a power of two (up to a limit of some 512 kilobytes, then each page for very large objects is in chunks of those kilobytes.)
- A memory page holds only objects of a set size class.
- This avoids a coalescing step where the system must stop to combine free blocks and reindex them for later allocations. Freeing an object simply returns the entire chunk to the front of a free list which can be done in a single atomic swap.
Allocation
- If there are no more free blocks during an allocation, the "thread local list" is reaped.
- If no blocks could be claimed, a new page is allocated and appended via linked list to the last block in line. This new page is used to allocate memory from.
- Mimalloc then performs worse where commonly accessed objects end up trapped in later pages of a chain of pages.
Releasing memory
- A non-owning thread frees memory by placing the block in the "thread free list."
- When the owning thread frees memory from a page the block is added to the "thread local list."
Footnotes
- 1. Mimalloc reuses the term "page" and does not mean pages in the operating system sense. It just means a block of memory dedicated to holding objects of a given size class.