如何避免动态图中的“堆指针意大利面条”？

一般问题

假设您正在编写一个由图组成的系统，以及可以根据相邻节点的配置激活的图重写规则。也就是说，您有一个在运行时不可预测地增长/收缩的动态图。如果你天真地使用malloc，新节点将被分配在内存中的随机位置；经过足够的时间，你的堆将变成一个指针意大利面条，给你带来可怕的缓存效率。有没有什么轻量级的增量技术可以实现连接在一起的节点在内存中保持靠近?

我尝试过的

我唯一能想到的是将节点嵌入笛卡尔空间中，并通过一些物理弹性模拟来排斥/吸引节点。这会将有线节点保持在一起，但看起来很愚蠢，我猜模拟的开销会比缓存效率加速更大。

坚实的例子

This https://i.stack.imgur.com/eD36T.jpg是我正在尝试实施的系统。This http://paste.ofcode.org/34tfgELFk8HNSyDQd46wawB是我尝试用 C 语言优化的代码的一个简短片段。This https://github.com/MaiaVictor/optlam/blob/master/optlam.jsrepo 是 JS 中的一个原型、有效实现，具有糟糕的缓存效率（以及语言本身的效率）。这个视频 https://www.youtube.com/watch?v=lhNtgbFTXFE以图形方式显示系统的运行情况。

您要解决的是线性排列问题。完美的解决方案被认为是 NP 困难的，但存在一些很好的近似。这里有一个paper http://dl.acm.org/citation.cfm?id=760642这应该是一个很好的起点。