GitHub gelang es, die Groß-/Kleinschreibungsfaltung, also Case Folding, mit einer Geschwindigkeit von über 45 Gigabyte pro Sekunde auf einem einzigen Kern auszuführen. Dazu wurde die Programmschleife so umgestaltet, dass sie nicht beim ersten Nicht-ASCII-Byte anhält, sondern den gesamten Puffer ohne datenabhängige Steuerverzweigungen durchsucht. Das Unternehmen verwendet diesen Vorgang in der Quelltextsuchmaschine Blackbird, die mehr als 180 Millionen Repositorys und über 480 Terabyte Quelltext indiziert.
Alexander Neubeck und Greg Orzell stellten die Einzelheiten dieses Designs in einem am 31. Juli 2026 im GitHub-Blog veröffentlichten Beitrag vor. Der Beitrag kündigte außerdem an, dass das Ergebnis in einer quelloffenen Rust-Bibliothek namens casefold verfügbar gemacht wurde.
Groß-/Kleinschreibungsfaltung ist nicht bloß die Umwandlung in Kleinbuchstaben
Suchmaschinen und Werkzeuge zum Abgleichen von Texten benötigen eine standardisierte Darstellung, durch die sich Zeichenketten, die sich nur in der Groß-/Kleinschreibung unterscheiden, beim Vergleich als gleich erweisen. Das zeigt sich bei der Suche, bei nicht zwischen Groß- und Kleinschreibung unterscheidenden regulären Ausdrücken sowie bei Benutzernamen und Hostnamen.
Die Umwandlung von Text in Kleinbuchstaben erfüllt jedoch nicht denselben Zweck. Die Kleinschreibung kann von Sprache und Kontext abhängen, etwa durch die unterschiedliche Form des griechischen Sigma am Wortende und im Wortinneren oder durch die unterschiedlichen Regeln für den Buchstaben I im Türkischen. Die Groß-/Kleinschreibungsfaltung ist dagegen für Vergleiche ausgelegt und daher sprach- und kontextunabhängig. Das Ergebnis unterscheidet sich außerdem in Fällen wie dem deutschen ß, dem türkischen İ und dem griechischen Schluss-Sigma.
Die Bibliothek führt eine einfache Eins-zu-eins-Faltung gemäß den Zuständen C und S in der Datei CaseFolding.txt der Unicode-Zeichendatenbank aus. Mehrzeichenfaltungen, etwa die Umwandlung von ß in ss, sowie für die türkische Sprache spezifische Faltungen werden nicht ausgeführt.
Entfernung der Optimierung, die die Schleife verlangsamte
Da Quelltext größtenteils aus ASCII-Zeichen besteht, konzentriert sich der schnellste Pfad darauf, die lateinischen Großbuchstaben von A bis Z in Kleinbuchstaben umzuwandeln. Das naheliegende Design hielt beim ersten Nicht-ASCII-Byte sofort an und übergab den restlichen Text an einen Unicode-Pfad. Tests auf einem Apple-M4-Prozessor zeigten jedoch, dass dieser Ansatz nur etwa 3 Gigabyte pro Sekunde erreichte.
Der Hauptgrund dafür sind die Steuerverzweigungen innerhalb der Schleife. Statt jedes Byte zu prüfen und frühzeitig anzuhalten, sammelt der Algorithmus das höchste Bit aller Bytes in einer einzigen Variable und prüft das Ergebnis erst nach Abschluss des Durchlaufs. Ob ein Byte im Bereich der Großbuchstaben liegt, wird dagegen rechnerisch geprüft, indem der Buchstabe A mit Überlauf subtrahiert und das Ergebnis mit der Zahl 26 verglichen wird. Anschließend wird eine arithmetische Maske verwendet, um das fünfte Bit im Byte zu setzen. Dadurch wird der Großbuchstabe ohne Verzweigung oder bedingte Speicherung in einen Kleinbuchstaben umgewandelt.
Diese Struktur ermöglicht es dem LLVM-Compiler, Vektorinstruktionen zu erzeugen, die mithilfe von NEON auf dem Apple M4 jeweils 16 Bytes verarbeiten. Das Ergebnis liegt bei über 45 Gigabyte pro Sekunde und nähert sich damit der Grenze der Speicherbandbreite. Messungen von GitHub zeigen, dass die Entfernung des vorzeitigen Ausstiegs der Faktor war, der die Vektorisierung ermöglichte: Das Beibehalten des datenabhängigen Ausstiegs verhindert die Erzeugung von Vektorinstruktionen, selbst wenn der übrige Teil der Schleife verzweigungsfrei ist.
Warum ein zusammengeführter Durchlauf nicht immer schneller ist
GitHub testete einen Kompromiss, der ASCII blockweise prüft und anschließend den ASCII-Präfix umwandelt. Dieser Ansatz liest die Daten zweimal, erreichte jedoch etwa 23 Gigabyte pro Sekunde und war damit deutlich schneller als die naive Schleife, während die Möglichkeit erhalten blieb, beim ersten Nicht-ASCII-Block anzuhalten.
Die Zusammenführung von Prüfung und Umwandlung in einer einzigen Schleife, die mit 16-Byte-Blöcken arbeitet, war dagegen langsamer: Sie erreichte etwa 8,7 Gigabyte pro Sekunde gegenüber 23 Gigabyte pro Sekunde bei der Lösung mit zwei Durchläufen. Dem Beitrag zufolge verhindert die Ausstiegsverzweigung nach jedem Block, dass der Compiler die Schleife entrollt oder die Wartezeit zwischen Lesen, Prüfen, Umwandeln und Schreiben verbirgt. Daher waren zwei saubere, vektorisierbare Schleifen schneller als eine einzige Schleife, die die Daten zwar seltener berührt, aber eine inhaltsabhängige Verzweigung enthält.
Verringerung der Speicherzuweisungen
Die Funktion simple_fold übernimmt eine String-Zeichenkette im Besitz, wodurch sie deren Puffer verändern und direkt zurückgeben kann. Wenn der Text vollständig aus ASCII besteht, wird derselbe Speicher nach der Umwandlung der Zeichen an Ort und Stelle ohne zweiten Puffer oder zusätzliche Kopie zurückgegeben.
Wenn Nicht-ASCII-Zeichen vorkommen, erstellt der Algorithmus erst dann einen neuen Puffer, wenn er ein Zeichen erreicht, dessen Länge oder Inhalt sich ändert. Der Beitrag erklärt, dass die meisten Faltungen die UTF-8-Länge beibehalten oder verringern; die beiden Zeichen U+023A und U+023E können ihre Länge jedoch jeweils von zwei auf drei Bytes erhöhen. Deshalb reserviert der Algorithmus einmalig eine maximale Kapazität, die ungefähr dem 1,5-Fachen der Eingabelänge entspricht, anstatt den Puffer schrittweise zu vergrößern und die Daten erneut zu kopieren.
Unveränderte Bytegruppen werden außerdem mit copy_nonoverlapping übertragen, statt Byte für Byte kopiert zu werden. Einige nichtlateinische Texte wie CJK, Hangul, Kana, Arabisch, Hebräisch und Symbole behalten ihre ursprüngliche Speicherzuweisung, wenn sie keine Zeichen enthalten, die gefaltet werden müssen.
Unicode-Verarbeitung im Bytebereich
Unicode 16.0 enthält 1484 einfache Faltungsoperationen. GitHub komprimierte deren Tabelle jedoch auf 1776 Bytes, indem die Ansammlung faltbarer Zeichen in Seiten mit jeweils 64 Codepunkten ausgenutzt wurde. Um zu prüfen, ob ein Zeichen gefaltet werden muss, verwendet der Algorithmus eine Bitkarte. Ist das entsprechende Bit nicht gesetzt, wird das Zeichen sofort abgewiesen, ohne UTF-8 zu dekodieren oder eine Hashtabelle zu durchsuchen.
Innerhalb der Seiten, die Faltungsoperationen enthalten, speichert der Algorithmus zusammenhängende Bereiche statt eines separaten Eintrags für jeden Codepunkt. Die Bereiche werden durch Anfang, Ende, Schrittweite und Differenz beschrieben, wodurch sich etwa 1484 Operationen auf 238 Bereiche verteilen, die über 59 Seiten verteilt sind. Außerdem wird ein paralleler Vergleich mit acht Schlüsseln gleichzeitig verwendet, um den passenden Bereich zu bestimmen.
Nach dem Auffinden des Bereichs werden die gefalteten Zeichen durch das Addieren von Bytes auf UTF-8-Ebene mit einer für den Bereich spezifischen Konstante berechnet, statt das Zeichen in einen Codepunkt zu dekodieren und anschließend erneut zu kodieren. Dadurch lässt sich auch eine Längenänderung verarbeiten, etwa die Umwandlung von U+212A, dem Kelvinzeichen, von drei Bytes in das ein Byte lange Zeichen k oder die Umwandlung von U+023A in ein drei Byte langes Zeichen.
Dieser Ansatz setzt voraus, dass die Eingabe gültiges und kürzestes UTF-8 verwendet, eine Voraussetzung, die durch die Typen String und str in Rust garantiert wird. Rohe Daten aus anderen Quellen müssen dagegen vor der Verwendung dieser Berechnungen auf ihre Gültigkeit geprüft oder normalisiert werden.
Ergebnis und Grenzen der Messungen
Im häufigen ASCII-Fall überschreitet die Geschwindigkeit der Bibliothek 45 Gigabyte pro Sekunde. Den im Beitrag genannten Messungen zufolge ist sie damit mehr als 50 % schneller als die nicht vollständig äquivalente Funktion str::to_lowercase. Bei Eingaben im ungünstigsten Fall, bei denen die meisten Zeichen gefaltet werden müssen, waren die auf Berechnungen im Bytebereich basierenden Lösungen ungefähr doppelt so schnell wie der optimierte Pfad zur UTF-8-Dekodierung und erneuten Kodierung.
GitHub betont, dass die Zahlen und Vergleichsverhältnisse richtungsweisend und nicht wörtlich zwischen Prozessoren übertragbar sind, da sie von der automatischen Vektorisierung, SWAR, Byteberechnungen in little-endian-Reihenfolge sowie von der Speicherbandbreite und der Prozessorarchitektur abhängen. Der Beitrag fasst die Idee in zwei Prinzipien zusammen: den häufigen Pfad vollständig ohne Verzweigungen zu durchsuchen und den seltenen Unicode-Pfad im Bytebereich auszuführen, statt Zeichen zu dekodieren und erneut zu kodieren.