strstr schneller als Algorithmen?

Lesezeit: 8 Minuten

Benutzer-Avatar
Josch

Ich habe eine Datei mit 21056 Bytes.

Ich habe ein Programm in C geschrieben, das die gesamte Datei in einen Puffer liest und dann mehrere Suchalgorithmen verwendet, um die Datei nach einem Token mit 82 Zeichen zu durchsuchen.

Ich habe alle Implementierungen der Algorithmen aus dem verwendet „Exakte String-Matching-Algorithmen“ Seite. Ich habe verwendet: KMP, BM, TBM und Horspool. Und dann habe ich verwendet strstr und jeweils Benchmarking durchgeführt.

Was ich mich frage ist, jedes Mal strstr übertrifft alle anderen Algorithmen. Der einzige, der manchmal schneller ist, ist BM.

Sollte nicht strstr der langsamste sein?

Hier ist mein Benchmark-Code mit einem Beispiel für das Benchmarking von BM:

double get_time()
{
    LARGE_INTEGER t, f;
    QueryPerformanceCounter(&t);
    QueryPerformanceFrequency(&f);
    return (double)t.QuadPart/(double)f.QuadPart;
}
before = get_time();
BM(token, strlen(token), buffer, len);
after = get_time();
printf("Time: %f\n\n", after - before);

Kann mir jemand erklären warum strstr übertrifft die anderen Suchalgorithmen? Ich werde bei Bedarf mehr Code auf Anfrage posten.

  • Der Fehler liegt in deinem Code. Zumindest Horspool sollte sich konstant outperformen strstr – KMP kann tatsächlich langsamer sein. Aber da du deinen Code nicht gepostet hast, können wir dir nicht helfen. Sie können Ihre Daten jedoch bewusst auswählen, um die naive Suche zum Erfolg zu führen, sodass auch die Wahl der Eingabedaten relevant ist.

    – Konrad Rudolf

    28. September 2011 um 17:15 Uhr


  • Suchen Sie ernsthaft nach einem 80-Byte-String in einem 20k-String? … Ihre Stichprobengröße ist so klein, dass Sie es von Hand machen könnten!

    – Blind

    28. September 2011 um 17:18 Uhr


Benutzer-Avatar
ToniK

Warum denken Sie strstr sollte langsamer sein als alle anderen? Weißt du, welcher Algorithmus strstr Verwendet? Das halte ich für ziemlich wahrscheinlich strstr verwendet einen fein abgestimmten, prozessorspezifischen, Assembly-codierten Algorithmus der KMP Typ oder besser. In diesem Fall haben Sie keine Chance, es zu übertreffen C für so kleine Benchmarks.

(Der Grund, warum ich das für wahrscheinlich halte, ist, dass Programmierer es lieben, solche Dinge zu implementieren.)

  • @Josh Das tut es, lass dich nicht täuschen.

    – Konrad Rudolf

    28. September 2011 um 17:34 Uhr

  • glibc-Implementierung. Es ist kein Assembler, aber ich bin sicher, dass es stark optimiert ist.

    – Piotr Praszmo

    28. September 2011 um 17:35 Uhr


  • @Josh: Tut es nicht, lass dich nicht täuschen!

    – TonyK

    28. September 2011 um 18:00 Uhr

  • @Banthar Color mich überrascht. ich hatte mehrfach angeschaut strstr Implementierungen (ich habe in den letzten Jahren intensiv an Zeichenfolgensuchimplementierungen gearbeitet) und jede Implementierung, die ich gesehen habe, war die naive Suche – was eine ist gute Wahlübrigens (siehe oben). Ich bin auch überrascht, dass sie BM anstelle von Horspool für lange Nadeln verwendet haben, da letzteres bekanntermaßen in typischen Situationen im Durchschnitt besser abschneidet (wiederum siehe oben).

    – Konrad Rudolf

    29. September 2011 um 6:51 Uhr

  • @Konrad: Ah, ich sehe, die Beschreibung des Algorithmus war auf der von mir verlinkten Seite etwas verwirrend formuliert. Aber es ist tatsächlich ein schwächerfreier Algorithmus: konstante Zeit und linearer Raum. Dass es existiert, sollte besser bekannt und geschätzt werden! 🙂 Außerdem ist es genau dort, wo es sein sollte: in der Bibliotheksimplementierung von strstr(). 🙂

    – j_random_hacker

    29. September 2011 um 12:32 Uhr

