Ein komprimierendes Utility auf Basis von Huffman-Codes in Haskell bauen

 (lazamar.github.io)
1 Punkte von GN⁺ 2024-07-06 | 1 Kommentare | Auf WhatsApp teilen
  • Durch die Implementierung eines Huffman-Coding-Kompressors in nur rund 150 Zeilen Haskell wird gezeigt, wie sich beliebige Binärdateien mit konstantem Speicherverbrauch kodieren und dekodieren lassen.
  • Huffman-Codes weisen häufig auftretenden Werten kurze Bitfolgen zu und ermöglichen es dem Decoder dank der Eigenschaft prefix-free code, Bitfolgen eindeutig zu interpretieren.
  • Die Implementierung baut mit FreqMap, HTree und CodeMap aus einer Häufigkeitstabelle einen Baum auf und erzeugt Ergebnisse schrittweise durch lazy evaluation mit concatMap und einem rekursiven Decoder.
  • Binärdateien werden mit Data.ByteString.Char8 behandelt, sodass Bytes wie Char verarbeitet werden können; vor dem komprimierten Ergebnis wird die Häufigkeitstabelle serialisiert, und die Bitfolge wird byteweise mit Padding gespeichert.
  • Im Test schrumpfte War and Peace von 3,2M auf 1,9M, und die 106M große ghcup-Binärdatei auf 84M; die maximale Resident Set Size wurde dabei mit unter 300KB beobachtet.

Grundidee der Kompression mit Huffman-Codes

  • Ziel ist es, mit Huffman coding in nur rund 150 Zeilen Haskell ein Datenkompressions-Utility zu implementieren.
  • Der vollständige Code ist im GitHub-Repository veröffentlicht.
  • Huffman-Codes weisen jedem Zeichen oder Wert eine eindeutige Bitfolge zu.
    • Häufig vorkommende Werte erhalten kurze Bitfolgen.
    • Selten vorkommende Werte erhalten lange Bitfolgen.
    • Da häufige Werte mit weniger Bits als in ihrer ursprünglichen Darstellung kodiert werden, entsteht der Kompressionseffekt.
  • Im Beispiel aaab ergibt sich mit a = 1 und b = 0 das Resultat 1110.
    • Das ist ein Beispiel dafür, wie eine Zeichenkette, die in UTF-8 4 Byte benötigen würde, in einem halben Byte dargestellt werden kann.

Prefix-free code und Huffman-Baum

  • Damit das Dekodieren nicht mehrdeutig ist, darf kein Codewort ein Präfix eines anderen Codeworts sein.
    • Wenn man etwa in aaabc a = 1, b = 10 und c = 01 zuweist, könnte 101 mehrdeutig sein: ac oder ba.
  • Ein prefix-free code lässt sich als vollständiger Binärbaum darstellen.
    • Alle Werte werden in Blättern abgelegt.
    • Die linke Kante wird mit 1, die rechte Kante mit 0 markiert.
    • Der Pfad von der Wurzel zum Blatt ist das Codewort des jeweiligen Werts.
  • Ein Huffman-Baum wird erzeugt, indem seltene Werte von unten nach oben zusammengefasst werden.
    • Jedes Zeichen wird zusammen mit seiner Auftretenshäufigkeit als Knoten angelegt.
    • Die beiden Knoten mit der kleinsten Häufigkeit werden zu einem Baum verbunden.
    • Das Gewicht des neuen Baums ist die Summe der Gewichte beider Knoten.
    • Das wird wiederholt, bis nur noch ein einziger Baum übrig ist.
  • Dadurch liegen häufiger vorkommende Werte näher an der Wurzel und erhalten kürzere Codewörter.

Aufbau des Haskell-Encoders

  • Die wichtigsten Typen der Implementierung sind Bit, Code, FreqMap, CodeMap, Weight und HTree.
    • Bit ist One oder Zero.
    • Code ist [Bit].
    • FreqMap ist Map Char Int und speichert die Anzahl der Vorkommen je Zeichen.
    • CodeMap ist Map Char Code und speichert das Codewort je Zeichen.
    • HTree ist Leaf Weight Char oder Fork Weight HTree HTree.
  • HTree kann anhand seines Gewichts verglichen werden, was Sortierung und Einfügen beim Aufbau des Baums vereinfacht.
  • countFrequency berechnet die Anzahl der Vorkommen jedes Zeichens in einer Zeichenkette.
  • buildTree wandelt eine FreqMap in eine Liste von Blättern um, sortiert sie und verbindet wiederholt die kleinsten zwei Knoten zu einem Huffman-Baum.
  • buildCodes durchläuft den Baum und hängt links One und rechts Zero an, um die Codewörter für alle Zeichen zu erzeugen.
  • encode :: FreqMap -> String -> [Bit] baut aus der FreqMap Baum und Code-Map auf und ersetzt dann jedes Zeichen der Eingabe durch sein Codewort, sodass eine Liste von Bits entsteht.

Schrittweise Verarbeitung mit lazy evaluation

  • Die zentrale Transformation beim Kodieren ist concatMap codeFor str.
    • Konzeptionell wird dabei [Char] erst in [[Bit]] umgewandelt und anschließend zu [Bit] abgeflacht.
    • Dank lazy evaluation in Haskell funktioniert das nicht so, dass zuerst die gesamte Eingabe kodiert und erst danach zusammengefügt wird.
  • Die kleinen Listen werden von links nach rechts verarbeitet und in eine große Ergebnisliste abgeflacht.
    • Der Tail der Ergebnisliste bleibt als noch nicht ausgewerteter Thunk erhalten.
    • Erst wenn Werte gebraucht werden, wird der nächste Teil berechnet.
  • Der Decoder erzeugt Ergebnisse auf dieselbe Weise schrittweise.
    • decode :: FreqMap -> [Bit] -> String bewegt sich je nach Bit nach links oder rechts im Baum.
    • Wird ein Blatt erreicht, wird das Zeichen ausgegeben und wieder an der Wurzel begonnen.
    • Das wird wiederholt, bis die Gesamtzahl der dekodierten Zeichen dem Gewicht des Huffman-Baums entspricht.
  • Der Decoder stoppt also nicht am Ende der Eingabe-Bitliste, sondern anhand der Anzahl der Zeichen.
    • Der Grund ist, dass bei der Serialisierung am Ende Padding-Bits ergänzt werden, um auf Byte-Grenzen auszurichten.
  • Die Funktion go gibt beim Erreichen eines Blatts eine Liste zurück, deren Head bekannt ist und deren Tail ein rekursiver Aufruf ist; dadurch kann das Ergebnis ausgewertet werden, bevor die gesamte Rekursion abgeschlossen ist.

Verarbeitung von Binärdateien und Serialisierung

  • Binärdaten lassen sich als Wiederholung eines von 256 möglichen Bytes betrachten.
  • Data.ByteString.Char8 ermöglicht es, ein ByteString mit Char-Operationen zu behandeln, wobei jedes Char auf 8 Bit gekürzt wird.
    • Dadurch lässt sich derselbe textorientierte Coder mit wenigen Änderungen auch auf Binärdaten anwenden.
  • In der komprimierten Datei steht zuerst die für das Dekodieren nötige FreqMap, danach folgt die kodierte Bitfolge.
  • serializeFreqMap schreibt die Häufigkeitstabelle in folgendem Format.
    • Die Länge der Map wird als Word8 gespeichert, allerdings um 1 reduziert, um den Wertebereich vollständig auszunutzen.
    • Jeder Eintrag speichert den Schlüssel als Word8 und den Häufigkeitswert als 64-Bit-Ganzzahl im Big-Endian-Format.
  • serialize erzeugt mit dem Put-Monad aus dem binary-Paket ein ByteString.
    • Es liest Bits einzeln ein und füllt damit jeweils ein Byte.
    • Sobald 8 Bit voll sind, wird mit putWord8 geschrieben.
    • Das letzte Byte wird mit Zero aufgefüllt.

