Zeichen müssen auf irgendeine Weise in Bits codiert werden. Die meisten Zeichenfolgen im Internet, einschließlich dieses Beitrags auf Habré, sind in UTF-8 codiert. Das UTF-8-Format repräsentiert "Zeichen" in einem, zwei, drei oder vier Bytes. Dies ist eine Verallgemeinerung für den ASCII-Standard, der nur ein Byte pro Zeichen verwendet. Das heißt, die ASCII-Zeichenfolge ist auch eine UTF-8-Zeichenfolge.
Es ist tatsächlich etwas komplizierter, da UTF-8 technisch Codepunkte beschreibt. Ein sichtbares Zeichen wie ein Emoji kann aus mehreren Codepunkten bestehen ... aber die meisten Programmierer benötigen diese pedantische Formulierung nicht.
Es gibt auch andere Standards. Einige ältere Programmiersprachen wie C # und Java basieren auf UTF-16. Es werden zwei oder vier Bytes pro Zeichen verwendet. Es schien damals eine gute Idee zu sein, aber jetzt geht der Konsens dahin, UTF-8 jederzeit und überall einzusetzen.
Die meisten Codierungen unterliegen durchsetzbaren Einschränkungen. Mit anderen Worten, keine zufällige Folge von Bits kann in UTF-8 eingehen. Daher müssen Sie die Zeichenfolgen überprüfen - überprüfen Sie, ob es sich wirklich um UTF-8 handelt.
Was macht es aus? Toll. Der Webserver von Microsoft weist beispielsweise eine solche Sicherheitsanfälligkeit auf: Er akzeptiert einen URI, der als gültig und sicher erscheint, dem Angreifer jedoch bei der Interpretation durch den Server Remotezugriff auf die Festplatte gewährt. Selbst wenn Sie Sicherheitsbedenken beiseite lassen, möchten Sie mit ziemlicher Sicherheit keine ungültigen Zeilen in Ihrer Datenbank speichern.
Daher validieren Programmiersprachen, Webserver, Browser und Datenbankmodule UTF-8 ständig.
Wenn Ihre Zeichenfolgen meistens nur ASCII sind, sind die Überprüfungen ziemlich schnell und die UTF-8-Überprüfung ist kein Problem. Vorbei sind die Zeiten, in denen die meisten Zeichenfolgen ASCII-codiert waren. Wir leben in einer Welt von Emojis und vielen nationalen Alphabeten.
Im Jahr 2018 fragte ich mich:Wie schnell können UTF-8-Strings validiert werden ? Zu diesem Zeitpunkt fand ich eine Validierungsoption mit mehreren CPU-Zyklen pro Symbol. Man konnte sich beruhigen, aber diese Antwort befriedigte mich nicht.
Die Arbeit hat Jahre gedauert, aber es scheint, dass wir jetzt eine Version haben, die nahezu ideal ist. Der neue Algorithmus ist eine Größenordnung schneller als andere Schnellsuchoptionen. Wir haben ein Whitepaper vorbereitet: "UTF-8-Validierung in weniger als einer Anweisung pro Byte" (veröffentlicht in Software: Practice and Experience ) und ein Benchmarking-Dienstprogramm veröffentlicht .
Alle Details werden in einem wissenschaftlichen Artikel erklärt, daher werden wir hier nicht auf Details eingehen, sondern nur kurz auf das Wesentliche eingehen. Der Hauptteil der UTF-8-Validierung erfolgt durch die Suche nach Paaren aufeinanderfolgender Bytes. Nachdem alle Bytepaare überprüft und mögliche Verstöße aus diesen Informationen ermittelt wurden, bleibt relativ wenig zu tun.
Alle Prozessoren verfügen über schnelle SIMD-Anweisungen. Sie arbeiten mit breiten Registern (128 Bit, 256 Bit usw.). Die meisten Sätze haben eine "vektorisierte Suchanweisung", die beispielsweise 16-Byte-Werte (im Bereich von 0 bis 16) annimmt und in einer 16-Byte-Tabelle nach ihnen sucht. In Intel- und AMD-Prozessoren entspricht diese Beschreibung der Anweisung
pshufb... Ein Wert zwischen 0 und 16 wird manchmal als Nibble bezeichnet und umfasst 4 Bits. Das Byte besteht aus zwei Halbbytes (niedrig und hoch).
In unserem Suchalgorithmus wird der vektorisierte Suchbefehl dreimal aufgerufen: einmal für Low Nibble, einmal für High Nibble und einmal für High Nibble für das nächste Byte. Wir haben drei entsprechende 16-Byte-Nachschlagetabellen. Wenn Sie sie richtig auswählen, findet das bitweise UND der drei Suchvorgänge einen Fehler.
Weitere Informationen finden Sie im wissenschaftlichen Artikel. Letztendlich wird die UTF-8-Validierung jedoch fast vollständig mit nur fünf Zeilen schnellem C ++ - Code ohne Verzweigungen durchgeführt. Diese fünf Zeilen prüfen Blöcke mit jeweils bis zu 32 Byte.
simd8 classify(simd8 input, simd8 previous_input) {
auto prev1 = input.prev<1>(previous_input);
auto byte_1_high = prev1.shift_right <4>().lookup_16(table1);
auto byte_1_low = (prev1 & 0x0F).lookup_16(table2);
auto byte_2_high = input.shift_right <4>().lookup_16(table3);
return (byte_1_high & byte_1_low & byte_2_high);
}Obwohl dies nicht sofort offensichtlich ist, ist diese Validierung ausreichend und 100% sicher. Es ist wirklich so . Es sind nur noch wenige kostengünstige zusätzliche technische Schritte übrig.
Auf den neuesten Intel / AMD-Prozessoren ist daher etwas weniger als ein Befehl pro Byte erforderlich, um selbst die zufälligsten Junk-Eingabedaten zu überprüfen. Da der Code extrem optimiert ist, können Sie bis zu drei Anweisungen pro Zyklus und noch mehr ausführen. Das heißt, wir verwenden einen kleinen Teil des Zyklus (weniger als ein Drittel) pro Eingangsbyte auf einer modernen CPU. Somit wird die Verarbeitungsgeschwindigkeit zuverlässig bei über 12 GB / s gehalten.
Die Lehre ist, dass reguläre Nachschlagetabellen nützlich sind, aber vektorisierte Tabellen die Grundbausteine für Hochgeschwindigkeitsalgorithmen sind.
Wenn Sie die schnelle UTF-8-Validierungsfunktion in der Produktion verwenden müssen, empfehlen wir die simdjson- Bibliothek (Version 0.5 oder höher). Es ist gut getestet und verfügt über nützliche integrierte Funktionen wie das Laufzeit-Dispatching. Obwohl die Bibliothek zum Parsen von JSON ausgelegt ist, können Sie sie nur für die UTF-8-Validierung verwenden, selbst wenn überhaupt kein JSON vorhanden ist. Es unterstützt 64-Bit-ARM- und x64-Prozessoren und verfügt auch über eine Fallback-Verarbeitung für andere CPUs. Wir haben es zusammen mit einer Quelldatei in eine Header-Datei gepackt. Sie können es also einfach in Ihr C ++ - Projekt einfügen.
Vorherige Arbeit... Der Hauptvorteil bei der Popularisierung der vektorisierten Klassifizierungsmethode, die der Schlüssel zum Suchalgorithmus ist, liegt bei Mula. Soweit ich weiß, hat Keiser als erster unsere dreifache Suchstrategie vorgeschlagen. Der erste praktische SIMD-basierte UTF-8-Validierungsalgorithmus wurde von K. Willets erstellt. Mehrere Personen, darunter Z. Wegner, haben Verbesserungen vorgenommen. Travis Downs hatte kluge Ideen, wie herkömmliche Algorithmen beschleunigt werden können.
Weiterführende Literatur . Wenn Ihnen diese Arbeit gefällt, mögen Sie möglicherweise andere Artikel zu verwandten Themen: "Base64-Codierung und -Decodierung mit nahezu Kopiergeschwindigkeit" (Software: Practice and Experience, 50 (2), 2020) und "Parsing JSON Gigabytes Per Second" ( VLDB Journal, 28 (6), 2019).