Mi incuriosisce i problemi di prestazioni tabella hash

Question

Ho letto che le tabelle hash a Haskell avevano problemi di prestazioni (sul Haskell -Cafe nel 2006 e volare di rana Consulenza blog nel 2009), e dato che mi piace Haskell che mi preoccupava.

E 'stato un anno fa, quello che è lo stato oggi (giugno 2010)? Ha il "problema tabella di hash" stato risolto in GHC?

Answer 1

Il problema era che il garbage collector è necessario per attraversare array mutabili di puntatori ( "array in scatola") alla ricerca di puntatori ai dati che potrebbero essere pronti a rilasciare. Inscatolato, array mutabili sono il principale meccanismo di attuazione di una tabella hash, cosicché particolare struttura presentò il problema GC attraversamento. Questo è comune a molte lingue. Il sintomo è eccessivo garbage collection (fino al 95% del tempo trascorso in GC).

La correzione è stato quello di implementare "marcatura carta" nel GC per gli array mutabili di puntatori, che si sono verificati alla fine del 2009. non si dovrebbe vedere GC eccessiva quando si utilizzano le matrici di puntatori mutabili in Haskell ora. Sulle semplici parametri di riferimento, inserimento tabella hash per grandi hash migliorata da 10x.

Si noti che il problema GC a piedi non influisce strutture puramente funzionali , nè gli array disimballati ( come la maggior parte dei dati file parallele , o vettore -come matrici, in Haskell. essa non incide hashtables memorizzati sul mucchio C (come Judy ). Il che significa che non ha influenzato Haskellers giorno per giorno non utilizza le tabelle hash imperativi.

Se si utilizza hashtables in Haskell, non si deve osservare alcun problema ora. Qui, per esempio, è un programma semplice tabella hash che gli inserti 10 milioni di interi in un hash. Farò l'analisi comparativa, in quanto la citazione originale non presenta alcun codice o punti di riferimento.

import Control.Monad
import qualified Data.HashTable as H
import System.Environment

main = do
  [size] <- fmap (fmap read) getArgs
  m <- H.new (==) H.hashInt
  forM_ [1..size] $ \n -> H.insert m n n
  v <- H.lookup m 100
  print v

Con GHC 6.10.2, prima della correzione, l'inserimento di interi 10M:

$ time ./A 10000000 +RTS -s
...
47s.

Con GHC 6.13, dopo la correzione:

./A 10000000 +RTS -s 
...
8s

L'aumento della superficie di default mucchio:

./A +RTS -s -A2G
...
2.3s

Evitare hashtables e utilizzando un IntMap:

import Control.Monad
import Data.List
import qualified Data.IntMap as I
import System.Environment

main = do
  [size] <- fmap (fmap read) getArgs
  let k = foldl' (\m n -> I.insert n n m) I.empty [1..size]
  print $ I.lookup 100 k

E otteniamo:

$ time ./A 10000000 +RTS -s        
./A 10000000 +RTS -s
6s

O, in alternativa, utilizzando una matrice judy (che è un involucro Haskell chiamando codice C tramite l'interfaccia straniera funzione):

import Control.Monad
import Data.List
import System.Environment
import qualified Data.Judy as J

main = do
  [size] <- fmap (fmap read) getArgs
  j <- J.new :: IO (J.JudyL Int)
  forM_ [1..size] $ \n -> J.insert (fromIntegral n) n j
  print =<< J.lookup 100 j

L'esecuzione di questo,

$ time ./A 10000000 +RTS -s
...
2.1s

Quindi, come si può vedere, la questione GC con hashtables è fisso , e ci sono da sempre altre biblioteche e strutture di dati che erano perfettamente adatto. In sintesi, questo è un non-problema.

Nota: a partire dal 2013, si dovrebbe probabilmente basta usare il hashtables pacchetto, che supporta < a href = "http://gregorycollins.net/posts/2011/06/11/announcing-hashtables" rel = "noreferrer"> una serie di tabelle hash mutevoli modo nativo.

Answer 2

Una domanda come questa può davvero essere risolta solo da esperimento. Ma se non si ha il tempo o il denaro per fare esperimenti, si deve chiedere ad altre persone quello che pensano. Quando lo fa, si potrebbe prendere in considerazione l'origine e considerare se le informazioni fornite sono stati riesaminati o controllati in alcun modo.

Jon Harrop ha avanzato alcune affermazioni interessanti circa Haskell. Mi permetto di suggerire che si esegue una ricerca su Google Gruppi e altrove per la prova di competenza di Harrop in Haskell, Lisp, e di altri linguaggi funzionali. Si potrebbe anche leggere il lavoro di Chris Okasaki e Andy Gill sugli alberi Patricia in Haskell, vedere come la loro competenza è considerata. È inoltre possibile trovare le cui rivendicazioni, se del caso, sono stati verificati da una terza parte. Poi si può fare la vostra propria mente quanto seriamente prendere diversi reclami della gente riguardo le prestazioni dei diversi linguaggi funzionali.

Oh, e non alimentare il troll.

---

P.S. Sarebbe abbastanza ragionevole per voi di fare i propri esperimenti, ma forse non necessaria, dal momento che i fidati Don Stewart presenta alcune belle microbenchmarks nella sua bella risposta. Ecco un addendum alla risposta di Don:

---

Addendum: Utilizzo del codice di Don Stewart su un AMD Phenom 9850 Black Edition con clock a 2,5 GHz con 4 GB di RAM, in modalità a 32 bit, con ghc -O,

• Con l'heap predefinito, il IntMap è del 40% più veloce rispetto alla tabella di hash.
• Con il mucchio 2G, la tabella hash è del 40% più veloce rispetto al IntMap.
• Se vado a dieci milioni di elementi con il mucchio di default, il IntMap è quattro volte più veloce rispetto alla tabella di hash (tempo di CPU) o due volte più veloce da muro- orologio in tempo.

Sono un po 'sorpreso da questo risultato, ma rassicurati sul fatto che le strutture di dati funzionali eseguire abbastanza bene. E confermato nella mia convinzione che la pena davvero di punto di riferimento il codice alle condizioni reali in cui sta andando per essere utilizzato.

Answer 3

In breve, anche con la correzione nell'ultima GHC, Haskell è ancora in grado di fornire un dizionario (mutabile o immutabile), che è competitivo efficiente.

tabelle hash di Haskell erano 32 × più lento di alternative come C ++ e .NET con GHC 6.10. Che era parzialmente dovuto ad una insetto prestazioni nella spazzatura collettore GHC che è stato fissato per GHC 6.12.2 . Ma i risultati di Simon Marlow ci mostrano solo un miglioramento del 5 × prestazione che lascia ancora le tabelle hash di Haskell molte volte più lento rispetto alla maggior parte delle alternative.

alternative puramente funzionale sono anche molto più lento di una tabella hash decente. Ad esempio, IntMap di Haskell è 10 × più lento di tabella di hash di .NET .

Utilizzando F # 2010 e l'ultima Haskell Platform 2010.2.0.0 (pubblicato ieri!) con GHC 6.12.3 su questo 2.0GHz E5405 Xeon a 32 bit di Windows Vista per inserire 20M INT> int legature in una tabella hash vuoto troviamo che Haskell è ancora 29 × più lento di F # in tempo reale e oltre 200 × più lento in termini di tempo di CPU, perché il Haskell brucia tutti i core:

GHC 6.12.3 Data.HashTable: 42.8s (new!)
.NET hash table:            1.47s

A condizione che si esegue solo microbenchmarks di breve durata è possibile disattivare il garbage collector GHC come suggerisce Don Stewart sopra. Con la richiesta di una generazione vivaio così grande che questo particolare programma non sarà mai riempirlo, ha portato il tempo per la tabella hash Haskell fino a 1.5s solo qui. Tuttavia, ciò mina completamente i punto di avere una generazione vivaio e verrà massicciamente interferisca con il funzionamento di altri codici perché i valori appena allocate saranno ora sempre freddo nella cache (che è il motivo per cui la generazione vivaio è tipicamente la dimensione della cache L2, ordini di grandezza più piccolo di questo).