我正在F#中研究多核并行。我不得不承认，不变性确实有助于编写正确的并行实现。然而，当内核数量增长时，很难实现良好的加速和可扩展性。例如，我对快速排序算法的经验是，许多尝试以纯功能的方式实现并行快速排序并使用List或Array作为表示的尝试都失败了。对这些实现的分析表明，与顺序版本相比，缓存未命中的数量显著增加。然而，如果使用数组内部的突变实现并行快速排序，则可以获得良好的加速。因此，我认为突变可能是优化多核并行性的一个很好的实践。
我认为缓存局部性是函数语言中多核并行的一大障碍。函数式编程涉及创建许多短命对象；这些对象的破坏可能会破坏CPU缓存的一致性。我已经看到了许多关于如何在命令式语言中改进缓存位置的建议，例如，here和here。但我不清楚在函数式编程中如何做到这一点，尤其是对于经常出现的递归数据结构，如树等。
是否有任何技术可以在不纯净的函数语言（特别是F#）中改进缓存位置？任何建议或代码示例都非常受欢迎。
据我所知，缓存位置（多线程或其他）的关键是
- 将工作单元保留在可放入缓存的连续RAM块中
为此目的；
-
尽可能避开物体
- 对象是在堆上分配的，根据堆碎片等，对象可能会被喷得到处都是
- 您对对象的内存位置基本上没有任何控制，GC可以随时移动它们
- 使用数组。大多数编译器将数组解释为一个连续的内存块。
- 其他集合数据类型可能会将内容分布在各处——例如，链表由指针组成
- 使用基元类型的数组。对象类型是在堆上分配的，因此对象数组只是指向可能分布在堆中的对象的指针数组
- 如果不能使用基元，请使用结构数组。结构的字段在内存中按顺序排列，并被.NET编译器视为基元
- 计算将在其上执行缓存的机器上的缓存大小
- CPU具有不同大小的二级缓存
- 谨慎的做法可能是将代码设计为可扩展到不同的缓存大小
- 或者更简单地说，编写适合代码运行的最低通用缓存大小的代码
- 计算出需要靠近每个基准的位置
- 在实践中，您不会将整个工作集放入二级缓存
- 检查（或重新设计）您的算法，以便您使用的数据结构将所需的数据"下一个"保持在以前所需的接近数据的位置
在实践中，这意味着你可能最终使用的数据结构在理论上不是计算机科学的完美例子——但没关系，计算机在理论上也不是计算机科学完美的例子。
关于这个主题的一篇很好的学术论文是使用复制的高速缓存高效字符串排序
允许F#中函数的可变性是一件好事，但它只应在优化代码时使用。纯功能风格通常会产生更直观的实现，因此是首选。
以下是快速搜索返回的内容：Haskell中的Parallel Quicksort。让我们把讨论性能的重点放在性能上。选择一个处理器，然后用特定的算法对其进行测试。
为了不具体地回答您的问题，我想说，Clojure实现STM的方法在一般情况下可以成为一堂关于如何在多核处理器上解耦执行路径和提高缓存位置性的课程。但只有当读取次数超过写入次数时，它才有效。
我不是并行专家，但这是我的建议。
- 我认为，一种局部可变的方法，其中每个核心都被分配一个可读写的内存区域，将永远胜过纯方法
- 试着制定你的算法，使其在连续的内存区域上按顺序工作。这意味着，如果您使用的是图，则可能值得将节点"扁平化"为数组，并在处理之前用索引替换引用。不管缓存位置问题如何，这在.NET中始终是一种很好的优化技术，因为它有助于避免垃圾收集
一个很好的方法是将工作分成更小的部分，并在每个核心上的每个部分上迭代。
我首先要做的一个选择是，在并行之前，在单个内核上寻找缓存位置的改进，这应该只是为每个内核再次细分工作的问题。例如，如果你用大矩阵进行矩阵计算，那么你可以把计算分成更小的部分。
这里有一个很好的例子：缓存本地性能
Tomas Petricek的书中有一些很棒的章节Real Work函数式编程，请参阅第14章编写并行函数式程序，您可能会发现对二进制树的并行处理特别感兴趣。
编写可扩展的应用程序缓存位置对您的应用程序速度至关重要。Scott Meyers的演讲很好地解释了这些原则。由于在内存中创建了新对象，从而迫使CPU再次从新对象中重新加载数据，因此不可变性在缓存局部性方面不能很好地发挥作用。正如在谈话中所指出的，即使在现代CPU上，L1高速缓存也只有32KB的大小，在所有核心之间共享代码和数据。如果你使用多线程，你应该尽可能少地消耗内存（再见免疫），以保持在最快的缓存中。二级缓存大约为4-8MB，与您尝试排序的数据相比，它要大得多，但仍然很小
如果您设法编写一个消耗尽可能少的内存（数据缓存位置）的应用程序，您可以获得20或更多的加速。但是，如果你为一个核心管理这一点，那么扩展到更多核心可能会损害性能，因为所有核心都在争夺相同的二级缓存。
为了最大限度地利用它，C++人员使用PGA（Profile Guided Optimization，概要文件引导优化），这允许他们对自己的应用程序进行概要分析，这些应用程序被用作编译器的输入数据，以针对特定用例发出更好的优化代码。
在托管代码中，您可以在一定程度上变得更好，但由于有这么多因素影响您的缓存位置，因此在现实世界中，由于总缓存位置，您不太可能看到20的加速。这仍然是C++和编译器使用评测数据的机制。
您可以从中获得一些想法：
缓存遗忘http://supertech.csail.mit.edu/cacheObliviousBTree.html缓存遗忘搜索树项目
DSapce@MIT多核处理器中的缓存一致性策略http://dspace.mit.edu/handle/1721.1/61276
通过F#中矩阵乘法的优雅高效实现，描述了缓存遗忘算法的革命性思想。