Schnelle Strlen mit Bit-Operationen

Question

fand ich diesen Code

int strlen_my(const char *s) 
{ 
    int len = 0; 
    for(;;) 
    { 
     unsigned x = *(unsigned*)s; 
     if((x & 0xFF) == 0) return len; 
     if((x & 0xFF00) == 0) return len + 1; 
     if((x & 0xFF0000) == 0) return len + 2; 
     if((x & 0xFF000000) == 0) return len + 3; 
     s += 4, len += 4; 
    } 
} 

ich sehr interessiert bin, zu wissen, wie es funktioniert. Kann jemand erklären, wie es funktioniert?

Answer 1

Ein bitweises UND mit Einsen wird das Bitmuster vom anderen Operanden abrufen. Bedeutung, 10101 & 11111 = 10101. Wenn das Ergebnis dieses bitweisen UND 0 ist, wissen wir, dass der andere Operand 0 ist. Ein Ergebnis von 0, wenn ein einzelnes Byte mit 0xFF (Einsen) UND-verknüpft wird, wird ein NULL-Byte anzeigen.

Der Code selbst überprüft jedes Byte des Char-Arrays in Vier-Byte-Partitionen. HINWEIS: Dieser Code ist nicht tragbar; Auf einer anderen Maschine oder einem anderen Compiler könnte ein vorzeichenloser Int-Wert mehr als 4 Bytes betragen. Es wäre wahrscheinlich besser, den uint32_t-Datentyp zu verwenden, um 32-Bit-Ganzzahlen ohne Vorzeichen zu gewährleisten.

Das erste, was zu beachten ist, dass auf einer Little-Endian-Maschine die Bytes, aus denen das Zeichen-Array besteht, in umgekehrter Reihenfolge in einen vorzeichenlosen Datentyp eingelesen werden; Das heißt, wenn die vier Bytes an der aktuellen Adresse das Bitmuster sind, das abcd entspricht, dann enthält die vorzeichenlose Variable das Bitmuster entsprechend dcba.

Die zweite besteht darin, dass eine in C konstante hexadezimale Zahl zu einer int-großen Zahl mit den angegebenen Bytes am kleinen Ende des Bitmusters führt. Bedeutung, 0xFF ist eigentlich 0x000000FF beim Kompilieren mit 4-Byte-Ints. 0xFF00 ist 0x0000FF00. Und so weiter.

So sucht das Programm grundsätzlich nach dem NULL-Zeichen in den vier möglichen Positionen. Wenn in der aktuellen Partition kein NULL-Zeichen vorhanden ist, wird mit dem nächsten Vier-Byte-Slot fortgefahren.

Nehmen Sie das Char-Array abcdef für ein Beispiel. In C haben String-Konstanten immer Null-Terminatoren am Ende, also gibt es ein 0x00 Byte am Ende dieser Zeichenkette.

Es wird funktionieren wie folgt:

Read "ABCD" in unsigned int x:

x: 0x64636261 [ASCII representations for "dcba"] 

prüfen jedes Byte für einen Nullabschluss:

0x64636261 
& 0x000000FF 
    0x00000061 != 0, 

    0x64636261 
& 0x0000FF00 
    0x00006200 != 0, 

und überprüfen Sie die anderen zwei Positionen; Es gibt keine Null-Terminatoren in dieser 4-Byte-Partition, also gehe zur nächsten Partition.

Read "ef" in unsigned int x:

x: 0xBF006665 [ASCII representations for "fe"] 

Notiere die 0xBF Byte; Das ist nach der Länge der Zeichenfolge, also lesen wir in Müll vom Laufzeit-Stack. Es könnte alles sein. Auf einer Maschine, die keine nicht ausgerichteten Zugriffe zulässt, stürzt sie ab, wenn der Speicher nach der Zeichenfolge nicht 1-Byte-ausgerichtet ist. Wenn nur ein Zeichen in der Zeichenfolge verblieben wäre, würden wir zwei zusätzliche Bytes lesen, so dass die Ausrichtung des Speichers neben dem char-Array 2-Byte-ausgerichtet sein müsste.

prüfen jedes Byte für einen Nullabschluss:

0xBF006665 
& 0x000000FF 
    0x00000065 != 0, 

    0xBF006665 
& 0x0000FF00 
    0x00006600 != 0, 

    0xBF006665 
& 0x00FF0000 
    0x00000000 == 0 !!! 

So kehren wir len + 2; len war 4, da wir es einmal um 4 inkrementiert haben, also geben wir 6 zurück, was tatsächlich die Länge der Zeichenkette ist.

Answer 2

Er erkennt, ob auf einem Little-Endian-Rechner irgendwelche Bits in einem bestimmten Byte gesetzt sind. Da wir nur ein einzelnes Byte prüfen (da alle Nibbles, 0 oder 0xF, verdoppelt sind) und es sich zufällig um die letzte Byte-Position handelt (da die Maschine ein Little-Endian ist und das Byte-Muster für die Zahlen daher umgekehrt ist)) können wir sofort wissen, welches Byte NUL enthält.

Answer 3

