asynchronous - F# 中多核并行中缓存局部性的最佳实践

Question

我正在研究 F# 中的多核并行性。我不得不承认，不变性确实有助于编写正确的并行实现。然而，当核心数量增加时，很难实现良好的加速和良好的可扩展性。例如，我对快速排序算法的经验是，许多尝试以纯函数方式并使用 List 来实现并行快速排序。或 Array因为代表失败了。分析这些实现表明，与顺序版本相比，缓存未命中的数量显着增加。但是，如果使用数组内部的变异实现并行快速排序，则可以获得良好的加速。因此，我认为变异可能是优化多核并行性的好方法。

我相信 cache locality是函数式语言中多核并行的一大障碍。函数式编程涉及创建许多短期对象；破坏这些对象可能会破坏 CPU 缓存的一致性属性。我已经看到了很多关于如何在命令式语言中提高缓存局部性的建议，例如，here和 here .但是我不清楚它们将如何在函数式编程中完成，尤其是对于经常出现的递归数据结构，如树等。

是否有任何技术可以在不纯的函数式语言(特别是 F#)中提高缓存局部性？任何建议或代码示例都非常受欢迎。

Answer 1

据我所知，缓存局部性(多线程或其他)的关键是

将工作单元保存在适合缓存的连续 RAM block 中

为此 ;

尽可能避开物体

对象是在堆上分配的，并且可能会散布到各处，这取决于堆碎片等。

您对对象的内存位置的控制基本上为零，以至于 GC 可能随时移动它们。

使用数组。大多数编译器将数组解释为连续的内存块。

其他集合数据类型可能会将事物分布在各处 - 例如，链表由指针组成。

使用原始类型的数组。对象类型是在堆上分配的，因此对象数组只是指向可能分布在整个堆中的对象的指针数组。

如果不能使用原语，请使用结构数组。结构的字段在内存中按顺序排列，并被 .NET 编译器视为基元。

计算出您将在其上执行缓存的机器上的缓存大小

CPU 有不同大小的二级缓存

谨慎设计代码以适应不同的缓存大小

或者更简单地说，编写适合您的代码将在

上运行的最低公共(public)缓存大小的代码。

计算出需要靠近每个基准的位置

在实践中，您不会将整个工作集放入二级缓存

检查(或重新设计)您的算法，以便您使用的数据结构将“下一个”需要的数据保存在之前需要的数据附近。

在实践中，这意味着您最终可能会使用在理论上不是计算机科学完美示例的数据结构 - 但没关系，计算机也不是计算机科学理论上完美的示例。

一篇关于该主题的优秀学术论文是 Cache-Efficient String Sorting Using Copying