一、简介

mimalloc 是微软研究院在 2019 年发表并开源的一个新的内存分配库：

  • 代码量少，核心代码行数 <3500 行

    • tcmalloc ~20k LOC
    • jemalloc ~25k LOC

  • 性能大大优于市面上其他 memory allocator

    • 比 tcmalloc 快 7%
    • 比 jemalloc 快 14%

  • 三个局部存储的分片的 free list

    • 增加数据访问局部性 (locality)
    • 减少访问竞争
    • 支持性能优化到极致的 alloc 和 free 的 fast path
    • 引入一个时间节奏（temporal cadence），使分配器适时离开 fast path 来处理一些维护性的任务

二、内存分配和释放机制

mimalloc 的内存分配释放机制要点：

  • 极致的空闲列表分片
  • 分配和释放的主路径经过深度优化，其他的情况都被延迟到 generic 方法中进行。
  • 没有使用锁，所有的多线程数据竞争都使用原子操作来解决。最坏情况下有上界，元数据约占 0.2%，实际分配空间浪费不超过 16.7%。

1. 空闲列表分片机制

  • 空闲列表

    • 为每个 mimalloc 页（一般是 64KiB）维护一个空闲列表，而不是像传统机制那样为整个 size class（如 2n2^n）维护一个空闲列表。
    • 只要当前页的空闲列表不为空，malloc 就可以一直分配本页中的内存，而不用管堆中是不是有其他新 free 的区域
    • 这样可以提高新分配内存的空间局部性，使大部分新分配的地址都处在同一页中，提高 L2 Cache 的命中率

高性能内存分配库 mimalloc 简介 - 图1

  • 本地空闲列表

    • 释放大对象时，可能会引起连锁反应递归地释放一大堆对象，造成最坏情况下的 free 时长不可控。因此需要限制 free 的个数，将后续要 free 的对象挂在一个列表上，等后续内存紧张时再释放（malloc_generic 中）。但需要一个机制保证 malloc_generic 每隔一段时间就能被调用到。

    • 为每个 mimalloc 页除了维护一个空闲列表外，再增加一个本地空闲列表（local-free list），当空闲列表被分配完后，将调用 malloc_generic，malloc_generic 会用原子操作将本地空闲列表转成新的空闲列表

      1. page->free = page->local_free; 
      2. page->local_free = NULL;

    • 因为空闲列表不会增长，经过一段时间总会被分配完，此机制相当于引入一个时间节奏，使 malloc_generic 的分配代码总是能够定期地被执行，此机制可以用来平摊一些耗时操作的开销：

      • 延后执行的引用计数减导致的 free
      • 维持一个稳定的心跳机制
      • 回收线程释放列表中的内存

  • 线程释放列表

    • 在 mimalloc 中，mimalloc 页属于一个 “线程局部” 的堆，所有本线程的内存分配都从这个线程局部堆上分配，不需要锁。

    • 但任何线程都能 free 本线程分配的内存。为保证本线程 free 本线程局部堆上的数据不需要锁，将其他线程释放的内存放到一个独立的线程释放列表（thread-free list）中，也能减少 malloc 中 fast path 上的原子操作

      • 其他线程释放本线程分配的空间时，会调用 atomic_push 方法，将对应的地址原子地放到本线程的释放列表中：
        1. void atomic_push( block_t** list, block_t* block ) {
        2. do { block->next = *list; }
        3. while (!atomic_compare_and_swap(list, block, block->next));
        4. }

        各个线程释放内存时操作的对象被分片到各个 mimalloc 页上，减少了线程间的竞争

    • 每隔一段时间线程释放列表会被原子地移动到空闲列表中，达到批量处理远程 free 的效果

      1. tfree = atomic_swap( &page->thread_free, NULL );
      2. append( page->free, tfree );
      3. 复制代码

2. 具体实现

  • malloc 实现
    1. void* malloc_small( size_t n ) { // 0 < n <= 1024
    2.   heap_t* heap = tlb;           //线程局部存储指针指向的线程局部堆
    3.   page_t* page = heap->pages_direct[(n+7)>>3]; // divide up by 8
    4.   block_t* block = page->free;  //空闲列表
    5.   if (block==NULL) return malloc_generic(heap,n); // slow path
    6.   page->free = block->next;     //移动空闲列表指针
    7.   page->used++;
    8.   return block;
    9. }
    10. 复制代码


高性能内存分配库 mimalloc 简介 - 图2

  1. //slow path，mimalloc机制保证此方法会隔一段时间被调到
  2. void* malloc_generic( heap_t* heap, size_t size ) {
  3.     deferred_free();        // 调用用户自定义的方法
  4.     // 遍历现有page
  5.     foreach( page in heap->pages[size_class(size)] ) {
  6.         page_collect(page); //回收页内空间
  7.         if (page->used - page->thread_freed == 0) {
  8.           page_free(page);
  9.         }
  10.         else if (page->free != NULL) {
  11.           return malloc(size);
  12.         }
  13.     }
  14.     .... // 现有页中无空闲空间，重新分配一页，并从新页中分配空间
  15. }
  17. void page_collect(page) {
  18.     page->free = page->local_free; // 将空闲列表设置为本地空闲列表
  19.     page->local_free = NULL;       // 本地空闲列表置空
  20.     ... // 原子地处理 线程释放 列表
  21. }
  22. 复制代码

  • free 的实现

    1. void free( void* p ) {
    2. //找到p所在的segment
    3. segment_t* segment = (segment_t*)((uintptr_t)p & ~(4*MB));
    4. if (segment==NULL) return;
    5. //找到p所在的page
    6. page_t* page = &segment->pages[(p - segment) >> segment->page_shift];
    7. block_t* block = (block_t*)p;
    9. if (thread_id() == segment->thread_id) { // free的是本线程分配的内存（local free）
    10.   block->next = page->local_free;
    11.   page->local_free = block;
    12.   page->used--;
    13.   if (page->used - page->thread_freed == 0) page_free(page);
    14. }
    15. else { // free的是其他线程分配的内存（non-local free）
    16.   atomic_push( &page->thread_free, block);
    17.   atomic_incr( &page->thread_freed );
    18. }
    19. }
    20. 复制代码

参考资料

高性能内存分配库 mimalloc 简介 - 图3
https://juejin.cn/post/6854573214727831559