KittenMoji

Letztes Wochenende habe ich auf Mastodon einen Tweet gesehen, wo jemand KittenMoji erwähnt hat. KittenMoji ist eine Byte-zu-Text-Codierung. Ähnlich wie bei der Hexadezimalschreibweise oder Base64 können damit Binärdaten als Text encodiert werden.

KittenMoji verwendet, wie der Name schon nahelegt, Emojis zur Codierung. Alle verwendeten Emojis belegen, als UTF-8 codiert, jeweils vier Bytes, also 32 Bit. KittenMoji ist eine Base256-Codierung, also ein Byte wird auf genau ein Emoji abgebildet. Im Gegensatz also zu Base64, das jeweils 6 Bits mit 8 Bits encodiert oder Hexadezimalschreibweise, die jeweils 8 Bit mit 16 Bits encodiert, werden bei KittenMoji jeweils 8 Bits mit 32 Bits encodiert.

KittenMoji ist also extrem ineffizient und es gibt eigentlich keinen Grund, es zu verwenden. Ich habe ein Rust-Crate zur De-und Encodierung von KittenMoji geschrieben.

Das kittenmoji-crate

Irgendwie funktioniert mein Gehirn am besten wenn das, was ich programmiere, komplett unwichtig ist. Ich habe das crate dann auch auf crates.io, der offiziellen Rust-Paketplattform veröffentlicht. Einfach mal um zu schauen, wie das funktioniert. Wenn ich einen dummen Fehler mache: kein Problem, ist ja kein wichtiges Paket. Falls ich irgendwann einmal ein wichtiges Paket veröffentliche, weiß ich dann schon, wie das läuft.

Das kittenmoji-crate besteht im Prinzip aus sechs Funktionen: drei zum Encodieren, drei zum Decodieren. Jeweils eine Funktion, die einen byte-slice bzw. string-slice en- bzw. decodiert, eine Funktion, die einen byte-Iterator entgegennimmt und einen char-Iterator zurückgibt (fürs Encodieren, entsprechend umgekehrt fürs Decodieren) und jeweils eine Funktion, die einen bytestream liest und ihn entsprechend de- oder encodiert.

Letzteres wird in zwei Beispielprogrammen demonstriert, encode und decode, die jeweils von stdin lesen und nach stdout schreiben und die Daten dazwischen en- oder decodieren. Das funktioniert mit beliebig großen Dateien, der interne Buffer hat eine konstante Größe, der genutzte Arbeitsspeicher hält sich also in Grenzen und ist nicht von der Größe der Eingabedaten abhängig.

Optimierung des Encoders

Wer das Blog hier schon eine Weile verfolgt weiß, dass ich gelegentlich einfach mal ganz nutzlose Programme optimiere. Zum Beispiel das zeilenweise Einlesen einer Datei. Oder einen primitiven DGA-Detektor. Oder einen Brainfuckinterpreter. Mein erstes Veröffentlichtes Rust-Crate? Natürlich!

Ich habe mich hier auf die Stream-Varianten fokussiert, weil die mutmaßlich die größten Datenmengen verarbeiten und dementsprechend am meisten von einer Optimierung profitieren. Zur Messung habe ich wieder einmal Hyperfine verwendet. Encodiert habe ich… ein CD-Image einer Windows 98 SE (hey, ich habe Anfang des Jahrtausends Geld dafür ausgegeben, dann soll sich diese CD auch mal nützlich machen!).

Die Datei ist knapp 600MiB groß (626524160 Byte, um genau zu sein). Der Code sah zu diesem Zeitpunkt so aus:

pub fn encode_stream(mut input: impl Read, mut output: impl Write) -> io::Result<()> {
    let mut buf: [u8; BUFFER_SIZE] = [0; BUFFER_SIZE];
    let mut n = input.read(&mut buf)?;
    let mut cbuf: [u8; 4] = [0; 4];
    while n > 0 {
        for c in encode(buf[..n].iter().copied()) {
            let s = c.encode_utf8(&mut cbuf);
            output.write_all(s.as_bytes())?;
        }
        n = input.read(&mut buf)?;
    }
    Ok(())
}

Es wird also in einer Schleife Daten gelesen, in einen Buffer auf dem Stack geschrieben und dann wird der oben erwähnte Iterator aufgerufen, der dann die Bytes mittels einer Lookup-Tabelle in Unicode-chars umwandelt, die dann als UTF-8 codiert und dann geschrieben werden. Wie schnell ist das?

$ hyperfine -w1 "cat ~/Dateien/CD-Images/Win98SE.iso | target/release/examples/encode  > /dev/null"
  Time (mean ± σ):      4.654 s ±  0.245 s    [User: 4.461 s, System: 0.462 s]
  Range (min … max):    4.359 s …  5.172 s    10 runs

Ich habe hier nach /dev/null geschrieben, weil ich die Schreibgeschwindigkeit meiner SSD jetzt nun wirklich nicht in die Messung einbeziehen wollte. Dennoch schwanken die Werte bei verschiedenen Messdurchläufen recht stark, also sind sie mit Vorsicht zu genießen. Ich habe das Experiment mehrere Male laufen lassen, die Werte schwanken immer im selben Bereich.

Schnell ist das jedenfalls nicht. Was könnte man also verbessern? Nun, zunächst ist mir aufgefallen, dass ich eine Menge kleiner Funktionsaufrufe habe. Der Iterator, das UTF-8-Codieren… alles für jedes einzelne Byte im Input. über 600 Millionen Bytes sind das dementsprechend viele Aufrufe. Kann man das vielleicht verkleinern? Aber natürlich. Erst einmal bin ich den Iterator losgeworden, und habe den Krams inline gemacht. Meine Lookup-Tabelle hat aber char-Werte zurückgegeben, den Aufruf von char::encode_utf8() hätte ich also trotzdem noch gebraucht. Also habe ich eine zweite Lookup-Tabelle erstellt, die stattdessen &str enthält, also kleine statische Strings, die praktischerweise schon UTF-8 codiert sind. Ergebnis:

  Time (mean ± σ):      2.519 s ±  0.070 s    [User: 2.317 s, System: 0.465 s]
  Range (min … max):    2.443 s …  2.682 s    10 runs

Diese Verbesserung kann sich sehen lassen. Aber es geht noch besser. Mit den &str-Werten ist es nämlich so: Das Programm muss zunächst auf das Array zugreifen, um sich an der richtigen Stelle eine Referenz auf den String zu holen, dieser Referenz folgen, dann eine Funktion aufrufen, um den String als byte-Slice zu interpretieren (zumindest dieser Funktionsaufruf sollte aber vom Compiler rausoptimiert werden) um dann die Daten zu schreiben. Zu viele Dereferenzieren. In vielen Fällen macht das nicht viel aus. Hier aber schon, weil es so oft gemacht wird. Außerdem muss bei den Slices mit viel mehr Daten gehandelt werden. Der Pointer? 8 Byte. Die Größenangabe? 8 Byte. Die Nutzdaten? 4 Byte.

Wie wäre es also, wenn ich eine Indirektion umgehe, und statische Arrays in die Lookuptabelle stecke? Der Encodierungscode sieht danach etwa so aus:

let mut buf: [u8; ENCODE_BUFFER_SIZE] = [0; ENCODE_BUFFER_SIZE];
let mut n = input.read(&mut buf)?;
while n > 0 {
    for b in &buf[..n] {
        output.write_all(&ALPHABET_BYTES[*b as usize])?;
    }
    n = input.read(&mut buf)?;
}
Ok(())

Und die Geschwindigkeit ist noch einmal deutlich verbessert worden:

  Time (mean ± σ):      1.379 s ±  0.023 s    [User: 1.191 s, System: 0.435 s]
  Range (min … max):    1.356 s …  1.420 s    10 runs

Ich könnte auch noch versuchen, die Anzahl der write()-Aufrufe zu verringern. Ich würde sowieso einen gebufferten Writer empfehlen, aber da muss ich halt trotzdem noch einen Haufen Funktionsaufrufe machen. Wenn ich die reduzieren kann, bin ich vielleicht trotz des Overheads, den ein zusätzlicher Buffer bringt, schneller:

let mut write_buf: [u8; ENCODE_BUFFER_SIZE * 4] = [0; ENCODE_BUFFER_SIZE * 4];
let mut n = input.read(&mut buf)?;
while n > 0 {
    for (i, b) in buf[..n].iter().enumerate() {
        let bytes = ALPHABET_BYTES[*b as usize];
        write_buf[i * 4] = bytes[0];
        write_buf[i * 4 + 1] = bytes[1];
        write_buf[i * 4 + 2] = bytes[2];
        write_buf[i * 4 + 3] = bytes[3];
    }
    output.write_all(&write_buf[..n * 4])?;
    n = input.read(&mut buf)?;
}

Das bringt tatsächlich noch einmal ein paar 100ms:

  Time (mean ± σ):     975.3 ms ±  67.0 ms    [User: 796.8 ms, System: 416.2 ms]
  Range (min … max):   924.5 ms … 1135.5 ms    10 runs

