Home [论文阅读] Mimalloc: Free List Sharding in Action
Post
Cancel

[论文阅读] Mimalloc: Free List Sharding in Action

粗略看了西半球最快内存分配器mimalloc的论文和源码,这里简单做点笔记。本文是论文阅读篇。

亮点

论文Mimalloc: Free List Sharding in Action提到mimalloc跑得快的设计要点有三处:

  1. 使用三种页级本地(完全无锁)链表并实现分片,提高局部性和避免竞争。
  2. 高度调优的快速路径,路径尽可能短且少分支。
  3. 可预测的周期性维护操作(temporal cadence),可以用于批量处理(比如延迟释放)。

这些策略使得mimalloc分别比高性能的tcmalloc和jemalloc还要快7%和14%。

设计动机

mimalloc当初是为了支持Lean和Koka语言的运行时而产生的,它们有这两种负载特征:

  • 都是函数式编程语言,需要频繁分配短周期、小尺寸的对象(并且jemalloc在这里表现不佳)。
  • 运行时使用引用计数来管理内存,需要提供延迟释放的特性来避免大型数据结构引起的停顿。

这也暗示了mimalloc在这种负载下可能有更好的性能表现。

链表分片

Allocation free list

论文指出许多分配器是基于size-class(按大小划分)的方式来实现single free list,这种做法并没有足够好的空间局部性。

single-free-list

比如上图(A)位于一整块的堆空间,在free list上新分配一个包含3个元素的链表p后如图(B)所示,这种支离破碎的现象并不罕见。

free-list-sharding

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

heap

上图就是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 #亮点;

This post is licensed under CC BY 4.0 by the author.
Contents