如何在动态图中避免"heap pointer spaghetti"？
How to avoid "heap pointer spaghetti" in dynamic graphs?
一般问题
假设您正在编写一个系统，该系统由一个图形以及可以根据相邻节点的配置激活的图形重写规则组成。也就是说，您有一个在运行时 grows/shrinks 不可预测的动态图。如果你天真地使用 malloc，新节点将被分配到内存中的随机位置；足够长的时间后，您的堆将成为指针意大利面条，给您带来糟糕的缓存效率。是否有任何轻量级增量技术可以使连接在一起的 节点在内存中保持靠近 ？
我试过的
我唯一能想到的就是将节点嵌入笛卡尔 space 中，并进行一些 repulsed/attracted 节点的物理弹性模拟。这会将有线节点保持在一起，但看起来很傻，我猜模拟的开销会比缓存效率加速更大。
实实在在的例子
This is the system I'm trying to implement. This is a brief snippet of the code I'm trying to optimize in C. This repo is a prototypal, working implementation in JS, with terrible cache efficiency (and of the language itself). This video 以图形方式显示运行中的系统。
如果您真的很在意内存的布局，您自己管理一下可能是值得的。
您可以在启动时malloc 一大块内存，然后从该块中分配space。您将需要一个单独的结构来跟踪已分配和未分配的内容。如果您知道所有分配的结构都具有一定的大小，可以简化 allocated/free space 管理，即索引数组，否则您可以在免费 space 中使用指针链表.鉴于您可能一次分配一个结构，您可能不需要担心跟踪最小的 and/or 最大的连续空闲块 space.
您需要注意的一件事是对齐。同样，如果您总是以单个结构大小的倍数分配内存，这会使事情变得更容易，否则确保所有分配都从 4 字节边界开始可能是个好主意，即地址与您的地址之间的差异分配并且从 malloc 收到的起始地址是 4.
的倍数
您可以将额外的参数传递给您的自定义分配函数，以提示应该放置区块的位置，例如一个或多个附近节点的地址。
您要解决的是线性排列问题。完美的解决方案被认为是 NP 难的，但存在一些很好的近似值。这是一个 paper 应该是一个很好的起点。
您可能会从一半space 垃圾回收的角度来看待这个问题。这并不难实现（我已经为解释器完成了），特别是因为您只对固定大小的节点结构执行此操作。从一大块内存（称为一半space）中分配。当它变得太满或太零散时，停止并将所有内容复制到另一个（你也可以做得更大）。诀窍是更新所有指针。为此，有一种非常优雅和高效的算法，称为扫描复制。有一个nice discussion of it at Cornell。它本质上首先遍历图的宽度，边复制边复制，除了您正在复制的内容之外没有任何额外的 space。该算法的一个很好的 属性 是广度优先级别在每次复制后最终都是相邻的。如果这是足够好的局部性级别，您将使用此方法非常有效地获得它。
这可以看作是 graph partitioning problem, where you're trying to cluster linked graph nodes on the same memory block. METIS is a good graph partitioning algorithm that is probably not appropriate for your use case because it requires global operations across the entire graph, however two distributed graph partitioning algorithms that may be modified to be applicable for your use case are DIDIC and Ja-Be-Ja - the former attempts to minimize the number of edges that cross partitions without respect to partition size, while the latter attempts to create equally sized partitions. Both algorithms only require local knowledge of the graph to cluster each node, so if you've got any spare cycles you can use them to incrementally rebalance the graph. Fennel 是一种在流图上运行的相关算法，例如您可以在最初分配图节点时使用 Fennel 或类似算法，然后在重新平衡图时使用 DIDIC/Ja-Be-Ja。
一般问题
假设您正在编写一个系统，该系统由一个图形以及可以根据相邻节点的配置激活的图形重写规则组成。也就是说，您有一个在运行时 grows/shrinks 不可预测的动态图。如果你天真地使用 malloc，新节点将被分配到内存中的随机位置；足够长的时间后，您的堆将成为指针意大利面条，给您带来糟糕的缓存效率。是否有任何轻量级增量技术可以使连接在一起的 节点在内存中保持靠近 ？
我试过的
我唯一能想到的就是将节点嵌入笛卡尔 space 中，并进行一些 repulsed/attracted 节点的物理弹性模拟。这会将有线节点保持在一起，但看起来很傻，我猜模拟的开销会比缓存效率加速更大。
实实在在的例子
This is the system I'm trying to implement. This is a brief snippet of the code I'm trying to optimize in C. This repo is a prototypal, working implementation in JS, with terrible cache efficiency (and of the language itself). This video 以图形方式显示运行中的系统。
如果您真的很在意内存的布局，您自己管理一下可能是值得的。
您可以在启动时malloc 一大块内存，然后从该块中分配space。您将需要一个单独的结构来跟踪已分配和未分配的内容。如果您知道所有分配的结构都具有一定的大小，可以简化 allocated/free space 管理，即索引数组，否则您可以在免费 space 中使用指针链表.鉴于您可能一次分配一个结构，您可能不需要担心跟踪最小的 and/or 最大的连续空闲块 space.
您需要注意的一件事是对齐。同样，如果您总是以单个结构大小的倍数分配内存，这会使事情变得更容易，否则确保所有分配都从 4 字节边界开始可能是个好主意，即地址与您的地址之间的差异分配并且从 malloc 收到的起始地址是 4.
您可以将额外的参数传递给您的自定义分配函数，以提示应该放置区块的位置，例如一个或多个附近节点的地址。
您要解决的是线性排列问题。完美的解决方案被认为是 NP 难的，但存在一些很好的近似值。这是一个 paper 应该是一个很好的起点。
您可能会从一半space 垃圾回收的角度来看待这个问题。这并不难实现（我已经为解释器完成了），特别是因为您只对固定大小的节点结构执行此操作。从一大块内存（称为一半space）中分配。当它变得太满或太零散时，停止并将所有内容复制到另一个（你也可以做得更大）。诀窍是更新所有指针。为此，有一种非常优雅和高效的算法，称为扫描复制。有一个nice discussion of it at Cornell。它本质上首先遍历图的宽度，边复制边复制，除了您正在复制的内容之外没有任何额外的 space。该算法的一个很好的 属性 是广度优先级别在每次复制后最终都是相邻的。如果这是足够好的局部性级别，您将使用此方法非常有效地获得它。
这可以看作是 graph partitioning problem, where you're trying to cluster linked graph nodes on the same memory block. METIS is a good graph partitioning algorithm that is probably not appropriate for your use case because it requires global operations across the entire graph, however two distributed graph partitioning algorithms that may be modified to be applicable for your use case are DIDIC and Ja-Be-Ja - the former attempts to minimize the number of edges that cross partitions without respect to partition size, while the latter attempts to create equally sized partitions. Both algorithms only require local knowledge of the graph to cluster each node, so if you've got any spare cycles you can use them to incrementally rebalance the graph. Fennel 是一种在流图上运行的相关算法，例如您可以在最初分配图节点时使用 Fennel 或类似算法，然后在重新平衡图时使用 DIDIC/Ja-Be-Ja。