haskell - Haskell 中高效的 HashMap 容器？

Question

我想使用 Haskell 计算存储在文件中的唯一 block 。
该 block 只是长度为 512 的连续字节，目标文件的大小至少为 1GB。

这是我的初步尝试。

import           Control.Monad
import qualified Data.ByteString.Lazy as LB
import           Data.Foldable
import           Data.HashMap
import           Data.Int
import qualified Data.List            as DL
import           System.Environment

type DummyDedupe = Map LB.ByteString Int64

toBlocks :: Int64 -> LB.ByteString -> [LB.ByteString]
toBlocks n bs | LB.null bs = []
              | otherwise = let (block, rest) = LB.splitAt n bs
                            in block : toBlocks n rest

dedupeBlocks :: [LB.ByteString] -> DummyDedupe -> DummyDedupe
dedupeBlocks = flip $ DL.foldl' (\acc block -> insertWith (+) block 1 $! acc)

dedupeFile :: FilePath -> DummyDedupe -> IO DummyDedupe
dedupeFile fp dd = LB.readFile fp >>= return . (`dedupeBlocks` dd) . toBlocks 512

main :: IO ()
main = do
  dd <- getArgs >>= (`dedupeFile` empty) . head
  putStrLn . show . (*512) . size $ dd
  putStrLn . show . (*512) . foldl' (+) 0 $ dd

它有效，但我对它的执行时间和内存使用感到沮丧。特别是当我与下面列出的 C++ 甚至 Python 实现进行比较时，它慢了 3~5 倍，并且消耗了 2~3 倍的内存空间。

import os
import os.path
import sys

def dedupeFile(dd, fp):
    fd = os.open(fp, os.O_RDONLY)
    for block in iter(lambda : os.read(fd, 512), ''):
        dd.setdefault(block, 0)
        dd[block] = dd[block] + 1
    os.close(fd)
    return dd

dd = {}
dedupeFile(dd, sys.argv[1])

print(len(dd) * 512)
print(sum(dd.values()) * 512)

我以为主要是hashmap实现的原因，尝试了 hashmap等其他实现, hashtables和 unordered-containers .
但是并没有什么明显的区别。

请帮助我改进这个程序。

Answer 1

我认为您无法击败 python 字典的性能。它们实际上是在 c 中实现的，并在其中进行了多年的优化，另一方面，hashmap 是新的，并没有那么优化。因此，在我看来，获得 3 倍的性能就足够了。您可以在某些地方优化您的 haskell 代码，但这仍然无关紧要。如果您仍然坚持提高性能，我认为您应该在代码中使用高度优化的 c 库和 ffi。

以下是一些类似的讨论

haskell beginners