Benutzer-Avatar
Mischa

Horspool, KMP et al. sind optimal darin, die Anzahl von Byte-Vergleichen zu minimieren.

Dies ist jedoch nicht der Flaschenhals eines modernen Prozessors. Auf einem x86/64-Prozessor wird Ihre Zeichenfolge geladen L1-Cache in Chunks mit Cache-Zeilenbreite (normalerweise 64 Bytes). Egal wie schlau Ihr Algorithmus ist, wenn er Ihnen keine größeren Schritte als das gibt, gewinnen Sie nichts; und der kompliziertere Horspool-Code (mindestens eine Tabellensuche) kann nicht mithalten.

Außerdem stecken Sie mit der “C”-String-Einschränkung der Null-Terminierung fest: SOMEWHERE muss der Code jedes Byte untersuchen.

strstr() wird voraussichtlich für eine Vielzahl von Fällen optimal sein; zB Suche nach winzigen Zeichenfolgen wie "\r\n" in einer kurzen Zeichenfolge sowie in viel längeren Zeichenfolgen, in denen ein intelligenterer Algorithmus eine Hoffnung haben könnte. Die grundlegende strchr/memcmp-Schleife ist über den gesamten Bereich wahrscheinlicher Eingaben ziemlich schwer zu schlagen.

So ziemlich alle x86-kompatiblen Prozessoren seit 2003 haben SSE2 unterstützt. Wenn du zerlegt hast strlen()/x86 für glibc, haben Sie vielleicht bemerkt, dass einige SSE2-PCMPEQ- und MOVMASK-Operationen verwendet werden, um jeweils 16 Bytes auf einmal nach dem Null-Terminator zu suchen. Die Lösung ist so effizient, dass sie die offensichtliche supereinfache Schleife für alles, was länger als die leere Zeichenfolge ist, schlägt.

Ich nahm diese Idee und kam mit a strstr() das schlägt glibc’s strstr() für alle Fälle größer als 1 Byte — wobei der relative Unterschied ziemlich irrelevant ist. Wenn Sie interessiert sind, schauen Sie sich an:

  • Konvergenz SSE2 und strstr()

  • Ein besseres strstr() ohne ASM-Code

    Wenn Sie eine Nicht-SSE2-Lösung sehen möchten, die dominiert strstr() für Zielzeichenfolgen von mehr als 15 Bytes, überprüfen Sie Folgendes:

    die eher Multibyte-Vergleiche verwendet als strchr()um einen Punkt zu finden, an dem ein Memcmp ausgeführt werden soll.

Übrigens haben Sie wahrscheinlich inzwischen herausgefunden, dass die x86 REP SCASB / REP CMPSB-Operationen für alles, was länger als 32 Bytes ist, auf den Arsch fallen und für kürzere Zeichenfolgen keine große Verbesserung darstellen. Ich wünschte, Intel hätte dem etwas mehr Aufmerksamkeit gewidmet, als dem Hinzufügen von SSE4.2-„String“-Operationen.

Für Saiten, die groß genug sind, um eine Rolle zu spielen, zeigen meine Leistungstests, dass BNDM auf ganzer Linie besser ist als Horspool. BNDM ist toleranter gegenüber “pathologischen” Fällen, wie z. B. Zielen, die das letzte Byte eines Musters stark wiederholen. BNDM kann auch SSE2 (128-Bit-Register) auf eine Weise nutzen, die mit 32-Bit-Registern in Bezug auf Effizienz und Anlaufkosten konkurriert. Quellcode hier.

  • Haben Sie versucht, einen Patch an die glibc zu senden? Dies erfordert natürlich einen sorgfältigen Benchmark über eine Vielzahl verschiedener Eingaben, aber Ihre obige Erklärung scheint solide zu sein.

    – Konrad Rudolf

    29. Oktober 2011 um 10:30 Uhr

  • Ist es angesichts der Cache-Optimierung Zeitverschwendung zu versuchen, die naive Suche mit Horspool zu übertreffen?

    – mike

    5. März 2013 um 3:40 Uhr

  • @Mischa, Irgendwelche Ratschläge, wie man diesen Code für Windows kompiliert? Ich habe keine Ahnung, was ffs ist und wo man es bekommt.

    – Benutzer626528

    5. April 2013 um 12:01 Uhr

  • Wow, tut mir leid, dass ich darauf nie geantwortet habe. Fürs Protokoll, das MSVC-Äquivalent ist _BitScanForward(), aber es ist ein bisschen klobig. Ich wickle es ein als (verzeihen Sie bitte den Code in den Kommentaren, O Editor) static inline uint32_t intlowz(uint32_t x) { uint32_t pos; return x ? (_BitScanForward(&pos, x), pos) : 32; }

    – Mischa

    27. Mai 2017 um 23:00 Uhr


