粗略看了西半球最快内存分配器mimalloc的论文和源码，这里简单做点笔记。本文是论文阅读篇。
亮点
论文Mimalloc: Free List Sharding in Action提到mimalloc跑得快的设计要点有三处：
- 使用三种页级本地（完全无锁）链表并实现分片，提高局部性和避免竞争。
- 高度调优的快速路径，路径尽可能短且少分支。
- 可预测的周期性维护操作（temporal cadence），可以用于批量处理（比如延迟释放）。
这些策略使得mimalloc分别比高性能的tcmalloc和jemalloc还要快7%和14%。
设计动机
mimalloc当初是为了支持Lean和Koka语言的运行时而产生的，它们有这两种负载特征：
- 都是函数式编程语言，需要频繁分配短周期、小尺寸的对象（并且jemalloc在这里表现不佳）。
- 运行时使用引用计数来管理内存，需要提供延迟释放的特性来避免大型数据结构引起的停顿。
这也暗示了mimalloc在这种负载下可能有更好的性能表现。
链表分片
Allocation free list
论文指出许多分配器是基于size-class（按大小划分）的方式来实现single free list，这种做法并没有足够好的空间局部性。
比如上图(A)位于一整块的堆空间，在free list上新分配一个包含3个元素的链表p后如图(B)所示，这种支离破碎的现象并不罕见。
mimalloc通过分片的方式解决这个问题。堆按size-class被划分为多个页，通常每个页的大小为64KB。很显然使用分片后，局部性得到提升（见红线部分）。微软也基于Lean编译器做了基准测试，表示这种策略提高了25%的性能，主要是因为L2 cache命中率的提升。
Local free list
对于大型数据结构来说，free()操作实际会引起递归嵌套的多次free()。为了避免类似最坏情况，可以引入一个计数器，当free()达到一定次数后就把剩下的指针放入延迟链表（论文是基于引用计数的前提去讨论的，因此称为deferred decrement list，但也说了这种情况不管是否引用计数都会存在）。
至于什么时候才对延迟链表进行free()，那就是当内存资源紧张时：mimalloc为上层提供一个deferred_free()回调，当free list为空的时候会被调用。而这种操作是在慢路径（generic path）中才存在的，仍保证了快路径的高效。这里的设计思路是任何麻烦事情都应放到慢路径。
那又有问题了，我该如何保证慢路径总会在某时刻被调用到？比如反复的在同一个页内分配释放，但恰好链表不为空，那不是完蛋了？mimalloc针对这种情况保证了慢路径会在固定分配次数后必然调用。
为此mimalloc再次在每个页面切分一个local free list。当我们分配时，会从常规free list分配对象，而释放时，对象会放回到local free list。因此分配用的free list是肯定会在固定操作次数后变为空链表（所以是可预测的）。另外当free list为空时，则直接将local free list切换为free list使用，使得可以继续分配。这种情况仍不需要为快速路径付出任何代价。
Thread free list
mimalloc中的页归属于线程局部的堆，其分配是本地完成的，因此无锁是理所当然的。但是，对于一个对象来说，任意线程都可以释放它。为了避免free()操作持锁，mimalloc再一次为每页面切分thread free list，并且把其他线程释放的对象都使用原子操作放到这个链表中。
同样的，在慢路径中也会收集thread free list并最后切换为free list使用。
这种操作尤其适合非对称的并发负载，也就是一部分线程主要负责分配，另一部分线程主要负责释放。
快速路径
论文没有单独的篇幅来介绍快速路径，这里简单体会一下它有多快：
void* malloc_in_page( page_t* page, size_t size ) {
block_t* block = page->free; // free list
if (block==NULL) return malloc_generic(size); // generic path
page->free = block->next;
page->used++;
return block;
}
分配流程并不使用碰撞指针，只需简单的寻址以及单个判断分支即可完成。
实现
Data structures
上图就是mimalloc设计的堆，通过tlb（thread local data）寻址得到。而堆按照size-class计算下标索引可以得到页。
页和元数据都存放于段中。段的头部存放元数据，因此段中首个页面的大小实际要减去元数据大小。
一般来说，段的大小为\(4MB\)。实际上mimalloc根据对象大小设计了三种页面/段的对应关系：
- small：小于等于\(8KB\)的对象使用，页面大小为\(64KB\)，段中有64个页面。
- large：小于等于\(512KB\)的对象使用，段中只有一个页面。
- huge：大于\(512KB\)的对象使用，段中只有一个页面，段的大小取决于对象大小。
对于large和huge仍然使用段的概念是为了保证代码的一致性，减少special case。
malloc()
上面快速路径的代码展示了已定位到page的情况下的内存分配流程，这里补充一下page寻址。对于小对象（\(\le 1KB\)）来说，可以通过pages_direct寻址：
void* malloc_small( size_t n ) { // 0 < n <= 1024
heap_t* heap = tlb;
page_t* page = heap->pages_direct[(n+7)>>3]; // divide up by 8
return malloc_in_page(page, n);
}
慢路径分配会在后面解释。
free()
与其他分配器相同，free(p)需要获取p相关的元数据。也正是这个理由，mimalloc将元数据放到堆的首部。由于堆是按照\(4MB\)对齐的，因此可以通过位运算得到元数据：
void free( void* p ) {
segment_t* segment = (segment_t*)((uintptr_t)p & ~(4*MB));
if (segment==NULL) return;
page_t* page = &segment->pages[(p - segment) >> segment->page_shift];
block_t* block = (block_t*)p;
if (thread_id() == segment->thread_id) { // local free
block->next = page->local_free;
page->local_free = block;
page->used--;
if (page->used - page->thread_freed == 0) page_free(page);
}
else { // non-local free
atomic_push( &page->thread_free, block );
atomic_incr( &page->thread_freed );
}
}
其中page_shift根据不同页面有不同大小：small page为\(16\)（位移得到\(64KB\)）；large/huge page为\(22\)（位移得到\(4MB\)）。因此对于后者来说，index永远是0。在这种基于地址偏移量的释放算法中，p并不需要记录大小信息。
后面主要的分支是判断是否本地数据。这里需要高效的thread_id()实现，而在大多数平台中，这个操作是足够快的：比如Linux x86-64实现仅需要获取fs寄存器。
正如前面所说的，p可能会放回local_free或者thread_free。对于local free的情况，还会判断页面所有对象已被释放的情况，这里会紧接着对页面执行释放。这种操作完全是可以省略掉的，就是说可以放在慢路径上再去处理，只是这样做会更加高效。
Generic allocation
通用分配流程即前面提到的慢路径，因为它通常是做一些更昂贵的操作。
void* malloc_generic( heap_t* heap, size_t size ) {
deferred_free();
foreach( page in heap->pages[size_class(size)] ) {
page_collect(page);
if (page->used - page->thread_freed == 0) {
page_free(page);
}
else if (page->free != NULL) {
return malloc(size);
}
}
.... // allocate a fresh page and malloc from there
}
void page_collect(page) {
page->free = page->local_free; // move the local free list
page->local_free = NULL;
... // move the thread free list atomically
}
简单来说，慢路径以size-class线性遍历page list中的页面，遍历的过程中顺手释放页面（与上面free()流程的if分支是相同的操作），直到找到任意可复用的对象就返回。实际的实现流程会复杂点，比如页面释放不一定是立刻执行的，可能会留存一些作为缓存；以及释放页面数是有限制的，避免整个函数延迟过高。并且也对for-each做了优化，如果找到了可用的页面，那么下一次的慢路径直接从这个页面开始遍历。
Full list
mimalloc的核心算法已经介绍完了，也在大多数基准测试中表现不错，但仍需要在特殊场合改进：测试发现大量满页（full page）时会引起30%的性能下降，这种情况发生在大量长生命周期的大对象分配上。而满页导致性能下降的原因很直观，就是满页仍然留存在page list中，而慢路径malloc()是需要线性复杂度去遍历的。
一种朴素的解决方案是实现一个full list：当页面分配已满时则将其放入到full list中，当任意对象释放时再放回page list。这种做法能解决性能问题，但是使得线程安全的处理变得复杂。
所以mimalloc再次在堆上新增一个thread delayed free list，里面存放的是非本地释放的对象。也就是说非本地的free()操作，会把对象原子地放入到thread delayed free list中，而在慢路径的分配过程中因为必然是本地操作的，因此可以把这些delayed free的对象都释放掉，并且非满页也可以从full list移动到常规page list中（前面提到，慢路径的调用是有周期性的）。
但前面非本地的free()操作也提过会放到thread free list中，这种情况该如何区分？mimalloc使用tagged pointer的技巧，在thread free list指针的低2位上用了三种标记：
- NORMAL：一般情况，表示放到thread free list。
- DELAYED：页面移动到full list时，打上该标记，表示非本地
free()要放到delayed free list。 - DELAYING：临时标记，表示线程终止时堆仍然可用的特殊情况。
执行delayed free后，总会还原到NORMAL标记。
总结
goto #亮点;