Skip to content

Pourquoi le strlen de la glibc doit-il être si compliqué pour s'exécuter rapidement ?

Nos meilleurs programmeurs ont épuisé leurs réserves de café, dans leur recherche jour et nuit de la réponse, jusqu'à ce qu'Alejandra trouve la trouvaille à Gitea et en ce moment nous la partageons avec vous.

Solution :

Vous ne besoin et vous ne devriez jamais écrire un tel code - surtout si vous n'êtes pas un compilateur C / vendeur de bibliothèque standard. C'est du code utilisé pour implémenter strlen avec quelques hacks de vitesse et hypothèses très discutables (qui ne sont pas testés avec des assertions ou mentionnés dans les commentaires) :

  • unsigned long est soit 4 soit 8 octets
  • les octets sont 8 bits
  • un pointeur peut être converti en unsigned long long et non uintptr_t
  • on peut aligner le pointeur simplement en vérifiant que les 2 ou 3 bits d'ordre inférieur sont nuls.
  • on peut accéder à une chaîne de caractères comme unsigned longs
  • on peut lire au-delà de la fin du tableau sans aucun effet néfaste.

Qui plus est, un bon compilateur pourrait même remplacer le code écrit comme suit .

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

(remarquez qu'il doit s'agir d'un type compatible avec le type size_t) avec une version inlined du compilateur builtin strlenou vectoriser le code; mais il est peu probable qu'un compilateur soit capable d'optimiser la version complexe.


Le site strlen est décrite par C11 7.24.6.3 comme :

Description

  1. Le site strlen calcule la longueur de la chaîne de caractères pointée par s.

Elle retourne

  1. Le site strlen renvoie le nombre de caractères qui précèdent le caractère nul de terminaison.

Maintenant, si la chaîne de caractères pointée par s se trouvait dans un tableau de caractères juste assez long pour contenir la chaîne et le NUL de fin, la fonction comportement sera indéfini si l'on accède à la chaîne de caractères après le terminateur nul, par exemple dans la section

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

Donc, en réalité, la chaîne ne fait que manière d'implémenter cette fonction dans un C entièrement portable et conforme aux standards. correctement est la façon dont il est écrit dans votre question, sauf pour les transformations triviales - on peut prétendre être plus rapide en déroulant la boucle etc, mais il faut quand même le faire un octet à la fois.

(Comme les commentateurs l'ont souligné, lorsque la portabilité stricte est un trop lourd fardeau, tirer parti des hypothèses raisonnables ou sûres connues n'est pas toujours une mauvaise chose. Surtout dans le code qui est fait partie de une implémentation C spécifique. Mais vous devez comprendre les règles avant de savoir comment/quand vous pouvez les contourner).


La liaison strlen liée vérifie d'abord les octets individuellement jusqu'à ce que le pointeur pointe sur la limite d'alignement naturelle de 4 ou 8 octets de l'élément unsigned long. La norme C dit que l'accès à un pointeur qui n'est pas correctement aligné a... un comportement non défini, donc cela doit absolument être fait pour que le prochain sale tour soit encore plus sale. (En pratique, sur certaines architectures de processeurs autres que x86, un mot mal aligné ou un chargement de double-mot sera défaillant. C 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 d'erreur sur les implémentations où la protection de la mémoire fonctionne en blocs alignés (par exemple, les pages de mémoire virtuelle de 4kiB).

Maintenant vient la partie sale : le code casse la promesse et lit 4 ou 8 octets de 8 bits à la fois (une long int), et utilise une astuce de bit avec une addition non signée pour déterminer rapidement s'il y avait des des zéro dans ces 4 ou 8 octets - il utilise un nombre spécialement conçu pour que le bit de report change les bits qui sont pris par un masque de bits. En substance, cela permettrait de déterminer si l'un des 4 ou 8 octets du masque est supposé être un zéro. plus rapide que de boucler sur chacun de ces octets. Enfin, il y a une boucle à la fin pour déterminer... quel octet était le premier zéro, s'il y en a un, et pour retourner le résultat.

Le plus gros problème est que dans sizeof (unsigned long) - 1 temps sur sizeof (unsigned long) cas, il lira au-delà de la fin de la chaîne de caractères - seulement si l'octet nul se trouve dans le champ dernier octet accédé (c'est à dire dans le little-endian le plus significatif, et dans le big-endian le moins significatif), il fait le pas accéder au tableau en dehors des limites !


Le code, même s'il est utilisé pour implémenter strlen dans une bibliothèque standard C, est mauvais code. Il contient plusieurs aspects définis par l'implémentation et non définis et ne doit pas être utilisé. partout à la place du système fourni par le strlen - J'ai renommé la fonction en the_strlen ici et ajouté ce qui suit main:

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

Le tampon est soigneusement dimensionné pour qu'il puisse contenir exactement les hello world et le terminateur. Cependant, sur mon processeur 64 bits, le unsigned long est de 8 octets, donc l'accès à cette dernière partie dépasserait ce tampon.

Si je compile maintenant avec -fsanitize=undefined et -fsanitize=address et que j'exécute le programme résultant, j'obtiens :

% ./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

c'est à dire que de mauvaises choses sont arrivées.

Il y a eu beaucoup de suppositions (légèrement ou entièrement) erronées dans les commentaires sur certains détails / contexte pour cela.

Vous êtes en train de regarder l'implémentation optimisée de fallback C de la glibc. (Pour les ISA qui n'ont pas une implémentation asm écrite à la main).. Ou une ancienne version de ce code, qui se trouve toujours dans l'arbre source de la glibc. https://code.woboq.org/userspace/glibc/string/strlen.c.html est un navigateur de code basé sur l'arbre git actuel de la glibc. Apparemment, il est encore utilisé par quelques cibles glibc grand public, dont MIPS. (Merci @zwol).

