Bing速度背后的12000行秘密：mimalloc如何打破内存分配器的权衡困境

内存分配在系统性能中常常不为人注意。但对于微软的必应团队来说，切换到公司自家研究部门构建的自定义分配器直接转化为更快的响应时间。这个分配器，即mimalloc，是微软研究院RiSE团队一篇新博客文章的主题，文章解释了使其能够从单线程编程语言运行时扩展到500 GiB云服务的设计决策。

仅仅12000行C代码，mimalloc刻意保持紧凑。它的真正创新在于如何规避一个经典的系统权衡：是在多个线程之间进行扩展，还是让内存使用量尽可能接近应用程序的实际需求。这篇发表在微软研究院网站上的博客，以异乎寻常的技术深度深入剖析了其架构，包括快速路径的代码片段，以及与Azure Cosmos DB团队合作开发的“页窃取”机制。

快速路径：分支少，无原子操作

mimalloc的核心洞察是，大多数分配都是小型的且属于线程本地。每个线程都有自己的线程本地堆，即“theap”，它拥有一组64 KiB的“mimalloc页”。每个页包含单一大小类别的块。要分配一个块，线程只需从空闲列表中弹出它，无需锁，无需原子操作。该博客提供了x64上快速路径的汇编输出：七条指令，只有两个罕见分支（一个用于超大分配，一个用于空页）。

这种分支最小化源于一种精心设计的初始化策略：线程本地theap指针永不为NULL，并且small_pages数组中的所有条目都指向预初始化的空页（其空闲列表为NULL）。正如作者所指出的，这消除了大多数分配器所需的两个条件检查，将常见情况转换为一条直行指令序列。

每页三个空闲列表：随机化灵感

mimalloc与其同类产品最大的不同在于其空闲列表设计。每个mimalloc页维护三个空闲列表：用于分配的主free列表，用于由拥有该页的线程释放的块的local_free列表，以及用于由其他线程释放的块的thread_free列表（原子操作）。一个程序可能轻易拥有数千个正在运行的空闲列表。

博客明确将此设计与随机化算法联系起来。正如treap使用随机分割来保持树平衡而无需复杂的旋转一样，mimalloc依赖于大数定律：拥有数千个按页划分的原子列表，两个线程同时尝试释放到同一页的概率很低。大多数compare-and-swap操作是无竞争的且开销低廉。“纯粹靠运气，我们最终也能得到平衡得足够的树，”作者写道，进一步延伸这个类比。

这种按页排列的方式还提高了缓存局部性。由于分配倾向于在同一个页内进行直到该页满，最近释放的块很可能与线程已在使用的缓存行相同，这与每个大小类别只有一个空闲列表的设计形成鲜明对比，后者可能将块分散到整个内存中。

分配器的三重困境：展示权衡的基准测试

该文章包含一个使这种权衡可见的基准测试。使用具有大约800个活动线程的Windows线程池，该测试运行一种交替进行分配、释放和短暂阻塞的工作负载，模拟现代云服务。比较了三种分配器：

• 标准系统分配器：内存共享出色（仅占用实时数据的1.1倍），但在测试期间仅分配了56 GB。它没有扩展性。
• 一个竞争性并发分配器：分配了262 GiB，几乎是4倍，但占用了实时数据4倍的内存。在规模上，这个比例变得不可接受。
• mimalloc：分配了相同的262 GiB，同时将占用的内存保持在仅实时数据的1.3倍。红线（已占用内存）紧贴蓝线（实时数据）。

该博客将这一突破归功于“页窃取”机制，这是与Azure Cosmos DB团队共同开发的技术，允许线程在没有昂贵的跨线程同步的情况下获得页的所有权。作者承诺将发布一份包含精确描述的技术报告，但基准测试结果已经表明，mimalloc实现了长期被认为不可能的事情：在不导致内存爆炸的情况下扩展吞吐量。

从Lean到必应再到CPython

最初于2020年设计用于支持Lean和Koka编程语言，这两种语言都依赖于编译器引导的引用计数，mimalloc现在已被微软研究院以外的领域广泛采用。必应将其用于生产环境，直接贡献于更快的响应时间。在微软之外，它是CPython 3.13+无GIL版本的内存分配器，已集成到Unreal Engine中，并用于像《死亡搁浅》这样的游戏。仅其Rust包装器每天就有超过10万次下载。

该项目托管在GitHub上，已获得超过12000颗星。支持Windows、macOS、Linux、FreeBSD、NetBSD、DragonFly BSD以及各种游戏机的移植版本。该博客强调，其清晰的内部数据结构，借用Fred Brooks的“表格，而非流程图”哲学，使得外部贡献者比许多业界分配器更容易进行移植和定制。

这对系统构建者意味着什么

对于构建高并发服务的团队，尤其是那些使用内存占用达数百GB的大型语言模型的团队，mimalloc有界的最坏情况分配时间和低内部碎片化提供了一条无需重写应用程序代码即可获得更好性能的具体路径。它是malloc和free的直接替代品。

更深刻的教训是，这个分配器之所以能扩展，并非因为革命性的数据结构，而是因为一个深思熟虑的统计赌注：将协调成本分散到数千个微小列表中，冲突的概率就会崩溃。在每台服务器线程数持续增长、大语言模型推理常常消耗数百GB内存的时代，这个赌注正在微软内外的大规模生产环境中得到回报。