Compacting the Uncompactable by Bobby Powers

  • Mesh performs allocations by meshing together pages at the physical layer, and simply pointing each of the virtual pages invoived in the mesh to the meshed physical page. This results in compaction without having to rewrite pointers (especially when pointers are indistingushable from integers).

  • Pages are divided into blocks, and two pages are meshable when every block on both pages does not have a corresponding block at the same memory location on the other page. Not sure how the block size is chosen; heuristic based on historical allocations or fixed?

  • It does a bunch of work to make it more probable that pages will mesh together, such as randomizing allocations. The randomizer maintains a thread-local vector of free locations, and shuffles this index to hand out allocations. Not sure this works in a multi-threaded environment.

  • Uses a matching graph algorithm (the talk didn’t go into too much detail, but the paper appears to cover this) to find pairs of meshable pages.

  • Significant improvements over jemalloc (Firefox), Redis' custom defragmentor and the Ruby interpreter:

Look Up

  • mmap
  • Moving GC
  • Memory page / page tables
  • libmesh
  • Virtual memory
  • segfault
  • Memory compaction
  • Tracing GC
  • Swift: why no GC?
  • jemalloc
  • free slowpath
  • MinCliqueCover
  • CPU intrinsics
  • TLB flush
  • Generational GC
  • Cache coherence
  • Segfault handler
  • Ring buffer