Haskell的局部性质是什么？

Question

现代CPU经过优化，使得访问和修改内存中的相同位置（时间位置）以及内存中的连续位置（空间位置）都是极其快速的操作。

现在，由于Haskell是一种纯粹的不可变语言，您自然不能覆盖现有的内存块，这可能会使 之类的操作比C中具有连续访问的结果变量的 循环慢得多。

Haskell在内部做了什么来减轻这种性能损失吗？一般来说，它关于局部性的性质是什么？

Answer 1

Haskell是一种非常高级的语言，你要问的是一个非常低级的细节问题。

总体而言，Haskells的性能可能与Java或C#等任何收集垃圾的语言相似。特别是，Haskell具有可变数组，它将具有类似于任何其他数组的性能。（您可能需要未装箱数组来匹配C的性能。）

对于fold（折叠），如果最终结果是机器整数，那么在整个循环期间，它可能会在处理器寄存器中结束。因此，最终的机器代码与C中的一个连续访问变量几乎完全相同。（如果结果是字典之类的，那么很可能不是。但这也和C语言一样。）

更一般说来，如果本地性对你来说很重要，那么任何一种垃圾收集的语言都可能不是你的朋友。但是，同样，您可以使用未装箱数组来解决这个问题。

所有这些讨论都很棒，但如果你真的想知道一个特定的Haskell程序有多快，就用基准测试它吧。事实证明，编写良好的Haskell程序通常都是相当快的。（就像大多数编译语言一样。）

补充:你可以要求GHC以核心格式输出部分编译的代码，核心格式比Haskell的级别低，但比机器代码的级别高。这可以让您看到编译器决定做什么（特别是，在什么地方内联了东西，在什么地方删除了抽象，等等）。这可以帮助您找出最终代码的样子，而不必一直深入到机器代码。

Answer 2

null

然而，确实存在许多更高级的特性来允许这样的控制，以及在这些特性之上公开友好抽象的库。 库可能是后者中最流行的。这个库提供了几种固定大小的数组类型，其中两种（codeData.vector.unboxed/code>和 )通过将向量及其内容表示为连续的内存数组来提供数据位置。 甚至包含一个简单的自动“数组结构”转换。一对未装箱的向量将被表示为一对未装箱的向量，每对组件对应一个。

另一个例子是用于图像处理的 库，它将内存中的图像表示为连续的位图。这实际上可以追溯到 ，它利用标准工具（codeforeign.storable/code>)将用户定义的Haskell数据类型与原始字节进行转换。

但是一般的模式是这样的:在Haskell中，当您对内存局部性感兴趣时，您可以确定哪些数据需要从中受益，并将其捆绑在一个定制的数据类型中，该类型的实现旨在提供局部性和性能保证。编写这样的数据类型是一项高级工作，但是大部分的工作已经以可重用的方式完成了（例如，请注意 主要只是重用

还应注意:

提供流融合优化，以便在应用嵌套向量转换时消除中间数组。如果您生成一个从0到1,000,000的向量，过滤掉偶数，将 函数映射到该向量上，并对结果的元素进行求和，则不会分配任何数组。库可以聪明地将该向量重写到从0到1,000,000的累加器循环中。所以向量的 并不一定比 循环慢，可能根本没有数组/li> 还提供了可变数组。更一般地，在Haskell中，如果您真的坚持，您可以覆盖现有内存。它只是(a)不是该语言中的默认范例，因此(b)有点笨拙，但如果您只需要在一些性能敏感的点使用它，则绝对容易处理。/li>

所以大多数时候，“我想要内存局部性”的答案是“使用