Die Schleife nimmt 4 Bytes des Char-Arrays für jede Iteration. Die vier if-Anweisungen werden verwendet, um zu bestimmen, ob die Zeichenfolge vorbei ist, wobei eine Bitmaske mit AND-Operator verwendet wird, um den Status des i-ten Elements des ausgewählten Teilstrings zu lesen.

Answer 4

Es handelt undefiniertes Verhalten (nicht ausgerichtete Zugriffe, 75% Wahrscheinlichkeit, auf das Ende des Arrays zuzugreifen) für eine sehr fragwürdige Beschleunigung (es ist sehr wahrscheinlich sogar noch langsamer). Und ist nicht standardkonform, weil int anstelle von size_t zurückgegeben wird. Selbst wenn nicht ausgerichtete Zugriffe auf der Plattform erlaubt sind, können sie viel langsamer sein als ausgerichtete Zugriffe.

Es funktioniert auch nicht auf Big-Endian-Systemen, oder wenn unsigned nicht 32 Bits ist. Nicht zu vergessen die Mehrfachmaske und bedingte Operationen.

Das heißt:

Es testet 4 8-Bit-Bytes zu einer Zeit durch Laden eines unsigned (die nicht einmal mehr als 16 Bits haben, gewährleistet ist). Sobald eines der Bytes den '\0' -Endterminator enthält, gibt es die Summe der aktuellen Länge plus der Position dieses Bytes zurück. Sonst erhöht es die aktuelle Länge um die Anzahl der parallel getesteten Bytes (4) und erhält die nächste unsigned.

Mein Rat: schlechtes Beispiel der Optimierung plus zu viele Unsicherheiten/Fallstricke. Es ist wahrscheinlich nicht noch schneller - einfach gegen die Standardversion Profil:

size_t strlen(restrict const char *s) 
{ 
    size_t l = 0; 
    while (*s++) 
     l++; 
    return l; 
} 

Es könnte eine Art und Weise zu verwenden spezielle Vektor-Anweisungen, aber es sei denn, Sie beweisen, kann dies eine kritische Funktion ist, sollten Sie dies auf die verlassen Compiler - einige können solche Schleifen viel besser abwickeln/beschleunigen.

Answer 5

Code "funktioniert", indem versucht wird, 4 Bytes gleichzeitig zu lesen, indem angenommen wird, dass die Zeichenfolge wie ein Array von int ausgelegt und zugänglich ist. Code liest die erste int und dann jedes Byte der Reihe nach und prüft, ob es das Nullzeichen ist. In der Theorie wird Code, der mit int arbeitet, schneller als 4 einzelne char-Operationen ausgeführt.

Aber es gibt Probleme:

Ausrichtung ist ein Problem: z.B. *(unsigned*)s kann Seg-Fehler.

Endian ist ein Problem, mit if((x & 0xFF) == 0) nicht das Byte an der Adresse bekommen könnte s

s += 4 ist ein Problem, wie sizeof(int) von 4.

Array-Typen unterscheiden int Bereich, besser zu nutzen size_t überschreiten.

---

Ein Versuch, diese Schwierigkeiten zu korrigieren.

#include <stddef.h> 
#include <stdio.h> 

static inline aligned_as_int(const char *s) { 
    max_align_t mat; // C11 
    uintptr_t i = (uintptr_t) s; 
    return i % sizeof mat == 0; 
} 

size_t strlen_my(const char *s) { 
    size_t len = 0; 
    // align 
    while (!aligned_as_int(s)) { 
    if (*s == 0) return len; 
    s++; 
    len++; 
    } 
    for (;;) { 
    unsigned x = *(unsigned*) s; 
    #if UINT_MAX >> CHAR_BIT == UCHAR_MAX 
     if(!(x & 0xFF) || !(x & 0xFF00)) break; 
     s += 2, len += 2; 
    #elif UINT_MAX >> CHAR_BIT*3 == UCHAR_MAX 
     if (!(x & 0xFF) || !(x & 0xFF00) || !(x & 0xFF0000) || !(x & 0xFF000000)) break; 
     s += 4, len += 4; 
    #elif UINT_MAX >> CHAR_BIT*7 == UCHAR_MAX 
     if ( !(x & 0xFF) || !(x & 0xFF00) 
      || !(x & 0xFF0000) || !(x & 0xFF000000) 
      || !(x & 0xFF00000000) || !(x & 0xFF0000000000) 
      || !(x & 0xFF000000000000) || !(x & 0xFF00000000000000)) break; 
     s += 8, len += 8; 
    #else 
     #error TBD code 
    #endif 
    } 
    while (*s++) { 
    len++; 
    } 
    return len; 
} 

Answer 6

Alle Vorschläge sind langsamer als ein einfaches strlen().

Der Grund ist, dass sie die Anzahl der Vergleiche nicht reduzieren und nur einer mit Ausrichtung befasst.

Suchen Sie im Internet nach dem Vorschlag von tlen() an Torbjorn Granlund (tege@sics.se) und Dan Sahlin (dan@sics.se). Wenn Sie auf einer 64-Bit-Plattform sind, hilft dies wirklich, die Dinge zu beschleunigen.