case insensitive string comparison möglichst schnell

[Krishty]

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?

[joggel]

Also... wenn du hier etwas fragst, dann verstehe ich meist kaum die Frage^^.
Aber, mir fällt hier nur eins ein:
ASCIIs einfach anhand des Zahlenwertes vergleichen?
Jeder ASCII-Wert wird ja durch einen Zahlenwert dargestellt...
Ein cast pro Zeichen und dann vergleichen.
Oder gibt es da noch mehr zu beachten?

okay... anscheinend doch...

Gruß

[eXile]

Ideen?

Ich plädiere auf String in Großbuchstaben umwandeln und strcmp anwenden, da letzteres dank SSE 4 mit dem _mm_cmpistri-Intrinsic den String ziemlich flott wegfuttern kann.

Meine Erfahrung (zumindest mit den wenigen Mathefunktionen, die ich mir genauer angeschaut habe) ist, dass zwar Funktionen mit großen Funktionswerttabellen in Benchmarks sehr gut aussehen (außer vielleicht gegenüber Minimax-Polynomen, welche meiner Meinung nach besser sind); aber in realem Code verwendet kehrt sich dieser Vorteil eher ins Gegenteil um, eben weil (wie du schon sagtest) der Cache sofort platt gemacht wird.

[kimmi]

Ich denke, auch in diesen wirtschaftlich harten Zeiten würde ich zu strncmp raten anstatt zu strcmp.

@Krishty: kannst du deine Ergebnisse bei Zeiten hier mal präsentieren?

ich würde bei kurzen Strings, die in eine Cacheline passen, einen direkten Vergleich durchführen ( mit einem Bit-&-Vergleich, keinen Compare, aber nagelt mich nicht auf den Operator fest, ich muß da immer erst rumprobieren ), bei längeren Strings eXiles Ratschlag folgen und hoffen, dass strncmp SSE4 nutzt.

Gruß Kimmi

[eXile]

Ich denke, auch in diesen wirtschaftlich harten Zeiten würde ich zu strncmp raten anstatt zu strcmp.

Natürlich, es ging mir eher um die Tatsache, dass man halt mit strcmp/strncmp die Strings schnell vergleichen kann (nämlich 16 Zeichen auf einmal); dass man immer strncmp nehmen sollte, wenn man die Wahl hat, ist klar. Mir ist übrigens noch nicht klar, ob beispielsweise Visual Studio wirklich obiges Intrinsic benutzt; im Zweifel muss man das auch selber implementieren.

[BeRsErKeR]

Man könnte einen kleinen Trick mit einer Art Lookup-Tabelle nutzen. Und zwar ist diese 2^7 (also 128) Bytes groß. Zu jedem ASCII-Zeichen wird ein Verundungs-Byte gespeichert. Für die meisten ist dies 255 (0xFF), für alle Kleinbuchstaben ist es 223 (0xDF).

Bei einem Stringvergleich bildet man den Absolutwert der Differenz beider ASCII-Werte und verundet diesen mit den beiden zugehörigen Werten aus der Lookup-Tabelle. Ist das Ergebnis 0 sind die Buchstaben gleich, sonst ungleich. Dadurch werden Klein- und Großbuchstaben als identisch erkannt. Man benötigt aber pro Buchstabe eine Subtraktion, eine Absolutwertbildung und 2 Lookups und Verundungen.

Hier mal ein schnell dahingeschriebener Beispielcode in C:

Code: Ansicht erweitern :: Alles auswählen

#include <stdio.h>
#include <string.h>
#include <math.h>

#define min(a,b) (((a) < (b)) ? (a) : (b))

const char lookup[] =
{
        0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
        0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
        0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
        0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
        0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
        0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
        0xFF, 0xDF, 0xDF, 0xDF, 0xDF, 0xDF, 0xDF, 0xDF, 0xDF, 0xDF, 0xDF, 0xDF, 0xDF, 0xDF, 0xDF, 0xDF,
        0xDF, 0xDF, 0xDF, 0xDF, 0xDF, 0xDF, 0xDF, 0xDF, 0xDF, 0xDF, 0xDF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF
};

// return 1 if equal
// return 0 if not equal
int compare(char *s1, char *s2, int len)
{
        int i;
        for (i=0; i<len; ++i)
        {
                if ((abs(s1[i] - s2[i]) & lookup[s1[i]] & lookup[s2[i]]) != 0)
                        return 0;
        }

        return 1;
}