Sur les ISA populaires comme x86 et ARM, glibc utilise des asm écrits à la main.

Donc l'incitation à changer quoi que ce soit à 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'octets à la fois, mais... même ce bithack est assez mauvais comparé à l'asm efficace pour les CPU modernes. (en particulier x86 où AVX2 SIMD permet de vérifier 32 octets avec quelques instructions, permettant 32 à 64 octets par cycle d'horloge dans la boucle principale si les données sont chaudes dans le cache L1d sur les CPU modernes avec une charge vectorielle 2/clock et un débit ALU, c'est-à-dire pour des chaînes de taille moyenne où l'overhead de démarrage ne domine pas).

La glibc utilise des astuces de liaison dynamique pour résoudre strlen à une version optimale pour votre CPU, ainsi, même au sein de x86, il existe une version SSE2 (vecteurs de 16 octets, ligne de base pour x86-64) et une version AVX2 (vecteurs de 32 octets).

Le x86 dispose d'un transfert de données efficace entre les registres vectoriels et les registres à usage général, ce qui le rend uniquement( ?) bon pour utiliser la SIMD afin d'accélérer les fonctions sur des chaînes de longueur implicite où le contrôle de la boucle dépend des données. pcmpeqb / pmovmskb permet de tester 16 octets séparés à la fois.

La glibc a une version AArch64 comme cela utilisant AdvSIMD, et une version pour les CPU AArch64 où les registres vector->GP bloquent le pipeline, donc elle utilise effectivement ce bithack. Mais utilise count-leading-zeros pour trouver le byte-within-register une fois qu'il obtient un hit, et profite des accès non alignés efficaces de AArch64 après avoir vérifié le page-crossing.

Également lié : Pourquoi ce code est-il 6,5x plus lent avec les optimisations activées ? a quelques détails supplémentaires sur ce qui est rapide vs lent dans l'asm x86 pour... strlen avec un grand tampon et une implémentation asm simple qui pourrait être bon pour gcc de savoir comment inline. (Certaines versions de gcc ont imprudemment mis en ligne rep scasb qui est très lent, ou un bithack de 4 octets à la fois comme celui-ci. Donc la recette inline-strlen de gcc a besoin d'être mise à jour ou désactivée).

L'Asm n'a pas de "comportement indéfini" à la C.

; il est sûr d'accéder aux octets en mémoire comme vous le souhaitez, et un chargement aligné qui inclut n'importe quel octet valide ne peut pas faire de faute. La protection de la mémoire se produit avec une granularité de page alignée ; les accès alignés plus étroits que cela ne peuvent pas traverser une frontière de page. Est-il sûr de lire au-delà de 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 fait créer aux compilateurs pour une implémentation autonome non-inline de cette fonction.

