如何在GHC中编写尽可能高效的数据结构？
所以有时候我需要写一个我在Hackage上找不到的数据结构，或者我发现的东西没有经过测试或者没有足够的质量让我信任，或者它只是我不想成为依赖的东西。我现在正在读Okasaki的书，它很好地解释了如何设计渐近快速的数据结构。
但是，我是专门使用GHC的。常量因素对我的应用程序来说是个大问题。内存使用对我来说也是个大问题。所以我有一些关于GHC的问题。
特别是
- How to最大化节点共享
- How to reduce memory footprint
- 如何避免由于不正确的strictness/laziness
- How导致的空间泄漏让GHC为代码的重要部分生成紧密的内部循环
我在网上浏览过很多地方，我对如何使用GHC有一个模糊的概念，例如，查看核心输出，使用UNPACK编译指示，等等。但我不确定我能不能理解。
因此，我打开了我最喜欢的数据结构库容器，并查看了Data.Sequence模块。我不能说我理解他们为了让Seq更快所做的很多事情。
首先吸引我眼球的是FingerTree a的定义。我想这只是我对指状树不熟悉的原因。吸引我眼球的第二件事是所有的SPECIALIZE编译指示。我不知道这里发生了什么，我很好奇，因为代码中到处都是这些东西。
许多函数还具有与之相关联的INLINE杂注。我可以猜出这是什么意思，但是我如何判断何时INLINE函数呢？
在第~475行附近，事情变得非常有趣，这一部分的标题是“应用构造”。他们定义了一个新类型的包装器来表示Identity monad，他们编写了自己的严格状态monad的副本，并且他们有一个定义为applicativeTree的函数，这个函数显然是专用于Identity monad的，这增加了函数输出的共享。我不知道这是怎么回事。什么魔法被用来增加分享？
无论如何，我不确定从Data.Sequence中能学到什么。有没有其他“模范程序”可以让我阅读以获取智慧？我真的很想知道，当我真的需要更快的数据结构时，如何增强它们。有一件事特别重要，那就是编写数据结构，使融合变得容易，以及如何着手编写良好的融合规则。
回答 2
Stack Overflow用户
发布于 2011-06-22 06:50:22
这是一个很大的话题！大多数已经在其他地方解释过了，所以我不会尝试在这里写一章书。而是：
- 现实世界哈斯克尔，第25章，"Performance“-讨论了概要分析、简单的专门化和解包、读取核心和一些核心
Johan Tibell在这个主题上写了很多文章：
- Computing the size of a data structure
- Memory footprints of common data types
- Faster persistent structures through hashing
- Reasoning about laziness
以及下面的一些内容：
- Reading GHC Core
- How GHC does optimization
- Profiling for performance
- Tweaking GC settings
- General improvements
- More on unpacking
- Unboxing and strictness
还有其他一些东西：
Stack Overflow用户
发布于 2011-06-22 07:41:06
applicativeTree很奇特，但主要是在某种程度上与FingerTrees有关，这本身就是一种奇特的数据结构。我们讨论了一些错综复杂的over at cstheory。请注意，applicativeTree是为在任何应用程序上工作而编写的。当它专用于Id时，它就可以以一种其他方式不能共享的方式共享节点。您可以通过内联Id方法并查看发生了什么来自己完成专门化。注意，这种特殊化只在一个地方使用-- O(log ) replicate函数。事实上，更通用的函数巧妙地专门处理常量情况，这是代码重用的一个非常巧妙的做法，但仅此而已。
总的来说，我认为Sequence教授了更多关于设计持久数据结构的知识，而不是关于测试性能的所有技巧。Dons的建议当然很棒。我还将浏览真正规范和调优的库的源代码--特别是Map、IntMap、Set和IntSet。除此之外，值得一看的是米兰的paper on his improvements to containers。
https://stackoverflow.com/questions/6432284
复制相似问题