Neugierig auf die HashTable Performance-Probleme

StackOverflow https://stackoverflow.com/questions/3058529

  •  27-09-2019
  •  | 
  •  

Frage

las ich, dass Hash-Tabellen in Haskell Performance-Probleme hatten (auf dem Haskell -Cafe 2006 und Frog Consultancy fliegen Blog im Jahr 2009), und da ich wie Haskell besorgt es mir.

, die vor einem Jahr war, was ist der Status jetzt (Juni 2010)? Hat das "Hash-Tabelle Problem" wurde in GHC fixiert?

War es hilfreich?

Lösung

Das Problem war, dass der Garbage Collector erforderlich ist wandelbar Arrays von Zeigern ( „boxed arrays“) für Zeiger auf Daten suchen zu durchqueren, die freizugeben bereit sein könnten. Boxed, wandelbar Arrays sind der Hauptmechanismus, der eine Hash-Tabelle für die Umsetzung, so dass bestimmte Struktur des GC-Traversal-Problem auftauchte. Dies ist die in vielen Sprachen. Das Symptom ist übermäßige Garbage Collection (bis zu 95% der Zeit in GC ausgegeben).

Das Update war an implementieren "Kartenmarkierung" in der GC für veränderbare Arrays von Zeigern, die Ende 2009 aufgetreten sollten Sie nicht übermäßig GC sehen, wenn veränderbare Arrays von Zeigern in Haskell jetzt verwenden. Auf dem einfachen Benchmarks hashtable Einfügung für großen Hashes von 10x verbessert.

Beachten Sie, dass das GC Walking Problem nicht betroffen rein funktionale Strukturen , noch unboxed Arrays ( wie die meisten Daten parallel Arrays oder vektor -ähnlichen Arrays in Haskell. Ebenso wenig ist die Hash-Tabellen gespeichert auf dem C-Heap (wie judy ). Was bedeutet, dass es nicht beeinflussen Tag zu Tag Haskellers nicht zwingend notwendig, Hash-Tabellen.

Wenn Sie Hash-Tabellen in Haskell verwenden, sollten Sie Problem jetzt nicht beobachten. Hier zum Beispiel ist ein einfaches Hash-Tabelle Programm, dass Einsätze 10 Millionen Ints in einen Hash. Ich werde das Benchmarking tun, da das ursprüngliche Zitat keinen Code oder Benchmarks Nicht bestimmt. 

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

Mit GHC 6.10.2, vor dem Update, 10M Ints einfügen: 

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

Mit GHC 6,13, nach dem Update: 

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

Die Erhöhung des Standard-Heap-Bereich: 

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

Vermeiden von Hash-Tabellen und unter Verwendung eines 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

Und wir bekommen: 

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

oder alternativ eine judy Array (die eine Haskell ist Wrapper-C-Code durch die Fremdfunktionsschnittstelle aufruft): 

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

Ausführen dieses, 

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

So, wie Sie sehen können, das GC Problem mit Hash-Tabellen ist festgelegt , und es hat immer andere Bibliotheken und Datenstrukturen , die perfekt geeignet waren. Zusammengefasst ist dies kein Thema.

Hinweis: ab 2013, sollten Sie wahrscheinlich verwenden Sie einfach die Hashtables Paket, das unterstützt < a href = "http://gregorycollins.net/posts/2011/06/11/announcing-hashtables" rel = "noreferrer"> eine Reihe von wandelbaren Hashtables nativ.

Andere Tipps

Eine Frage wie diese kann wirklich nur durch das Experiment abgerechnet. Aber wenn Sie nicht die Zeit oder Geld haben Experimente zu tun, müssen Sie andere Leute fragen, was sie denken. Wenn Sie dies tun, können Sie die Quelle prüfen und prüfen, ob angesichts der Informationen, die in irgendeiner Weise überprüft oder überprüft wurde.

Jon Harrop hat einige interessante Aussagen über Haskell vorgerückt. Lassen Sie mich vorschlagen, dass Sie auf Google Groups zu suchen und an anderer Stelle zum Nachweis von Expertise des Harrop in Haskell, Lisp und anderen funktionalen Sprachen. Sie könnten auch die Arbeit von Chris Okasaki und Andy Gill auf Patricia Bäume in Haskell lesen, sehen, wie sie ihre Kompetenz angesehen wird. Sie können auch deren Ansprüche, wenn überhaupt finden, wird von einem Dritten geprüft. Dann können Sie Ihre eigene Meinung bilden, wie ernst unterschiedliche Menschen Behauptungen über die Leistung der verschiedenen funktionalen Sprachen zu nehmen.

Oh, und Sie den Troll nicht ernähren.

P. S. Es wäre durchaus sinnvoll für Sie Ihre eigenen Experimente zu tun, aber vielleicht nicht notwendig, da die treuen Don Stewart präsentiert einige schöne Microbenchmarks in seiner feinen Antwort. Hier ist ein Nachtrag zu Don Antwort:

Nachtrag: Code Don Stewart Verwendung auf einer AMD Phenom 9850 Black Edition getaktet mit 2,5 GHz mit 4 GB RAM, in 32-Bit-Modus, mit ghc -O,

  • Mit den Standard-Haufen, die IntMap ist 40% schneller als die Hash-Tabelle.
  • Mit dem 2G-Haufen, die Hash-Tabelle ist 40% schneller als die IntMap.
  • Wenn ich auf zehn Millionen Elemente mit dem Standard-Heap gehen, die IntMap ist viermal schneller als die Hash-Tabelle (CPU-Zeit) oder doppelt so schnell von Wand- Uhrzeit.

Ich bin ein wenig überrascht über dieses Ergebnis, aber beruhigt, dass funktionale Datenstrukturen recht gut ab. Und in meiner Überzeugung bestätigt, dass es wirklich zu Benchmark zahlt Ihren Code unter den tatsächlichen Bedingungen, in denen verwendet wird, es wird.

Kurz gesagt, auch mit dem Update in der neuesten GHC, Haskell ist nach wie vor nicht in der Lage, einen Wörterbuch (wandelbar oder unveränderlich) bereitzustellen, die kompetitiv effizient ist.

Haskells Hash-Tabellen waren 32 × langsamer als Alternativen wie C ++ und .NET mit GHC 6.10. Dies war teilweise auf einen Leistung Fehler in der GHC Garbage Collector, der für die feste wurde GHC 6.12.2 . Aber Simon Marlow Ergebnisse zeigen, dass es nur eine 5 × Leistungsverbesserung, die noch Blätter Haskells Hash-Tabellen viele Male langsamer als die meisten Alternativen.

Rein funktionale Alternativen sind auch viel langsamer als eine anständige Hash-Tabelle. Zum Beispiel Haskells IntMap ist 10 x langsamer als Hash-Tabelle .NET .

Mit F # 2010 und die Haskell Platform neueste 2010.2.0.0 (gestern veröffentlicht!) mit GHC 6.12.3 auf dieser 2,0 GHz E5405 Xeon 32-Bit-Windows Vista laufen wir zum einfügen 20M int-> int Bindungen in eine leere Hash-Tabelle finden, dass Haskell ist immer noch 29 × langsamer als F # in Echtzeit und über 200 × langsamer hinsichtlich der CPU-Zeit, da die Haskell alle Kerne brennt: 

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

Sofern Sie nur kurzlebig Microbenchmarks laufen Sie GHC Garbage Collector deaktivieren kann als Don Stewart schlägt oben. Mit der Frage nach einem Kindergarten Generation so groß, dass dieses besondere Programm wird es nie füllen, brachte er die Zeit für die Tabelle Haskell Hash auf nur hier 1,5s. Dies ist jedoch völlig den ganzen Punkt untergräbt eine Kindergeneration mit und wird massiv auf die Leistung anderen Code verschlechtern, weil frisch zugewiesenen Werte werden nun immer kalt im Cache sein (weshalb die Kindergarten Generation der Regel die Größe der L2-Cache, Größenordnung kleiner als diese).

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top