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 语言实现这些东西应该“显然”要快得多。事实上，我怀疑答案并不是那么明确。