Skip to content

Latest commit

 

History

History
42 lines (32 loc) · 1.94 KB

difference.md

File metadata and controls

42 lines (32 loc) · 1.94 KB
Raw

Difference from published paper

This document outlines the changes that have diverged from the published paper on snmalloc.

  1. Link no longer terminates the bump-free list. The paper describes a complex invariant for how the final element of the bump-free list can also be the link node.

    We now have a much simpler invariant. The link is either 1, signifying the block is completely full. Or not 1, signifying it has at least one free element at the offset contained in link, and that contains the DLL node for this sizeclass.

    The bump-free list contains additional free elements, and the remaining bump allocated space.

    The value 1, is never a valid bump allocation value, as we initially allocate the first entry as the link, so we can use 1 as the no more bump space value.

  2. Separate Bump/Free list. We have separate bump ptr and free list. This is required to have a "fast free list" in each allocator for each sizeclass. We bump allocate a whole os page (4KiB) worth of allocations in one go, so that the CPU predicts the free list path for the fast path.

  3. Per allocator per sizeclass fast free list. Each allocator has an array for each small size class that contains a free list of some elements for that sizeclass. This enables a very compressed path for the common allocation case.

  4. We now store a direct pointer to the next element in each slabs free list rather than a relative offset into the slab. This enables list calculation on the fast path.

  5. There is a single bump-ptr per size class that is part of the allocator structure. The per size class slab list now only contains slabs with free list, and not if it only has a bump ptr.

[2-4] Are changes that are directly inspired by (mimalloc)[http://github.com/microsoft/mimalloc].