Ruby-Hashes: SWAR-Suche macht kleine Hashes O(1)
Speeding Up (Small) Ruby Hashes
In Rubys Hash-Klasse sind Hashes mit bis zu acht Einträgen keine echten Hashtabellen, sondern Arrays von Paaren. Die lineare Suche in diesen AR-Tabellen ist bis zu 1,58-mal langsamer als der Zugriff auf den ersten Eintrag. Ein Patch ersetzt die Schleife durch eine SWAR-basierte Suche, die alle acht Hinweis-Bytes gleichzeitig in einem 64-Bit-Register prüft. Dadurch wird die Suche unabhängig von der Position des Schlüssels und erreicht O(1)-Verhalten. Der Entwickler Jean Boussier beschreibt die Technik in einem Blogpost und zeigt, dass die Optimierung die Leistung deutlich verbessert.
Die Kernidee ist, dass wir statt der Liste von acht 1-Byte-Zahlen die gesamte 8-Byte-Zahl als ein einziges Zahl interpretieren und dann, solange wir sicherstellen, dass kein Überlauf auftritt, dieselben Operationen auf allen Bytes gleichzeitig ausführen können.