case insensitive string comparison möglichst schnell
Verfasst: 24.04.2012, 20:23
Hi,
Ich überlege im Augenblick (rein interessehalber), wie man einen Vergleich zwischen zwei gleich langen ASCII (7 Bits, ihr erinnert euch)-Zeichenketten beliebiger Länge möglichst schnell hinbekommt. Die etablierte Lösung ist, beim Vergleich alle Buchstaben zu Großbuchstaben zu konvertieren.
Weiß jemand, ob das schneller geht?
Einerseits dürften all die Sprünge (vor allem der read-compare-modify-compare-Vorgang) die Sprungvorhersage der CPU enorm strapazieren.
Andererseits sind ASCII-Strings klein und 64 Buchstaben landen auf einen Schlag im Cache und stehen zur Auswertung bereit. Durch out-of-order-Ausführung dürfte also, wenn die CPU zu den tatsächlichen Vergleichen kommt, bereit ein Batzen Buchstaben fertig zu Großbuchstaben konvertiert und die zweite Welle der Sprünge vorhersagbar sein.
Weiter bietet SSE2 die CMOV-Anweisung, die zwei Drittel der Sprünge (nämlich die bei der Konvertierung von Klein- zu Großbuchstaben) eliminiert und durch Datenabhängigkeiten ersetzt. Die Kosten sind, dass beide Pfade unbedingt in die Ausführung wandern.
Eine weitere Möglichkeit wären Nachschlagetabellen, die zeigen, ob zwei Buchstaben gleich sind. Hier werden die vorhersagbaren Sprünge durch Cache-Verfehlungen erkauft: So eine Tabelle wäre naiv 128×128 Bytes == 16 KiB groß, was den Cache ziemlich ruinieren dürfte. Packt man sie auf Bit-Ebene, werden 2 KiB draus. Man kann die Größe auf 1 KiB reduzieren, indem ein weiterer Sprung eingeführt und die Adressierungsarithmetik verkompliziert wird (die Tabelle ist diagonal spiegelsymmetrisch; man müsste immer den größeren ASCII-Wert zuerst nachschlagen und kann dadurch die Hälfte der Einträge sparen).
Ideen?
Ich überlege im Augenblick (rein interessehalber), wie man einen Vergleich zwischen zwei gleich langen ASCII (7 Bits, ihr erinnert euch)-Zeichenketten beliebiger Länge möglichst schnell hinbekommt. Die etablierte Lösung ist, beim Vergleich alle Buchstaben zu Großbuchstaben zu konvertieren.
Weiß jemand, ob das schneller geht?
Einerseits dürften all die Sprünge (vor allem der read-compare-modify-compare-Vorgang) die Sprungvorhersage der CPU enorm strapazieren.
Andererseits sind ASCII-Strings klein und 64 Buchstaben landen auf einen Schlag im Cache und stehen zur Auswertung bereit. Durch out-of-order-Ausführung dürfte also, wenn die CPU zu den tatsächlichen Vergleichen kommt, bereit ein Batzen Buchstaben fertig zu Großbuchstaben konvertiert und die zweite Welle der Sprünge vorhersagbar sein.
Weiter bietet SSE2 die CMOV-Anweisung, die zwei Drittel der Sprünge (nämlich die bei der Konvertierung von Klein- zu Großbuchstaben) eliminiert und durch Datenabhängigkeiten ersetzt. Die Kosten sind, dass beide Pfade unbedingt in die Ausführung wandern.
Eine weitere Möglichkeit wären Nachschlagetabellen, die zeigen, ob zwei Buchstaben gleich sind. Hier werden die vorhersagbaren Sprünge durch Cache-Verfehlungen erkauft: So eine Tabelle wäre naiv 128×128 Bytes == 16 KiB groß, was den Cache ziemlich ruinieren dürfte. Packt man sie auf Bit-Ebene, werden 2 KiB draus. Man kann die Größe auf 1 KiB reduzieren, indem ein weiterer Sprung eingeführt und die Adressierungsarithmetik verkompliziert wird (die Tabelle ist diagonal spiegelsymmetrisch; man müsste immer den größeren ASCII-Wert zuerst nachschlagen und kann dadurch die Hälfte der Einträge sparen).
Ideen?