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?
c
optimization
glibc
portability
strlen
Leichtigkeitsrennen im Orbit
quelle
quelle
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).Antworten:
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 longist entweder 4 oder 8 Bytesunsigned long longund nicht geworfen werdenuintptr_tunsigned longs auf einen String zugreifenDarüber hinaus könnte ein guter Compiler sogar Code ersetzen, der als geschrieben wurde
(
size_tBeachten Siestrlen, 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 :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 inDie 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 zeigtunsigned 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 vonsizeof (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 Funktionthe_strlenhier umbenannt und Folgendes hinzugefügtmain:Der Puffer ist sorgfältig dimensioniert, damit er genau die
hello worldZeichenfolge und den Terminator aufnehmen kann. Auf meinem 64-Bit-Prozessor sindunsigned 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:dh schlimme Dinge sind passiert.
quelle
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 voncharDaten durch einunsigned 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. Diesstrlen("foo")kann eine Konstante für die Kompilierungszeit sein3. 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 derprintfImplementierung)Dies
strlenmacht einige Annahmen:CHAR_BITist ein Vielfaches von 8 . Richtig auf allen GNU-Systemen. POSIX 2001 garantiert sogarCHAR_BIT == 8. (Dies sieht für Systeme mitCHAR_BIT= 16oder32wie einige DSPs sicher aus. Die Schleife für nicht ausgerichtete Prologe führt immer 0 Iterationen aus, wennsizeof(long) = sizeof(char) = 1jeder Zeiger immer ausgerichtet ist undp & 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.unsigned longist 4 oder 8 Bytes. Oder vielleicht würde es tatsächlich für jede Größe vonunsigned longbis zu 8 funktionieren , und es wird ein verwendetassert(), 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:
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
memcpyCPP-Makro des Linux-Kernels , für das Zeiger-Casting verwendet wurdeunsigned 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 vonunsigned long[]Cast zu aconst 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-Typattribut
may_aliasgibt einem Typ den gleichen Alias - alles wiechar*. (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? )Sie können auch
aligned(1)einen Typ mit ausdrückenalignof(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 darin
memcpy, dass moderne Compiler wissen, wie sie als einzelne Ladeanweisung inline sind. z.BDies funktioniert auch für nicht ausgerichtete Lasten, da dies
memcpywie beichareinem Zugriff von Zeit zu Zeit funktioniert . In der Praxis verstehen moderne Compiler dies jedochmemcpysehr 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, ummemcpynur 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önnenp = __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 auchstrlen. 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 /ktestoderkortestkönnte dasstrlenHyperthreading 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.
quelle
CHAR_BIT == 8ist eine POSIX-Anforderung (Stand -2001 rev; siehe hier ). (4) Die C-Fallback-Implementierung vonstrlenwird für einige unterstützte CPUs verwendet. Ich glaube, die häufigste ist MIPS.__attribute__((__may_alias__))Attributen behoben werden (dies ist nicht portierbar, sollte aber für glibc in Ordnung sein).char*, aber es ist immer noch UB, eincharObjekt (z. B. einen Teil von achar[]) über a zu lesen / schreibenlong*. Strenge Aliasing-Regel und 'char *'CHAR_BITmindestens 8 sein müssen ( siehe Anhang E von C11), sodasscharein 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 Typcharund werden mit den Zeichen der Multibyte-Zeichenfolge initialisiert, wie in UTF-8 codiert.“Dies wird in den Kommentaren in der von Ihnen verlinkten Datei erläutert:
und:
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
quelle
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 von
strlenist dem in der Frage vorgeschlagenen Code sehr ähnlich. Die Komplexität einer Implementierung wird vom Autor bestimmt.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 amd64strlenlautet beispielsweise asm. Ähnlich wie in den Kommentaren / Antworten von PeterCordes, in denen darauf hingewiesen wird, dass die Nicht-Fallback-GNU-Implementierungen ebenfalls asm sind.quelle
s - strist undefiniert, wenn das Ergebnis in nicht darstellbar istptrdiff_t.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 wennstrlennicht inline und echte Compiler werden es nur zu einem Subtrahieren kompilieren.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 (idealerweiseaddress % 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 ist0x80, 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.
quelle
size_tist nicht garantiert ausgerichtet zu sein.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.) .
quelle
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.
quelle
if()break. ICC kann solche Schleifen automatisch vektorisieren, aber IDK, wie gut es mit einem naiven Strlen funktioniert. Und ja, SSE2pcmpeqb/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 .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:
(Hervorhebung von mir.)
quelle
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 dierangeCheck- 11 Codezeilen gab! - Im Google / Oracle-Kampf würde ich sagen, dass die Besorgnis der FSF gut platziert war.