haskell - Haskell 中的快速数据结构

Question

我发现在containers包中关键的数据结构，例如Data.Map或Data.IntMap在纯 Haskell 中实现。问题：我想知道，在 中实施它们不是更有效C吗？我知道 ghc 非常好，但绝对无法与优化C代码竞争。

Answer 1

这是一个有趣的问题，但我不确定是否有人能够以一种或另一种方式提供任何确凿的答案（除了设计和构建一个广泛的测试套件并生成大量数字之外）。

这个问题背后的假设似乎是“C 总是很快，Haskell 总是很慢，所以用 C 而不是 Haskell 编写代码不是更好吗？” 我不确定这个假设是否准确。（在我有限的经验中，并不是 Haskell很慢，而是 Haskell可能很慢 - 或非常快 - 很难预测你将获得什么样的速度。）

通过 FFI 调用 C 有开销。Haskell 数据结构由垃圾收集器处理；通过 C 使用的内存必须手动管理。你在这里付出了相当多的努力，可能没有你想象的那么多好处。

由于可变性，C 数据结构往往更有效。大多数人不想在 Haskell 中使用可变数据结构。（从某种意义上说，它首先否定了使用 Haskell 的所有好处，所以为什么要麻烦呢？）如果您在 C 中使用不可变数据结构，您甚至可能会发现它比 Haskell 慢。（例如，有人告诉我 C 在动态内存分配方面非常慢，这对于持久性数据结构来说是个问题。另一种方法是在整个地方复制东西，这也不会很快。）

最重要的是，GHC 做了一些聪明的优化，比如砍伐森林，这有时会导致容器在运行时完全消失。C 编译器永远不会做这样的事情。而 Haskell 作为一种懒惰的语言，有时可以完全跳过你要求它做的工作；如果容器是用 C 实现的，那将无法工作。

总之，“看起来”在 C 中实现这些东西应该“显然”快得多。实际上，我怀疑答案并不那么明确。

Answer 2

GHC 的运行时针对有效分配不可变结构进行了优化。它通常会在此任务中击败 C 运行时 (malloc)。因此，C 主要用于优化算法，而不是数据结构。一个例外是非常低级的数据结构或高度调整的可变结构。

Answer 3

首先，Data.Map不是通常的命令式映射，而是所谓的持久性映射。它应该支持有效地保存自身的多个版本。C 不太适合这种类型的数据结构——例如，经典的 C 风格的内存管理是不可能的。

其次，GHC 堆布局相当复杂，尤其是在使用Ord a字典进行比较的情况下。因此，与旧的优秀 C 的接口并不简单，接口的成本可能会超过所谓的更好代码生成的优势。

用 C实现Data.Map是可能的，但由于所有这些簿记，它几乎没有帮助。您可以尝试让我们知道它是否更快 :) 如您所见，它尚未完成，因为社区非常确定无能为力。