经典的内存分配问题关注如何在内存中放置不同大小的对象，同时最小化所谓的内存最高水位（high-water mark）。自 1970 年代初以来已知，任何确定性在线分配器的最优竞争比都是 $\Theta(\log M)$，其中 $M$ 表示请求序列的最高水位体积。
本文首先指出，许多实际使用的分配器通过采用略有不同的模型规避了 1971 年的下界。这类分配器允许 $k$-聚合请求碎片化：只要同时存在的碎片数的全局最大值不超过同时请求数全局最大值的 $k$ 倍，分配器即可将请求拆分为多个碎片。
核心问题是：请求碎片化是否从根本上改变了内存分配问题？如果改变，影响程度如何？
主要发现出人意料。即使仅使用 $k = 1 + o(1)$ 的碎片化，原本在经典模型下为 $\Theta(\log M)$ 的最优竞争比会骤降至 $\Theta(\log \log M)$。该结果对确定性和随机化算法均成立，并给出了匹配的上界和下界，证明了该界限是紧的。
点评：本文通过引入 $k$-聚合碎片化概念，展示了即使极小的碎片容忍度也能显著提升在线内存分配的竞争性能。这一发现对设计更高效的实际分配器具有重要启示，值得进一步探索碎片化策略在不同系统负载下的实际表现。