标记-整理算法以o(n)时间复杂度和o(1)辅助空间实现外部碎片治理，通过标记活跃对象并紧凑迁移来释放大块连续空闲空间，兼顾实效性与资源开销平衡。

标记-整理算法（Mark-Compaction）是解决外部碎片的核心手段，它通过“标记活跃对象 + 移动并紧凑排列”两阶段操作，将分散的已用内存块迁移到连续区域，从而释放出大块空闲空间。其算法复杂度需从时间和空间两个维度分析，且与实现细节强相关。

时间复杂度：O(n + m)
其中 n 是整个内存池中所有内存块（含已分配与空闲）的总数，m 是活跃对象数量。

• 标记阶段：需遍历全部内存块或对象引用图，时间开销为 O(n)；
• 整理阶段：需对每个活跃对象执行复制和指针更新，若采用线性紧凑布局（如从低地址开始填入），移动操作本身为 O(m)，但指针修正可能涉及全局引用扫描，最坏达 O(n)；
• 合并空闲区、重建元数据等收尾操作为 O(1) 或 O(k)，k 为空闲块数量，通常远小于 n。
  因此整体时间复杂度为 O(n)，在实际系统中常视为线性可接受，但会带来明显暂停（stop-the-world）开销。

空间复杂度：O(1) 辅助空间（不计移动缓冲）

• 算法本身无需额外分配与内存规模成正比的存储空间；
• 标记位可复用原有内存元数据（如使用 bit-map 或 in-place flag）；
• 指针重定位若依赖句柄表，则句柄表大小为 O(m)，属于必要结构而非临时开销；
• 若系统支持虚拟内存映射（如页表重映射），物理移动可被隐藏，此时整理过程实质是页表调整，空间开销进一步降低。

影响实际性能的关键因素

Delphi 内存管理指导性内容 PDF版

Delphi 内存管理方面的指导性内容，摘录做成了PDF格式的电子书，本书是从一本Delphi书籍中摘录的内存管理那一章内容，不牵扯其它方面的内容，相对具有针对性。内容涉及遍历内存块、共享内存管理器、第三方内存管理器、Delphi内存管理实现框架、用户调用例程的实现等内容。

下载

• 活跃对象密度：若大部分内存已释放，m ≪ n，整理代价显著下降；
• 引用关系复杂度：深度嵌套或跨区域引用越多，指针更新越耗时；
• 是否支持增量式或并发整理：全量标记-整理需暂停应用，而分代+增量实现可摊薄延迟，但增加逻辑复杂度；
• 内存布局局部性：连续访问模式能提升缓存命中率，减少整理过程中的访存延迟。

对比其他碎片整理策略

• 单纯合并空闲块（如 buddy system 中的伙伴合并）：时间复杂度 O(f)，f 为空闲块数，仅处理外部碎片，不改善内存分布密度；
• 引用计数+延迟回收：无整理开销，但无法消除外部碎片，且不适用于循环引用场景；
• 垃圾回收中的复制算法（如 Cheney 算法）：时间复杂度同为 O(m)，但要求双倍空间，空间复杂度升至 O(size_of_used_heap)。

不复杂但容易忽略：标记-整理的价值不在理论最优，而在实效平衡——它用一次可控的线性开销，换来后续大量连续分配的成功率跃升。