int main(int argc, char **argv)
{
        int len;

        if (argc < 3)
                return 0;

        len = min(strlen(argv[1]), strlen(argv[2]));

        if (compare(argv[1], argv[2], len))
                printf("Die Strings \"%s\" und \"%s\" sind gleich.\n", argv[1], argv[2]);
        else
                printf("Die Strings \"%s\" und \"%s\" sind NICHT gleich.\n", argv[1], argv[2]);

        return 0;
}

[simbad]

isupper/islower verwendet eine Lookup-Table, wenn ich mich recht entsinne. Ob die irgendwo noch einen ineffektive Umsetzung beinhalten weiß ich nicht.

[BeRsErKeR]

Hmm eine einfache Lookup-Tabelle, die auf Großbuchstaben Kleinbuchstaben mappt wäre natürlich noch besser. Ich frage mich nur ob es schneller ist den Lookup beim Vergleich zweier Zeichen durchzuführen, oder vorher den gesamten String in Kleinbuchstaben umzuwandeln.

[dot]

Also ich würd in erster Linie mal was in Richtung Bitgeschupse suchen. Immerhin unterscheiden sich die ASCII Codes der Groß- und Kleinbuchstaben nur in einem einzelnen Bit (eben genau um diesen Vergleich einfacher zu gestalten).
Das sechste Bit auf 0 setzen, vergleichen und bei Gleichheit schauen ob das Byte aus dem Bereich [65, 90] ist, ist alles was du tun musst. Das sollte sich doch irgendwie einfach realisieren lassen...

[Florian Keßeler]

Hmm eine einfache Lookup-Tabelle, die auf Großbuchstaben Kleinbuchstaben mappt wäre natürlich noch besser. Ich frage mich nur ob es schneller ist den Lookup beim Vergleich zweier Zeichen durchzuführen, oder vorher den gesamten String in Kleinbuchstaben umzuwandeln.

Vermutung: Wenn man beides gleichzeitig macht und beispielsweise aus beiden Strings jeweils ein komplettes Maschinenwort (was auch immer das bei der jeweiligen Architektur heißen mag) in ein Register lädt, die dann byteweise direkt im Register konvertiert und anschließend das komplette Register vergleicht, spart man sich einige Speicherzugriffe und mit etwas Glück passen LUT und Strings in den L1-Cache. Bei entsprechender Verwendung geeigneter Datentypen würde ich aber vermuten, dass ein ausreichend guter Compiler das sowieso so macht...

[dot]

Hier mal eine Skizze (Idee ist, mit ein bisschen Bitgefummle 16 Buchstaben auf einmal zu vergleichen):

Code: Ansicht erweitern :: Alles auswählen

#include <iostream>
#include <locale>
#include <algorithm>
#include <cassert>
#include <emmintrin.h>


bool groundTruth(const char* a, size_t la, const char* b, size_t lb)
{
  if (la != lb)
    return false;

  std::locale loc;
  const std::ctype<char>& ct = std::use_facet<std::ctype<char>>(loc);

  const char* ea = a + la;
  while (a < ea)
    if (ct.tolower(*a++) != ct.tolower(*b++))
      return false;
  return true;
}


bool equal(const char* a, size_t la, const char* b, size_t lb)
{
  if (la != lb)
    return false;

  assert((la % sizeof(__m128i)) == 0);

  const __m128i* ptra = reinterpret_cast<const __m128i*>(a);
  const __m128i* ptrb = reinterpret_cast<const __m128i*>(b);
  const __m128i* end = ptra + la / sizeof(__m128i);

  __m128i mask = _mm_set_epi8(0x5F, 0x5F, 0x5F, 0x5F, 0x5F, 0x5F, 0x5F, 0x5F, 0x5F, 0x5F, 0x5F, 0x5F, 0x5F, 0x5F, 0x5F, 0x5F);
  __m128i range_start = _mm_set_epi8(0x40, 0x40, 0x40, 0x40, 0x40, 0x40, 0x40, 0x40, 0x40, 0x40, 0x40, 0x40, 0x40, 0x40, 0x40, 0x40);
  __m128i range_end = _mm_set_epi8(0x5B, 0x5B, 0x5B, 0x5B, 0x5B, 0x5B, 0x5B, 0x5B, 0x5B, 0x5B, 0x5B, 0x5B, 0x5B, 0x5B, 0x5B, 0x5B);

  while (ptra < end)
  {
    __m128i x = _mm_load_si128(ptra++);
    __m128i y = _mm_load_si128(ptrb++);
    __m128i masked_x = _mm_and_si128(x, mask);
    __m128i masked_y = _mm_and_si128(y, mask);
    __m128i range_x = _mm_and_si128(_mm_cmpgt_epi8(masked_x, range_start), _mm_cmplt_epi8(masked_x, range_end));  // is x a letter?
    __m128i range_y = _mm_and_si128(_mm_cmpgt_epi8(masked_y, range_start), _mm_cmplt_epi8(masked_y, range_end));  // is y a letter?
    __m128i masked_eq = _mm_and_si128(_mm_and_si128(_mm_cmpeq_epi8(masked_x, masked_y), range_x), range_y);
    __m128i eq = _mm_or_si128(_mm_cmpeq_epi8(x, y), masked_eq);

    int r = _mm_movemask_epi8(eq);

    if (r != 0xFFFF)
      return false;
  }

  return true;
}