Ohne Ihren Code zu sehen, ist es schwer, genau zu sagen. strstr ist stark optimiert und normalerweise in Assemblersprache geschrieben. Es macht Dinge wie das Lesen von Daten von jeweils 4 Bytes und deren Vergleich (Bit-Twiddeln, falls erforderlich, wenn die Ausrichtung nicht stimmt), um die Speicherlatenz zu minimieren. Es kann auch Dinge wie SSE nutzen, um 16 Bytes gleichzeitig zu laden. Wenn Ihr Code jeweils nur ein Byte lädt, wird er wahrscheinlich durch Speicherlatenz zerstört.

Verwenden Sie Ihren Debugger und gehen Sie schrittweise durch die Disassemblierung von strstr — Sie werden wahrscheinlich einige interessante Dinge darin finden.

  • Die Auswirkungen von 4-Byte-Vergleichen und SSE auf die String-Suche sind ziemlich begrenzt, da leider lineare Abhängigkeiten zwischen den Elementen bestehen. Insbesondere können Sie nicht einfach in nicht überlappenden 4-Byte-Blöcken vergleichen: Selbst wenn Sie jeweils 4 Bytes vergleichen, müssen Sie immer noch überlappende Blöcke vergleichen, ohne viel zu gewinnen.

    – Konrad Rudolf

    29. September 2011 um 6:56 Uhr

  • @Konrad: strstr kann grundsätzlich als Loop-Around implementiert werden strchr und strcmp/memcmp (mit memcmp erfordert eine Initiale strlen). strchr kann mit einigen Bit-Twiddling-Tricks und 4-Byte-Ladevorgängen implementiert werden. memcmp kann 4 Bytes gleichzeitig von jedem der beiden Komparanden laden und diese Wörter vergleichen. Wenn die beiden Operanden nicht die gleiche Ausrichtung haben, verfolgen Sie jeweils zwei Wörter und ändern sie mit Bits, um das falsch ausgerichtete Wort mit der anderen Zeichenfolge zu vergleichen. Sehen sysdeps/x86_64/memcmp.S in glibc zum Beispiel.

    – Adam Rosenfield

    29. September 2011 um 17:35 Uhr

  • @Konrad: Sie gewinnen etwas, wenn Sie die ersten 4 Bytes eines Musters mit einem gleitenden 4-Byte-Fenster vergleichen, indem Sie das nächste Byte der Zielzeichenfolge verschieben und in das Ende eines 32-Bit-Wortes einfügen. Es ist nicht so, wie Sie es sich wünschen würden, da das Mischen von 8- und 32-Bit-Befehlen auf demselben Register die Befehlspipeline blockiert. SSE ist eine andere Geschichte: Sie können 16 Bytes aus der Zielzeichenfolge mit dem ersten Byte des Musters vergleichen, das 16 Mal repliziert wird. Das rockt ernsthaft. Siehe meinen Beitrag unten zu einem Artikel mit weiteren Details.

    – Mischa

    28. Oktober 2011 um 18:48 Uhr

Stellen Sie sich vor, Sie möchten etwas reinigen lassen. Sie könnten es einfach selbst reinigen oder zehn professionelle Reinigungskräfte mit der Reinigung beauftragen. Handelt es sich bei der Reinigungsaufgabe um ein Bürogebäude, wäre letztere Lösung vorzuziehen. Wenn es sich bei der Reinigungsaufgabe um ein Fenster handelte, wäre Ersteres vorzuziehen.

Sie erhalten nie eine Amortisation für die Zeit, die Sie für die Einrichtung aufgewendet haben, um die Arbeit effizient zu erledigen, da die Arbeit nicht sehr lange dauert.

1186660cookie-checkstrstr schneller als Algorithmen?

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy