Warum muss glibcs ​​strlen so kompliziert sein, um schnell zu laufen?

286

Ich habe hier den strlenCode durchgesehen und mich gefragt, ob die im Code verwendeten Optimierungen wirklich benötigt werden. Warum funktioniert so etwas zum Beispiel nicht gleich gut oder besser?

unsigned long strlen(char s[]) {
    unsigned long i;
    for (i = 0; s[i] != '\0'; i++)
        continue;
    return i;
}

Ist einfacherer Code für den Compiler nicht besser und / oder einfacher zu optimieren?

Der Code strlenauf der Seite hinter dem Link sieht folgendermaßen aus:

/* Copyright (C) 1991, 1993, 1997, 2000, 2003 Free Software Foundation, Inc.
   This file is part of the GNU C Library.
   Written by Torbjorn Granlund ([email protected]),
   with help from Dan Sahlin ([email protected]);
   commentary by Jim Blandy ([email protected]).

   The GNU C Library is free software; you can redistribute it and/or
   modify it under the terms of the GNU Lesser General Public
   License as published by the Free Software Foundation; either
   version 2.1 of the License, or (at your option) any later version.

   The GNU C Library is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   Lesser General Public License for more details.

   You should have received a copy of the GNU Lesser General Public
   License along with the GNU C Library; if not, write to the Free
   Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
   02111-1307 USA.  */

#include <string.h>
#include <stdlib.h>

#undef strlen

/* Return the length of the null-terminated string STR.  Scan for
   the null terminator quickly by testing four bytes at a time.  */
size_t
strlen (str)
     const char *str;
{
  const char *char_ptr;
  const unsigned long int *longword_ptr;
  unsigned long int longword, magic_bits, himagic, lomagic;

  /* Handle the first few characters by reading one character at a time.
     Do this until CHAR_PTR is aligned on a longword boundary.  */
  for (char_ptr = str; ((unsigned long int) char_ptr
            & (sizeof (longword) - 1)) != 0;
       ++char_ptr)
    if (*char_ptr == '\0')
      return char_ptr - str;

  /* All these elucidatory comments refer to 4-byte longwords,
     but the theory applies equally well to 8-byte longwords.  */

  longword_ptr = (unsigned long int *) char_ptr;

  /* Bits 31, 24, 16, and 8 of this number are zero.  Call these bits
     the "holes."  Note that there is a hole just to the left of
     each byte, with an extra at the end:

     bits:  01111110 11111110 11111110 11111111
     bytes: AAAAAAAA BBBBBBBB CCCCCCCC DDDDDDDD

     The 1-bits make sure that carries propagate to the next 0-bit.
     The 0-bits provide holes for carries to fall into.  */
  magic_bits = 0x7efefeffL;
  himagic = 0x80808080L;
  lomagic = 0x01010101L;
  if (sizeof (longword) > 4)
    {
      /* 64-bit version of the magic.  */
      /* Do the shift in two steps to avoid a warning if long has 32 bits.  */
      magic_bits = ((0x7efefefeL << 16) << 16) | 0xfefefeffL;
      himagic = ((himagic << 16) << 16) | himagic;
      lomagic = ((lomagic << 16) << 16) | lomagic;
    }
  if (sizeof (longword) > 8)
    abort ();

  /* Instead of the traditional loop which tests each character,
     we will test a longword at a time.  The tricky part is testing
     if *any of the four* bytes in the longword in question are zero.  */
  for (;;)
    {
      /* We tentatively exit the loop if adding MAGIC_BITS to
     LONGWORD fails to change any of the hole bits of LONGWORD.

     1) Is this safe?  Will it catch all the zero bytes?
     Suppose there is a byte with all zeros.  Any carry bits
     propagating from its left will fall into the hole at its
     least significant bit and stop.  Since there will be no
     carry from its most significant bit, the LSB of the
     byte to the left will be unchanged, and the zero will be
     detected.

     2) Is this worthwhile?  Will it ignore everything except
     zero bytes?  Suppose every byte of LONGWORD has a bit set
     somewhere.  There will be a carry into bit 8.  If bit 8
     is set, this will carry into bit 16.  If bit 8 is clear,
     one of bits 9-15 must be set, so there will be a carry
     into bit 16.  Similarly, there will be a carry into bit
     24.  If one of bits 24-30 is set, there will be a carry
     into bit 31, so all of the hole bits will be changed.

     The one misfire occurs when bits 24-30 are clear and bit
     31 is set; in this case, the hole at bit 31 is not
     changed.  If we had access to the processor carry flag,
     we could close this loophole by putting the fourth hole
     at bit 32!

     So it ignores everything except 128's, when they're aligned
     properly.  */

      longword = *longword_ptr++;

      if (
#if 0
      /* Add MAGIC_BITS to LONGWORD.  */
      (((longword + magic_bits)

        /* Set those bits that were unchanged by the addition.  */
        ^ ~longword)

       /* Look at only the hole bits.  If any of the hole bits
          are unchanged, most likely one of the bytes was a
          zero.  */
       & ~magic_bits)
#else
      ((longword - lomagic) & himagic)
#endif
      != 0)
    {
      /* Which of the bytes was the zero?  If none of them were, it was
         a misfire; continue the search.  */

      const char *cp = (const char *) (longword_ptr - 1);

      if (cp[0] == 0)
        return cp - str;
      if (cp[1] == 0)
        return cp - str + 1;
      if (cp[2] == 0)
        return cp - str + 2;
      if (cp[3] == 0)
        return cp - str + 3;
      if (sizeof (longword) > 4)
        {
          if (cp[4] == 0)
        return cp - str + 4;
          if (cp[5] == 0)
        return cp - str + 5;
          if (cp[6] == 0)
        return cp - str + 6;
          if (cp[7] == 0)
        return cp - str + 7;
        }
    }
    }
}
libc_hidden_builtin_def (strlen)

Warum läuft diese Version schnell?

Macht es nicht viel unnötige Arbeit?

