概览

当今的关键服务和应用通常具有高度并发性，使用数百个线程。它们还运行在大内存规模下，常常达到数百GB，尤其是在使用大语言模型时。mimalloc 是一个开源、现代、可扩展的内存分配器，可直接替代 malloc 和 free。它相对较小（约12K行代码），具有清晰的内部数据结构，易于构建并集成到其他项目中。它提供了有界的最坏情况分配时间（最多到操作系统原语）、有界的空间开销、低内部碎片，并且几乎完全依赖原子操作来最小化争用。mimalloc 在 GitHub 上可用（在新标签页中打开），拥有超过12K颗星。

mimalloc

在微软研究院（MSR）的 RiSE 小组，我们从事形式化方法、编程语言和软件工程（包括新兴的 agent 系统）的基础研究，特别关注那些可证明正确、安全且高性能的系统。mimalloc 内存分配器最初于2020年设计，作为 RiSE 开发的先进编程语言 Lean（在新标签页中打开）和 Koka（在新标签页中打开）的快速分配器，这两种语言都使用了新颖的编译器引导引用计数（参见 Perceus）。mimalloc 的可扩展设计也被证明在微软的大型服务中表现极为出色。通过与产品团队的紧密合作，mimalloc 显著改善了 Bing 等服务的响应时间。

如今，mimalloc 被广泛应用于微软内外的大型服务和应用程序中。它作为 NoGIL CPython 3.13+ 的分配器，集成到了 Unreal Engine 中，并用于《死亡搁浅》等游戏。该项目在 GitHub 上开源，拥有超过12K颗星。仅其 Rust 封装每天就有超过10万次下载。mimalloc 在广泛场景中都很有效——从小型应用（如 Koka 或 Lean）到内存占用超过500 GiB、拥有数百个线程的大型服务。尽管应用范围如此之广，其代码库仍然紧凑，约12K行 C 代码。

反映其研究起源，mimalloc 强调具有强不变量的清晰内部数据结构，使其比许多工业分配器更容易理解和推理。正如 Fred Brooks 在其名著《人月神话》中已经指出的："展示你的流程图并隐藏你的表格，我仍然会感到困惑。展示你的表格，我就不需要你的流程图了；一切都会显而易见。"因此，mimalloc 已被移植到许多平台——Windows、macOS、Linux、FreeBSD、NetBSD、DragonFly 以及各种游戏主机——并且易于构建和集成到其他项目中。例如，清晰的数据结构使 Sam Gross 等人能够采用 mimalloc 作为 NoGIL CPython 的并发分配器。这种设计也使得在其上实现循环垃圾回收相对直接。

快速路径

与其他可扩展分配器（如 tcmalloc 和 jemalloc）一样，mimalloc 的一个核心设计原则是每个线程维护自己的线程本地堆，我们称之为"theap"。每个 theap 拥有一组 mimalloc "页"，通常为64 KiB。每个 mimalloc 页包含固定大小的块，按大小类组织以减少内部碎片。通过为每个线程提供自己的 theap 和 mimalloc 页集，内存分配和释放通常无需同步即可进行。仅当线程释放由另一个线程分配的块时才需要原子操作。

此外，在实践中，大多数分配都非常小，通常小于1 KiB。对于这样的小分配，mimalloc 提供了一个快速路径，其主要分配函数如下所示：

void * mi_malloc( size_t size ) {
  mi_theap_t * const theap = mi_get_thread_local_theap();
  if (size > MI_MAX_SMALL_SIZE ) return mi_malloc_generic(theap,size); // 慢速通用路径
  const size_t index = (size + sizeof ( void *))/ sizeof ( void *); // 四舍五入大小
  mi_page_t * const page = theap->small_pages[index];
  mi_block_t * const block = page->free; // 空闲列表头部
  if (block == NULL ) return mi_malloc_generic(theap,size); // 慢速通用路径
  page->free = block->next; // 弹出空闲列表
  page->used++;
  return block;
}

