Je regardais le strlen
code ici et je me demandais si les optimisations utilisées dans le code étaient vraiment nécessaires? Par exemple, pourquoi quelque chose comme le suivant ne fonctionnerait-il pas aussi bien ou mieux?
unsigned long strlen(char s[]) {
unsigned long i;
for (i = 0; s[i] != '\0'; i++)
continue;
return i;
}
Le code plus simple n'est-il pas meilleur et / ou plus facile à optimiser pour le compilateur?
Le code de strlen
la page derrière le lien ressemble à ceci:
/* 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)
Pourquoi cette version fonctionne-t-elle rapidement?
Ne fait-il pas beaucoup de travail inutile?
c
optimization
glibc
portability
strlen
Courses de légèreté en orbite
la source
la source
sysdeps
répertoire sera utilisée à la place, sur la plupart des architectures prises en charge par la glibc (l'architecture la plus utilisée qui n'a pas de remplacement est MIPS).Réponses:
Vous n'avez pas besoin et vous ne devriez jamais écrire de code comme ça - surtout si vous n'êtes pas un compilateur C / fournisseur de bibliothèque standard. C'est du code utilisé pour implémenter
strlen
avec des hacks et hypothèses de vitesse très discutables (qui ne sont pas testés avec des assertions ou mentionnés dans les commentaires):unsigned long
est de 4 ou 8 octetsunsigned long long
et nonuintptr_t
unsigned long
sDe plus, un bon compilateur pourrait même remplacer le code écrit comme
(notez qu'il doit s'agir d'un type compatible avec
size_t
) avec une version intégrée du compilateur intégréstrlen
, ou vectorisez le code; mais il est peu probable qu'un compilateur soit en mesure d'optimiser la version complexe.La
strlen
fonction est décrite par C11 7.24.6.3 comme:Maintenant, si la chaîne pointée par
s
était dans un tableau de caractères juste assez long pour contenir la chaîne et le NUL de fin, le comportement ne sera pas défini si nous accédons à la chaîne après le terminateur nul, par exemple dansDonc, vraiment la seule façon dans C entièrement portable / conforme aux normes de l'implémenter correctement est la façon dont cela est écrit dans votre question , à l'exception des transformations triviales - vous pouvez prétendre être plus rapide en déroulant la boucle, etc., mais cela doit encore être fait un octet à la fois.
(Comme l'ont souligné des commentateurs, lorsque la portabilité stricte est trop lourde, tirer parti d'hypothèses raisonnables ou sûres n'est pas toujours une mauvaise chose. Surtout dans le code qui fait partie d' une implémentation C spécifique. Mais vous devez comprendre le règles avant de savoir comment / quand vous pouvez les plier.)
L'
strlen
implémentation liée vérifie d'abord les octets individuellement jusqu'à ce que le pointeur pointe vers la limite d'alignement naturelle de 4 ou 8 octets duunsigned long
. La norme C indique que l'accès à un pointeur qui n'est pas correctement aligné a un comportement indéfini , donc cela doit absolument être fait pour que la prochaine astuce sale soit encore plus sale. (En pratique, sur une architecture de CPU autre que x86, un mot ou un mot double mal aligné sera défectueux. C n'est pas un langage d'assemblage portable, mais ce code l'utilise de cette façon). C'est aussi ce qui permet de lire au-delà de la fin d'un objet sans risque de défaut sur les implémentations où la protection de la mémoire fonctionne en blocs alignés (ex: pages de mémoire virtuelle de 4 Ko).Vient maintenant la partie sale: le code rompt la promesse et lit 4 ou 8 octets de 8 bits à la fois (a
long int
), et utilise une astuce avec ajout non signé pour déterminer rapidement s'il n'y avait aucun octet dans ces 4 ou 8 octets - il utilise un nombre spécialement conçu pour que le bit de report change les bits capturés par un masque de bits. Essentiellement, cela déterminerait si l'un des 4 ou 8 octets du masque sont des zéros censément plus rapides que le fait de parcourir chacun de ces octets. Enfin, il y a une boucle à la fin pour déterminer quel octet était le premier zéro, le cas échéant, et pour retourner le résultat.Le plus gros problème est que dans
sizeof (unsigned long) - 1
certainssizeof (unsigned long)
cas, il lira au-delà de la fin de la chaîne - uniquement si l'octet nul se trouve dans le dernier octet consulté (c'est-à-dire en petit-boutien le plus significatif et en gros-boutien le moins significatif) , n'accède-t-il pas au tableau hors limites!Le code, même s'il est utilisé pour être implémenté
strlen
dans une bibliothèque standard C, est un mauvais code. Il comporte plusieurs aspects définis et non définis par l'implémentation et ne doit pas être utilisé n'importe où au lieu de celui fourni par lestrlen
système.J'ai renommé la fonctionthe_strlen
ici et ajouté ce qui suitmain
:Le tampon est soigneusement dimensionné afin qu'il puisse contenir exactement la
hello world
chaîne et le terminateur. Cependant, sur mon processeur 64 bits,unsigned long
c'est 8 octets, donc l'accès à cette dernière partie dépasserait ce tampon.Si maintenant je compile avec
-fsanitize=undefined
et-fsanitize=address
exécute le programme résultant, j'obtiens:c'est-à-dire que de mauvaises choses se sont produites.
la source
Il y a eu beaucoup de suppositions erronées (légèrement ou entièrement) dans les commentaires à propos de certains détails / antécédents pour cela.
Vous regardez l' implémentation optimisée de secours optimisée de glibc C. (Pour les ISA qui n'ont pas d'implémentation asm manuscrite) . Ou une ancienne version de ce code, qui est toujours dans l'arborescence des sources de la glibc. https://code.woboq.org/userspace/glibc/string/strlen.c.html est un navigateur de code basé sur l'arbre git glibc actuel. Apparemment, il est toujours utilisé par quelques cibles de la glibc, dont MIPS. (Merci @zwol).
Sur les ISA populaires comme x86 et ARM, la glibc utilise un asm écrit à la main
Ainsi, l'incitation à changer quoi que ce soit à propos de ce code est plus faible que vous ne le pensez.
Ce code bithack ( https://graphics.stanford.edu/~seander/bithacks.html#ZeroInWord ) n'est pas ce qui fonctionne réellement sur votre serveur / ordinateur de bureau / ordinateur portable / smartphone. C'est mieux qu'une boucle naïve d'octet à la fois, mais même ce bithack est assez mauvais par rapport à un asm efficace pour les processeurs modernes (en particulier x86 où AVX2 SIMD permet de vérifier 32 octets avec quelques instructions, autorisant 32 à 64 octets par horloge cycle dans la boucle principale si les données sont chaudes dans le cache L1d sur les processeurs modernes avec une charge vectorielle 2 / horloge et un débit ALU, c'est-à-dire pour les chaînes de taille moyenne où la surcharge de démarrage ne domine pas.)
glibc utilise des astuces de liaison dynamique pour se résoudre
strlen
à une version optimale pour votre CPU, donc même dans x86, il existe une version SSE2 (vecteurs 16 octets, ligne de base pour x86-64) et une version AVX2 (vecteurs 32 octets).x86 offre un transfert de données efficace entre les registres vectoriels et les registres à usage général, ce qui le rend particulièrement utile pour utiliser SIMD pour accélérer les fonctions sur les chaînes de longueur implicite où le contrôle de boucle dépend des données.
pcmpeqb
/pmovmskb
permet de tester 16 octets distincts à la fois.glibc a une version AArch64 comme celle utilisant AdvSIMD , et une version pour les processeurs AArch64 où vector-> GP enregistre bloque le pipeline, donc il utilise réellement ce bithack . Mais utilise count-leader-zeros pour trouver l'octet dans le registre une fois qu'il obtient un coup, et profite des accès non alignés efficaces d'AArch64 après avoir vérifié le croisement de page.
Également lié: Pourquoi ce code est-il 6.5x plus lent avec des optimisations activées? a plus de détails sur ce qui est rapide par rapport à lent dans asm x86
strlen
avec un grand tampon et une implémentation asm simple qui pourrait être bonne pour gcc pour savoir comment s'aligner. (Certaines versions de gcc sont imprudemment en ligne,rep scasb
ce qui est très lent, ou un bithack de 4 octets à la fois comme celui-ci. La recette en ligne de GCC doit donc être mise à jour ou désactivée.)Asm n'a pas de "comportement indéfini" de style C ; il est sûr d'accéder aux octets en mémoire comme vous le souhaitez, et une charge alignée qui inclut tous les octets valides ne peut pas faire défaut. La protection de la mémoire se produit avec la granularité des pages alignées; les accès alignés plus étroits que cela ne peuvent pas traverser une limite de page. Est-il sûr de lire après la fin d'un tampon dans la même page sur x86 et x64? Le même raisonnement s'applique au code machine que ce hack C oblige les compilateurs à créer pour une implémentation autonome non en ligne de cette fonction.
Lorsqu'un compilateur émet du code pour appeler une fonction non en ligne inconnue, il doit supposer que la fonction modifie toutes les variables globales et toute mémoire vers laquelle il peut éventuellement avoir un pointeur. c'est-à-dire que tout sauf les locaux qui n'ont pas eu leur adresse d'échappement doivent être synchronisés en mémoire pendant l'appel. Cela s'applique aux fonctions écrites en asm, évidemment, mais aussi aux fonctions de bibliothèque. Si vous n'activez pas l'optimisation du temps de liaison, elle s'applique même à des unités de traduction distinctes (fichiers source).
Pourquoi c'est sûr dans le cadre de la glibc mais pas autrement.
Le facteur le plus important est que cela
strlen
ne peut s'aligner sur rien d'autre. Ce n'est pas sûr pour ça; il contient UB à alias strict (lecture deschar
données via ununsigned long*
).char*
est autorisé à alias autre chose mais l'inverse n'est pas vrai .Il s'agit d'une fonction de bibliothèque pour une bibliothèque compilée à l'avance (glibc). Il ne sera pas intégré à l'optimisation du temps de liaison dans les appelants. Cela signifie qu'il suffit de compiler en code machine sûr pour une version autonome de
strlen
. Il n'a pas besoin d'être portable / sûr C.La bibliothèque GNU C n'a qu'à compiler avec GCC. Apparemment, il n'est pas pris en charge pour le compiler avec clang ou ICC, même s'ils prennent en charge les extensions GNU. GCC est un compilateur avancé qui transforme un fichier source C en un fichier objet de code machine. Pas un interprète, donc à moins qu'il ne soit en ligne au moment de la compilation, les octets en mémoire ne sont que des octets en mémoire. c'est-à-dire que l'UB à alias strict n'est pas dangereux lorsque les accès avec différents types se produisent dans différentes fonctions qui ne s'alignent pas les unes dans les autres.
N'oubliez pas que son
strlen
comportement est défini par la norme ISO C. Ce nom de fonction fait spécifiquement partie de l'implémentation. Les compilateurs comme GCC traitent même le nom comme une fonction intégrée à moins que vous ne l'utilisiez-fno-builtin-strlen
, doncstrlen("foo")
peut être une constante de temps de compilation3
. La définition de la bibliothèque est uniquement utilisée lorsque décide gcc d'émettre effectivement un appel à elle au lieu de inline sa propre recette ou quelque chose.Lorsque UB n'est pas visible par le compilateur au moment de la compilation, vous obtenez un code machine sain. Le code machine doit fonctionner pour le cas sans UB, et même si vous le souhaitez , il n'y a aucun moyen pour l'asm de détecter les types que l'appelant a utilisés pour mettre des données dans la mémoire pointée.
Glibc est compilé dans une bibliothèque statique ou dynamique autonome qui ne peut pas s'aligner avec l'optimisation du temps de liaison. Les scripts de construction de glibc ne créent pas de bibliothèques statiques "grosses" contenant du code machine + une représentation interne gcc GIMPLE pour une optimisation du temps de liaison lors de l'intégration dans un programme. (c.-à
libc.a
-d. ne participera pas à l'-flto
optimisation du temps de liaison dans le programme principal.) Construire la glibc de cette façon serait potentiellement dangereux pour les cibles qui l'utilisent réellement.c
.En fait, comme le commente @zwol, LTO ne peut pas être utilisé lors de la construction de la glibc elle - même , en raison d'un code "fragile" comme celui-ci qui pourrait se casser s'il était possible d'aligner entre les fichiers source de la glibc. (Il existe des utilisations internes de
strlen
, par exemple, peut-être dans le cadre de laprintf
mise en œuvre)Cela
strlen
fait certaines hypothèses:CHAR_BIT
est un multiple de 8 . Vrai sur tous les systèmes GNU. POSIX 2001 garantit mêmeCHAR_BIT == 8
. (Cela semble sûr pour les systèmes avecCHAR_BIT= 16
ou32
, comme certains DSP; la boucle de prologue non aligné exécutera toujours 0 itérations sisizeof(long) = sizeof(char) = 1
parce que chaque pointeur est toujours aligné etp & sizeof(long)-1
est toujours nul.) Mais si vous aviez un jeu de caractères non ASCII où les caractères sont 9 ou 12 bits de large,0x8080...
est le mauvais modèle.unsigned long
est de 4 ou 8 octets. Ou peut-être que cela fonctionnerait pour n'importe quelle tailleunsigned long
jusqu'à 8, et il utilise unassert()
pour vérifier cela.Ces deux ne sont pas possibles UB, ils sont simplement non portables vers certaines implémentations C. Ce code fait (ou faisait) partie de l'implémentation C sur les plateformes où il fonctionne, donc ça va.
L'hypothèse suivante est le potentiel C UB:
0
est UB; il pourrait s'agir d'unchar[]
tableau C contenant{1,2,0,3}
par exemple)Ce dernier point est ce qui permet de lire en toute sécurité après la fin d'un objet C ici. C'est à peu près sûr même en s'alignant avec les compilateurs actuels parce que je pense qu'ils ne traitent pas actuellement qu'impliquer un chemin d'exécution est inaccessible. Mais de toute façon, l'aliasing strict est déjà un incontournable si jamais vous laissez cela en ligne.
Ensuite, vous auriez des problèmes comme l'ancienne
memcpy
macro CPP non sécurisée du noyau Linux qui utilisait le casting de pointeurs versunsigned long
( gcc, alias strict et histoires d'horreur ).Cela
strlen
remonte à l'époque où l'on pouvait s'en tirer avec des trucs comme ça en général ; il était à peu près sûr sans la mise en garde "seulement quand il n'est pas inclus" avant GCC3.UB qui n'est visible que lorsque vous regardez à travers les limites des appels / ret ne peut pas nous blesser. (par exemple, appeler ceci sur un
char buf[]
au lieu d'un tableau deunsigned long[]
transtypage en aconst char*
). Une fois que le code machine est gravé dans la pierre, il ne s'agit que d'octets en mémoire. Un appel de fonction non en ligne doit supposer que l'appelé lit tout / tout la mémoire.Écrire ceci en toute sécurité, sans UB à alias strict
L' attribut de type GCC
may_alias
donne à un type le même traitement d'alias-n'importe quoi quechar*
. (Suggéré par @KonradBorowsk). Les en-têtes GCC l'utilisent actuellement pour les types de vecteurs SIMD x86 comme__m128i
pour que vous puissiez toujours le faire en toute sécurité_mm_loadu_si128( (__m128i*)foo )
. (Voir «reinterpret_cast» entre le pointeur vectoriel matériel et le type correspondant est-il un comportement non défini? Pour plus de détails sur ce que cela signifie et ne signifie pas.)Vous pouvez également utiliser
aligned(1)
pour exprimer un type avecalignof(T) = 1
.typedef unsigned long __attribute__((may_alias, aligned(1))) unaligned_aliasing_ulong;
Un moyen portable d'exprimer une charge d'alias en ISO est avec
memcpy
lequel les compilateurs modernes savent comment s'aligner en tant qu'instruction de chargement unique. par exempleCela fonctionne également pour les chargements non alignés, car il
memcpy
fonctionne commechar
un accès à la fois. Mais dans la pratique, les compilateurs modernes comprennentmemcpy
très bien.Le danger ici est que si GCC ne sait pas avec certitude qu'il
char_ptr
est aligné sur un mot, il ne l'inline pas sur certaines plates-formes qui pourraient ne pas prendre en charge les charges non alignées dans asm. par exemple MIPS avant MIPS64r6, ou ARM plus ancien. Si vous receviez un appel de fonction réelmemcpy
juste pour charger un mot (et le laisser dans une autre mémoire), ce serait un désastre. GCC peut parfois voir quand le code aligne un pointeur. Ou après la boucle char-at-a-time qui atteint une limite ulong que vous pouvez utiliserp = __builtin_assume_aligned(p, sizeof(unsigned long));
Cela n'évite pas l'UB possible lu après l'objet, mais avec le GCC actuel ce n'est pas dangereux dans la pratique.
Pourquoi une source C optimisée à la main est nécessaire: les compilateurs actuels ne sont pas assez bons
L'asm optimisé à la main peut être encore meilleur lorsque vous voulez chaque dernière baisse de performances pour une fonction de bibliothèque standard largement utilisée. Surtout pour quelque chose comme
memcpy
, mais aussistrlen
. Dans ce cas, il ne serait pas beaucoup plus facile d'utiliser C avec des intrinsèques x86 pour tirer parti de SSE2.Mais ici, nous ne parlons que d'une version naïve contre Bithack C sans fonctionnalités spécifiques à ISA.
(Je pense que nous pouvons le considérer comme une donnée
strlen
suffisamment utilisée pour qu'il soit aussi rapide que possible de l'exécuter. La question devient donc de savoir si nous pouvons obtenir un code machine efficace à partir d'une source plus simple. Non, nous ne pouvons pas.)GCC et clang actuels ne sont pas capables de vectoriser automatiquement les boucles dont le nombre d'itérations n'est pas connu avant la première itération . (par exemple, il doit être possible de vérifier si la boucle exécutera au moins 16 itérations avant d' exécuter la première itération.) Par exemple, l'autovectorisation de memcpy est possible (tampon de longueur explicite) mais pas strcpy ou strlen (chaîne de longueur implicite), étant donné le courant compilateurs.
Cela inclut les boucles de recherche ou toute autre boucle avec
if()break
un compteur dépendant des données ainsi qu'un compteur.ICC (le compilateur d'Intel pour x86) peut vectoriser automatiquement certaines boucles de recherche, mais ne crée toujours qu'un asm naïf octet à la fois pour un C simple / naïf
strlen
comme la libc d'OpenBSD. ( Godbolt ). (De la réponse de @ Peske ).Une libc optimisée à la main
strlen
est nécessaire pour les performances avec les compilateurs actuels . Aller 1 octet à la fois (avec le déroulement peut-être 2 octets par cycle sur les CPU superscalaires larges) est pathétique lorsque la mémoire principale peut suivre environ 8 octets par cycle, et le cache L1d peut fournir 16 à 64 par cycle. (2 charges de 32 octets par cycle sur les processeurs x86 grand public modernes depuis Haswell et Ryzen. Sans compter l'AVX512 qui peut réduire les vitesses d'horloge uniquement pour l'utilisation de vecteurs 512 bits; c'est pourquoi la glibc n'est probablement pas pressée d'ajouter une version AVX512 Bien qu'avec les vecteurs 256 bits, les masques AVX512VL + BW se comparent en un masque et /ktest
oukortest
pourraient rendre l'strlen
hyperthreading plus convivial en réduisant son uops / itération.)J'inclus non-x86 ici, c'est les "16 octets". par exemple, la plupart des processeurs AArch64 peuvent faire au moins cela, je pense, et certains certainement plus. Et certains ont un débit d'exécution suffisant pour
strlen
suivre cette bande passante de charge.Bien sûr, les programmes qui fonctionnent avec de grandes chaînes doivent généralement garder une trace des longueurs pour éviter d'avoir à refaire très souvent la recherche de la longueur des chaînes C de longueur implicite. Mais les performances de courte à moyenne longueur bénéficient toujours d'implémentations écrites à la main, et je suis sûr que certains programmes finissent par utiliser strlen sur des chaînes de longueur moyenne.
la source
CHAR_BIT == 8
est une exigence POSIX (à partir de la version -2001; voir ici ). (4) L'implémentation de secours Cstrlen
est utilisée pour certains processeurs pris en charge, je pense que le plus commun est MIPS.__attribute__((__may_alias__))
attribut (ce n'est pas portable, mais cela devrait convenir à la glibc).char*
, mais il est toujours UB de lire / écrire unchar
objet (par exemple une partie de achar[]
) via along*
. Règle d'alias stricte et pointeurs 'char *'CHAR_BIT
doit être au moins 8 ( qv Annexe E de C11), donc au moins 7 bitschar
n'est pas quelque chose dont un avocat spécialisé dans les langues doit s'inquiéter. Cela était motivé par l'exigence: «Pour les littéraux de chaîne UTF-8, les éléments du tableau ont un typechar
et sont initialisés avec les caractères de la séquence de caractères multi-octets, comme encodés en UTF-8.»Cela est expliqué dans les commentaires du fichier que vous avez lié:
et:
En C, il est possible de raisonner en détail sur l'efficacité.
Il est moins efficace d'itérer à travers des caractères individuels à la recherche d'un null que de tester plus d'un octet à la fois, comme le fait ce code.
La complexité supplémentaire vient du fait de devoir s'assurer que la chaîne sous test est alignée au bon endroit pour commencer à tester plus d'un octet à la fois (le long d'une limite de mot long, comme décrit dans les commentaires), et de devoir s'assurer que les hypothèses sur les tailles des types de données ne sont pas violés lorsque le code est utilisé.
Dans la plupart (mais pas tous) du développement de logiciels modernes, cette attention aux détails d'efficacité n'est pas nécessaire, ou ne vaut pas le coût d'une complexité de code supplémentaire.
Un endroit où il est logique de prêter attention à l'efficacité comme celui-ci est dans les bibliothèques standard, comme l'exemple que vous avez lié.
Si vous voulez en savoir plus sur les limites des mots, consultez cette question et cette excellente page wikipedia
la source
En plus des excellentes réponses ici, je tiens à souligner que le code lié dans la question est pour l'implémentation de GNU
strlen
.L' implémentation d'OpenBSD
strlen
est très similaire au code proposé dans la question. La complexité d'une implémentation est déterminée par l'auteur.EDIT : Le code OpenBSD que j'ai lié ci-dessus semble être une implémentation de secours pour les ISA qui n'ont pas leur propre implémentation asm. Il existe différentes implémentations
strlen
selon l'architecture. Le code pour amd64strlen
, par exemple, est asm. Semblable aux commentaires / réponses de PeterCordes soulignant que les implémentations GNU non de secours sont également asm.la source
s - str
n'est pas défini si le résultat n'est pas représentable dansptrdiff_t
.PTRDIFF_MAX
. Mais il est toujours possible d'avoirmmap
plus de mémoire que cela sur Linux au moins (par exemple, dans un processus 32 bits sous un noyau x86-64, je pourrais mapper environ 2,7 Go contigus avant de commencer à avoir des échecs). IDK sur OpenBSD; le noyau pourrait rendre impossible d'atteindre celareturn
sans segfaulting ou s'arrêter dans la taille. Mais oui, vous penseriez qu'un codage défensif qui évite le C UB théorique serait quelque chose qu'OpenBSD voudrait faire. Même s'ilstrlen
ne peut pas être en ligne et que les vrais compilateurs le compileront simplement en soustraction.En bref, il s'agit d'une optimisation des performances que la bibliothèque standard peut faire en sachant avec quel compilateur elle est compilée - vous ne devriez pas écrire de code comme celui-ci, sauf si vous écrivez une bibliothèque standard et peut dépendre d'un compilateur spécifique. Plus précisément, il traite le nombre d'alignement d'octets en même temps - 4 sur les plates-formes 32 bits, 8 sur les plates-formes 64 bits. Cela signifie qu'il peut être 4 ou 8 fois plus rapide que l'itération d'octets naïfs.
Pour expliquer comment cela fonctionne, considérez l'image suivante. Supposons ici la plate-forme 32 bits (alignement sur 4 octets).
Disons que la lettre "H" de "Hello, world!" une chaîne a été fournie comme argument pour
strlen
. Parce que le CPU aime avoir des choses alignées en mémoire (idéalement,address % sizeof(size_t) == 0
), les octets avant l'alignement sont traités octet par octet, en utilisant une méthode lente.Ensuite, pour chaque bloc de taille d'alignement, le calcul
(longbits - 0x01010101) & 0x80808080 != 0
vérifie si l'un des octets d'un entier est nul. Ce calcul a un faux positif quand au moins l'un des octets est supérieur à0x80
, mais le plus souvent il devrait fonctionner. Si ce n'est pas le cas (comme dans la zone jaune), la longueur est augmentée par la taille de l'alignement.Si l'un des octets d'un entier s'avère être zéro (ou
0x81
), la chaîne est vérifiée octet par octet pour déterminer la position de zéro.Cela peut rendre un accès hors limites, mais comme il se trouve dans un alignement, il est plus probable qu'improbable d'être correct, les unités de mappage de mémoire n'ont généralement pas une précision au niveau des octets.
la source
size_t
n'est pas garanti d'être aligné.Vous voulez que le code soit correct, maintenable et rapide. Ces facteurs ont une importance différente:
"correct" est absolument essentiel.
"maintenable" dépend de combien vous allez maintenir le code: strlen est une fonction de bibliothèque C standard depuis plus de 40 ans. Ça ne va pas changer. La maintenabilité est donc tout à fait sans importance - pour cette fonction.
"Rapide": Dans de nombreuses applications, strcpy, strlen etc. utilisent une quantité importante de temps d'exécution. Pour obtenir le même gain de vitesse global que cette implémentation compliquée, mais pas très compliquée de strlen en améliorant le compilateur, il faudrait des efforts héroïques.
Être rapide a un autre avantage: lorsque les programmeurs découvrent que l'appel à "strlen" est la méthode la plus rapide, ils peuvent mesurer le nombre d'octets dans une chaîne, ils ne sont plus tentés d'écrire leur propre code pour accélérer les choses.
Donc, pour strlen, la vitesse est beaucoup plus importante et la maintenabilité beaucoup moins importante que pour la plupart des codes que vous écrirez jamais.
Pourquoi cela doit-il être si compliqué? Supposons que vous ayez une chaîne de 1 000 octets. L'implémentation simple examinera 1 000 octets. Une implémentation actuelle examinerait probablement des mots de 64 bits à la fois, ce qui signifie 125 mots de 64 bits ou de huit octets. Il pourrait même utiliser des instructions vectorielles examinant par exemple 32 octets à la fois, ce qui serait encore plus compliqué et encore plus rapide. L'utilisation d'instructions vectorielles conduit à un code un peu plus compliqué mais assez simple, vérifier si l'un des huit octets d'un mot de 64 bits est nul nécessite quelques astuces intelligentes. Ainsi, pour les chaînes moyennes à longues, ce code devrait être environ quatre fois plus rapide. Pour une fonction aussi importante que strlen, cela vaut la peine d'écrire une fonction plus complexe.
PS. Le code n'est pas très portable. Mais cela fait partie de la bibliothèque Standard C, qui fait partie de l'implémentation - elle n'a pas besoin d'être portable.
PPS. Quelqu'un a publié un exemple où un outil de débogage s'est plaint d'accéder aux octets après la fin d'une chaîne. Une implémentation peut être conçue qui garantit ce qui suit: Si p est un pointeur valide vers un octet, alors tout accès à un octet dans le même bloc aligné qui serait un comportement indéfini selon la norme C, retournera une valeur non spécifiée.
PPPS. Intel a ajouté des instructions à ses processeurs ultérieurs qui forment un bloc de construction pour la fonction strstr () (recherche d'une sous-chaîne dans une chaîne). Leur description est ahurissante, mais ils peuvent rendre cette fonction particulière probablement 100 fois plus rapide. (Fondamentalement, étant donné un tableau a contenant "Hello, world!" Et un tableau b commençant par 16 octets "HelloHelloHelloH" et contenant plus d'octets, il comprend que la chaîne a n'apparaît pas dans b plus tôt qu'à partir de l'index 15) .
la source
En bref: la vérification d'une chaîne octet par octet sera potentiellement lente sur les architectures qui peuvent extraire de plus grandes quantités de données à la fois.
Si la vérification de la terminaison nulle peut être effectuée sur une base 32 ou 64 bits, cela réduit le nombre de vérifications que le compilateur doit effectuer. C'est ce que le code lié tente de faire, avec un système spécifique à l'esprit. Ils font des hypothèses sur l'adressage, l'alignement, l'utilisation du cache, les configurations de compilateur non standard, etc., etc.
La lecture octet par octet comme dans votre exemple serait une approche judicieuse sur un processeur 8 bits, ou lors de l'écriture d'une bibliothèque portable écrite en standard C.
Regarder les bibliothèques standard C pour savoir comment écrire du code rapide / bon n'est pas une bonne idée, car il sera non portable et s'appuiera sur des hypothèses non standard ou un comportement mal défini. Si vous êtes débutant, la lecture d'un tel code sera probablement plus nuisible qu'éducative.
la source
if()break
. ICC peut vectoriser automatiquement de telles boucles, mais IDK comment il le fait avec un strlen naïf. Et oui, SSE2pcmpeqb
/pmovmskb
est très bon pour strlen, testant 16 octets à la fois. code.woboq.org/userspace/glibc/sysdeps/x86_64/strlen.S.html est la version SSE2 de glibc. Voir également ce Q&R .Une chose importante non mentionnée par les autres réponses est que la FSF est très prudente pour s'assurer que le code propriétaire ne se transforme pas en projets GNU. Dans les normes de codage GNU sous Référence aux programmes propriétaires , il y a un avertissement concernant l'organisation de votre implémentation de manière à ce qu'elle ne puisse pas être confondue avec le code propriétaire existant:
(Je souligne.)
la source
strlen()
sont susceptibles de sortir similaires ou identiques au code existant. Quelque chose d'aussi "fou" que l'implémentation de glibc ne peut pas être retracé comme ça. Compte tenu de la querelle juridique sur lesrangeCheck
- 11 lignes de code! - dans la lutte Google / Oracle, je dirais que la préoccupation de la FSF était bien placée.