采用内存局部性分配有什么好处？

内存分配时的局部性分配（Locality of Allocation）是指将相关的内存对象分配在相邻或相近的内存区域中。这种分配策略在现代计算机系统中具有显著的好处，主要体现在以下几个方面：

---

1. 提高缓存命中率

现代计算机系统依赖于多级缓存（L1、L2、L3）来加速内存访问。局部性分配可以确保相关的对象在物理内存中相邻，从而增加这些对象被加载到同一缓存行的概率。这带来了以下好处：

• 减少缓存未命中（Cache Miss）：缓存未命中会导致处理器从主存中加载数据，显著增加访问延迟。局部性分配可以减少这种情况的发生。

• 提高缓存利用率：相邻的对象更可能被同时使用，缓存行中的数据可以被充分利用，减少缓存空间的浪费。

• L1 ->  L2 ->  L3 ->  内存 ->  磁盘 的访问速度由高到低，图示如下：

---

2. 减少内存碎片

局部性分配通过将对象集中在特定的内存区域（如内存页或段）中，可以减少内存碎片的产生：

• 内部碎片减少：由于对象被集中分配，内存页的利用率更高，减少了因分配大小不匹配导致的内存浪费。

• 外部碎片减少：局部性分配减少了内存中分散的小块空闲区域，降低了外部碎片的发生概率。

• 两者区别如下

• 区别点	内部碎片	外部碎片
  定义	已分配给进程但未被利用，存在于分配给进程的内存块内部的空闲内存	系统中存在的分散、不连续的小空闲内存块，难以满足大进程内存分配需求
  产生位置	进程已分配的内存空间内部	已分配内存块之间的空闲内存区域
  产生原因	1. 固定分区分配中，分区大小大于进程需求 2. 页式存储中，进程最后一页不满一页 3. 分配算法导致分配的内存块大于实际需求	1. 动态分区分配时，进程不断创建和撤销，产生不连续的空闲分区 2. 内存回收不及时或不合理，未合并相邻空闲块
  可利用性	在所属进程释放内存前，无法被其他进程利用	理论上若能合并成大的连续空间可被利用，但实际因不连续难以利用
  对系统的影响	主要降低内存利用率，可能导致系统在有总空间时仍无法满足新进程需求	降低内存利用率和内存分配效率，限制进程并发执行，影响系统性能
  解决方式	1. 调整内存分配单位大小（如采用更小页面尺寸） 2. 采用更灵活的分配策略，按进程实际需求分配	1. 内存紧缩（移动已分配内存块合并空闲区） 2. 改进内存分配和回收算法（如伙伴系统算法、最佳适应算法）

内存部碎片如图所示

外部碎片如图所示：

3. 提升访问性能

局部性分配可以优化内存访问模式，带来以下性能提升：

• 空间局部性（Spatial Locality）：相邻的对象更可能被连续访问，减少了内存访问的随机性，提高了内存带宽的利用率。

• 时间局部性（Temporal Locality）：频繁访问的对象集中在同一区域，减少了内存访问的延迟。

---

4. 优化多线程性能

在多线程环境中，局部性分配可以减少线程间的竞争和缓存一致性开销：

• 减少伪共享（False Sharing）：当多个线程访问同一缓存行中的不同数据时，会导致缓存行在不同核心之间频繁无效化。局部性分配可以将不同线程的数据分配到不同的缓存行中，减少伪共享。

• 降低锁争用：通过将线程本地的对象分配在相邻区域，可以减少线程间的锁争用，提高并发性能。

---

5. 支持延迟释放和垃圾回收

局部性分配可以与延迟释放和垃圾回收机制结合，带来以下好处：

• 批量释放：将相关的对象集中分配，可以在释放时批量处理，减少释放操作的频率和开销。

• 垃圾回收效率提升：在垃圾回收过程中，局部性分配可以减少内存扫描的范围，提高回收效率。

---

6. 简化内存管理

局部性分配通过将对象集中在特定的内存区域中，简化了内存管理的复杂性：

• 减少元数据开销：局部性分配可以减少内存管理数据结构（如空闲列表、位图等）的规模，降低元数据开销。

• 提高分配速度：由于对象集中在特定区域，分配器可以更快地找到合适的内存块，减少分配时间。

---

7. 支持特定应用场景

局部性分配特别适合以下应用场景：

• 函数式编程语言：函数式语言通常会产生大量短期小对象，局部性分配可以减少内存碎片和提高缓存命中率。

• 高性能计算：在科学计算和图形处理中，局部性分配可以优化数据访问模式，提高计算效率。

• 实时系统：局部性分配可以减少内存访问的不可预测性，满足实时系统的低延迟需求。

---

总结

局部性分配通过提高缓存命中率、减少内存碎片、优化访问模式、提升多线程性能、支持延迟释放和简化内存管理，显著提升了内存分配器的性能和效率。而大名鼎鼎的 mimalloc 分片空闲列表的设计，看、就充分利用了局部性分配的优势，在多种基准测试中表现优异。