现代 CPU 已经过优化,因此访问和修改内存中的同一位置(时间局部性)以及内存中的连续位置(空间局部性)是非常快速的操作。
现在,由于 Haskell 是一种纯粹不可变的语言,你自然不能覆盖现有的内存块,这可能会使像 foldl
这样的东西比带有 a 的 for
循环慢得多连续访问的结果变量将在 C 中。
Haskell 是否在内部采取任何措施来减轻这种性能损失?总的来说,它关于局部性的属性是什么?
最佳答案
一般规则是,对于“普通”Haskell 编程,您几乎无法(如果有的话)控制内存布局和内存位置。
但是,确实存在许多允许此类控制的更高级功能,以及在这些功能之上公开友好抽象的库。 vector
图书馆可能是后者中最受欢迎的。这个库提供了几种固定大小的数组类型,其中两种( Data.Vector.Unboxed
和 Data.Vector.Storable
)通过将向量及其内容表示为连续的内存数组来为您提供数据局部性。 Data.Vector.Unboxed
甚至包含一个简单的自动“数组结构”转换——一个未装箱的向量对将被表示为一对未装箱的向量,每个向量对的组件都有一个。
另一个例子是 JuicyPixels
用于图像处理的库,它将内存中的图像表示为连续的位图。这实际上是 Data.Vector.Storable
,它利用标准工具 ( Foreign.Storable
) 将用户定义的 Haskell 数据类型转换为原始字节和从原始字节转换。
但一般模式是这样的:在 Haskell 中,当您对内存局部性感兴趣时,您会确定哪些数据需要从中受益,并将其捆绑在一个自定义数据类型中,该数据类型的实现旨在提供局部性和性能保证.编写这样的数据类型是一项高级任务,但大部分工作已经以可重用的方式完成(例如,请注意 JuicyPixels
大多只是重用 vector
)。
还要注意:
-
vector
提供 流融合 优化以在应用嵌套向量转换时消除中间数组。如果生成一个从 0 到 1,000,000 的向量,过滤掉偶数,映射(^2)
对其进行函数并对结果的元素求和,从未分配过任何数组——库具有将其重写为从 0 到 1,000,000 的累加器循环的智能。所以一个foldl
的向量不一定比for
慢循环——可能根本就没有数组! -
vector
也提供可变数组。更一般地说,在 Haskell 中,如果您真的坚持,您可以覆盖现有内存。它只是 (a) 不是语言中的默认范式,因此 (b) 有点笨拙,但如果您只需要在一些性能敏感的地方使用它,它绝对易于处理。
所以大多数时候,“我想要内存位置”的答案是“使用 vector
。”
关于performance - Haskell 的局部属性是什么?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/29843960/