Lorsqu'un compilateur émet du code pour appeler une fonction non-inline inconnue, il doit supposer que cette fonction modifie toutes/toutes les variables globales et toute mémoire sur laquelle elle pourrait éventuellement avoir un pointeur. C'est-à-dire que tout, sauf les locales qui n'ont pas eu leur échappatoire d'adresse, doit être synchronisé en mémoire à travers l'appel. Ceci s'applique aux fonctions écrites en asm, évidemment, mais aussi aux fonctions des bibliothèques. Si vous n'activez pas l'optimisation au moment de la liaison, cela s'applique même aux unités de traduction séparées (fichiers sources).


Pourquoi c'est sûr en tant que partie de la glibc mais pas sinon.

Le facteur le plus important est que cette strlen ne peut pas être inline dans quoi que ce soit d'autre. Ce n'est pas sûr pour cela ; il contient du strict aliasing UB (lecture char données à travers un unsigned long*). char* est autorisé à aliaser n'importe quoi d'autre mais l'inverse est pas vrai.

Il s'agit d'une fonction de bibliothèque pour une bibliothèque compilée en avance sur le temps (glibc). Elle ne sera pas inlined avec link-time-optimization 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 / C sûr.

La bibliothèque GNU C doit seulement être compilée avec GCC. Apparemment, il n'est pas supporté de la compiler avec clang ou ICC, même s'ils supportent les extensions GNU. GCC est un compilateur en avance sur le temps qui transforme un fichier source C en un fichier objet de code machine. Ce n'est pas un interprète, donc à moins qu'il n'inline au moment de la compilation, les octets en mémoire sont juste des octets en mémoire. C'est à dire que l'UB avec un aliasing strict n'est pas dangereux quand les accès avec des types différents se produisent dans des fonctions différentes qui ne s'inline pas les unes dans les autres.

Rappelez-vous que strlenLe comportement de strlenest défini par la norme ISO C. Ce nom de fonction est 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 n'utilisiez -fno-builtin-strlendonc strlen("foo") peut être une constante de temps de compilation 3. La définition dans la bibliothèque est seulement utilisée lorsque gcc décide d'émettre réellement un appel à celle-ci au lieu d'inliner sa propre recette ou autre.

Quand 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 no-UB, et même si on a... vouliez le faire, il n'y a aucun moyen pour l'asm de détecter quels types l'appelant a utilisé pour mettre des données dans la mémoire pointée.

