问题标签 [unordered-containers]

数据

首先，让我们生成一些输入，这样我们就有了具体的数据要讨论：

这将生成一个文件input.txt，其中包含从 0 到 3999999 的数字，每个数字占一行。这意味着我们应该有一个包含 4,000,000 行的文件，总计 30,888,890 字节，大约 29 MiB。

一切都是清单

对，让我们将所有内容加载到内存中[Text]：

并运行它：

运行时间为 1.4 秒，占用 533 MB 内存。在Haskell Wiki 的 Memory Footprint中，4MText实例应该占用 6 个字 + 2N 字节的内存。我是 64 位的，所以一个字是 8 个字节。这意味着它应该是 (6 * 8 字节 * 4000000) + (2*26888890) 字节 = 234 MiB。（26888890 是input.txt不是换行符的所有字节）。对于将包含所有内容的列表，我们需要额外的 (1 + 3N) 个单词 + N * sizeof(v) 的内存。sizeof(v) 应该是 8，因为它将是指向Text. 然后该列表应使用 (1 + 3 * 4000000) * 8 字节 + 4000000 * 8 字节 = 122MiB。因此，总共（列表 + 字符串）我们预计使用了 356 MiB 的内存。我不知道我们内存的 177 MiB (50%) 的差异在哪里，但现在让我们忽略它。

大哈希集

最后，我们将来到我真正感兴趣的用例：将所有单词存储在一个大的Data.HashSet. 为此，我稍微改变了程序

如果我们再次运行它

这很糟糕：使用了 13 秒和 1094MiB 的内存。内存占用页面列出了 4.5N 个字 + N * sizeof(v) 的哈希集，应该变成 (4.5 * 4000000 * 8bytes) + (4000000 * 8bytes) = 167 MiB。添加 stings 的存储空间 (234 MiB)，我预计 401 MiB 是两倍多，而且感觉很慢:(。

思想实验：手动管理内存

作为一个思想实验：使用一种我们可以手动控制内存布局并使用开放寻址实现 HashSet 的语言，我希望以下是大小。为了公平起见，我希望字符串仍然是 UTF-16（这就是Data.Text做）。鉴于总共有 26888890 个字符（不含换行符），UTF-16 中的字符串应该大约为 53777780 字节 (2 * 26888890) = 51 MiB。我们需要存储每个字符串的长度，即 8 字节 * 4000000 = 30 MiB。我们需要空间来存储散列集（4000000 * 8 字节），同样是 30 MiB。鉴于散列集通常呈指数增长，人们可能会期望 32 MiB 或 64 MiB 最坏的情况。让我们来看最坏的情况：表格 64 MiB + 字符串长度 30 MiB + 实际字符串数据 51 MiB，总计 145 MiB。

因此，鉴于这Data.HashSet不是存储字符串的专门实现，计算出来的 401 MiB 不会太糟糕，但实际使用的 1094 MiB 似乎有点浪费。

问题终于:)

所以我们终于到了那里：

• 我的计算错误在哪里？
• 我的实现中是否存在一些问题，或者 1094 MiB 真的是我们能得到的最好的吗？

版本和东西

• 我可能应该使用ByteStrings 而不是Text因为我只需要 ascii 字符
• 我在 GHC 7.10.1 和unordered-containers-0.2.5.1

比较：4,000,000Int秒：

看起来没有任何好转：

对于 4M Ints，这几乎是 800 MiB！

直到大约一个月前，一切都很好......

突然我得到

从代码：

我想知道你是否介意帮我破译它到底在告诉我什么？我知道我的结果存在某种类型的语法错误，但我不明白发生了什么变化以及为什么它不像以前那样编译？

参考：https ://github.com/berkson/berkson.github.io/blob/source/source/blog.hs#L330

我正在研究一个引用unordered-containers-0.2.8.0:Data.HashMap.Base.HashMap.

包含该类型值的模块未在导入部分说明它来自何处，我无法导入Data.HashMap.Base。

然而:browsing 表明该类型至少在某些情况下是抽象的。

这是否意味着我可以从其中一个Lazy或多个Strict变体中导入函数？

在处理哈希映射时，我看到了一些处理哈希冲突的策略，但我们想出了一些不同的方法。我想知道这是否是新事物。

此版本的哈希映射仅在哈希和将被哈希的数据结构是可盐化的情况下才有效。hashable（在 Haskell 中就是这种情况，我们建议实施这种方法。）

这个想法是，不是在哈希映射的每个单元格中存储一个列表或数组，而是存储一个递归哈希映射。此递归哈希映射的唯一区别是您使用不同的盐。这样，哈希映射的一个级别上的哈希冲突很可能不是下一级的哈希冲突。结果，插入这样的哈希映射不再是 O（此哈希上的冲突数），而是 O（此上的冲突以递归方式发生的级别数），这很可能更好。

更详细的解释和实现可以在这里找到：

https://github.com/tibbe/unordered-containers/pull/217/files/58af4519ace34c5f7d3c1359907ff75e27b9cdb8#diff-ba23e0f18c79cb873ac5375367524cfaR114

我一直在尝试使用 ghc-heap-view 包和它提供的实用程序来确保 Haskell 程序的内存模型的严格性，当我注意到我HashMap的 s 在一系列插入时似乎不在 NF 中. 我尝试打印堆树，确实显示了一些 thunk。然后我尝试了另一种插入元素的方法（使用unionand singleton），这次它很严格。

有人可以解释为什么会这样，并建议我是否可以做任何事情来使insert行为与其他方法相同？

这是我的测试代码：

这是输出：