Эффективный контейнер хэш-карты в Haskell?

Я хочу подсчитать уникальные блоки, хранящиеся в файле, используя Haskell. Блок представляет собой только последовательные байты с длиной 512, а целевой файл имеет размер не менее 1 ГБ.

Это моя первая попытка.

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

Это работает, но я расстроился с его временем выполнения и использованием памяти. Особенно, когда я сравнивал себя с реализацией С++ и даже с реализацией 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. Но не было никакой заметной разницы.

Пожалуйста, помогите мне улучшить эту программу.

Ответы

Ответ 1

Я не думаю, что вы сможете побить производительность словарей python. Они фактически реализованы в c с годами оптимизаций, введенных в нее, с другой стороны hashmap является новым и не настолько оптимизированным. Так что получить 3-х производительность на мой взгляд достаточно. Вы можете оптимизировать код haskell в определенных местах, но все равно это не имеет большого значения. Если вы все еще настаиваете на повышении производительности, я думаю, вы должны использовать высоко оптимизированную библиотеку c с ffi в вашем коде.

Вот некоторые из подобных обсуждений

начинающие haskell

Ответ 2

Это может быть совершенно неуместно в зависимости от вашего использования, но я немного обеспокоен insertWith (+) block 1. Если ваши счета достигают больших чисел, вы будете накапливать thunks в ячейках хэш-карты. Неважно, что вы использовали ($!), который только заставляет позвоночник - значения, вероятно, все еще ленивы.

Data.HashMap не предоставляет строгой версии insertWith', например Data.Map. Но вы можете реализовать его:

insertWith' :: (Hashable k, Ord k) => (a -> a -> a) -> k -> a 
                                   -> HashMap k a -> HashMap k a
insertWith' f k v m = maybe id seq maybeval m'
    where
    (maybeval, m') = insertLookupWithKey (const f) k v m

Кроме того, вы можете захотеть вывести (но не ввести) список строгих байтов из toBlocks, что ускорит процесс хэширования.

Это все, что у меня есть, но я не гуру производительности.