通过使用线程本地 theap，我们不需要任何原子操作或线程同步。我们还尽量减少分支数量。特别是，线程本地 theap 永远不会是 NULL，我们用一个所有页都为空的特殊空 theap 来初始化它。这样，我们就不需要单独检查 theap 是否为 NULL。类似地，small_pages 数组中的指针永远不会是 NULL，我们再次使用特殊的空页（其中 page->free==NULL）来避免单独检查。最后，页使用空闲列表而不是单独的 bump pointer 进行初始化，避免了特殊情况，并允许通过简单地从空闲列表中弹出块来进行分配。

在 x64 上，这段代码现在转化为几条指令，只有两个不常见的分支：

mi_malloc:
  movq %rdi , %rsi          ; rsi = size
  movq _mi_theap_default@GOTTPOFF( %rip ), %rax
  movq %fs :( %rax ), %rdi  ; rdi = thread local theap
  cmpq $1024 , %rsi         ; size > MI_MAX_SMALL_SIZE?
  ja .LBB0_generic
  leaq 7 ( %rsi ), %rax     ; 四舍五入到 sizeof(void*)
  andq $-8 , %rax
  movq 232 ( %rdi , %rax ), %rcx ; rcx = heap->small_pages[index]
  movq 8 ( %rcx ), %rax     ; block = rax = page->free
  testq %rax , %rax         ; block == NULL?
  je .LBB0_generic
  movq ( %rax ), %rdx       ; page->free = block->next
  movq %rdx , 8 ( %rcx )
  incw 16 ( %rcx )          ; page->used++
  retq
.LBB0_generic :
  jmp _mi_malloc_generic@PLT ; 尾调用

类似地，mimalloc 为释放块提供了快速路径。在实践中，大多数块由分配该块的同一线程释放。我们可以通过检查当前线程 ID 是否与相应 mimalloc 页中存储的线程 ID 匹配来优化这种情况。如果匹配，我们可以直接将块推送到页的空闲列表上，而无需原子操作或锁：

void mi_free( void * p) {
  mi_page_t * const page = mi_ptr_page(p); // 获取包含 p 的页元数据
  if (page== NULL ) return ;
  if (mi_thread_id() == page->thread_id) { // 我们拥有这个页吗？
    mi_block_t * const block = ( mi_block_t *)p;
    block->next = page->local_free; // 推送到 `local_free` 列表
    page->local_free = block;
    if (--page->used == 0 ) mi_page_free(page); // 整个页都空闲了吗？
  } else {
    mi_free_cross_thread(page, p); // 在另一个线程拥有的页中释放
  }
}

最新 mimalloc v3 中的 mi_ptr_page 函数使用按需分配的整个内存映射来检索页元数据。在早期版本中，这通过对齐技巧更快。然而，在实践中，当全局覆盖 free 时，经常会有无效指针传递给 mi_free。使用单独的地图可以高效地检测这种情况，并在指针无效时返回 NULL。特别是，mi_ptr_page(NULL) == NULL，这通过仅测试 page 是否为 NULL 来避免额外分支。此外，used 计数用于高效检测页中所有块何时已被释放。

当块跨线程释放时，我们进入 mi_free_cross_thread 函数——这是第一个需要原子操作的路径：

void mi_free_cross_thread( mi_page_t * page, mi_block_t * block) {
  mi_block_t * tfree = mi_atomic_load(&page->thread_free); // 线程空闲列表头部
  do {
    block->next = tfree; // 将我们的块推到前面
  } while (!mi_atomic_compare_and_swap(&page->thread_free, &tfree /* 期望值 */ , block /* 新值 */ ))
}

该块可以通过将其推送到页的线程空闲列表上来释放。由于这是多线程的，需要原子比较并交换操作来原子地推送块。尽管如此，在现代硬件上，当无争用时，此类操作是高效的，因为它们的操作与缓存一致性协议（MOESI）集成在一起。

视频系列

再思考

一个与 Sinead Bovell 合作的视频系列，围绕每个人都在问的关于 AI 的问题展开。借助来自微软各地的专家声音，我们解析了这项快速变化的技术所带来的紧张与承诺，探索正在演变的内容以及可能的未来。

探索系列（在新标签页中打开）

空闲列表混乱

