Je lis "Ecrire un excellent code Volume 2" et il montre l'impulsion de SHLEN suivante:
int myStrlen( char *s )
{
char *start;
start = s;
while( *s != 0 )
{
++s;
}
return s - start;
}
7 Réponses :
Victor, jetez un coup d'oeil à ceci:
http://en.wikipedia.org/wiki/strlen#Implementation
P.s. La raison pour laquelle vous ne comprenez pas la version Glibc est probablement parce qu'elle utilise un changement de bit pour trouver le \ 0.
Je suppose que, avec un compilateur modéré, cela produira exactement le même octet-code que la mise en œuvre de l'OPS ...
@Martin: Vous ne pouvez pas vérifier un "mot" contre zéro, ça ne fonctionnera pas
@Victor: Désolé, je ne voulais pas lancer d'aspersions sur votre capacité de programmation. Si vous recherchez une explication de la mise en œuvre GLIBC, postez une question et je suis sûr que les gens plus intelligents que moi pourront l'expliquer.
Pas de problème, je ne me suis pas senti offensé, je commençais juste.
Les instructions du cas spécial X86 mentionnent sont en fait plus lentement qu'une boucle sur les processeurs modernes IIRC
de Optimiser SHLEN () , un blogpost Par Colm MacCarThaigh:
Malheureusement en C, nous sommes condamnés à une mise en œuvre O (n), meilleur cas, mais nous ne sommes toujours pas faits ... nous pouvons faire quelque chose à peu près la taille même de n.
Cela donne un bon exemple dans quelle direction vous pouvez travailler pour accélérer. Et une autre citation de celle-ci
Parfois, allez vraiment très vite vous rend vraiment vraiment fou.
Pour commencer, cela ne vaut rien pour les codages comme UTF-8 ... c'est-à-dire que le calcul du nombre de caractères dans une chaîne UTF-8 est plus compliqué, tandis que le nombre d'octets est bien sûr aussi facile à Calculez comme dans, disons, une chaîne ASCII.
En général, vous pouvez optimiser sur certaines plates-formes en lisant dans des registres plus importants. Étant donné que les autres liens affichés jusqu'à présent n'ont pas d'exemple de cela, voici un peu de pseudo-pseudocode pour l'endian inférieur:
Cela n'améliorera probablement pas les performances, j'ai le sentiment que cela fera disparaître.
@YI_H: Inconvénients: Un supplément et par octet. Avantages: 75% moins de charges de la mémoire, 75% de sauts de moins. De quel côté gagne le concours est presque certainement spécifique à l'architecture. Je n'ai aucune connaissance concrète sur la manière dont cela se produirait sur quelles architectures, vous pourriez donc bien avoir raison. Mais vous pourriez aussi bien être faux. ;)
C'est en fait 75% moins de chargement de la ligne de cache, car ils sont des octets consécutifs.
Ouais. Totalement correct. Peut-être devrais-je reconsidérer que rester éveillé.
lire une variable qui n'a pas de même taille que la taille du bus de données de la machine est coûteuse, car la machine ne peut lire que des variables de cette taille. Par conséquent, chaque fois que quelque chose de taille différente (disons plus petit) est demandé, la machine doit fonctionner pour qu'il ressemble à une variable de la taille demandée (comme le déplacement des bits). Vous feriez donc mieux de lire les données des mots de la machine à la machine, puis utilisez-le et utiliser pour vérifier 0s. De plus, lors de la numérisation via la chaîne, assurez-vous de commencer à une adresse de départ alignée.
Comme d'autres ont souligné, un algorithme plus rapide lit des mots entiers au lieu de caractères individuels et utilise Opérations sur les bits trouver la null de terminaison. Soyez conscient de Word-alignant votre pointeur si vous prenez cette approche, car certaines architectures de la CPU ne vous permettent pas de lire des mots d'une adresse non alignée (et c'est un excellent moyen de déclencher un segfault même sur des architectures qui ne nécessitent pas d'alignement).
excellent code met l'accent sur lisibilité sur vitesse dans tous les cas de performance. Écrivez votre code aussi clairement que vous pouvez et optimiser uniquement les pièces qui se révèlent être des goulots d'étranglement.
Je suppose que l'argument "Great Code est le code lecteurs" ne tient pas dans le cas de la bibliothèque C STD qui vise la performance.
Étant donné que les bibliothèques STD sont aussi largement utilisées et fréquemment utilisées, l'exception "Performance-critique" est appropriée. Pourtant, la plupart d'entre eux pourraient utiliser une meilleure documentation ...
Répondre à la question de l'OP sur l'endroit où trouver des suggestions Comment écrire du code pour la performance, voici
Les suivants doivent être plus rapides que l'algorithme naïf et travailler pour 32/64 bits.
union intptr {
char* c;
long* l;
#define LSIZE sizeof(long)
};
#define aligned_(x, a) \
((unsigned long) (x) % (a) == 0)
#define punpktt_(x, from, to) \
((to) (-1)/(from) (-1)*(from) (x))
#define punpkbl_(x) \
punpktt_(x, unsigned char, unsigned long)
#define plessbl_(x, y) \
(((x) - punpkbl_(y)) & ~(x) & punpkbl_(0x80))
#define pzerobl_(x) \
plessbl_(x, 1)
static inline unsigned long maskffs_(unsigned long x)
{
unsigned long acc = 0x00010203UL;
if (LSIZE == 8)
acc = ((acc << 16) << 16) | 0x04050607UL;
return ((x & -x) >> 7) * acc >> (LSIZE*8-8);
}
size_t strlen(const char* base)
{
union intptr p = { (char*) base };
unsigned long mask;
for ( ; !aligned_(p.c, LSIZE); p.c++ )
if (*p.c == 0)
return p.c - base;
while ( !(mask = pzerobl_(*p.l)) )
p.l++;
return p.c - base + maskffs_(mask);
}
Êtes-vous sûr que c'est un problème d'optimisation? Ou juste le problème de sécurité standard?
@Victor Ne croyez pas tout ce que vous lisez. Cette fonction est rapide assez .
J'ai écrit une fois
Strlen () dans Assembleur pour un système I386 qui a utilisé les opérations de chaîne de CPU (REP) et a fonctionné 6 fois plus rapidement que le code C optimisé.@Loadmaster: Pouvez-vous publier ce code s'il vous plaît?
C'était à la fois où les compilateurs n'étaient pas si bons. Vous pouvez même accélérer le code avec un
enregistrer int i; .Pour l'écrire comme ça, pourquoi pas
tandis que (* s ++! = 0); à la place?Je m'opposerais à la distribution de
ptrdiff_t àint ya Vous n'êtes probablement pas en train de passer des chaînes de 2 Go àStrlen () Mais c'est toujours bâclé. De plus, le compilateur peut produire un meilleur code deint i = 0; tandis que (S [i]) i ++; Retour I; car il peut en dire plus sur ce que vous faites avec le pointeur (c'est-à-dire qu'il peut analyser la boucle meilleure).