Leichtigkeitsrennen im Orbit
quelle
2
Kommentare sind nicht für eine ausführliche Diskussion gedacht. Dieses Gespräch wurde in den Chat verschoben .
Samuel Liew
18
Das offizielle Quell-Repository für GNU libc befindet sich zum späteren Nachschlagen unter < sourceware.org/git/?p=glibc.git >. < sourceware.org/git/?p=glibc.git;a=blob;f=string/… > zeigt tatsächlich Code ähnlich dem oben genannten an. sysdepsAuf den meisten von glibc unterstützten Architekturen wird jedoch stattdessen eine handgeschriebene Assembler-Implementierung aus dem Verzeichnis verwendet (die am häufigsten verwendete Architektur ohne Ersatz ist MIPS).
zwol
9
Abstimmung, um dies als primär meinungsbasiert zu schließen; "Werden xxx in xxx wirklich benötigt?" ist subjektiv zu den Meinungen der Menschen.
SS Anne
2
@ JL2210: Guter Punkt, der Titel wurde korrigiert, um den Geist der Frage in einem Titel festzuhalten, der nicht so klingt, als würde er sich fragen, ob Leistung benötigt wird. Warum brauchen wir diese Optimierungen, um Leistung zu erzielen?
Peter Cordes
9
@ JL2210 FWIW, der ursprüngliche Titel war "Warum ist strlen in C so komplex?", Und er wurde als "zu breit" geschlossen, dann wieder geöffnet und dann als "hauptsächlich meinungsbasiert" geschlossen. Ich habe versucht, dies zu beheben (in der Zwischenzeit in das Kreuzfeuer von "Du hast meine Frage gebrochen!" Und "Ihr missbraucht eure Bearbeitungsfähigkeiten!"), Aber IMVHO lag das Problem (und liegt immer noch) in der Grundvoraussetzung der Frage. Das war problematisch ("Dieser Code ist zu komplex, als dass ich ihn verstehen könnte" ist nicht gut für Fragen und Antworten geeignet - IMO ist es eine Bitte um Nachhilfe, keine Antwort). Ich berühre es nicht wieder mit einer 60-Fuß-Stange :)

Antworten:

233

Sie brauchen keinen solchen Code und sollten ihn auch nie schreiben - insbesondere, wenn Sie kein C-Compiler / Standardbibliotheksanbieter sind. Es ist Code, der verwendet wird, um strleneinige sehr fragwürdige Speed-Hacks und Annahmen zu implementieren (die nicht mit Behauptungen getestet oder in den Kommentaren erwähnt werden):

  • unsigned long ist entweder 4 oder 8 Bytes
  • Bytes sind 8 Bits
  • Ein Zeiger kann auf unsigned long longund nicht geworfen werdenuintptr_t
  • Man kann den Zeiger einfach ausrichten, indem man prüft, ob die 2 oder 3 Bits niedrigster Ordnung Null sind
  • man kann als unsigned longs auf einen String zugreifen
  • man kann über das Ende des Arrays hinaus ohne negative Auswirkungen lesen.

Darüber hinaus könnte ein guter Compiler sogar Code ersetzen, der als geschrieben wurde

size_t stupid_strlen(const char s[]) {
    size_t i;
    for (i=0; s[i] != '\0'; i++)
        ;
    return i;
}