La glibc est compilée en une bibliothèque statique ou dynamique autonome qui ne peut pas être inline avec une optimisation au moment de la liaison. Les scripts de construction de la glibc ne créent pas de "grosses" bibliothèques statiques contenant le code machine + la représentation interne GIMPLE de gcc pour l'optimisation au moment de la liaison lors de l'inlining dans un programme. (c'est-à-dire libc.a ne participera pas à -flto optimisation au moment de la liaison dans le programme principal). Construire la glibc de cette façon serait potentiellement dangereux. sur les cibles qui utilisent réellement cette .c.

En fait, comme le commente @zwol, LTO ne peut pas être utilisé lors de la construction de la glibc elle-même, à cause d'un code "fragile" comme celui-ci qui pourrait se casser si l'inlining entre les fichiers sources de la glibc était possible. (Il y a quelques utilisations internes de strlen par exemple, peut-être dans le cadre de la fonction printf implementation)


Ce strlen fait quelques hypothèses :

  • CHAR_BIT est un multiple de 8. Vrai sur tous les systèmes GNU. POSIX 2001 garantit même CHAR_BIT == 8. (Cela semble sûr pour les systèmes avec CHAR_BIT= 16 ou 32comme certains DSP ; la boucle prologue non alignée exécutera toujours 0 itération si sizeof(long) = sizeof(char) = 1 car chaque pointeur est toujours aligné et p & sizeof(long)-1 est toujours égal à zéro). Mais si vous aviez un jeu de caractères non-ASCII où les chars ont une largeur de 9 ou 12 bits, 0x8080... est le mauvais motif.
  • (peut-être) unsigned long est de 4 ou 8 octets. Ou peut-être que cela fonctionnerait en fait pour n'importe quelle taille de unsigned long jusqu'à 8, et qu'il utilise un assert() pour vérifier cela.

Ces deux-là ne sont pas des UB possibles, c'est juste de la non-portabilité vers certaines implémentations C. Ce code est (ou était) fait partie de l'implémentation C sur les plateformes où il fonctionne, donc c'est bien.

L'hypothèse suivante est l'UB C potentielle :

  • Un chargement aligné qui contient n'importe quel octet valide ne peut pas faire de faute., et est sûr tant que vous ignorez les octets en dehors de l'objet que vous voulez réellement. (Vrai en asm sur tous les systèmes GNU, et sur tous les CPU normaux parce que la protection de la mémoire se produit avec une granularité de page alignée. Est-il sûr de lire au-delà de la fin d'un tampon dans la même page sur x86 et x64 ? sûr en C quand l'UB n'est pas visible au moment de la compilation. Sans inlining, c'est le cas ici. Le compilateur ne peut pas prouver que la lecture au-delà du premier tampon 0 est UB ; il pourrait être un C char[] contenant {1,2,0,3} par exemple)

Ce dernier point est ce qui rend sûr la lecture au-delà de la fin d'un objet C ici. C'est à peu près sûr même en inlining 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 showstopper si vous laissez jamais cela inline.

Ensuite, vous auriez des problèmes comme l'ancien unsafe du noyau Linux. memcpyCPP macro qui utilisait le transfert de pointeur vers unsigned long (gcc, strict-aliasing, et histoires d'horreur). (Linux moderne compile avec -fno-strict-aliasing au lieu d'être prudent avec may_alias attributs).

Ce strlendate de l'époque où l'on pouvait s'en tirer avec ce genre de choses en général.; c'était à peu près sûr avant GCC3, même sans une mise en garde "seulement quand on ne fait pas d'inlining".


UB qui n'est visible que lorsqu'on regarde à travers les frontières call/ret ne peut pas nous faire de mal. (par exemple, appeler ceci sur un char buf[] plutôt que sur un tableau de unsigned long[] transformé en un const char*). Une fois que le code machine est gravé dans le marbre, il ne s'agit plus que de traiter des octets en mémoire. Un appel de fonction non inline doit supposer que le destinataire lit tout/tout en mémoire.


Écrire cela en toute sécurité, sans strict-aliasing UB.

L'attribut de type de GCC may_alias donne à un type le même traitement alias-tout comme char*. (Proposé par @KonradBorowsk). Les en-têtes de GCC l'utilisent actuellement pour les types vectoriels SIMD x86 tels que __m128i donc vous pouvez toujours faire en toute sécurité _mm_loadu_si128( (__m128i*)foo ). (Voir Is `reinterpret_cast`ing between hardware SIMD vector pointer and the corresponding type an undefined behavior ? pour plus de détails sur ce que cela signifie et ne signifie pas).

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

  // handle unaligned startup somehow, e.g. check for page crossing then check an unaligned word
  // else check single bytes until an alignment boundary.
  aliasing_ulong *longword_ptr = (aliasing_ulong *)char_ptr;

  for (;;) {
     // alignment still required, but can safely alias anything including a char[]
     unsigned long ulong = *longword_ptr++;

     ...
  }
}

Vous pouvez utiliser aligned(1) pour exprimer un type avec alignof(T) = 1.
typedef unsigned long __attribute__((may_alias, aligned(1))) unaligned_aliasing_ulong;. Cela pourrait être utile pour la partie de démarrage non alignée de strlen, si vous ne faites pas simplement char par char jusqu'à la première limite d'alignement. (La boucle principale doit être alignée pour que vous ne fassiez pas de faute si le terminateur est juste avant une page non alignée).

Une façon portable d'exprimer une charge d'aliasing en ISO est avec... memcpy que les compilateurs modernes savent mettre en ligne comme une seule instruction de chargement. par exemple

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

Cela fonctionne également pour les charges non alignées car memcpy fonctionne comme si par char-à un moment donné. Mais en pratique, les compilateurs modernes comprennent memcpy très bien.