Deserialisierung und Strategie für konstanten Speicherverbrauch

  • deserializeFreqMap liest die serialisierte Häufigkeitstabelle mit Data.Binary.Get ein.
    • Zuerst wird die Länge gelesen und um 1 erhöht, um die tatsächliche Zahl der Einträge zu erhalten.
    • Dann werden je Eintrag ein Word8-Schlüssel und eine 64-Bit-Häufigkeit gelesen, um die FreqMap wiederherzustellen.
  • Der restliche Eingabeteil wird nicht komplett mit Get verarbeitet, sondern nach dem Offset direkt aus dem ByteString entnommen und in eine Bitliste umgewandelt.
  • deserialize liefert (FreqMap, [Bit]) zurück, wobei [Bit] eine lazy Liste ist, die nicht sofort vollständig ausgewertet wird.
    • Ihre Länge abzufragen sollte vermieden werden, weil dadurch die gesamte Liste ausgewertet werden müsste.
  • Der Grund, nicht die komplette Eingabe mit Get zu verarbeiten, ist, dass das bind des Monads die Reihenfolge erzwingt.
    • Das würde zu einer Struktur führen, in der die Liste erst zurückgegeben werden kann, wenn die gesamte Eingabe verarbeitet ist.
  • Die Strategie für konstanten Speicherverbrauch besteht darin, beim Schreiben der Ausgabebits jeweils nur den nächsten kleinen Teil der Eingabe auszuwerten.
    • Ein Teil des ByteString wird ausgewertet und das entsprechende Dateifragment eingelesen.
    • Verarbeitete Ausgabe wird in die Datei geschrieben.
    • Nicht mehr referenzierte Eingabefragmente und Bitlisten können vom Garbage Collector freigegeben werden.
  • Da eine FreqMap auf Byte-Basis höchstens 256 Einträge enthält, bleibt ihr Overhead konstant klein.

CLI zum Komprimieren und Dekomprimieren von Dateien

  • compress liest die Eingabedatei zweimal.
    • Im ersten Durchlauf wird die FreqMap erstellt.
    • Im zweiten Durchlauf werden die Daten mit dieser FreqMap kodiert.
  • Würde man die Datei nur einmal lesen und dieselbe Referenz an encode übergeben, müsste nach dem Erzeugen der Häufigkeitstabelle weiterhin die Referenz auf die komplette Eingabedatei gehalten werden; dadurch müsste die gesamte Datei im Speicher bleiben.
  • Durch das zweimalige Lesen kann sowohl beim Erzeugen der Häufigkeitstabelle als auch beim Kodieren bereits verarbeiteter Speicher fortlaufend freigegeben werden.
  • decompress liest die komprimierte Datei, erhält mit deserialize die FreqMap und die Bitliste und schreibt das Ergebnis von decode in eine Datei.
  • Die CLI akzeptiert die folgenden Argumente.
    • compress FILE FILE
    • decompress FILE FILE
  • Da nur Pakete verwendet werden, die mit GHC ausgeliefert werden, kann ohne cabal direkt mit ghc -O2 Main.hs -o main kompiliert werden.

Laufzeitergebnisse und Speichernutzung

  • Beim Test mit Tolstois War and Peace war das Ergebnis nach Kompression und Dekompression per diff identisch.
    • Original WarAndPeace.txt: 3,2M
    • Komprimierte Datei: 1,9M
    • Dekomprimierte Datei: 3,2M
    • Die Größe verringerte sich um rund 40%.
  • Auch bei der größeren Binärdatei ghcup funktionierten Kompression und Dekompression.
    • Original ghcup: 106M
    • Komprimierte Datei: 84M
    • Dekomprimierte Datei: 106M
    • Die Kompression dauerte etwa 15,173 Sekunden, die Dekompression etwa 14,555 Sekunden.
  • Laut +RTS -s lag die maximale Resident Set Size bei der Verarbeitung von ghcup unter 300KB.
  • Beide Prozesse verwendeten insgesamt weniger als 10MB Speicher.
  • Wo die Laufzeit verbraucht wurde, zeigt ein separates Profil.

