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

Question

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

dan*_*raj 46 haskell data-structures

所以有时我需要编写一个我在Hackage上找不到的数据结构,或者我发现没有经过测试或质量不足以让我信任,或者只是我不想成为依赖项.我现在正在阅读冈崎的书,它很擅长解释如何设计渐近快速的数据结构.

但是,我正在专门研究GHC.常数因素对我的应用来说是一个大问题.内存使用对我来说也是一个大问题.所以我对GHC有特别的疑问.

特别是

如何最大化节点共享
如何减少内存占用
如何避免因严格不严/懒惰造成的空间泄漏
如何让GHC为重要的代码段生成紧密的内部循环

我浏览了网络上的各个地方,我对如何使用GHC 有一个模糊的想法,例如,查看核心输出,使用UNPACK编译指示等.但我不确定我明白了.

所以我弹出了我最喜欢的数据结构库,容器,并查看了Data.Sequence模块.我不能说我理解他们正在做的很多事情,以使Seq快速.

引起我注意的第一件事就是定义FingerTree a.我认为这只是我对手指树不熟悉.引起我注意的第二件事是所有的SPECIALIZEpragma.我不知道这里发生了什么,我很好奇,因为这些都遍布整个代码.

许多函数也有一个INLINE与它们相关的编译指示.我可以猜到这意味着什么,但是如何判断何时INLINE起作用呢？

事情变得非常有趣~~475线,一个被称为"应用建筑"的部分.它们定义了一个newtype包装器来表示Identity monad,它们编写自己的严格状态monad副本,并且它们有一个被定义的函数applicativeTree,它显然专用于Identity monad,这增加了函数输出的共享.我不知道这里发生了什么.什么巫术被用来增加分享？

无论如何,我不确定从Data.Sequence中学到很多东西.是否有其他"模范程序"我可以阅读以获得智慧？我真的很想知道当我真正需要它们更快时,如何更新我的数据结构.有一件事特别是编写使融合变得容易的数据结构,以及如何编写良好的融合规则.

Answer 1

Don*_*art 41

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

真实世界Haskell,第25章," 性能 " - 讨论分析,简单专业化和解包,阅读核心,以及一些优化.

约翰·蒂贝尔在这个主题上写了很多:

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

还有其他一些事情:

SPECIALIZE导致比INLINE更少的代码膨胀,因为每种类型只有一个额外的函数体,而不是每个调用站点一个额外的函数体.我的经验法则:对具有高阶参数的函数使用INLINE(以避免间接调用),否则使用SPECIALIZE.通过添加INLINABLE,我使用了几乎独占的地方,我之前使用了SPECIALIZE,因为INLINABLE允许在不同的模块中进行专业化. (7认同)
我在CUFP上的"高性能Haskell"讲话包含了"关于懒惰的推理"的幻灯片的超集.你可以在这里找到它:http://blog.johantibell.com/2010/09/slides-from-my-high-performance-haskell.html (2认同)

Answer 2

scl*_*clv 13

applicativeTree非常花哨,但主要是以与FingerTrees有关的方式,这本身就是一个非常奇特的数据结构.我们对cstheory的复杂性进行了一些讨论.请注意,这applicativeTree是为了适用于任何 Applicative.只有这样才发生,当它专门用于Id它时,它可以以其他方式不能共享节点.您可以通过内联Id方法并查看发生的情况来自行完成专业化.请注意,此专门化仅在一个位置使用 - O(log n)replicate函数.事实上,更通用的功能专门适用于常量情况是一个非常聪明的代码重用,但这就是全部.

总的来说Sequence,我认为更多的是关于设计持久性数据结构而不是关于实现性能的所有技巧.Dons的建议当然很棒.我也只希望通过源浏览真的 -规范和调整库Map,IntMap,Set,和IntSet特别.与此同时,值得一看的是米兰关于容器改进的论文.

和HashMap和HashSet,我的新宠. (3认同)
你见过Johan的hashmap吗？http://hackage.haskell.org/packages/archive/unordered-containers/0.1.3.0/doc/html/src/Data-HashMap-Common.html#HashMap (3认同)

归档时间：	14 年，2 月前
查看次数：	2301 次
最近记录：	14 年，2 月前