Angenommen, Sie arbeiten mit einem x86 32-Bit-System. Ihre Aufgabe ist es, die Strlen so schnell wie möglich zu implementieren.
Es gibt zwei Probleme, auf die Sie achten müssen: 1. Adressausrichtung. 2. Speicher mit Maschinenwortlänge lesen (4 Byte).
Es ist nicht schwer, die erste Adresse in der angegebenen Zeichenfolge zu finden.
Dann können wir den Speicher einmal mit den 4 Bytes lesen und die Gesamtlänge hochzählen. Aber wir sollten aufhören, sobald in den 4 Bytes ein Null-Byte ist, und die linken Bytes vor Null-Byte zählen. Um das Nullbyte schnell zu überprüfen, gibt es ein Code-Snippet von glibc:
%Vor%Ich habe es in Visual C ++ verwendet, um es mit der CRT-Implementierung zu vergleichen. Die CRTs sind viel schneller als die oben genannten.
Ich bin nicht vertraut mit CRT-Implementierung, haben sie einen schnelleren Weg verwendet, um das Nullbyte zu überprüfen?
Es kommt darauf an. Microsofts Bibliothek hat wirklich zwei verschiedene Versionen von strlen. One ist eine portable Version in C, die die trivialste Version von strlen ist, ziemlich nah (und wahrscheinlich äquivalent) zu:
%Vor% Der andere ist in Assembler-Sprache (wird nur für Intel x86 verwendet), und ziemlich ähnlich zu dem, was Sie oben haben, zumindest so weit wie 4 Bytes laden, Prüfung einer von ihnen ist Null und reagieren entsprechend. Der einzige offensichtliche Unterschied besteht darin, dass sie die Bytes subtrahieren und addieren. I.e. anstelle von word-0x0101010101 verwenden sie word + 0x7efefeff .
Es gibt auch intrinsische Versionen des Compilers, die das REPNE SCAS-Befehlspaar verwenden, obwohl diese im Allgemeinen auf älteren Compilern sind, können sie immer noch ziemlich schnell sein. Es gibt auch SSE2-Versionen von strlen, wie Dr. Agner Fogs Performance-Bibliothek oder etwas wie dies
Entfernen Sie diese "L" -Suffixe und sehen Sie ... Sie fördern alle Berechnungen auf "long"! Bei meinen 32-Bit-Tests verdoppelt das allein die Kosten.
Ich mache auch zwei Mikrooptimierungen:
Da die meisten Strings, die wir scannen, aus ASCII-Zeichen im Bereich 0 ~ 127 bestehen, wird das high-Bit (fast) nie gesetzt , also erst in einem zweiten Test prüfen.
Erhöht einen Index anstelle eines Zeigers , was auf einigen Architekturen (insbesondere x86) günstiger ist und Ihnen die Länge für "frei" ...
Angenommen, Sie kennen die maximal mögliche Länge und haben den Speicher vor der Verwendung auf \ 0 initialisiert, können Sie eine binäre Teilung durchführen und je nach Wert nach links / rechts gehen (\ 0, geteilt nach links, sonst aufgespalten) Recht). Auf diese Weise verringern Sie die Anzahl der erforderlichen Überprüfungen erheblich, um die Länge zu ermitteln. Nicht optimal (erfordert etwas Setup), sollte aber wirklich schnell sein.
// Eric
Eine solche enge Schleife in Assembler wäre natürlich am schnellsten, aber wenn Sie es in C (++) besser lesbar und / oder portabel halten wollen, können Sie die Geschwindigkeit des Standards noch erhöhen funktionieren, indem Sie das register -Schlüsselwort verwenden.
Das Schlüsselwort register veranlasst den Compiler, den Zähler in einem Register auf der CPU statt im Speicher zu speichern, was die Schleife erheblich beschleunigt.
Beachten Sie jedoch, dass das Schlüsselwort register nur ein Vorschlag ist und der Compiler es ignorieren kann, wenn es der Ansicht ist, dass es besser ist, insbesondere wenn bestimmte Optimierungsoptionen verwendet werden. Das heißt, obwohl es mit ziemlicher Sicherheit für eine lokale Klassenvariable in einer Triple-For-Schleife ignoriert wird, wird es wahrscheinlich für den unten stehenden Code geehrt, was die Leistung ziemlich verbessert (fast gleichauf mit der Assembler-Version) ):