9

数据

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

python -c 'for f in xrange(4000000):  print f' > input.txt

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

一切都是清单

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

import Data.Conduit
import Data.Text (Text)
import Control.Monad.Trans.Resource (runResourceT)
import qualified Data.Conduit.Binary as CB
import qualified Data.Conduit.Text as CT
import qualified Data.Conduit.List as CL

main :: IO ()
main = do
hs <- (runResourceT
          $ CB.sourceFile "input.txt"
         $$ CT.decode CT.utf8
         =$ CT.lines
         =$ CL.fold (\b a -> a `seq` b `seq` a:b) [])
print $ head hs

并运行它：

[1 of 1] Compiling Main             ( Test.hs, Test.o )
Linking Test ...
"3999999"
2,425,996,328 bytes allocated in the heap
972,945,088 bytes copied during GC
280,665,656 bytes maximum residency (13 sample(s))
5,120,528 bytes maximum slop
533 MB total memory in use (0 MB lost due to fragmentation)

Tot time (elapsed)  Avg pause  Max pause
Gen  0      4378 colls,     0 par    0.296s   0.309s     0.0001s    0.0009s
Gen  1        13 colls,     0 par    0.452s   0.661s     0.0508s    0.2511s

INIT    time    0.000s  (  0.000s elapsed)
MUT     time    0.460s  (  0.465s elapsed)
GC      time    0.748s  (  0.970s elapsed)
EXIT    time    0.002s  (  0.034s elapsed)
Total   time    1.212s  (  1.469s elapsed)

%GC     time      61.7%  (66.0% elapsed)

Alloc rate    5,271,326,694 bytes per MUT second

Productivity  38.3% of total user, 31.6% of total elapsed


real    0m1.481s
user    0m1.212s
sys 0m0.232s

运行时间为 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. 为此，我稍微改变了程序

import Data.Conduit
import Data.Text (Text)
import Control.Monad.Trans.Resource (runResourceT)
import qualified Data.Conduit.Binary as CB
import qualified Data.Conduit.Text as CT
import qualified Data.Conduit.List as CL
import qualified Data.HashSet as HS

main :: IO ()
main = do
hs <- (runResourceT
          $ CB.sourceFile "input.txt"
         $$ CT.decode CT.utf8
         =$ CT.lines
         =$ CL.fold (\b a -> a `seq` b `seq` HS.insert a b) HS.empty)
print $ HS.size hs

如果我们再次运行它

$ ghc -fforce-recomp -O3 -rtsopts Test.hs && time ./Test +RTS -sstderr
[1 of 1] Compiling Main             ( Test.hs, Test.o )
Linking Test ...
4000000
6,544,900,208 bytes allocated in the heap
6,314,477,464 bytes copied during GC
442,295,792 bytes maximum residency (26 sample(s))
8,868,304 bytes maximum slop
1094 MB total memory in use (0 MB lost due to fragmentation)

Tot time (elapsed)  Avg pause  Max pause
Gen  0     12420 colls,     0 par    5.756s   5.869s     0.0005s    0.0034s
Gen  1        26 colls,     0 par    3.068s   3.633s     0.1397s    0.6409s

INIT    time    0.000s  (  0.000s elapsed)
MUT     time    3.567s  (  3.592s elapsed)
GC      time    8.823s  (  9.502s elapsed)
EXIT    time    0.008s  (  0.097s elapsed)
Total   time   12.399s  ( 13.192s elapsed)

%GC     time      71.2%  (72.0% elapsed)

Alloc rate    1,835,018,578 bytes per MUT second

Productivity  28.8% of total user, 27.1% of total elapsed


real    0m13.208s
user    0m12.399s
sys 0m0.646s

这很糟糕：使用了 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秒：

import Data.List (foldl')
import qualified Data.HashSet as HS

main = do
    let hs = foldl' (\b a -> a `seq` b `seq` HS.insert a b) (HS.empty :: HS.HashSet Int) [1..4000000]
    print $ HS.size hs

看起来没有任何好转：

[...]
798 MB total memory in use (0 MB lost due to fragmentation)
[...]
real    0m9.956s

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

4

0 回答 0