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