为什么不对主内存使用日志结构分配器
Why do not use log-structured allocator for main memory
刚刚学习了日志结构文件系统。我很困惑为什么不使用日志结构作为主内存分配器。它可以显着减少碎片。
日志结构文件系统使用顺序写入循环日志来持久保存文件系统数据，并且通常以完全相同的方式处理更新。在某些时候，日志结构的文件系统必须回收未使用的space（日志中的过时条目）以使其可用于将来的写入。在简单的实现中，只要文件系统用完磁盘space.
，就可以通过重写日志并跳过进程中未使用的条目来回收未使用的条目。
本地代码的内存分配器可以做类似的事情。一个简单的实现将需要一大块内存和一个需要为分配过程递增的下一个指针。释放需要将条目标记为已释放（可以是条目中的标志或专用空闲列表）或者需要以其他方式限制释放（按先进先出顺序释放，只有整个分配 space 可以解除分配）。
事实上，这种分配器被称为“线性分配器”并且今天仍在使用。一个优点是分配性能，另一个优点是释放的简单性和效率，如果它发生在 FIFO 顺序或影响整个分配 space。堆栈分配是一个突出的例子。 JVM 通常使用线性分配器进行对象分配。 Apache 网络服务器使用它的一个变体来处理每个请求的内存分配。
使用线性分配器作为通用分配器存在更多问题，因为 space 回收困难。要回收 space，将条目标记为空闲是不够的，因为这可能导致高度碎片化并破坏线性分配的优势（仅需为实际分配任务递增指针）。因此，与文件系统类似，分配 space 必须被压缩，以便它只包含分配的条目，而空闲 space 可用于线性分配。压缩需要四处移动分配的条目 - 一个更改并使其先前已知地址无效的过程。在本机代码中，分配器不知道对已分配条目（存储为指针的地址）的引用位置。必须修补现有引用以使分配器操作对调用者透明，这对于像 malloc.
这样的通用分配器来说是不可行的
为什么不可行？更新现有参考需要执行以下步骤：
- 挂起所有线程以停止所有分配条目修改器（除非使用所谓的“写屏障”）
- 扫描寄存器、堆栈和堆以查找指向已移动对象的指针
- 指针的确切位置未知，与引用匹配的数据可能会被误认为是引用（在像 Boehm 这样的保守 GC 的情况下不是问题，例如，它不执行复制。误报只会延迟集合），因此内存可能会被破坏
- 指针可能未对齐，因此扫描必须使用指针大小 window 按字节推进
- 由于指针标记等策略和 XOR 链表等数据结构，指针可能会被混淆
- 代码可能依赖于先前的指针值（与托管代码相反，可以读取引用的值）
- 恢复所有先前挂起的线程
使用 RTTI，可以提供所需的元数据，但将指针传递给您无法控制的库（例如 glibc）仍然是一个问题。因此，在有限的范围内，这可以实施。通用分配器必须在所有本机代码场景中可用 - 对于需要移动分配条目的线性分配器，有太多限制使这不可行。最重要的是，用于停止线程和建立写屏障的低级机制可能会干扰分配器用户（例如 JVM）采用的类似机制。
但是，对于托管代码，这是常见的做法。例如，复制垃圾收集器维护两个分配 spaces - from-space 和 to-space - 来处理压缩。在垃圾回收期间，只有引用的分配条目被复制到另一个分配 space。完成后，可以再次以线性方式处理分配。
在特定场景中，已经使用了使用来自日志结构文件系统的策略的分配器。对于本机代码的通用内存分配，移动分配条目不可行的事实意味着线性分配器无法替代更传统的内存分配策略。
代替采用线性分配路线来减少碎片，一种替代方法是使用池分配器，它为固定大小的分配条目提供分配 spaces。通过以这种方式限制分配space，可以减少碎片。许多通用分配器使用池分配器进行小型分配。在某些情况下，这些应用程序 space 存在于每个线程的基础上，以消除锁定的需要并提高 CPU 缓存利用率。
刚刚学习了日志结构文件系统。我很困惑为什么不使用日志结构作为主内存分配器。它可以显着减少碎片。
日志结构文件系统使用顺序写入循环日志来持久保存文件系统数据，并且通常以完全相同的方式处理更新。在某些时候，日志结构的文件系统必须回收未使用的space（日志中的过时条目）以使其可用于将来的写入。在简单的实现中，只要文件系统用完磁盘space.
，就可以通过重写日志并跳过进程中未使用的条目来回收未使用的条目。本地代码的内存分配器可以做类似的事情。一个简单的实现将需要一大块内存和一个需要为分配过程递增的下一个指针。释放需要将条目标记为已释放（可以是条目中的标志或专用空闲列表）或者需要以其他方式限制释放（按先进先出顺序释放，只有整个分配 space 可以解除分配）。 事实上，这种分配器被称为“线性分配器”并且今天仍在使用。一个优点是分配性能，另一个优点是释放的简单性和效率，如果它发生在 FIFO 顺序或影响整个分配 space。堆栈分配是一个突出的例子。 JVM 通常使用线性分配器进行对象分配。 Apache 网络服务器使用它的一个变体来处理每个请求的内存分配。
使用线性分配器作为通用分配器存在更多问题，因为 space 回收困难。要回收 space，将条目标记为空闲是不够的，因为这可能导致高度碎片化并破坏线性分配的优势（仅需为实际分配任务递增指针）。因此，与文件系统类似，分配 space 必须被压缩，以便它只包含分配的条目，而空闲 space 可用于线性分配。压缩需要四处移动分配的条目 - 一个更改并使其先前已知地址无效的过程。在本机代码中，分配器不知道对已分配条目（存储为指针的地址）的引用位置。必须修补现有引用以使分配器操作对调用者透明，这对于像 malloc.
为什么不可行？更新现有参考需要执行以下步骤：
- 挂起所有线程以停止所有分配条目修改器（除非使用所谓的“写屏障”）
- 扫描寄存器、堆栈和堆以查找指向已移动对象的指针
- 指针的确切位置未知，与引用匹配的数据可能会被误认为是引用（在像 Boehm 这样的保守 GC 的情况下不是问题，例如，它不执行复制。误报只会延迟集合），因此内存可能会被破坏
- 指针可能未对齐，因此扫描必须使用指针大小 window 按字节推进
- 由于指针标记等策略和 XOR 链表等数据结构，指针可能会被混淆
- 代码可能依赖于先前的指针值（与托管代码相反，可以读取引用的值）
- 恢复所有先前挂起的线程
使用 RTTI，可以提供所需的元数据，但将指针传递给您无法控制的库（例如 glibc）仍然是一个问题。因此，在有限的范围内，这可以实施。通用分配器必须在所有本机代码场景中可用 - 对于需要移动分配条目的线性分配器，有太多限制使这不可行。最重要的是，用于停止线程和建立写屏障的低级机制可能会干扰分配器用户（例如 JVM）采用的类似机制。
但是，对于托管代码，这是常见的做法。例如，复制垃圾收集器维护两个分配 spaces - from-space 和 to-space - 来处理压缩。在垃圾回收期间，只有引用的分配条目被复制到另一个分配 space。完成后，可以再次以线性方式处理分配。
在特定场景中，已经使用了使用来自日志结构文件系统的策略的分配器。对于本机代码的通用内存分配，移动分配条目不可行的事实意味着线性分配器无法替代更传统的内存分配策略。
代替采用线性分配路线来减少碎片，一种替代方法是使用池分配器，它为固定大小的分配条目提供分配 spaces。通过以这种方式限制分配space，可以减少碎片。许多通用分配器使用池分配器进行小型分配。在某些情况下，这些应用程序 space 存在于每个线程的基础上，以消除锁定的需要并提高 CPU 缓存利用率。