Geben wir uns damit zufrieden und schauen mal das Decodieren an.

Optimieren des Decoders

Das Größte Problem bei der Optimierung des Decoders ist: Im Gegensatz zum Encoder kann das Decodieren fehlschlagen. Encoding ist eindeutig, jedes Byte ist genau einem Emoji zugeordnet. Beim Decoden ist das anders. Als Input kommen vier-Byte-Häppchen in Frage, die entweder

ein gültiges KittenMoji-Emoji sind
gültiger UTF-8-Text, aber kein gültiges KittenMoji
kein gültiger UTF-8 Text sind.

Ich zeige den Code hier jetzt nicht direkt, der ist ein bisschen sperrig, aber man kann die alte Version hier im Git-Repo auf gitlab.com finden.

Nur eine kurze Zusammenfassung, was der Code macht:

lese bytes in den Buffer
versuche, die Bytes als UTF-8-String zu interpretieren
wenn der String ungültig ist, weil am Ende bytes für einen vollständigen Codepoint fehlen (kann immer mal vorkommen, wenn man aus dem Stream liest): Nimm den kürzesten gültigen String und merk dir, wie viel im Buffer danach noch benötigt wird
wenn der String ungültig ist, weil er wirklich ungültig ist: breche mit Fehler ab
gehe durch alle Codepoints des strings
Für jeden Codepoint: schlage in einer (vorher generierten) Hashmap nach, auf welches Byte er gemapped ist
Wenn der Codepoint nicht gemapped ist: breche mit Fehler ab
Wenn der Codepoint gemapped ist: schreibe das dazugehörige Byte in den Output
Dann kümmere dich darum, dass die ggf. überstehenden Bytes am Ende an den Anfang des Buffers verschoben werden und lies die nächsten Bytes in den Buffer

