如何在动态图中避免“堆指针意大利面”？
一般问题
假设您正在编写一个由图形组成的系统，以及可以根据相邻节点的配置激活的图形重写规则。 也就是说，您有一个在运行时期间无法预测地增长/缩小的动态图形。 如果你天真地使用malloc ，新的节点将被分配在内存中的随机位置; 经过足够的时间，你的堆将成为指针意大利面，给你可怕的缓存效率。 是否有任何轻量级的增量技术可以使连接在一起的节点在内存中保持紧密联系 ？
我尝试了什么
我唯一能想到的是将节点嵌入笛卡尔空间，并使用一些物理弹性模拟来排斥/吸引节点。 那将有线节点保持在一起，但看起来很傻，我想模拟的开销会比缓存效率加速更大。
坚实的例子
这是我正在尝试实施的系统。 这是我试图在C中优化的代码的简短片段。 这个 repo是JS中的原型，工作实现，具有可怕的缓存效率（以及语言本身）。 该video以图形方式显示系统的运行情况。
您要解决的是线性排列问题 。 完美的解决方案被认为是NP难的，但存在一些好的近似。 这是一篇应该是一个好的起点的论文。
您可以根据半空间垃圾收集来看待这个问题。 这并不难实现（我已经为解释器完成了），特别是因为你只是为固定大小的节点结构而做。 从一个大块（称为半空间）的内存中分配。 当它变得太满或碎片时，停止并将所有东西复制到另一个（你也可以变大）。 诀窍是更新所有指针。 为此，有一种非常优雅和高效的算法称为扫描复制。 在康奈尔大学对它进行了很好的讨论 。 它基本上首先遍历图形宽度，然后复制，除了复制之外没有任何额外空间。 该算法的一个很好的特性是广度第一级在每次复制后最终相邻。 如果这是一个足够好的局部性，你可以用这种方法非常有效地获得它。
如果您真的关心内存的布局，那么自己管理它可能是值得的。
您可以在启动时malloc一大块内存，然后从该块中分配空间。 您需要一个单独的结构来跟踪已分配的内容和未分配的内容。 如果您知道所有已分配的结构都具有一定的大小，可以简化分配/可用空间管理，即索引数组，否则您可以在可用空间中使用链接的指针列表。 鉴于您可能一次分配一个结构，您可能不必担心跟踪最小和/或最大的连续可用空间块。
你需要注意的一件事是对齐。 同样，如果你总是以单个结构的大小的倍数分配内存，这会使事情变得更容易，否则确保所有分配从4字节边界开始，即地址之间的差异可能是一个好主意。分配和从malloc接收的起始地址是4的倍数。
您可以将其他参数传递给自定义分配函数，以提供有关块应放置位置的提示，例如一个或多个附近节点的地址。
这可以视为图分区问题，您尝试在同一内存块上集群链接图节点。 METIS是一个很好的图分区算法，可能不适合您的用例，因为它需要在整个图中进行全局操作，但是可以修改为适用于您的用例的两个分布式图分区算法是DIDIC和Ja-Be- Ja – 前者尝试在不考虑分区大小的情况下最小化跨越分区的边数，而后者尝试创建大小相等的分区。 这两种算法只需要图形的本地知识来聚类每个节点，因此如果您有任何备用周期，您可以使用它们逐步重新平衡图形。 Fennel是一种在流图上运行的相关算法，因此，例如，您可以在最初分配图节点时使用Fennel或类似算法，然后在重新平衡图时使用DIDIC / Ja-Be-Ja。