如何在GHC中编写尽可能高效的数据结构?

所以有时我需要写一个我在Hackage上找不到的数据结构,或者我发现没有经过testing或者质量足够让我信任,或者只是我不想成为依赖的东西。 我正在阅读冈崎的书,它很好的解释了如何devise渐近快速的数据结构。

但是,我正在与GHC合作。 对于我的应用程序来说,恒定的因素是很重要 内存使用对我来说也是一个大问题。 所以我有关于GHC的具体问题。

尤其是

  • 如何最大限度地共享节点
  • 如何减less内存占用
  • 如何避免由于不严格/懒惰造成的空间泄漏
  • 如何让GHC为重要代码段产生严密的内部循环

我环顾了networking上的各个地方,我对如何使用GHC有一个模糊的想法,例如,看核心输出,使用UNPACK编译指示等。 但我不知道我明白了。

所以我popup我最喜欢的数据结构库,容器,并查看Data.Sequence模块。 我不能说我很了解他们正在做什么使Seq快速。

FingerTree a的定义首先引起我的FingerTree a 。 我认为这只是我不熟悉手指树而已。 第二个引人注目的是所有的SPECIALIZE杂项。 我不知道这里发生了什么事情,而且我很好奇,因为这些代码遍布各处。

许多函数也有与之相关的INLINE附注。 我可以猜出这是什么意思,但是如何判断什么时候使用INLINE函数呢?

在~475线附近的事情变得非常有趣,一节被称为“适用性build设”。 他们定义了一个新的包装来表示身份monad,他们自己写了严格的monad副本,他们有一个定义为applicativeTree的函数,这个函数显然是专用于身份monad的,这就增加了函数输出的共享。 我不知道这里发生了什么事。 正在使用什么巫术来增加分享?

无论如何,我不确定从Data.Sequence学到多less东西。 还有其他的“模范课程”,我可以读懂智慧吗? 我真的很想知道如果我真的需要他们加快速度,那么我的数据结构将会如何。 有一点特别是写数据结构,使融合变得容易,以及如何写好融合规则。

这是一个很大的话题! 大多数已经在其他地方解释过了,所以我不会在这里写一本书的章节。 代替:

  • 真实世界Haskell,第25章,“ 性能 ” – 讨论分析,简单的专业化和解包,读取核心和一些优化。

Johan Tibell在这个话题上写了很多:

  • 计算数据结构的大小
  • 常见数据types的内存占用情况
  • 通过散列更快的持久结构
  • 推理懒惰

还有一些来自这里的东西:

  • 读GHC核心
  • GHC如何进行优化
  • 性能分析
  • 调整GC设置
  • 一般的改进
  • 更多关于拆包
  • 拆箱和严格

还有一些其他的东西:

  • 介绍代码和数据的专业化
  • 代码改进标志

applicativeTree是相当有趣的,但主要是与FingerTrees相关的一种方式,它们本身就是一个相当奇特的数据结构。 我们有一些在理论上的错综复杂的讨论。 请注意, applicativeTree是为了处理任何应用applicativeTree而编写的。 它恰好如此,当它被专门化为Id时,它可以共享节点,否则它不能。 您可以通过内联Id方法并查看会发生什么来自己完成专业化。 请注意,这种专业化只在一个地方使用 – O(log n) replicatefunction。 事实上,更一般的function专注于不断的情况是一个非常聪明的代码重用位,但这是真的。

一般来说, Sequence教授更多的是关于devise持久的数据结构,而不是关于性能的所有技巧,我想。 Dons的build议当然是非常好的。 我也只是浏览真正的规范和调整的库的来源 – 特别是MapIntMapSetIntSet 。 除此之外,值得一看米兰关于集装箱改造的文章 。