Mimalloc: Free List Sharding in Action

Created: 2020-07-24T04:01:46.536523

Return to the Index

This card pertains to a resource available on the internet.

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.