STL 的“partial_sum"有什么实际用途?

2022-01-09 00:00:00 partial algorithm sum c++ stl

STL 算法的实际用途是什么/在哪里?一个>?

What/where are the practical uses of the partial_sum algorithm in STL?

还有哪些其他有趣/重要的示例或用例?

What are some other interesting/non-trivial examples or use-cases?

推荐答案

我用它来减少我的玩具 lambda 演算解释器中一个简单的标记清除垃圾收集器的内存使用量.

I used it to reduce memory usage of a simple mark-sweep garbage collector in my toy lambda calculus interpreter.

GC 池是一个大小相同的对象数组.目标是消除未链接到其他对象的对象，并将剩余对象压缩到数组的开头.由于对象在内存中移动，因此每个链接都需要更新.这需要一个对象重映射表.

The GC pool is an array of objects of identical size. The goal is to eliminate objects that aren't linked to other objects, and condense the remaining objects into the beginning of the array. Since the objects are moved in memory, each link needs to be updated. This necessitates an object remapping table.

partial_sum 允许以压缩格式(每个对象只有一位)存储表，直到扫描完成并释放内存.由于对象很小，这显着减少了内存使用.

partial_sum allows the table to be stored in compressed format (as little as one bit per object) until the sweep is complete and memory has been freed. Since the objects are small, this significantly reduces memory use.

  1. 递归标记使用的对象并填充布尔数组.
  2. 使用 remove_if 将标记的对象压缩到池的开头.
  3. 在布尔值上使用 partial_sum 以生成指向新池的指针/索引表.
    • 这是因为第 N 个标记的对象在数组中有 N 个前面的 1，并获取池索引 N.
  1. Recursively mark used objects and populate the Boolean array.
  2. Use remove_if to condense the marked objects to the beginning of the pool.
  3. Use partial_sum over the Boolean values to generate a table of pointers/indexes into the new pool.
    • This works because the Nth marked object has N preceding 1's in the array and acquires pool index N.

将重映射表放在刚刚释放的内存中，对数据缓存特别友好.

It's especially friendly to the data cache to put the remap table in the just-freed, thus still hot, memory.

相关文章