Contenitore di mappe hash efficiente in Haskell?

Question

Voglio contare i blocchi unici memorizzati in un file usando Haskell. Il blocco è solo byte consecutivi con una lunghezza di 512 e il file di destinazione ha una dimensione di almeno 1 GB.

Questo è il mio tentativo iniziale.

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 

Funziona, ma sono stato frustrato dal tempo di esecuzione e dall'utilizzo della memoria. Specialmente quando ho confrontato con quelli di C++ e persino con l'implementazione di Python elencati di seguito, era 3 ~ 5 volte più lento e consumava 2 ~ 3 volte più spazio di memoria.

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) 

ho pensato che fosse dovuto principalmente alla realizzazione hashmap, e provato altre implementazioni, come hashmap, hashtables e unordered-containers. Ma non c'era alcuna differenza evidente.

Per favore aiutatemi a migliorare questo programma.

Answer 1

Non penso che sarete in grado di battere le prestazioni dei dizionari Python. In realtà sono implementati in c con anni di ottimizzazioni, mentre hashmap è nuovo e non molto ottimizzato. Quindi, ottenere una performance 3x secondo me è abbastanza buono. Puoi ottimizzare il tuo codice haskell in determinati punti, ma non importa molto. Se sei ancora irremovibile sull'aumento delle prestazioni, penso che dovresti usare una libreria c altamente ottimizzata con ffi nel tuo codice.

Ecco alcune delle discussioni simili

haskell beginners

Answer 2

Questo può essere del tutto irrilevante a seconda del loro utilizzo, ma io sono un po 'preoccupato per insertWith (+) block 1. Se i tuoi conteggi raggiungono numeri elevati, accumuli thunk nelle celle della mappa hash. Non importa che tu abbia usato ($!), che costringe solo la colonna vertebrale - i valori sono probabilmente ancora pigri.

Data.HashMap non fornisce una versione rigorosa insertWith' come Data.Map. Ma si può implementarlo:

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 

Inoltre, si consiglia di uscita (ma non in ingresso) un elenco di severe stringhe di byte da toBlocks, che renderà più veloce l'hashing.

Questo è tutto ciò che ho - io non sono un guru delle prestazioni, però.