Base64 zehnmal schneller en- und decodieren

Viele gängige Dokumentenformate im Internet sind reine Textformate wie etwa E-Mail (MIME) und Web (HTML, JavaScript, JSON und XML). Um Bilder oder ausführbaren Code in diese Dokumente aufzunehmen, werden diese üblicherweise zunächst mit Base64 als Text kodiert. Die Standard base64-Kodierung verwendet 64 ASCII-Zeichen – sowohl Klein- als auch Großbuchstaben, lateinische Buchstaben, Ziffern und zwei weitere Symbole.

Die beiden Forscher Wojciech Muła und Daniel Lemire von der Universität in Quebec haben gezeigt, wie man Base64-Daten mit nahezu der Geschwindigkeit einer Speicherkopie (memcpy) auf aktuellen Intel-Prozessoren kodieren und dekodieren können. Lediglich bei Daten, die komplett in den First-Level-Cache (L1) des Prozessors passen bleibt der memcpy-Befehl unschlagbar.

Die Forscher verwenden dabei den SIMD-Befehlssatz AVX-512, der für Standardprozessoren verfügbar ist (SIMD = Single Instruction Multiple Data). Die Implementierung erzeugt deutlich weniger Anweisungen als bisherige SIMD-beschleunigte base64-Codecs. Sie ist zudem vielseitiger, da sie – auch zur Laufzeit – an jede Base64-Variante angepasst werden kann, indem sie lediglich Konstanten ändert.

Beim Wechsel von einer Kodierung von 256-Bit-Registern (AVX2) auf 512-Bit-Register (AVX-512) sollte eigentlich im besten Fall eine Reduktion der Instruktionen auf die Hälft zu erwarten sein. Der von Muła und Lemire vorgelegte Algorithmus schafft sogar eine Reduktion um das siebenfache. Der beschriebene Codec arbeitet damit zehn bis 20-mal schneller als ein hochoptimierter konventioneller Codec, so die beiden Wissenschaftler.

Details zur Vorgehensweise erfahren Sie im Paper, das die beiden Wissenschaftlern zu ihrem Algorithmus veröffentlicht haben. Als PDF können Sie es von dieser Seite laden: https://arxiv.org/pdf/1910.05109.pdf