Le danger ici est que si GCC ne comprend pas connaît pas pour sûr que char_ptr est aligné en mot, il ne l'alignera pas sur certaines plateformes qui pourraient ne pas supporter les chargements non alignés en asm. Par exemple, MIPS avant MIPS64r6, ou les anciens ARM. Si vous avez un appel de fonction réel à memcpy 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, vous pourriez utiliser...
p = __builtin_assume_aligned(p, sizeof(unsigned long));

Cela n'évite pas le read-past-the-object possible UB, mais avec le GCC actuel ce n'est pas dangereux en pratique.


Pourquoi le source C optimisé à 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 goutte de performance pour une fonction de bibliothèque standard largement utilisée. Surtout pour quelque chose comme memcpy, mais aussi strlen . Dans ce cas, il ne serait pas beaucoup plus facile d'utiliser le C avec des intrinsèques x86 pour profiter de SSE2.

Mais ici, nous parlons juste d'une version naïve vs bithack du C sans aucune caractéristique spécifique à l'ISA.

(Je pense que nous pouvons considérer comme acquis que strlen est assez largement utilisé pour que le faire tourner aussi vite que possible soit important. La question devient donc de savoir si nous pouvons obtenir un code machine efficace à partir d'une source plus simple. Non, nous ne le pouvons pas).

GCC et clang actuels ne sont pas capables d'auto-vectoriser les boucles où 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 va exécuter 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), compte tenu des compilateurs actuels.

Cela inclut les boucles de recherche, ou toute autre boucle avec une dépendance aux données. if()break ainsi qu'un compteur.

ICC (le compilateur d'Intel pour x86) peut auto-vectoriser certaines boucles de recherche, mais ne fait toujours que de l'asm naïve par 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 un déroulage peut-être 2 octets par cycle sur les CPU superscalaires larges) est pathétique lorsque la mémoire principale peut suivre avec environ 8 octets par cycle, et le cache L1d peut fournir 16 à 64 par cycle. (2x 32 octets par cycle sur les CPU x86 modernes depuis Haswell et Ryzen. Sans compter AVX512 qui peut réduire les vitesses d'horloge juste pour l'utilisation de vecteurs de 512 bits ; c'est pourquoi la glibc n'est probablement pas pressée d'ajouter une version AVX512. Bien qu'avec des vecteurs de 256 bits, AVX512VL + BW masqué comparer dans un masque et. ktest ou kortest pourrait faire strlen plus favorable à l'hyperthreading en réduisant ses uops / itération).

J'inclus les non-x86 ici, c'est les "16 octets". Par exemple, la plupart des CPU AArch64 peuvent faire au moins cela, je pense, et certains certainement plus. Et certains ont un débit d'exécution suffisant pour strlenpour suivre cette bande passante de charge.

Bien sûr, les programmes qui travaillent avec de grandes chaînes de caractères devraient généralement garder la trace des longueurs pour éviter d'avoir à refaire la recherche de la longueur des chaînes de caractères C à longueur implicite très souvent. Mais les performances de courte à moyenne longueur bénéficient toujours des implémentations écrites à la main, et je suis sûr que certains programmes finissent par utiliser strlen sur des chaînes de longueur moyenne.

C'est expliqué dans les commentaires du fichier que vous avez lié :

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

et :

 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.  */

En C, il est possible de raisonner en détail sur l'efficacité.

Il est moins efficace d'itérer sur 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 de la nécessité de s'assurer que la chaîne de caractères testée est alignée au bon endroit pour commencer à tester plus d'un octet à la fois (le long d'une frontière de long mot, comme décrit dans les commentaires), et de la nécessité de s'assurer que les hypothèses sur les tailles des types de données ne sont pas violées lorsque le code est utilisé.

Dans la plupart des (mais pas tous) les développements logiciels modernes, cette attention aux détails d'efficacité n'est pas nécessaire, ou ne vaut pas le coût de la complexité supplémentaire du code.

Un endroit où il est judicieux de prêter attention à l'efficacité comme celle-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.


Je pense aussi que cette réponse ci-dessus est une discussion beaucoup plus claire et détaillée.

Si vous osez, vous avez la possibilité de laisser une division sur ce qui vous a impressionné dans cette revue.



Utilisez notre moteur de recherche

Ricerca
Generic filters

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée.