Haskell benötigt mehr Speicher als Python, wenn ich Map aus Datei lese. Warum?

Es ist ein bisschen spät, aber ich habe das ein wenig studiert und halte die Aussage von Dietrich Epp für richtig, kann aber etwas vereinfacht werden. Beachten Sie, dass es in der Python-Datei keine echte Python-Programmierung zu geben scheint: Sie orchestriert eine sehr einfache Sequenz von Aufrufen zu C-String-Operationen und dann zu einer C-Hash-Tabellenimplementierung. (Dies ist oft ein Problem mit wirklich einfachen Python v. Haskell-Benchmarks.) Der Haskell dagegen baut eine immense persistente Map auf, die ein ausgefallener Baum ist. Die Hauptpunkte der Opposition sind also C vs Haskell und Hashtable-with-destructive-update vs persistente Karte. Da sich die Eingabedatei kaum überschneidet, enthält die zu konstruierende Baumstruktur alle Informationen in der Eingabezeichenfolge, von denen einige wiederholt und dann mit einem Stapel Haskell-Konstruktoren neu angeordnet werden. Dies ist, denke ich, die Quelle des Alarms, den Sie erleben, aber es kann erklärt werden.

Vergleichen Sie diese beiden Dateien, eine mit ByteString:

und der andere ein Text-ähnliches Äquivalent:

Auf meinem Computer dauert der Python / C nur knapp 6 Sekunden, die Bytestring-Datei braucht 8 Sekunden und die Textdatei knapp über 10.

Die bytestring-Implementierung scheint etwas mehr Speicher zu verwenden als der python, die text-Implementierung deutlich mehr. Die Textimplementierung benötigt mehr Zeit, da sie natürlich eine Umwandlung in Text hinzufügt und dann Textoperationen verwendet, um die Zeichenfolgen- und Textvergleiche zu unterbrechen, um die Karte zu erstellen.

Hier ist ein Versuch, die Speicherphänomene im Textfall zu analysieren. Zuerst haben wir die Bytestring im Speicher (130m). Sobald der Text erstellt ist (~ 250m, um unwissenschaftlich zu beurteilen, was in top vor sich geht), wird die Bytekette während des Konstruierens der Struktur als Garbage Collection erfasst. Am Ende benötigt der Textbaum (~ 380m) mehr Speicher als der Bytestringbaum (~ 260m), weil die Textfragmente im Baum größer sind. Das Programm als Ganzes verwendet mehr, weil der Text, der während der Baumkonstruktion im Speicher gehalten wird, selbst größer ist. Um es grob auszudrücken: Jedes weiße Leerzeichen wird in einen Baumkonstruktor und zwei Textkonstruktoren zusammen mit der Textversion von dem, was das erste "Wort" der Zeile war und was auch immer die Textdarstellung des nächsten Wortes ist. Das Gewicht der Konstruktoren scheint in jedem Fall etwa 130 m zu betragen, also verwenden wir im letzten Moment der Konstruktion des Baumes etwa 130 m + 130 m + 130 m = 390 m im Byteketten-Fall und 250 m + 130 m + 250 m = 630 m im Textfall.

In der Haskell-Version passiert viel, was in der Python-Version nicht passiert.

• readFile verwendet Lazy IO, was im Allgemeinen etwas merkwürdig ist. Ich würde im Allgemeinen faulen IO vermeiden.

• Die Datei wird als Bystring in Zeilen aufgeteilt, die dann als UTF-8 dekodiert werden. Dies scheint ein wenig unnötig, angesichts der Existenz von Text IO-Funktionen.

• Die Haskell-Version verwendet einen Baum ( Data.Map ), während die Python-Version eine Hash-Tabelle verwendet.

• Die Strings sind alle faul, was wahrscheinlich nicht nötig ist, wenn sie relativ kurz sind. Lazy Strings haben ein paar Worte Overhead pro String, die sich addieren können. Sie könnten die faulen Strings fusionieren, oder Sie könnten die Datei auf einmal lesen, oder Sie könnten etwas wie Conduit verwenden.

• GHC verwendet einen Kopier-Collector, während die Standard-Python-Implementierung malloc() mit Referenzzählung und gelegentlichem GC verwendet. Diese Tatsache allein kann je nach Programm zu großen Unterschieden bei der Speichernutzung führen.

• Wer weiß, wie viele Thunks in der Haskell-Version erstellt werden.

• Es ist unbekannt, ob Sie Optimierungen aktiviert haben.

• Es ist unbekannt, wie viel die Haskell-Version langsamer macht.

• Wir haben Ihre Datendatei nicht, so dass wir sie nicht wirklich selbst testen können.