Efektywny pojemnik mapy haszującej w Haskell?

Question

Chcę policzyć unikalne bloki przechowywane w pliku przy użyciu Haskell. Blok to po prostu kolejne bajty o długości 512, a plik docelowy ma co najmniej 1 GB.

To jest moja pierwsza próba.

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 

Działa, ale jestem sfrustrowany jego czasem wykonania i zużyciem pamięci. Especilly, gdy porównałem go z wersją C++, a nawet implementacją Pythona wymienioną poniżej, był wolniejszy 3 ~ 5x i zużywał 2 ~ 3x więcej miejsca w pamięci.

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) 

myślałem, że to głównie ze względu na wdrożenie HashMap i spróbował inne implementacje takich jak hashmap, hashtables i unordered-containers. Ale nie było żadnej zauważalnej różnicy.

Proszę, pomóż mi ulepszyć ten program.

Answer 1

Nie sądzę, że będziesz w stanie pokonać wydajność słowników Pythona. W rzeczywistości są one wdrażane za pomocą wielu lat optymalizacji, z drugiej strony hashmap jest nowy i niezbyt zoptymalizowany. Wydaje mi się, że uzyskanie 3-krotnego wyniku jest wystarczająco dobre. Możesz zoptymalizować kod haskell w niektórych miejscach, ale nadal nie będzie to miało większego znaczenia. Jeśli nadal jesteś nieugięty w kwestii zwiększenia wydajności, myślę, że powinieneś użyć wysoce zoptymalizowanej biblioteki c z ffi w swoim kodzie.

Oto niektóre z podobnych dyskusji

haskell beginners

Answer 2

To może być całkowicie bez znaczenia w zależności od użytkowania, ale jestem lekko zaniepokojony insertWith (+) block 1. Jeśli twoje hrabiny osiągną wysokie liczby, będziesz gromadzić strzępy w komórkach mapy hash. Nie ma znaczenia, że ​​użyłeś ($!), który tylko wymusza kręgosłup - wartości są prawdopodobnie nadal leniwy.

Data.HashMap nie zawiera ścisłej wersji insertWith', takiej jak Data.Map. Ale można wdrożyć go:

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 

Również może chcesz wyjścia (ale nie wejście) listę ścisłych ByteStrings z toBlocks, co uczyni mieszania szybciej.

To wszystko, co mam - nie jestem jednak guru wydajności.