Mimalloc is a memory allocator that claims particularly high performance, and suggests that this is partly due to good spatial locality. According to https://www.microsoft.com/en-us/research/uploads/prod/2019/06/mimalloc-tr-v1.pdf
The main idea is to use extreme free list sharding: instead of one large free list per size class, we instead have a free list per mimalloc page (usually 64KiB). This keeps locality of allocation as malloc allocates inside one page until that page is full, regardless of where other objects are freed in the heap.
Okay. My first thought on reading this was that this is talking about locality at the page level, which is important if your program is going to be doing a lot of paging to disk. Fair enough. But that's not something you really want to be doing nowadays anyway. RAM is the new disk, cache is the new RAM; for anything computationally intensive, you always want to be staying in memory, and locality is about staying as much as possible in cache. And a cache line is 64 bytes, so it doesn't matter whether two objects are in the same multi-kilobyte page...
To test this, we did an experiment in the Lean compiler (Moura et al., 2015). Version 3 of the compiler had a custom allocator for allocating small objects where it used a single free list. We replaced this implementation with just a sharded free list per slab (page) and on some benchmarks with large data structures in a 1GiB heap, we saw performance improvements of over 25% with this single change! Early work by Feng and Berger (2005) on the locality improving VAM allocator also used a sharded free list design and they measured a significant reduction in the L2 cache misses.
... uh? That sounds like they are claiming increased locality at the page level, actually improves L2 cache hit rate.
Is this actually true? And if so, how?
Is it a stochastic thing, that if you cram as many objects as possible into the same 64K page, the percentage of them that happen to occupy the same 64 byte cache line will increase? Or is there something else going on?