performance - Haskell 的局部属性是什么？

Question

现代 CPU 已经过优化，因此访问和修改内存中的同一位置(时间局部性)以及内存中的连续位置(空间局部性)是非常快速的操作。

现在，由于 Haskell 是一种纯粹不可变的语言，你自然不能覆盖现有的内存块，这可能会使像 foldl 这样的东西比带有 a 的 for 循环慢得多连续访问的结果变量将在 C 中。

Haskell 是否在内部采取任何措施来减轻这种性能损失？总的来说，它关于局部性的属性是什么？

Answer 1

一般规则是，对于“普通”Haskell 编程，您几乎无法(如果有的话)控制内存布局和内存位置。

但是，确实存在许多允许此类控制的更高级功能，以及在这些功能之上公开友好抽象的库。 vector 图书馆可能是后者中最受欢迎的。这个库提供了几种固定大小的数组类型，其中两种( Data.Vector.Unboxed 和 Data.Vector.Storable )通过将向量及其内容表示为连续的内存数组来为您提供数据局部性。 Data.Vector.Unboxed甚至包含一个简单的自动“数组结构”转换——一个未装箱的向量对将被表示为一对未装箱的向量，每个向量对的组件都有一个。

另一个例子是 JuicyPixels 用于图像处理的库，它将内存中的图像表示为连续的位图。这实际上是 Data.Vector.Storable ，它利用标准工具 ( Foreign.Storable ) 将用户定义的 Haskell 数据类型转换为原始字节和从原始字节转换。

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

还要注意:

1. vector提供 流融合 优化以在应用嵌套向量转换时消除中间数组。如果生成一个从 0 到 1,000,000 的向量，过滤掉偶数，映射 (^2)对其进行函数并对结果的元素求和，从未分配过任何数组——库具有将其重写为从 0 到 1,000,000 的累加器循环的智能。所以一个foldl的向量不一定比 for 慢循环——可能根本就没有数组!
2. vector也提供可变数组。更一般地说，在 Haskell 中，如果您真的坚持，您可以覆盖现有内存。它只是 (a) 不是语言中的默认范式，因此 (b) 有点笨拙，但如果您只需要在一些性能敏感的地方使用它，它绝对易于处理。

所以大多数时候，“我想要内存位置”的答案是“使用 vector。”