( size_tBeachten Sie strlen, dass es sich um einen Typ handeln muss, der mit einer integrierten Inline-Version des eingebauten Compilers kompatibel ist , oder vektorisieren Sie den Code. Es ist jedoch unwahrscheinlich, dass ein Compiler die komplexe Version optimieren kann.


Die strlenFunktion wird in C11 7.24.6.3 wie folgt beschrieben :

Beschreibung

  1. Die strlenFunktion berechnet die Länge der Zeichenfolge, auf die s zeigt.

Kehrt zurück

  1. Die strlenFunktion gibt die Anzahl der Zeichen vor dem abschließenden Nullzeichen zurück.

Wenn nun der String ist, auf durch swar in einer Reihe von Zeichen gerade lang genug , um die Zeichenfolge und dem abschließenden NUL enthält, das Verhalten wird nicht definiert , wenn wir die Zeichenfolge nach dem Nullabschluss zuzugreifen, zum Beispiel in

char *str = "hello world";  // or
char array[] = "hello world";

Die einzige Möglichkeit in C, die vollständig portabel / standardkonform ist, dies korrekt zu implementieren , ist die Art und Weise, wie sie in Ihrer Frage geschrieben ist , mit Ausnahme trivialer Transformationen. Sie können so tun, als wären Sie schneller, indem Sie die Schleife usw. abrollen, aber es muss noch getan werden jeweils ein Byte .

(Wie Kommentatoren hervorgehoben haben, ist es nicht immer schlecht, vernünftige oder bekanntermaßen sichere Annahmen zu nutzen, wenn eine strikte Portabilität zu belastend ist. Insbesondere bei Code, der Teil einer bestimmten C-Implementierung ist Regeln, bevor Sie wissen, wie / wann Sie sie biegen können.)


Die verknüpfte strlenImplementierung überprüft zuerst die Bytes einzeln, bis der Zeiger auf die natürliche 4- oder 8-Byte-Ausrichtungsgrenze von zeigt unsigned long. Der C-Standard besagt, dass der Zugriff auf einen Zeiger, der nicht richtig ausgerichtet ist, ein undefiniertes Verhalten aufweist . Dies muss also unbedingt getan werden, damit der nächste schmutzige Trick noch schmutziger wird. (In der Praxis tritt bei einer anderen CPU-Architektur als x86 ein falsch ausgerichteter Wort- oder Doppelwortladevorgang auf. C ist keine portable Assemblersprache, wird jedoch von diesem Code auf diese Weise verwendet.) Dies ermöglicht auch das Lesen über das Ende eines Objekts hinaus, ohne dass bei Implementierungen, bei denen der Speicherschutz in ausgerichteten Blöcken (z. B. virtuellen 4-KB-Speicherseiten) funktioniert, Fehler auftreten können.

Jetzt kommt der schmutzige Teil: der Code bricht das Versprechen und liest 4 oder 8 8-Bit zu einem Zeitpunkt Bytes (a long int) und verwendet einen wenig Trick mit unsigned zusätzlich zu schnell herausfinden, ob es gab kein in denen Null - Bytes 4 oder 8 Bytes - Es wird eine speziell gestaltete Zahl verwendet, die dazu führt, dass das Übertragsbit Bits ändert, die von einer Bitmaske abgefangen werden. Im Wesentlichen würde dies dann herausfinden, ob eines der 4 oder 8 Bytes in der Maske Nullen sind, die angeblich schneller sind als das Durchlaufen jedes dieser Bytes. Schließlich gibt es am Ende eine Schleife, um herauszufinden, welches Byte die erste Null war, falls vorhanden, und um das Ergebnis zurückzugeben.

Das größte Problem ist, dass es in sizeof (unsigned long) - 1Zeiten außerhalb von sizeof (unsigned long)Fällen über das Ende der Zeichenfolge hinaus liest - nur wenn sich das Nullbyte im zuletzt aufgerufenen Byte befindet (dh im Little-Endian das höchstwertige und im Big-Endian das niedrigstwertige). , greift es nicht außerhalb der Grenzen auf das Array zu!


Der Code strlenist fehlerhafter Code , obwohl er zur Implementierung in einer C-Standardbibliothek verwendet wird . Es enthält mehrere implementierungsdefinierte und undefinierte Aspekte und sollte nirgendwo anstelle des vom System bereitgestellten verwendet werden. strlenIch habe die Funktion the_strlenhier umbenannt und Folgendes hinzugefügt main:

int main(void) {
    char buf[12];
    printf("%zu\n", the_strlen(fgets(buf, 12, stdin)));
}

Der Puffer ist sorgfältig dimensioniert, damit er genau die hello worldZeichenfolge und den Terminator aufnehmen kann. Auf meinem 64-Bit-Prozessor sind unsigned longes jedoch 8 Bytes, sodass der Zugriff auf den letzteren Teil diesen Puffer überschreiten würde.

Wenn ich jetzt mit -fsanitize=undefinedund kompiliere und -fsanitize=addressdas resultierende Programm ausführe, erhalte ich:

% ./a.out
hello world
=================================================================
==8355==ERROR: AddressSanitizer: stack-buffer-overflow on address 0x7ffffe63a3f8 at pc 0x55fbec46ab6c bp 0x7ffffe63a350 sp 0x7ffffe63a340
READ of size 8 at 0x7ffffe63a3f8 thread T0
    #0 0x55fbec46ab6b in the_strlen (.../a.out+0x1b6b)
    #1 0x55fbec46b139 in main (.../a.out+0x2139)
    #2 0x7f4f0848fb96 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x21b96)
    #3 0x55fbec46a949 in _start (.../a.out+0x1949)

Address 0x7ffffe63a3f8 is located in stack of thread T0 at offset 40 in frame
    #0 0x55fbec46b07c in main (.../a.out+0x207c)

  This frame has 1 object(s):
    [32, 44) 'buf' <== Memory access at offset 40 partially overflows this variable
HINT: this may be a false positive if your program uses some custom stack unwind mechanism or swapcontext
      (longjmp and C++ exceptions *are* supported)
SUMMARY: AddressSanitizer: stack-buffer-overflow (.../a.out+0x1b6b) in the_strlen
Shadow bytes around the buggy address:
  0x10007fcbf420: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10007fcbf430: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10007fcbf440: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10007fcbf450: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10007fcbf460: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
=>0x10007fcbf470: 00 00 00 00 00 00 00 00 00 00 f1 f1 f1 f1 00[04]
  0x10007fcbf480: f2 f2 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10007fcbf490: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10007fcbf4a0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10007fcbf4b0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10007fcbf4c0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
==8355==ABORTING

dh schlimme Dinge sind passiert.

Antti Haapala
quelle
120
Betreff: "sehr fragwürdige Speed-Hacks und Annahmen" - das heißt, sehr tragbar in portablem Code . Die Standardbibliothek wurde für eine bestimmte Compiler / Hardware-Kombination geschrieben, wobei das tatsächliche Verhalten von Dingen bekannt ist, die in der Sprachdefinition nicht definiert sind. Ja, die meisten Leute sollten keinen solchen Code schreiben, aber im Zusammenhang mit der Implementierung der Standardbibliothek ist nicht portabel nicht von Natur aus schlecht.
Pete Becker
4
Stimmen Sie zu, schreiben Sie niemals solche Dinge selbst. Oder fast nie. Vorzeitige Optimierung ist die Quelle allen Übels. (In diesem Fall könnte es tatsächlich motiviert sein). Wenn Sie am Ende viele strlen () -Aufrufe an derselben sehr langen Zeichenfolge ausführen, könnte Ihre Anwendung möglicherweise anders geschrieben sein. Sie können als Beispiel die Zeichenfolgenlänge bereits beim Erstellen der Zeichenfolge in einer Variablen speichern und müssen strlen () überhaupt nicht aufrufen.
Ghellquist
65
@ghellquist: Die Optimierung eines häufig verwendeten Bibliotheksaufrufs ist kaum eine "vorzeitige Optimierung".
Jamesqf
7
@Antti Haapala: Genau warum denkst du, sollte strlen O (1) sein? Und was wir hier haben, sind mehrere Implementierungen, die alle O (n) sind, aber mit unterschiedlichen konstanten Multiplikatoren. Sie denken vielleicht nicht, dass dies wichtig ist, aber für einige von uns ist eine Implementierung eines O (n) -Algorithmus, der seine Arbeit in Mikrosekunden erledigt, viel besser als eine, die Sekunden oder sogar Millisekunden dauert, da sie im Jahr mehrere Milliarden Mal aufgerufen werden kann Verlauf eines Jobs.
Jamesqf
8
@PeteBecker: Nicht nur, dass das Schreiben von nicht portierbarem Code im Kontext von Standardbibliotheken (in diesem Fall jedoch nicht so sehr) die Norm sein kann, da der Zweck einer Standardbibliothek darin besteht, eine Standardschnittstelle für implementierungsspezifische Inhalte bereitzustellen.
PlasmaHH
148

Es gab viele (leicht oder ganz) falsche Vermutungen in Kommentaren zu einigen Details / Hintergründen dafür.

Sie sehen die optimierte C-Fallback-optimierte Implementierung von glibc. (Für ISAs ohne handgeschriebene asm-Implementierung) . Oder eine alte Version dieses Codes, die sich noch im glibc-Quellbaum befindet. https://code.woboq.org/userspace/glibc/string/strlen.c.html ist ein Code-Browser, der auf dem aktuellen Glibc-Git-Baum basiert. Anscheinend wird es immer noch von einigen Mainstream-Glibc-Zielen verwendet, einschließlich MIPS. (Danke @zwol).

Auf gängigen ISAs wie x86 und ARM verwendet glibc handgeschriebenen asm

Der Anreiz, etwas an diesem Code zu ändern, ist also geringer als Sie vielleicht denken.

Dieser Bithack-Code ( https://graphics.stanford.edu/~seander/bithacks.html#ZeroInWord ) ist nicht das, was tatsächlich auf Ihrem Server / Desktop / Laptop / Smartphone ausgeführt wird. Es ist besser als eine naive Byte-zu-Zeit-Schleife, aber selbst dieser Bithack ist ziemlich schlecht im Vergleich zu einem effizienten ASM für moderne CPUs (insbesondere x86, wo AVX2 SIMD das Überprüfen von 32 Bytes mit ein paar Anweisungen ermöglicht und 32 bis 64 Bytes pro Takt zulässt Zyklus in der Hauptschleife, wenn Daten im L1d-Cache auf modernen CPUs mit 2 / Takt-Vektorlast und ALU-Durchsatz heiß sind, dh für mittelgroße Zeichenfolgen, bei denen der Startaufwand nicht dominiert.)

glibc verwendet dynamische Verknüpfungstricks, um strleneine optimale Version für Ihre CPU zu finden. Selbst innerhalb von x86 gibt es eine SSE2-Version (16-Byte-Vektoren, Baseline für x86-64) und eine AVX2-Version (32-Byte-Vektoren).

x86 verfügt über eine effiziente Datenübertragung zwischen Vektor- und Allzweckregistern, was es einzigartig (?) macht, SIMD zu verwenden, um Funktionen für Zeichenfolgen mit impliziter Länge zu beschleunigen, bei denen die Schleifensteuerung datenabhängig ist. pcmpeqb/ pmovmskbermöglicht das gleichzeitige Testen von 16 separaten Bytes.

glibc hat eine AArch64-Version wie die mit AdvSIMD und eine Version für AArch64-CPUs, bei der Vektor-> GP-Register die Pipeline blockieren, sodass dieser Bithack tatsächlich verwendet wird . Verwendet jedoch die Anzahl der führenden Nullen, um das Byte innerhalb des Registers zu finden, sobald es einen Treffer erhält, und nutzt die effizienten nicht ausgerichteten Zugriffe von AArch64, nachdem nach Seitenkreuzungen gesucht wurde.

Ebenfalls verwandt: Warum ist dieser Code bei aktivierten Optimierungen 6,5-mal langsamer? hat einige weitere Details darüber, was in x86 asm schnell und langsam ist, strlenmit einem großen Puffer und einer einfachen asm-Implementierung, die für gcc hilfreich sein kann, um zu wissen, wie man inline ist. (Einige gcc-Versionen sind unklug inline, rep scasbwas sehr langsam ist, oder ein 4-Byte-Bithack wie dieser. Daher muss das Inline-Strlen-Rezept von GCC aktualisiert oder deaktiviert werden.)

Asm hat kein "undefiniertes Verhalten" im C-Stil . Es ist sicher, auf Bytes im Speicher zuzugreifen, wie Sie möchten, und eine ausgerichtete Last, die gültige Bytes enthält, kann keinen Fehler verursachen. Der Speicherschutz erfolgt durch Granularität der ausgerichteten Seiten. Ausgerichtete Zugriffe, die schmaler sind, können eine Seitengrenze nicht überschreiten. Ist es sicher, über das Ende eines Puffers innerhalb derselben Seite auf x86 und x64 hinaus zu lesen? Die gleiche Überlegung gilt für den Maschinencode, den dieser C-Hack von Compilern für eine eigenständige Nicht-Inline-Implementierung dieser Funktion erstellt.

Wenn ein Compiler Code zum Aufrufen einer unbekannten Nicht-Inline-Funktion ausgibt, muss er davon ausgehen, dass die Funktion alle globalen Variablen und den Speicher ändert, auf den er möglicherweise einen Zeiger hat. Das heißt, alles außer Einheimischen, deren Adresse nicht entkommen ist, muss während des Anrufs im Speicher synchronisiert sein. Dies gilt natürlich für in asm geschriebene Funktionen, aber auch für Bibliotheksfunktionen. Wenn Sie die Optimierung der Verbindungszeit nicht aktivieren, gilt dies sogar für separate Übersetzungseinheiten (Quelldateien).


Warum dies als Teil von glibc sicher ist, aber nicht anders.

Der wichtigste Faktor ist, dass dies strlenzu nichts anderem führen kann. Dafür ist es nicht sicher. Es enthält UB mit striktem Aliasing (Lesen von charDaten durch ein unsigned long*). char*darf alles andere aliasen, aber das Gegenteil ist nicht der Fall .

Dies ist eine Bibliotheksfunktion für eine vorab kompilierte Bibliothek (glibc). Bei der Optimierung der Verbindungszeit für Anrufer wird dies nicht berücksichtigt. Dies bedeutet, dass nur ein sicherer Maschinencode für eine eigenständige Version von kompiliert werden muss strlen. Es muss nicht tragbar / sicher sein C.

Die GNU C-Bibliothek muss nur mit GCC kompiliert werden. Anscheinend wird es nicht unterstützt , es mit clang oder ICC zu kompilieren, obwohl sie GNU-Erweiterungen unterstützen. GCC ist ein früherer Compiler, der eine C-Quelldatei in eine Objektdatei mit Maschinencode umwandelt. Kein Interpreter. Wenn er also nicht zur Kompilierungszeit inline ist, sind Bytes im Speicher nur Bytes im Speicher. dh striktes Aliasing UB ist nicht gefährlich, wenn die Zugriffe mit unterschiedlichen Typen in unterschiedlichen Funktionen erfolgen, die nicht ineinander greifen.

Denken Sie daran, dass strlendas Verhalten durch den ISO C-Standard definiert ist. Dieser Funktionsname ist speziell Teil der Implementierung. Compiler wie GCC behandeln den Namen sogar als integrierte Funktion, sofern Sie ihn nicht verwenden -fno-builtin-strlen. Dies strlen("foo")kann eine Konstante für die Kompilierungszeit sein 3. Die Definition in der Bibliothek wird nur verwendet, wenn gcc beschließt, tatsächlich einen Aufruf an sie zu senden, anstatt ein eigenes Rezept oder etwas anderes einzufügen.

Wenn UB zur Kompilierungszeit für den Compiler nicht sichtbar ist , erhalten Sie einen vernünftigen Maschinencode. Der Maschinencode muss Arbeit für den nicht-UB Fall, und selbst wenn man wollte , gibt es keine Möglichkeit für die asm zu erkennen , welche Arten der Anrufer verwendet , um Daten zu setzen in den Spitz in dem Speicher.

Glibc wird zu einer eigenständigen statischen oder dynamischen Bibliothek kompiliert, die nicht mit der Optimierung der Verbindungszeit kompatibel ist. Die Build-Skripte von glibc erstellen keine "fetten" statischen Bibliotheken, die Maschinencode + gcc enthalten. GIMPLE-interne Darstellung zur Optimierung der Verbindungszeit beim Inlining in ein Programm. (dh libc.anicht an der -fltoOptimierung der Verbindungszeit im Hauptprogramm teilnehmen.) Das Erstellen von glibc auf diese Weise wäre für Ziele, die dies tatsächlich verwenden.c , möglicherweise unsicher .

Wie @zwol kommentiert, kann LTO beim Erstellen von glibc selbst nicht verwendet werden , da "spröder" Code wie dieser beschädigt werden kann , wenn Inlining zwischen glibc-Quelldateien möglich ist. (Es gibt einige interne Verwendungen von strlen, z. B. als Teil der printfImplementierung)


Dies strlenmacht einige Annahmen:

  • CHAR_BITist ein Vielfaches von 8 . Richtig auf allen GNU-Systemen. POSIX 2001 garantiert sogar CHAR_BIT == 8. (Dies sieht für Systeme mit CHAR_BIT= 16oder 32wie einige DSPs sicher aus. Die Schleife für nicht ausgerichtete Prologe führt immer 0 Iterationen aus, wenn sizeof(long) = sizeof(char) = 1jeder Zeiger immer ausgerichtet ist und p & sizeof(long)-1immer Null ist.) Wenn Sie jedoch einen Nicht-ASCII-Zeichensatz mit Zeichen 9 hatten oder 12 Bit breit, 0x8080...ist das falsche Muster.
  • (vielleicht) unsigned longist 4 oder 8 Bytes. Oder vielleicht würde es tatsächlich für jede Größe von unsigned longbis zu 8 funktionieren , und es wird ein verwendet assert(), um dies zu überprüfen.

Diese beiden sind UB nicht möglich, sie sind nur für einige C-Implementierungen nicht portierbar. Dieser Code ist (oder war) Teil der C-Implementierung auf Plattformen, auf denen er funktioniert. Das ist also in Ordnung.

Die nächste Annahme ist das Potenzial C UB:

  • Eine ausgerichtete Last, die gültige Bytes enthält, kann keine Fehler verursachen und ist sicher, solange Sie die Bytes außerhalb des gewünschten Objekts ignorieren. (Richtig in asm auf allen GNU-Systemen und auf allen normalen CPUs, da der Speicherschutz mit Granularität der ausgerichteten Seiten erfolgt. Ist es sicher, über das Ende eines Puffers innerhalb derselben Seite auf x86 und x64 zu lesen? Sicher in C, wenn die UB ist zur Kompilierungszeit nicht sichtbar. Ohne Inlining ist dies hier der Fall. Der Compiler kann nicht beweisen, dass das Lesen nach dem ersten 0UB ist; es könnte sich um ein C- char[]Array handeln, das {1,2,0,3}beispielsweise enthält.)

Dieser letzte Punkt macht es sicher, hier über das Ende eines C-Objekts hinaus zu lesen. Das ist ziemlich sicher, selbst wenn es mit aktuellen Compilern inline ist, da ich denke, dass sie derzeit nicht behandeln, dass ein Ausführungspfad nicht erreichbar ist. Trotzdem ist das strikte Aliasing bereits ein Showstopper, wenn Sie dies jemals inline lassen.

Dann hätten Sie Probleme wie das alte unsichere memcpy CPP-Makro des Linux-Kernels , für das Zeiger-Casting verwendet wurde unsigned long( gcc, striktes Aliasing und Horrorgeschichten ).

Dies strlengeht auf die Zeit zurück, in der man mit solchen Dingen im Allgemeinen davonkommen konnte . Früher war es ziemlich sicher ohne die Einschränkung "nur wenn nicht inliniert" vor GCC3.


UB, das nur sichtbar ist, wenn wir über Anruf- / Ret-Grenzen schauen, kann uns nicht schaden. (zB das Aufrufen von a char buf[]anstelle eines Arrays von unsigned long[]Cast zu a const char*). Sobald der Maschinencode in Stein gemeißelt ist, handelt es sich nur noch um Bytes im Speicher. Bei einem Nicht-Inline-Funktionsaufruf muss davon ausgegangen werden, dass der Angerufene den gesamten Speicher liest.


Schreiben Sie dies sicher, ohne UB strikt zu aliasen

Das GCC-Typattributmay_alias gibt einem Typ den gleichen Alias ​​- alles wie char*. (Vorgeschlagen von @KonradBorowsk). GCC-Header verwenden es derzeit für x86-SIMD-Vektortypen, __m128isodass Sie dies immer sicher tun können _mm_loadu_si128( (__m128i*)foo ). ( Weitere Informationen dazu, was dies bedeutet und was nicht, finden Sie unter Ist "Neuinterpretation_casting" zwischen dem Hardwarevektorzeiger und dem entsprechenden Typ ein undefiniertes Verhalten? )

strlen(const char *char_ptr)
{
  typedef unsigned long __attribute__((may_alias)) aliasing_ulong;

  aliasing_ulong *longword_ptr = (aliasing_ulong *)char_ptr;
  for (;;) {
     unsigned long ulong = *longword_ptr++;  // can safely alias anything
     ...
  }
}

Sie können auch aligned(1)einen Typ mit ausdrücken alignof(T) = 1.
typedef unsigned long __attribute__((may_alias, aligned(1))) unaligned_aliasing_ulong;

Eine tragbare Möglichkeit, eine Aliasing-Last in ISO auszudrücken, besteht darinmemcpy , dass moderne Compiler wissen, wie sie als einzelne Ladeanweisung inline sind. z.B

   unsigned long longword;
   memcpy(&longword, char_ptr, sizeof(longword));
   char_ptr += sizeof(longword);

Dies funktioniert auch für nicht ausgerichtete Lasten, da dies memcpywie bei chareinem Zugriff von Zeit zu Zeit funktioniert . In der Praxis verstehen moderne Compiler dies jedoch memcpysehr gut.

Hier besteht die Gefahr , dass , wenn GCC nicht wissen sicher , dass char_ptrwortausgerichtet ist, es wird nicht auf einigen Plattformen Inline , die nicht unaligned Lasten in asm unterstützen könnten. zB MIPS vor MIPS64r6 oder älterem ARM. Wenn Sie einen tatsächlichen Funktionsaufruf erhalten, um memcpynur ein Wort zu laden (und es in einem anderen Speicher zu belassen), wäre dies eine Katastrophe. GCC kann manchmal sehen, wenn Code einen Zeiger ausrichtet. Oder nach der Char-at-a-Time-Schleife, die eine lange Grenze erreicht, die Sie verwenden können
p = __builtin_assume_aligned(p, sizeof(unsigned long));

Dies vermeidet nicht das mögliche UB zum Vorlesen des Objekts, aber mit dem aktuellen GCC ist dies in der Praxis nicht gefährlich.


Warum eine handoptimierte C-Quelle erforderlich ist: Aktuelle Compiler sind nicht gut genug

Handoptimierter ASM kann sogar noch besser sein, wenn Sie den letzten Leistungsabfall für eine weit verbreitete Standardbibliotheksfunktion wünschen. Besonders für so etwas memcpy, aber auch strlen. In diesem Fall wäre es nicht viel einfacher, C mit x86-Intrinsics zu verwenden, um SSE2 zu nutzen.

Aber hier geht es nur um eine naive vs. bithack C-Version ohne ISA-spezifische Funktionen.

(Ich denke, wir können davon ausgehen strlen, dass es wichtig genug ist, es so schnell wie möglich laufen zu lassen. Daher stellt sich die Frage, ob wir effizienten Maschinencode aus einer einfacheren Quelle erhalten können. Nein, das können wir nicht.)

Aktuelle GCC und Clang sind nicht in der Lage, Schleifen automatisch zu vektorisieren, bei denen die Anzahl der Iterationen vor der ersten Iteration nicht bekannt ist . (z . B. muss geprüft werden können, ob die Schleife mindestens 16 Iterationen ausführen soll, bevor die erste Iteration ausgeführt wird.) z. B. ist die automatische Verankerung von memcpy möglich (Puffer mit expliziter Länge), jedoch nicht strcpy oder strlen (Zeichenfolge mit impliziter Länge), wenn der aktuelle Wert angegeben ist Compiler.

Dies schließt Suchschleifen oder jede andere Schleife mit einem datenabhängigen if()breaksowie einem Zähler ein.

ICC (Intels Compiler für x86) kann einige Suchschleifen automatisch vektorisieren, erstellt jedoch immer noch nur naive Bytes für einen einfachen / naiven C, strlenwie ihn OpenBSDs libc verwendet. ( Godbolt ). (Aus der Antwort von @ Peske ).

strlenFür die Leistung mit aktuellen Compilern ist eine handoptimierte libc erforderlich . Es ist erbärmlich, jeweils 1 Byte auf einmal zu arbeiten (wobei möglicherweise 2 Bytes pro Zyklus auf breiten superskalaren CPUs abgewickelt werden), wenn der Hauptspeicher mit etwa 8 Bytes pro Zyklus Schritt halten kann und der L1d-Cache 16 bis 64 Bytes pro Zyklus liefern kann. (2x 32-Byte-Ladevorgänge pro Zyklus auf modernen Mainstream-x86-CPUs seit Haswell und Ryzen. AVX512 wird nicht berücksichtigt, wodurch die Taktraten nur für die Verwendung von 512-Bit-Vektoren reduziert werden können. Deshalb hat glibc es wahrscheinlich nicht eilig, eine AVX512-Version hinzuzufügen Obwohl mit 256-Bit-Vektoren, wird AVX512VL + BW maskiert in eine Maske verglichen und / ktestoder kortestkönnte das strlenHyperthreading freundlicher machen, indem die Uops / Iteration reduziert wird.)

Ich schließe hier Nicht-x86 ein, das sind die "16 Bytes". Zum Beispiel können die meisten AArch64-CPUs zumindest das, denke ich, und einige sicherlich mehr. Und einige haben genug Ausführungsdurchsatz strlen, um mit dieser Lastbandbreite Schritt zu halten.

Natürlich sollten Programme, die mit großen Zeichenfolgen arbeiten, normalerweise die Längen verfolgen, um zu vermeiden, dass die Länge von C-Zeichenfolgen mit impliziter Länge sehr häufig ermittelt werden muss. Die Leistung von kurzer bis mittlerer Länge profitiert jedoch immer noch von handgeschriebenen Implementierungen, und ich bin sicher, dass einige Programme Strlen für Zeichenfolgen mittlerer Länge verwenden.

Peter Cordes
quelle
12
Einige Anmerkungen: (1) Es ist derzeit nicht möglich, glibc selbst mit einem anderen Compiler als GCC zu kompilieren. (2) Es ist derzeit nicht möglich, glibc selbst mit aktivierten Verbindungszeitoptimierungen zu kompilieren, da der Compiler genau in diesen Fällen UB sieht, wenn Inlining zulässig ist. (3) CHAR_BIT == 8ist eine POSIX-Anforderung (Stand -2001 rev; siehe hier ). (4) Die C-Fallback-Implementierung von strlenwird für einige unterstützte CPUs verwendet. Ich glaube, die häufigste ist MIPS.
zwol
1
Interessanterweise könnte das UB mit striktem Aliasing mithilfe von __attribute__((__may_alias__))Attributen behoben werden (dies ist nicht portierbar, sollte aber für glibc in Ordnung sein).
Konrad Borowski
1
@SebastianRedl: Sie können jedes Objekt über a lesen / schreiben char*, aber es ist immer noch UB, ein char Objekt (z. B. einen Teil von a char[]) über a zu lesen / schreiben long*. Strenge Aliasing-Regel und 'char *'
Peter Cordes
1
Die C- und C ++ - Standards besagen, dass CHAR_BITmindestens 8 sein müssen ( siehe Anhang E von C11), sodass charein Sprachanwalt sich keine Sorgen um mindestens 7-Bit machen muss. Dies wurde durch die Anforderung motiviert: „Für UTF-8-Zeichenfolgenliterale haben die Array-Elemente einen Typ charund werden mit den Zeichen der Multibyte-Zeichenfolge initialisiert, wie in UTF-8 codiert.“
Davislor
2
Diese Analyse scheint eine gute Grundlage für den Vorschlag eines Patches zu sein, der den Code angesichts derzeit deaktivierter Optimierungen robuster macht, abgesehen von einer hervorragenden Antwort.
Deduplikator
61

Dies wird in den Kommentaren in der von Ihnen verlinkten Datei erläutert:

 27 /* Return the length of the null-terminated string STR.  Scan for
 28    the null terminator quickly by testing four bytes at a time.  */

und:

 73   /* Instead of the traditional loop which tests each character,
 74      we will test a longword at a time.  The tricky part is testing
 75      if *any of the four* bytes in the longword in question are zero.  */

In C ist es möglich, detailliert über die Effizienz nachzudenken.

Es ist weniger effizient, einzelne Zeichen auf der Suche nach einer Null zu durchlaufen, als mehr als ein Byte gleichzeitig zu testen, wie dies bei diesem Code der Fall ist.

Die zusätzliche Komplexität ergibt sich aus der Notwendigkeit, sicherzustellen, dass die zu testende Zeichenfolge an der richtigen Stelle ausgerichtet ist, um mehr als ein Byte gleichzeitig zu testen (entlang einer Langwortgrenze, wie in den Kommentaren beschrieben), und aus der Notwendigkeit, sicherzustellen, dass die Annahmen erfüllt sind Über die Größe der Datentypen wird bei Verwendung des Codes nicht verstoßen.

In den meisten (aber nicht allen) modernen Softwareentwicklungen ist diese Aufmerksamkeit für Effizienzdetails nicht erforderlich oder die Kosten für zusätzliche Codekomplexität nicht wert.

Ein Ort, an dem es sinnvoll ist, auf solche Effizienz zu achten, sind Standardbibliotheken wie das von Ihnen verknüpfte Beispiel.


Wenn Sie mehr über Wortgrenzen erfahren möchten, lesen Sie diese Frage und diese ausgezeichnete Wikipedia-Seite

Timothy Jones
quelle
39

Zusätzlich zu den großartigen Antworten hier möchte ich darauf hinweisen, dass der in der Frage verknüpfte Code für die Implementierung von GNU bestimmt ist strlen.

Die OpenBSD-Implementierung vonstrlen ist dem in der Frage vorgeschlagenen Code sehr ähnlich. Die Komplexität einer Implementierung wird vom Autor bestimmt.

...
#include <string.h>

size_t
strlen(const char *str)
{
    const char *s;

    for (s = str; *s; ++s)
        ;
    return (s - str);
}

DEF_STRONG(strlen);

BEARBEITEN : Der oben verlinkte OpenBSD-Code scheint eine Fallback-Implementierung für ISAs zu sein, die keine eigene asm-Implementierung haben. strlenJe nach Architektur gibt es unterschiedliche Implementierungen . Der Code für amd64strlen lautet beispielsweise asm. Ähnlich wie in den Kommentaren / Antworten von PeterCordes, in denen darauf hingewiesen wird, dass die Nicht-Fallback-GNU-Implementierungen ebenfalls asm sind.

Peschke
quelle
5
Dies ist ein sehr schönes Beispiel für die verschiedenen Werte, die in OpenBSD- und GNU-Tools optimiert werden.
Jason
11
Es ist die tragbare Fallback-Implementierung von glibc . Alle wichtigen ISAs haben handgeschriebene asm-Implementierungen in glibc, wobei SIMD verwendet wird, wenn dies hilfreich ist (z. B. auf x86). Siehe code.woboq.org/userspace/glibc/sysdeps/x86_64/multiarch/… und code.woboq.org/userspace/glibc/sysdeps/aarch64/multiarch/…
Peter Cordes
4
Sogar die OpenBSD-Version hat einen Fehler, den das Original vermeidet! Das Verhalten von s - strist undefiniert, wenn das Ergebnis in nicht darstellbar ist ptrdiff_t.
Antti Haapala
1
@AnttiHaapala: In GNU C beträgt die maximale Objektgröße PTRDIFF_MAX. Aber es ist immer noch möglich, mmapmehr Speicher als das unter Linux zu haben (z. B. in einem 32-Bit-Prozess unter einem x86-64-Kernel könnte ich ungefähr 2,7 GB zusammenhängend zuordnen, bevor ich anfing, Fehler zu bekommen). IDK über OpenBSD; Der Kernel könnte es unmöglich machen, dies zu erreichen, returnohne Fehler zu machen oder innerhalb der Größe anzuhalten. Aber ja, Sie würden denken, dass defensive Codierung, die die theoretische C UB vermeidet, etwas ist, was OpenBSD tun möchte. Auch wenn strlennicht inline und echte Compiler werden es nur zu einem Subtrahieren kompilieren.
Peter Cordes
2
@ PeterCordes genau. Gleiches gilt für OpenBSD, z. B. i386-Assembly: cvsweb.openbsd.org/cgi-bin/cvsweb/src/lib/libc/arch/i386/string/…
dchest
34

Kurz gesagt, dies ist eine Leistungsoptimierung, die die Standardbibliothek durchführen kann, indem sie weiß, mit welchem ​​Compiler sie kompiliert wird. Sie sollten keinen solchen Code schreiben, es sei denn, Sie schreiben eine Standardbibliothek und können von einem bestimmten Compiler abhängen. Insbesondere wird die Ausrichtungsanzahl von Bytes gleichzeitig verarbeitet - 4 auf 32-Bit-Plattformen, 8 auf 64-Bit-Plattformen. Dies bedeutet, dass es vier- oder achtmal schneller sein kann als eine naive Byteration.

Betrachten Sie das folgende Bild, um zu erklären, wie dies funktioniert. Nehmen Sie hier die 32-Bit-Plattform an (4-Byte-Ausrichtung).

Nehmen wir an, der Buchstabe "H" von "Hallo Welt!" Zeichenfolge wurde als Argument für bereitgestellt strlen. Da die CPU (idealerweise address % sizeof(size_t) == 0) gerne Dinge im Speicher ausrichtet , werden die Bytes vor der Ausrichtung byteweise mit der langsamen Methode verarbeitet.

Dann wird für jeden Block mit Ausrichtungsgröße durch Berechnung (longbits - 0x01010101) & 0x80808080 != 0geprüft, ob eines der Bytes innerhalb einer Ganzzahl Null ist. Diese Berechnung ist falsch positiv, wenn mindestens eines der Bytes höher als ist 0x80, aber meistens sollte es funktionieren. Ist dies nicht der Fall (wie im gelben Bereich), wird die Länge um die Ausrichtungsgröße erhöht.

Wenn sich herausstellt, dass eines der Bytes innerhalb einer Ganzzahl Null (oder 0x81) ist, wird die Zeichenfolge Byte für Byte überprüft, um die Position von Null zu bestimmen.

Dies kann einen Zugriff außerhalb der Grenzen ermöglichen. Da er sich jedoch innerhalb einer Ausrichtung befindet, ist es mehr als wahrscheinlich, dass er in Ordnung ist. Speicherzuordnungseinheiten haben normalerweise keine Genauigkeit auf Byte-Ebene.

Konrad Borowski
quelle
Diese Implementierung ist Teil von glibc. Das GNU-System bietet Speicherschutz mit Seitengranularität. Ja, eine ausgerichtete Last, die gültige Bytes enthält, ist sicher.
Peter Cordes
size_tist nicht garantiert ausgerichtet zu sein.
SS Anne
32

Sie möchten, dass der Code korrekt, wartbar und schnell ist. Diese Faktoren haben unterschiedliche Bedeutung:

"richtig" ist absolut notwendig.

"wartbar" hängt davon ab, wie viel Sie den Code pflegen werden: strlen ist seit über 40 Jahren eine Standard-C-Bibliotheksfunktion. Es wird sich nicht ändern. Die Wartbarkeit ist daher für diese Funktion ziemlich unwichtig.

"Schnell": In vielen Anwendungen verbrauchen strcpy, strlen usw. einen erheblichen Teil der Ausführungszeit. Den gleichen Geschwindigkeitsgewinn wie diese komplizierte, aber nicht sehr komplizierte Implementierung von strlen durch Verbesserung des Compilers zu erzielen, würde heldenhafte Anstrengungen erfordern.

Schnell zu sein hat einen weiteren Vorteil: Wenn Programmierer herausfinden, dass das Aufrufen von "strlen" die schnellste Methode ist, mit der sie die Anzahl der Bytes in einer Zeichenfolge messen können, sind sie nicht mehr versucht, ihren eigenen Code zu schreiben, um die Dinge schneller zu machen.

Für strlen ist Geschwindigkeit viel wichtiger und Wartbarkeit viel weniger wichtig als für den meisten Code, den Sie jemals schreiben werden.

Warum muss es so kompliziert sein? Angenommen, Sie haben eine 1.000-Byte-Zeichenfolge. Die einfache Implementierung untersucht 1.000 Bytes. Eine aktuelle Implementierung würde wahrscheinlich 64-Bit-Wörter gleichzeitig untersuchen, was 125 64-Bit- oder 8-Byte-Wörter bedeutet. Es könnten sogar Vektoranweisungen verwendet werden, die beispielsweise 32 Bytes gleichzeitig untersuchen, was noch komplizierter und noch schneller wäre. Die Verwendung von Vektoranweisungen führt zu Code, der etwas komplizierter, aber recht einfach ist. Um zu überprüfen, ob eines von acht Bytes in einem 64-Bit-Wort Null ist, sind einige clevere Tricks erforderlich. Für mittlere bis lange Zeichenfolgen ist daher zu erwarten, dass dieser Code etwa viermal schneller ist. Für eine so wichtige Funktion wie strlen lohnt es sich, eine komplexere Funktion zu schreiben.

PS. Der Code ist nicht sehr portabel. Es ist jedoch Teil der Standard C-Bibliothek, die Teil der Implementierung ist - es muss nicht portierbar sein.

PPS. Jemand hat ein Beispiel veröffentlicht, in dem sich ein Debugging-Tool über den Zugriff auf Bytes nach dem Ende einer Zeichenfolge beschwert hat. Es kann eine Implementierung entworfen werden, die Folgendes garantiert: Wenn p ein gültiger Zeiger auf ein Byte ist, gibt jeder Zugriff auf ein Byte in demselben ausgerichteten Block, der gemäß dem C-Standard ein undefiniertes Verhalten wäre, einen nicht angegebenen Wert zurück.

PPPS. Intel hat seinen späteren Prozessoren Anweisungen hinzugefügt, die einen Baustein für die Funktion strstr () bilden (Suchen eines Teilstrings in einem String). Ihre Beschreibung ist umwerfend, aber sie können diese bestimmte Funktion wahrscheinlich 100-mal schneller machen. (Wenn ein Array a "Hello, world!" Und ein Array b mit 16 Bytes "HelloHelloHelloH" beginnt und mehr Bytes enthält, stellt sich heraus, dass die Zeichenfolge a in b nicht früher als ab Index 15 vorkommt.) .

gnasher729
quelle
Oder ... Wenn ich feststelle, dass ich viel stringbasierte Verarbeitung mache und es einen Engpass gibt, werde ich wahrscheinlich meine eigene Version von Pascal Strings implementieren, anstatt strlen zu verbessern ...
Baldrickk
1
Niemand bittet dich , dich zu verbessern. Aber es gut genug zu machen, vermeidet Unsinn wie Leute, die ihre eigenen Strings implementieren.
Gnasher729
24

Kurz gesagt: Das Überprüfen einer Zeichenfolge Byte für Byte ist bei Architekturen, die gleichzeitig größere Datenmengen abrufen können, möglicherweise langsam.

Wenn die Prüfung auf Nullbeendigung auf 32- oder 64-Bit-Basis durchgeführt werden kann, wird die Anzahl der vom Compiler durchzuführenden Prüfungen verringert. Dies versucht der verknüpfte Code unter Berücksichtigung eines bestimmten Systems. Sie machen Annahmen über Adressierung, Ausrichtung, Cache-Nutzung, nicht standardmäßige Compiler-Setups usw. usw.

Das Lesen von Byte für Byte wie in Ihrem Beispiel wäre ein sinnvoller Ansatz auf einer 8-Bit-CPU oder beim Schreiben einer tragbaren Bibliothek, die in Standard C geschrieben ist.

Es ist keine gute Idee, in C-Standardbibliotheken nach Ratschlägen zum Schreiben von schnellem / gutem Code zu suchen, da dieser nicht portierbar ist und auf nicht standardmäßigen Annahmen oder schlecht definiertem Verhalten beruht. Wenn Sie ein Anfänger sind, ist das Lesen eines solchen Codes wahrscheinlich schädlicher als das Lernen.

Lundin
quelle
1
Natürlich ist es sehr wahrscheinlich, dass der Optimierer diese Schleife abrollt oder automatisch vektorisiert, und der Vorabrufer kann dieses Zugriffsmuster trivial erkennen. Ob diese Tricks auf modernen Prozessoren tatsächlich eine Rolle spielen, müsste getestet werden. Wenn es einen Gewinn gibt, werden wahrscheinlich Vektoranweisungen verwendet.
Russbischof
6
@russbishop: Das würden Sie hoffen, aber nein. GCC und Clang sind nicht in der Lage, Schleifen automatisch zu vektorisieren, bei denen die Anzahl der Iterationen vor der ersten Iteration nicht bekannt ist. Dies schließt Suchschleifen oder jede andere Schleife mit einer datenabhängigen ein if()break. ICC kann solche Schleifen automatisch vektorisieren, aber IDK, wie gut es mit einem naiven Strlen funktioniert. Und ja, SSE2 pcmpeqb/ pmovmskbist sehr gut für strlen geeignet und testet jeweils 16 Bytes. code.woboq.org/userspace/glibc/sysdeps/x86_64/strlen.S.html ist die SSE2-Version von glibc. Siehe auch diese Fragen und Antworten .
Peter Cordes
Oof, das ist unglücklich. Ich bin normalerweise sehr gegen UB, aber wie Sie hervorheben, erfordern C-Strings das technisch UB-Ende des Pufferendes, um überhaupt eine Vektorisierung zu ermöglichen. Ich denke, dasselbe gilt für ARM64, da es eine Ausrichtung erfordert.
Russbischof
-6

Eine wichtige Sache, die in den anderen Antworten nicht erwähnt wird, ist, dass die FSF sehr vorsichtig ist, um sicherzustellen, dass proprietärer Code nicht in GNU-Projekte gelangt. In den GNU-Codierungsstandards unter Verweisen auf proprietäre Programme wird gewarnt, dass Ihre Implementierung so organisiert wird, dass sie nicht mit vorhandenem proprietärem Code verwechselt werden kann:

Beziehen Sie sich unter keinen Umständen auf den Unix-Quellcode für oder während Ihrer Arbeit an GNU! (Oder zu anderen proprietären Programmen.)

Wenn Sie eine vage Erinnerung an die Interna eines Unix-Programms haben, bedeutet dies nicht unbedingt, dass Sie keine Imitation davon schreiben können, aber versuchen Sie, die Imitation intern nach verschiedenen Grundsätzen zu organisieren, da dies wahrscheinlich die Details von macht Die Unix-Version ist für Ihre Ergebnisse irrelevant und unähnlich.

Beispielsweise wurden Unix-Dienstprogramme im Allgemeinen optimiert, um die Speichernutzung zu minimieren. Wenn Sie stattdessen auf Geschwindigkeit setzen , wird Ihr Programm sehr unterschiedlich sein.

(Hervorhebung von mir.)

Jack Kelly
quelle
5
Wie beantwortet dies die Frage?
SS Anne
1
Die Frage in OP lautete: "Würde dieser einfachere Code nicht besser funktionieren?", Und diese Frage wird nicht immer aus technischen Gründen entschieden. Für ein Projekt wie GNU ist die Vermeidung von rechtlichen Fallstricken ein wichtiger Teil des Codes, der "besser funktioniert", und "offensichtliche" Implementierungen von strlen()werden wahrscheinlich ähnlich oder identisch mit vorhandenem Code herauskommen. Etwas so "Verrücktes" wie die Implementierung von glibc kann so nicht zurückverfolgt werden. In Anbetracht dessen, wie viel juristischer Streit es über die rangeCheck- 11 Codezeilen gab! - Im Google / Oracle-Kampf würde ich sagen, dass die Besorgnis der FSF gut platziert war.
Jack Kelly