Nofl: A Precise Immix

Abstract

Can a memory manager be built with fast bump-pointer allocation, single-pass heap tracing, and a low upper bound on memory overhead? The Immix collector answered in the affirmative for the first two, but the granularity at which it reclaims memory means that in the worst case a tiny object can keep two 128-byte lines of memory from being re-used for allocation. This paper takes Immix to an extreme of precision, allowing all free space between objects to be reclaimed, down to the limit of the allocator's minimum alignment. We present the design of this Nofl layout, build a collector library around it, and build a new Scheme-to-C compiler as a workbench. We make a first evaluation of the Nofl-based mostly-marking collector when compared to standard copying and mark-sweep collectors and run against a limited set of microbenchmarks, finding that Nofl outperforms the others for tight-to-adequate heap sizes.