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

mimalloc 是微软研究院（Microsoft Research）RiSE 团队开发的一款开源、现代、可扩展的内存分配器，旨在作为传统 malloc 和 free 的即插即用替代品。其代码库相对精简，约 1.2 万行 C 代码，内部数据结构清晰，易于构建和集成到其他项目中。mimalloc 提供了有界的最坏情况分配时间（上限取决于操作系统原语）、有界的空间开销、低内部碎片，并且几乎完全依赖原子操作来最小化竞争。

mimalloc 最初于 2020 年设计，用于支持 RiSE 团队开发的前沿编程语言 Lean 和 Koka，这两种语言均采用新颖的编译器引导引用计数（参见 Perceus）。其可扩展设计在微软内部的大规模服务中也表现出色。通过与产品团队的紧密合作，mimalloc 显著提升了 Bing 等服务的响应时间。如今，mimalloc 已被广泛应用于微软内外的大型服务和应用程序，例如作为 NoGIL CPython 3.13+ 的分配器，集成到 Unreal Engine 中，并用于《死亡搁浅》等游戏。该项目在 GitHub 上开源，拥有超过 12,000 颗星。其 Rust 封装版本每日下载量超过 10 万次。

mimalloc 的核心理念是每个线程维护自己的线程本地堆（theap），每个 theap 拥有一组 mimalloc“页面”，页面通常为 64 KiB。每个页面包含固定大小的块，按大小类别组织以减少内部碎片。通过为每个线程分配独立的 theap 和页面，大多数内存分配和释放无需同步，仅当线程释放由另一个线程分配的块时才需要原子操作。

对于小型分配（通常小于 1 KiB），mimalloc 提供了快速路径。例如，mi_malloc 函数首先检查大小是否超过阈值，若未超过则直接从线程本地页面的空闲链表中弹出块，无需原子操作。在 x64 架构上，该路径仅包含少数几条指令和两个不常见分支。类似地，mimalloc 也为释放操作提供了快速路径：如果释放的块属于当前线程，可直接将其推入页面的 local_free 列表，无需原子操作；否则进入 mi_free_cross_thread，使用原子比较并交换（CAS）将块推入页面的 thread_free 列表。由于存在大量页面，跨线程释放操作通常不会发生竞争。

每个页面维护三个空闲链表：free 列表用于分配、local_free 列表用于同线程释放、thread_free 列表（原子操作）用于跨线程释放。这种设计保证了在固定次数的分配后空闲链表会耗尽，从而偶尔触发较慢的通用分配路径，用于清理空闲链表。由于每个 64 KiB 页面都拥有这三个链表，程序可能拥有数千个空闲链表，这对可扩展性和缓存局部性至关重要。

mimalloc 的设计灵感来自随机化算法。例如，平衡二叉树可以通过随机分割来达到足够平衡，而无需复杂的旋转操作。类似地，mimalloc 不依赖复杂并发数据结构，而是为每个页面设置一个线程空闲链表，任何线程都可通过简单原子 CAS 推入块。由于链表数量众多，多个线程同时向同一页面释放块的概率很低，因此大多数推入操作都是无竞争的原子更新。通过将链表组织在 64 KiB 页面内，分配倾向于在同一页面内进行，直到页面满为止，从而改善缓存局部性。相比之下，如果每个线程或进程只有一个空闲链表，分配可能重用散布在各处的最近释放块，导致局部性下降。

在可扩展性和内存高效共享之间存在基本矛盾。为达到最佳可扩展性，应让每个线程独占其页面以减少同步；但这可能导致内存浪费，例如一个线程拥有大量空闲块而另一个线程需要相同大小的块时，无法共享或窃取页面，必须分配新内存。反之，如果所有页面在所有线程间通过单一锁共享，内存利用率最优但可扩展性丧失。基准测试显示，标准 Windows 分配器内存占用接近理想（仅多 1.1 倍），但总分配量仅 56 GiB；而另一个高度并发的分配器在分配 262 GiB 数据的同时，提交的内存是活跃数据的 4 倍，这在大内存工作负载中不可接受。mimalloc 在两者之间取得了平衡，通过大量页面和原子操作实现了接近线性的可扩展性，同时保持较低的内存开销。

mimalloc 已移植到多个平台，包括 Windows、macOS、Linux、FreeBSD、NetBSD、DragonFly 以及多种游戏主机。其清晰的数据结构使得 Sam Gross 等人能够顺利将其采用为 NoGIL CPython 的并发分配器，也使得在其上实现循环垃圾回收相对直接。mimalloc 有效适用于从 Koka 或 Lean 等小型应用到内存超过 500 GiB、数百线程的大型服务等广泛场景。