mimalloc：面向现代时代的新型高性能可扩展内存分配器

# mimalloc: 面向现代时代的新型高性能可伸缩内存分配器 - 微软研究院 来源：https://www.microsoft.com/en-us/research/blog/mimalloc-a-high-performance-scalable-memory-allocator-for-the-modern-era/ 紫色到蓝色渐变背景上，三个白色线条图标——带有代码括号的显示器、互锁齿轮和速度表——显示在带有细微纹理图案的背景下。## 一目了然 - 当今的关键服务和应用通常高度并发，使用数百个线程。它们还运行在大型内存规模上，通常达到数百GB，尤其是在使用大型语言模型时。 - mimalloc 是一个开源、现代、可伸缩的内存分配器，可即插即用地替换 malloc 和 free。它相对较小（约 12K 行代码），具有清晰的内部数据结构，易于构建并集成到其他项目中。它提供了有界的最坏情况分配时间（最多到操作系统原语）、有界的空间开销、低内部碎片，并通过几乎完全依赖原子操作来最小化争用。 - mimalloc 在 GitHub (opens in new tab) (https://github.com/microsoft/mimalloc) 上可用，并拥有超过 12K 颗星。 在微软研究院 (MSR) 的 RiSE (opens in new tab) (https://www.microsoft.com/en-us/research/group/research-software-engineering-rise/) 团队，我们进行形式化方法、编程语言和软件工程（包括新兴的智能体系统）的基础研究，特别关注可以证明正确、安全和高性能的系统。mimalloc 内存分配器最初于 2020 年设计，作为 RiSE 开发的先进 Lean (opens in new tab) (http://leanprover.github.io/) 和 Koka (opens in new tab) (https://koka-lang.github.io/koka/doc/book.html) 编程语言的快速分配器，这两种语言都使用新颖的编译器引导引用计数（参见 *Perceus (https://www.microsoft.com/en-us/research/wp-content/uploads/2021/06/perceus-pldi21.pdf)* ）。 mimalloc 的可伸缩设计也已被证明在微软的大型服务中表现出色。通过与产品团队的密切合作，mimalloc 显著改善了 Bing 等服务的响应时间。如今，mimalloc 已广泛应用于微软内外的各种大型服务和应用程序。它用作 NoGIL CPython 3.13+ 的分配器，集成到 Unreal Engine 中，并用于诸如 *Death Stranding* 等游戏。该项目在 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 指针进行初始化，从而避免了特殊情况，并允许通过简单地从空闲链表弹出块来进行分配。在 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 ; round to 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 ; tailcall `` 类似地，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`，通过只测试页是否为 `NULL` 来避免额外分支。此外，用于计数来有效检测页中所有块何时被释放。 当块跨线程释放时，我们进入 `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）集成在一起。 ## 焦点：微软研究通讯 [](https://info.microsoft.com/ww-landing-microsoft-research-newsletter.html) ## 微软研究通讯 与微软的研究社区保持联系。 ## 空闲链表混乱 每个页有三个空闲链表：用于分配的空闲链表、用于释放块的 `local_free` 链表，以及用于跨线程释放块的 `thread_free`（原子）链表。这保证了在固定数量的分配之后，空闲链表会被耗尽，确保我们偶尔会走较慢的通用分配路径。这也用于清理空闲链表，将线程本地和本地空闲链表移回到主空闲链表。（注意：实际实现需要更多处理，以应对拥有线程从未再次分配或长时间阻塞的情况。） 因此，mimalloc 在每个（64 KiB）mimalloc 页中有三个空闲链表，这实际上意味着程序可以轻松拥有数千个空闲链表。这对于 mimalloc 的可伸缩性和缓存局部性至关重要。 对于这种设计，我们从随机化算法中汲取了灵感。例如，为了平衡二叉搜索树，我们可以使用基于权重或深度的巧妙策略，并执行特定的旋转以保持平衡。此类算法通常相当复杂。然而，我们也可以简化过程，在插入时随机决定分割，并且纯粹出于偶然，我们最终也会得到足够平衡的树。 类似地，许多多线程分配器依赖复杂的并发数据结构来同步对共享空闲链表的访问。相比之下，mimalloc 使用每页线程空闲链表，任何线程都可以使用简单的原子比较并交换来推送块。因为有数千个这样的链表，多个线程同时释放块到同一页的概率很低。结果，大多数推送操作是无争用的原子更新。通过按每 64 KiB mimalloc 页组织这些链表，缓存局部性得到改善，因为分配倾向于停留在同一个页中直到它被填满，而不管其他页中释放的对象如何。 相比之下，考虑一个每个线程或进程只有一个空闲链表的设计。当分配新结构同时释放相同大小的对象时——这是树转换等工作负载中的常见模式——分配可能会重用散布在内存各处的最近释放的对象，导致局部性降低。 ## 线程间的共享 可伸缩性和线程间高效内存共享之间存在根本性的张力。为了最佳伸缩，我们会给每个线程对其自己页的独占所有权，以最小化任何线程同步。另一方面，这可能导致内存浪费：假设一个线程有大量空闲块，而另一个线程需要分配该大小的块——如果没有能力共享或窃取那些页，我们就需要分配新的内存。在另一个极端，我们可以通过单个锁在所有线程之间共享所有页：此时内存使用最优，但我们不再具有可伸缩性。以下基准测试结果说明了这种张力： 该基准测试在固定时间内运行许多任务，使用 Windows 线程池，大约有 800 个活动线程。这些任务在分配、释放和短暂的阻塞期之间交替，模拟典型的服务工作负载。在图中，蓝线代表总活动数据，红线代表分配器提交的总内存。理想情况是红线尽可能接近蓝线。第一张图几乎是这种情况，它使用标准系统分配器：最终提交的内存仅比活动数据多 1.1 倍——很棒的结果！然而，在基准测试期间，它总共只分配了 56 GiB 数据。 与第二张图中的另一个高度并发分配器对比，该分配器在基准测试期间分配了 262 GiB——几乎是 4 倍。然而，它也提交了比活动数据多 4 倍的内存。在具有更大内存占用的实际工作负载中，这种比率很快就会变得不可接受。在这里我们看到标准分配器没有那么好地伸缩，但显示了更好的跨线程内存共享。 最后一张图显示了最新的 mimalloc 分配器。与第二个分配器类似，它在基准测试期间分配了 262 GiB，同时将提交的内存减少到活动数据的 1.3 倍，实现了可伸缩性和线程间高效内存共享。类似于现代线程池实现中的工作窃取，mimalloc 使用“页窃取”技术，允许线程获取页的所有权，而无需昂贵的跨线程同步。 这些改进是与微软 Azure Cosmos DB 团队密切合作完成的。精确描述超出了本博客的范围，但我们很快将发布一份技术报告——敬请期待。