Da sind viele Stellen, die langsam sind. Insbesondere, in der tight loop: viele Anfragen an die HashMap (inkl. vieler Berechnungen von Hashes, viele Überprüfungen auf Fehler, viele write()-Operationen. Wie langsam ist es?

Benchmark 1: cat encoded | target/release/examples/decode > /dev/null
  Time (mean ± σ):     11.583 s ±  0.520 s    [User: 11.072 s, System: 1.645 s]
  Range (min … max):   10.952 s … 12.446 s    10 runs

Oh-oh. Über 12 Sekunden. Mehr als doppelt so viel wie der unoptimierte Encoder. Naja, probieren wir mal denselben Trick: Anstatt mit Strings zu arbeiten, arbeiten wir mal direkt auf den Bytes (den Code dieses Zwischenstandes habe ich leider verworfen, deswegen kann ich den hier nicht zeigen).

  Time (mean ± σ):     12.428 s ±  0.574 s    [User: 11.899 s, System: 1.686 s]
  Range (min … max):   11.569 s … 13.488 s    10 runs

WTF, es ist langsamer geworden? Probieren wir es noch mal. Immer noch langsamer… Und obwohl wir uns die String-Überprüfung und die Decodierung des UTF-8 gespart haben. Ok, Änderungen zurücknehmen. Wir schauen uns erst einmal andere Optionen zur Optimierung an. Was ist zum Beispiel, wenn wir den Iterator über Bord werfen und direkt, ohne weitere Funktionsaufrufe, in der Map nachschlagen?

  Time (mean ± σ):     11.018 s ±  0.229 s    [User: 10.484 s, System: 1.730 s]
  Range (min … max):   10.627 s … 11.274 s    10 runs

Minimal besser. Aber vermutlich nicht einmal statistisch signifikant besser (ich habe es nicht nachgerechnet). Aber Moment: vielleicht geht es ja schneller, wenn wir den Buffer vergrößern, in den read() schreibt? So von 128 auf 1024 Bytes?

  Time (mean ± σ):      9.673 s ±  0.180 s    [User: 9.142 s, System: 1.677 s]
  Range (min … max):    9.350 s …  9.884 s    10 runs

Besser. Aber da geht noch mehr. Machen wir das Gleiche wie beim Encodieren: Schreiben wir den Output erst einmal in einen Buffer, um write()-Aufrufe zu sparen:

  Time (mean ± σ):      9.056 s ±  0.433 s    [User: 8.521 s, System: 1.674 s]
  Range (min … max):    8.457 s …  9.648 s    10 runs

Mühsam nährt sich das Eichhörnchen. Also müssen wir uns wohl noch einmal anschauen, warum das direkt-auf-Bytes-Arbeiten hier nichts gebracht hat. Meiner Vermutung ist: Es ist die Hashberechnung. Es kann sein, dass die auf einen char einfach wesentlich effizienter zu berechnen ist als auf einem array. Aber char will ich hier nicht nehmen, dann haben wir wieder die UTF-8-Überprüfung, die wir eigentlich nicht benötigen. Wir haben ohnehin nur gültige Codepoints in der Hashmap, wenn eine Bytefolge nicht gefunden wird, dann ist sie ungültig, egal ob sie gültiges UTF-8 ist oder nicht.

Aber wir können die 4-Byte-Folge ja einfach in u32 umrechnen. Normalerweise muss man sich bei so etwas um die Byte-Order kümmern. Hier aber nicht. Die Byte-Order ist mir egal, solange Hashmap und Suchstring die gleiche haben. Wenn ich also auf beiden Seiten einfach die native Byte-Order nehme müsste es auf allen Maschinen funktionieren und ist nicht mehr Aufwand für die CPU als eine einfache Kopieroperation.

for (i, bytes) in buf[..len].chunks_exact(4).enumerate() {
    // using native byte order here is ok because the decode_map does also uses native byte
    // order.
    write_buf[i] = *decode_map.get(&u32::from_ne_bytes(bytes.try_into().expect("expected 4 byte slice to be transformed to 4 byte array"))).ok_or_else(|| {
        io::Error::new(
            io::ErrorKind::InvalidData,
            format!("unexpected byte sequence in stream: '{bytes:0x?}', either invalid utf-8 or non-kittenmoji code point"),
        )
    })?;
}

Und?

  Time (mean ± σ):      5.805 s ±  0.223 s    [User: 5.353 s, System: 1.444 s]
  Range (min … max):    5.491 s …  6.131 s    10 runs

Now we're talking! Natürlich haben wir immer noch den ganzen HashMap-Krams, der die Geschwindigkeit herunterzieht. Bevor jemand fragt: Ich habe es mit einer sortierten Liste und einer Binärsuche ausprobiert, das war deutlich langsamer. Vermutlich, weil es bei dieser Suche viele branches gibt. Die triviale Lösung, einfach die Liste zu durchsuchen ist hier noch langsamer.

Um die Fehlerbehandlung kommen wir auch so oder so nicht herum. Eine kleine Optimierung wäre noch, statt mit chunks_exact zu iterieren und die slices in arrays umzuwandeln (wieder mit Fehlerbehandlung, in diesem Fall aber das etwas effizientere expect, weil wir wissen, dass alle slices 4 bytes lang sind und der Fehlerfall nicht eintritt). Die Alternative array_chunks ist minimal besser, aber bisher nur in der nightly-Version verfügbar und nicht stabil.

Fazit

Ich habe es geschafft, das Encodieren und Decodieren für ein unglaublich ineffizientes Encoding viel effizienter zu machen. Und das besonders da, wo man es wirklich nicht verwenden will. Ein kleines Stückchen Binärdaten mit Emojis zu encodieren? Das sieht lustig aus, und jemand auf Mastodon hat darauf hingewiesen, dass z.B. Mastodon (mit Längenbeschränkung für toots) jedes Emoji als ein Zeichen zählt. Hier ist dieses Encoding also sogar effizienter als Base64, zumindest für den Benutzer.

KittenMoji wurde übrigens für Schlüsselencoding im Small Web erdacht (siehe die Dokumentation von kitten, ein Small Web development kit). Die Idee hinter dem Small Web ist es, wieder mehr selbstgehostete Websites zu, aber trotzdem den Community-Effekt von z.B. Facebook zu haben. Also ein dezentrales soziales Netzwerk, ohne die Nachteile von Facebook. Es soll einfach aufzusetzen sein, aber um ehrlich zu sein, ich bleibe lieber bei meinem guten altmodischen Blog, ohne zu viele fancy features.

Das Repo für meinen KittenMoji De-/Encoder findet ihr auf Gitlab.com. Ich betrachte das Crate soweit erst einmal als Feature-Complete, warte aber noch ein bisschen ab, bis ich die Version auf 1.0.0 setze, vielleicht fällt mir ja noch irgendetwas Wichtiges ein. Wer noch weitere Ideen zur Optimierung hat kann sie gerne ausprobieren, ich nehme Patches an. Wichtig ist, dass alles safe rust ist und keine Abhängigkeiten zum Crate hinzugefügt werden.

Wer KittenMoji in der eigenen Software verwenden möchte… Ich würde fast empfehlen: Kopiert die Quelldateien und fügt sie bei euch ein, schlagt euch nicht mit einer Abhängigkeit herum, die ich höchstwahrscheinlich nicht pflegen werde.