每个页有三个空闲列表：用于分配的空闲列表、用于释放块的 local_free 列表，以及用于跨线程释放的块的 thread_free（原子）列表。这保证了在固定次数的分配后，空闲列表会耗尽，确保我们偶尔会走较慢的通用分配路径。这也用于通过将线程本地和本地空闲列表移回主空闲列表来清理空闲列表。（注意：实际实现需要更多小心来处理拥有线程不再分配或长时间被阻塞的情况。）

因此，mimalloc 每个（64 KiB）mimalloc 页有三个空闲列表，这实际上意味着一个程序可以轻松拥有数千个空闲列表。这对 mimalloc 的可扩展性和缓存局部性至关重要。

高度平衡树

随机化树

对于这种设计，我们从随机化算法中汲取了灵感。例如，为了平衡二叉树，我们可以使用基于权重或深度的智能策略，并执行特定的旋转来保持平衡。这类算法通常相当复杂。然而，我们也可以简化过程，在插入时随机决定分裂，而纯粹靠概率，我们最终也能得到足够平衡的树。

类似地，许多多线程分配器依赖复杂的并发数据结构来同步对共享空闲列表的访问。相比之下，mimalloc 使用每页的线程空闲列表，任何线程都可以使用简单的原子比较并交换来推送块。因为有数千个这样的列表，多个线程同时向同一页释放块的概率很低。因此，大多数推送操作都是无争用的原子更新。

通过将这些列表按每64 KiB mimalloc 页组织，缓存局部性得到改善，因为分配倾向于停留在同一页内直到该页满，而不管其他页中释放的对象如何。相比之下，考虑每个线程或进程只有一个空闲列表的设计。当在释放相同大小的对象的同时分配新结构时——这是树变换等工作负载中的常见模式——分配可能会重用散布在内存各处的最近释放的对象，导致局部性降低。

线程之间的共享

可扩展性和线程间高效内存共享之间存在根本性的紧张关系。为了最优地扩展，我们会给每个线程对其自己页的独占所有权，以最小化任何线程同步。另一方面，这可能导致内存浪费：假设一个线程有大量空闲块，而另一个线程需要分配该大小的块——如果无法共享或窃取这些页，我们就需要分配新的内存。在另一个极端，我们可以通过单个锁在所有线程之间共享所有页：现在内存使用是最优的，但我们不再具有可扩展性。

以下基准测试结果说明了这种紧张关系：

1.1x 提交，56 GiB 总计 | 4x 提交，262 GiB 总计 | 1.3x 提交，262 GiB 总计

该基准测试使用 Windows 线程池（约800个活动线程）在固定时间内运行许多任务。任务在分配、释放和短暂阻塞期之间交替，模拟典型的服务工作负载。在图中，蓝线代表总活跃数据，而红线代表分配器提交的总内存。理想情况是红线尽可能接近蓝线。第一个图几乎就是这种情况，它使用了标准系统分配器：结束时提交的内存仅比活跃数据多1.1倍——一个极好的结果！然而，在基准测试期间，它总共只分配了56 GiB 数据。

相比之下，第二个图中的另一个高度并发分配器在基准测试期间能够分配262 GiB——几乎是4倍。然而，它提交的内存也比活跃数据多4倍。在具有更大内存占用的实际工作负载中，这样的比率很快就会变得不可接受。这里我们看到标准分配器扩展性不佳，但显示了更好的跨线程内存共享。

最后一个图显示了最新的 mimalloc 分配器。与第二个分配器一样，它在基准测试期间分配了262 GiB，同时将提交内存减少到活跃数据的1.3倍，实现了可扩展性和线程间高效内存共享。

类似于现代线程池实现中的工作窃取，mimalloc 使用一种"页窃取"技术，允许线程在不进行昂贵的跨线程同步的情况下获取页的所有权。这些改进是与微软 Azure Cosmos DB 团队密切合作完成的。精确描述超出了本博客的范围，但我们很快将发布一份技术报告——敬请期待。

（在新标签页中打开）

文章《mimalloc：面向现代时代的新型高性能可扩展内存分配器》最初发表于微软研究院。