int main()
{
  __declspec(align(16)) const char a[] = "aaAAABAAAaaaaaaaccccccccxxxxxxxx";
  __declspec(align(16)) const char b[] = "aaaaabAaaaAAaaaaCCccCCccxxxXXxxx";

  bool b1 = groundTruth(a, sizeof(a) - 1, b, sizeof(b) - 1);
  bool b2 = equal(a, sizeof(a) - 1, b, sizeof(b) - 1);


  return b1 == b2;
}

Für sehr lange Strings könnte man natürlich auch die GPU benutzen

[BeRsErKeR]

Also ich würd in erster Linie mal was in Richtung Bitgeschupse suchen. Immerhin unterscheiden sich die ASCII Codes der Groß- und Kleinbuchstaben nur in einem einzelnen Bit (eben genau um diesen Vergleich einfacher zu gestalten).
Das sechste Bit auf 0 setzen, vergleichen und bei Gleichheit schauen ob das Byte aus dem Bereich [65, 90] ist, ist alles was du tun musst. Das sollte sich doch irgendwie einfach realisieren lassen...

Sowas ähnliches hab ich in meinem letzten Beispiel auch gemacht, indem ich einfach mit 0xFF oder 0xDF verunde. Letzterer Wert löscht bei Verundung das 6. Bit, welches bei einer Differenzbildung von Groß- und Kleinbuchstaben gesetzt wäre (Abstand ist genau 32, also 00100000b). Da die ASCII-Werte der Kleinbuchstaben so hohe Werte haben, dass es keinen zugehörigen ASCII-Wert, der um 32 größer ist gibt (im gültigen 7-Bit-ASCII) ist das ganze auch eindeutig.

[Florian Keßeler]

Für sehr lange Strings könnte man natürlich auch die GPU benutzen

Genau das wollte ich grade vorschlagen

[Krishty]

Wow; entschuldigt, dass ich erst jetzt Zeit zum Antworten habe.

Also... wenn du hier etwas fragst, dann verstehe ich meist kaum die Frage^^.
Aber, mir fällt hier nur eins ein:
ASCIIs einfach anhand des Zahlenwertes vergleichen?
Jeder ASCII-Wert wird ja durch einen Zahlenwert dargestellt...
Ein cast pro Zeichen und dann vergleichen.
Oder gibt es da noch mehr zu beachten?

okay... anscheinend doch...

Gruß

Darauf antworte ich gern – kann ja nicht schaden, das Problem noch einmal von vorn bis hinten zu überdenken.

Also: Richtig; im ASCII wird jedes Zeichen durch einen Zahlenwert repräsentiert. Dabei haben aber auch Groß- und Kleinbuchstaben unterschiedliche Werte – sonst könnte ein Programm ja nicht zwischen Groß und Klein unterscheiden.

Der Vergleich läuft also für alle nicht-Buchstaben-Zeichen (Zahlen, Punkte, Sonderzeichen) mit direktem Vergleich der Zahlenwerte ab. Buchstaben sind ein Sonderfall: Hier muss jeder Zahlenwert zu zwei Zahlenwerten gleichwertig sein (b z.B. für b und B).

Die Frage ist nun, wie dieser Sonderfall möglichst performant verarbeitet werden soll: Sprünge verursachen Datenabhängigkeiten und lassen die Pipeline des Prozessors hungern; Nachschlagetabellen behindern den Cache.

Ideen?

Ich plädiere auf String in Großbuchstaben umwandeln und strcmp anwenden, da letzteres dank SSE 4 mit dem _mm_cmpistri-Intrinsic den String ziemlich flott wegfuttern kann.