Mögliche weitere Verbesserungen

  • Ziel der Implementierung war ein möglichst einfaches und klares Kompressions-Utility; für höhere Effizienz wäre eine komplexere Implementierung nötig.
  • Mögliche Verbesserungen sind unter anderem:
    • Multithreading: Dateiabschnitte könnten parallel dekodiert werden; da sich Codewort-Grenzen an beliebigen Positionen aber nicht direkt erkennen lassen, müsste am Anfang der komprimierten Datei zusätzlich eine Tabelle mit Abschnittsgrenzen und erwarteten Dekodiergrößen stehen.
    • Single-Pass-Encoding: Man beginnt mit einer initialen Häufigkeitstabelle, in der alle Bytes die Frequenz 1 haben, kodiert jedes Byte zuerst und aktualisiert danach die Häufigkeitstabelle.
    • Canonical Huffman codes: Statt beim Dekodieren den Baum in O(log n) zu durchsuchen, könnte man Codes als Vektorindex nutzen und O(1)-Zugriff anstreben; siehe dazu Canonical Huffman code.
    • Schnellere Code-Erzeugung: Vor allem beim Single-Pass-Encoding müsste die Erzeugung der CodeMap deutlich schneller werden; es gibt auch schnellere Verfahren, um Codewörter ohne Baumkonstruktion zu erzeugen.
  • Künftig könnte man mit dem adaptiven Wörterbuchverfahren LZ77 in Kombination mit Huffman-Codes auch gzip implementieren.

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2024-07-06
Meinungen auf Hacker News

  • Für diese Aufgabe gibt es einen arraybasierten In-Place-Algorithmus, der weniger Bäume allokiert und weniger Zeigern folgt.
    Als ich an der Uni den baumbasierten Ansatz gelernt habe, wusste ich nicht, dass es auch andere Methoden gibt, und ich frage mich, ob es anderen genauso ging.
    Die Baumvariante ist intuitiv und hilft beim Verständnis, aber Situationen, in denen Kompression besonders wichtig ist, sind meist solche mit vielen Daten, die man schnell verarbeiten möchte; daher kann es sinnvoller sein, mit In-Place-Arrays zu arbeiten.
    In-Place Calculation of Minimum-Redundancy Codes, Moffat, Katajainen, 1995
    http://hjemmesider.diku.dk/~jyrki/Paper/WADS95.pdf

    • Allgemein ist auch On the Implementation of Minimum Redundancy Prefix Codes von Moffat und Turpin lesenswert.
      Charles Bloom hat es nachdrücklich empfohlen und später auch Erläuterungen ergänzt.
      https://cbloomrants.blogspot.com/2010/08/08-12-10-lost-huffm...
    • Im JPEG-Standard ITU T.81 (1992) wird dieser Algorithmus als Ablaufdiagramm beschrieben; Wissen über arraybasiertes Huffman-Coding scheint also schon in den 80ern in gewissem Umfang bekannt gewesen zu sein.
    • Es wird am Ende des Artikels erwähnt und als Übungsaufgabe für die Leser gelassen.
    • Der Satz „ich frage mich, ob das auch auf einige von euch zutrifft“ klingt wie eine List Comprehension.

  • Die Aussage „Kein Codewort darf Präfix eines anderen Codeworts sein, damit es eindeutig ist“ ist streng genommen nicht korrekt.
    Sogenannte eindeutig decodierbare Codes sind nicht mehrdeutig und bilden eine Obermenge der Präfixcodes.
    Ein einfaches Beispiel ist ein Code, der ein Präfixcode in umgekehrter Richtung ist. Für das Beispiel im Artikel wäre das a 1, b 00, c 10.
    Der Code für a ist ein Präfix des Codes für c, aber wenn man die Codefolge rückwärts verarbeitet, lässt sie sich weiterhin eindeutig decodieren. Interessant wäre es, eindeutig decodierbare Codes zu sehen, die weder Präfixcodes noch deren Umkehrung sind.

    • Wenn man einen Präfixcode und einen Suffixcode zusammensetzt, lassen sich solche Codes erzeugen, ohne unnötig ineffizient zu werden.
      Wenn A 0, B 01, C 11 gilt und dann a A 0, b BA 010, c BB 0101, d BC 0111, e C 11, erhält man {a=0,b=010,c=0101,d=0111,e=11}.
      Man kann von hinten eindeutig decodieren, etwa 0->A, und danach von vorn erneut eindeutig decodieren, etwa A->a; daher ist der Code offensichtlich eindeutig decodierbar.
      Hinsichtlich der Längen ist er identisch mit dem optimalen Präfixcode {a=0,b=110,c=1110,d=1111,e=10} und damit für dieselbe Wahrscheinlichkeitsverteilung einer von mehreren optimalen Codes.
      Gleichzeitig ist er wegen a=0 und b=010 weder ein Präfix- noch ein Suffixcode. Tatsächlich ist im Allgemeinen in keiner Richtung ein inkrementelles Decoding möglich; um cee...ee? von bee...ee? oder ?cc...cca von ?cc...ccb zu unterscheiden, kann selbst zur Bestimmung eines einzigen Symbols unendlich viel Lookahead nötig sein.
      Ich weiß nicht, ob beim Zusammensetzen eines unabhängig optimalen Präfixcodes mit einem unabhängig optimalen Suffixcode die Optimalität immer erhalten bleibt, aber bei den einfachsten Fällen, die mir außer degenerierten 1:1-Codes eingefallen sind, hat es gut funktioniert.
    • Das ist interessanter, als es zunächst klingt. Als adversariales Gegenbeispiel geht erst einmal so etwas wie a 101, b 1.
      Das ist aber ein schlechter Code, weil a=1, b=0 immer besser wäre.
      Die Kraft-Ungleichung sagt, welche Mengen von Codelängen sich eindeutig decodierbar machen lassen, und mit Huffman-Coding lassen sich all diese Mengen erreichen. Wenn man also Symbol-Coding betreibt, gibt es keinen Grund, Nicht-Präfixcodes zu verwenden, sofern man nicht zu einem anderen Verfahren wie ANS oder arithmetischem Coding wechselt.
      Allerdings weiß ich nicht, ob es eindeutig decodierbare Codes gibt, die dieselbe Längenmenge wie ein optimaler Huffman-Code haben und weder Präfixcodes noch deren Umkehrung, also Suffixcodes, sind.
      Wenn ich mir Zeit dafür nähme, würde ich mir https://en.wikipedia.org/wiki/Sardinas-Patterson_algorithm ansehen und wohl per Brute Force nach einem Gegenbeispiel suchen oder aus der Funktionsweise des Algorithmus einen Beweis ableiten.
    • Ein seltsames Beispiel, aber wie wäre es mit a 1, b 101?
      Es ist weder präfixfrei noch suffixfrei, aber jedes Auftreten von 0 entspricht dem Auftreten von b.
      Natürlich ist es offensichtlich ineffizient; am Ende ist also die Frage, ob es optimale Codes gibt, die weder präfixfrei noch suffixfrei sind.
      Bei einer Suche habe ich gesehen, dass https://blog.plover.com/CS/udcodes.html als Beispiel für einen eindeutig decodierbaren Code a 0011, b 011, c 11, d 1110 nennt.
      Die einzige Präfixbeziehung ist, dass c ein Präfix von d ist, also ist er „fast“ präfixfrei. Wenn eine Nachricht mit 1 beginnt, scheint man die erste 0 suchen und prüfen zu können, ob davor eine ungerade oder gerade Anzahl von 1 steht; damit ist die eindeutige Decodierbarkeit nachvollziehbar.
      Wie man allerdings zeigt, dass das für irgendeine Wahrscheinlichkeitsverteilung optimal ist, weiß ich nicht mehr, dafür ist mein Wissen über Codierungstheorie zu eingerostet.
    • Spannend, aber der Grund, warum man das normalerweise nicht nutzt, dürfte sein, dass man unter Umständen eine sehr lange Bitfolge lesen muss, bis ein Bit kommt, das die Mehrdeutigkeit auflöst.
      Bei 100000000000000001 zum Beispiel muss man alle Nullen bis zu ihrem Ende lesen, um zu wissen, ob der erste Code a oder c ist.

  • Ich frage mich, ob es unter den Tutorials, die ähnlich wie dieser Artikel Schritt für Schritt ein Haskell-Programm entwickeln, auch Materialien gibt, die fortgeschrittenere Features wie Monad Transformer oder Lenses behandeln.

    • Ich empfehle das Buch Haskell in Depth. Monad Transformer werden in Kapitel 6 behandelt, Lenses in den Kapiteln 3 und 14.
      Es behandelt auch andere fortgeschrittene Features wie Template Haskell und Concurrency, und es gibt ein Kapitel über den Umgang mit SQL-Datenbanken in Haskell.
    • https://github.com/turion/rhine-koans ist einen Blick wert.
      Das ist ein Tutorial zur FRP-Bibliothek Rhine und enthält gute Kommentare und Tests.

  • Im Scala-basierten Functional-Programming-Kurs von Coursera gibt es eine ziemlich ähnliche Aufgabe zu Huffman-Coding, inklusive automatischem Grader – gut für alle, die sie selbst lösen möchten
    https://www.coursera.org/learn/scala-functional-programming?...

  • Das letzte Mal, dass ich Huffman-Codes verwendet habe, war für das Makroprogramm des MICMAC-Prozessors, also um Assembly-Text mit minimalen Mikrozyklen und minimalen Mikroinstruktionen auszuführen
    Ausgangspunkt war ein Histogramm der ausgeführten Makroinstruktionen; soweit ich mich erinnere, schrieb ich zuerst einen Interpreter in C, um zu zählen, wie oft jede Instruktion ausgeführt wurde
    Danach erstellte ich ein Mikrocode-Programm zur schrittweisen Decodierung, das alle benötigten ISA-Makrooperationen implementierte. Die von mir erstellte Makroinstruktions-ISA war, glaube ich, nicht byteorientiert, sondern bitweise aufgebaut
    In der Praxis wäre das langsam und unbequem gewesen, aber der Vorteil von Huffman-Codes liegt darin, dass man die Präfixtiefe an die Werteverteilung anpassen kann und wegen eines 1-Bit-Präfixes keinen einseitig verzerrten Code erzeugen muss
    Außerdem basierte das Mikroprogramm auf einem Prozessormodell mit Pipeline, aber ohne Superskalarität, sodass auch Branch Prediction behandelt werden musste. Bei einer Fehlvorhersage eines Branches werden Zyklen durch Pipeline-Stalls verschwendet, während sich der korrekte Branch nach vorne ausbreitet

  • https://rosettacode.org/wiki/Huffman_coding

  • Da sich hier vermutlich Haskell-Programmierer versammeln, möchte ich fragen: Wie schnell ist Haskell heutzutage, wenn es von Programmierern genutzt wird, die auf Optimierung achten?
    Besonders interessiert mich die Performance bei Aufgaben, die wie Matrixoperationen von numerischer Berechnung und SIMD profitieren.

    • Haskells Geschwindigkeit kann mit Systemsprachen konkurrieren, aber man sollte im Hinterkopf behalten, dass seine zentrale Stärke die einfache Abstraktion ist.
      Der Kernpunkt ist, dass sich viele Teile leicht zu einem konsistenten, gut strukturierten Programm zusammensetzen lassen. Das ist nicht nur für enge Schleifen wichtig, sondern für das gesamte Programm.
      Haskell hat ein gutes FFI, sodass man für Teile, die von Natur aus imperative Optimierung brauchen, auf Sprachen ohne Garbage Collection ausweichen kann. Wenn man solche Teile in eine Bibliothek mit guten Typen kapselt, kann man diese rohe Performance überall in Haskell-Code nutzen, wo die Typen passen.
      Genau so haben wir bei Meta performante Haskell-Anwendungen gebaut. Wir haben schöne, große und schnelle Haskell-Programme geschrieben, aber für einige spezialisierte Bereiche C++-Komponenten eingebunden. 99 % der Zeit haben wir auf der Haskell-Seite damit verbracht, daraus nützlichere Anwendungen zusammenzusetzen.
    • Für alltägliche Backend-, Web- und CLI-Aufgaben gefällt mir die Performance von Haskell. Wenn ich aber performancekritischen Code schreibe, gehe ich zu Rust runter.
      Trotzdem ist Haskell nicht langsam. Als Beispiel kann ein kleines Programm dienen, das die Anzahl der 1-Bits in einer Datei zählt.
      Wenn es mit -msse4.2 kompiliert wird, nutzt es die Hardware-popcount-Instruktion korrekt und verarbeitet eine 1-GB-Eingabedatei in 0m0,090s. Auf MB gerundet nutzt der Heap 0.
      Ohne -msse4.2 kompiliert dauert es 0m0,293s.
      Matrixberechnungen habe ich nicht selbst ausprobiert, aber als Ausgangspunkt würde ich mir repa, accelerate und massiv ansehen.
      https://hackage.haskell.org/package/repa
      https://hackage.haskell.org/package/accelerate
      https://hackage.haskell.org/package/massiv
    • Ich habe Sam Derbyshire auf der ZuriHac getroffen und gehört, dass die schwierige Architekturarbeit für SIMD-Unterstützung komplett abgeschlossen ist.
      https://gitlab.haskell.org/ghc/ghc/-/issues/7741
      Es könnte in GHC 9.12 landen. Allerdings zielt es nur auf 128-Bit-Vektoren ab und dürfte, sofern sich nicht andere beteiligen, vor allem auf Gleitkommaoperationen ausgerichtet sein.
      Der Patch ist hier:
      https://gitlab.haskell.org/ghc/ghc/-/merge_requests/12860
    • Realistisch gesehen kann in keiner Sprache, auch nicht in C, vom Compiler optimierter Code so schnell sein wie handoptimierter Code in Bibliotheken wie BLAS.
      Ab einem gewissen Punkt spielt die Wahl der Host-Sprache keine große Rolle mehr. Wenn man Geschwindigkeit wirklich ernst nimmt, lagert man die Berechnung ohnehin aus.
      Aus demselben Grund ist es in Ordnung, dass AI-Code, der vermutlich zu den weltweit größten Verbrauchern von Rechenressourcen gehört, abgesehen von Low-Level-Rechenbibliotheken in Python geschrieben ist.
      Direkt geantwortet: Der GHC-Compiler ist sehr gut. High-Level-Code funktioniert ziemlich gut, und in den meisten realen Anwendungen liegen Performance-Engpässe nicht bei Fragen wie skalaren Operationen versus SIMD, sondern in der Architektur. Haskells „architektonische Asymptotik“ ist ziemlich vorteilhaft.
      Ich glaube, dass GHC SIMD-Unterstützung hat oder gerade bekommt, aber bei der Bewertung der Performance würde ich mich nicht darauf konzentrieren.
      Ich würde keinen Matrixmultiplikationsalgorithmus selbst in Haskell schreiben, aber wenn mir Geschwindigkeit ernst ist, würde ich ihn auch nicht selbst in Rust oder C schreiben.
      Numerische Berechnung wird oft als Performance-Maßstab herangezogen, aber tatsächlich ist sie bei kaum jemandem der Engpass; und wenn doch, ist es ziemlich egal, welche High-Level-Sprache man verwendet.
    • Haskell glänzt wirklich, wenn man High-Level-deklarativen Code schreiben möchte.
      Die Performance dieses Stils reicht normalerweise für CLI- oder Web-Backend-Aufgaben aus. Es gibt auch Werkzeuge, um recht schnellen Low-Level-Code zu schreiben, aber sie sind etwas sperrig; wenn man nur das tun will, ist Haskell wahrscheinlich nicht das beste Werkzeug.
      Wenn es allerdings ein paar klar eingegrenzte Hotspots gibt, die optimiert werden müssen, ist es ziemlich gut.
      Die CPU-Profiling-Tools sind gut, sodass das Finden und Optimieren von CPU-Hotspots relativ angenehm ist. Dagegen kann das Aufspüren seltsamer Speicherlecks, die durch Lazy Evaluation leichter entstehen, sehr frustrierend sein.
      Wenn man sich die Ergebnisse des benchmarks game ansieht, sind die schnellsten Haskell-Implementierungen im Allgemeinen 2- bis 5-mal langsamer als die schnellsten C-Versionen und in einem sehr imperativen Stil geschrieben.
      https://benchmarksgame-team.pages.debian.net/benchmarksgame/...

  • In der Tabelle im Abschnitt „Creating prefix-free codes“ scheint ein Tippfehler zu sein. D sollte 0010 sein, nicht 0110.

    • Deshalb habe ich mir eine ganze Weile den Kopf darüber zerbrochen, wie 0110 eindeutig sein kann, aber jetzt verstehe ich es.

  • Ich frage mich, was auf dem Shirt der Frau im Bild zu sehen ist.
    Direkter Link: https://lazamar.github.io/images/data-compressor.svg