Bringt nichts, weil die meisten Strings drei bis zehn Buchstaben lang sind. Ich möchte auch gerne erst bei SSE 2 bleiben, weil ich XP- und x86-kompatibel bleiben muss …

… es geht um das Erkennen von Schlüsselwörtern in Quelltext. Die Parallelisierung über zwei oder vier Buchstaben hinaus ist höchstwahrscheinlich völlig nutzlos.

@Krishty: kannst du deine Ergebnisse bei Zeiten hier mal präsentieren?

Ich habe noch keine; alles erst rein theoretisch

Man könnte einen kleinen Trick mit einer Art Lookup-Tabelle nutzen. Und zwar ist diese 2^7 (also 128) Bytes groß. Zu jedem ASCII-Zeichen wird ein Verundungs-Byte gespeichert. Für die meisten ist dies 255 (0xFF), für alle Kleinbuchstaben ist es 223 (0xDF).

Bei einem Stringvergleich bildet man den Absolutwert der Differenz beider ASCII-Werte und verundet diesen mit den beiden zugehörigen Werten aus der Lookup-Tabelle. Ist das Ergebnis 0 sind die Buchstaben gleich, sonst ungleich. Dadurch werden Klein- und Großbuchstaben als identisch erkannt. Man benötigt aber pro Buchstabe eine Subtraktion, eine Absolutwertbildung und 2 Lookups und Verundungen.

Auch eine interessante Methode. Die Absolutwertbildung lässt sich arithmetisch statt logisch durchführen; das würde aber trotzdem bei jeder Menge Datenabhängigkeiten bleiben.

Hmm eine einfache Lookup-Tabelle, die auf Großbuchstaben Kleinbuchstaben mappt wäre natürlich noch besser. Ich frage mich nur ob es schneller ist den Lookup beim Vergleich zweier Zeichen durchzuführen, oder vorher den gesamten String in Kleinbuchstaben umzuwandeln.

Das kommt darauf an, wie gleich die Strings im Schnitt sind. Wenn die meisten Strings sich direkt im ersten Buchstaben unterscheiden, ist ein Vergleich direkt nach dem Nachschlagen sicher schneller, weil sofort abgebrochen werden kann. Bei der anderen Methode müsste der komplette String konvertiert werden; selbst, wenn sich die Zeichen eindeutig unterscheiden. Dazu kommt die Frage, wo man die konvertierten Strings zwischenspeichern möchte.

Bei entsprechender Verwendung geeigneter Datentypen würde ich aber vermuten, dass ein ausreichend guter Compiler das sowieso so macht...

Nein, denn der Compiler weiß weder, wie lang die einzelnen Strings sind, noch, ob der überzählige Speicher bei Längen, die nicht ein Vielfaches der Wortgröße sind, gleich ist.

Also ich würd in erster Linie mal was in Richtung Bitgeschupse suchen. Immerhin unterscheiden sich die ASCII Codes der Groß- und Kleinbuchstaben nur in einem einzelnen Bit (eben genau um diesen Vergleich einfacher zu gestalten).
Das sechste Bit auf 0 setzen, vergleichen und bei Gleichheit schauen ob das Byte aus dem Bereich [65, 90] ist, ist alles was du tun musst. Das sollte sich doch irgendwie einfach realisieren lassen...

Prüfen, ob ein Byte in einem bestimmten Bereich ist, geht laut Bit Twiddling Hacks mit 7 arithmetischen Operationen; dazu noch ein kleines Bisschen Logik, um das & nur in diesem Fall anzuwenden. Das muss für beide Buchstaben geschehen, bevor der endgültige Vergleich durchgeführt werden kann. Keine Ahnung, wie einfach man das kriegt … danke für den Quelltext; aber, wie gesagt, sind meine Strings dafür viel zu kurz.

Ich schätze, dass letztendlich absolut garnichts daran vorbeiführt, zu benchen … die Zahl der Datenabhängigkeiten und Sprünge bleibt bei allen Lösungen fast konstant; die Optimierungsfrage läuft – so, wie ich das einschätze – nur darauf hinaus, welches von beiden schneller ist.

[simbad]

Wenn du Schlüsselwörter in einem Quelltext suchen willst, warum nimmst du nicht eine Zustandsmaschine, die Zeichen für zeichen prüft.
Da kannst du dann an den entsprechenden transitions sowohl die kleinen als auch die großen Buchstaben eintragen. Damit hast du dann

1. einen schnellen parser
2. brauchst keine konvertierung vor dem parsen

Nur mal so als Idee.