Comment écrire une meilleure fonction strlen?

Je suis la lecture de "l'Écriture du Code Volume 2" et il montre les suivantes strlen impelementation:

int myStrlen( char *s )
{
    char *start;
    start = s;
    while( *s != 0 )
    {
        ++s;
    }
    return s - start;
}

le livre dit que cette mise en œuvre est typique pour un inexpérimenté C programmeur. J'ai été le codage en C depuis 11 ans, et je ne vois pas comment écrire une fonction mieux que cela en C(je pense à l'écriture chose de mieux dans l'assemblage). Comment est-il possible d'écrire du code mieux que cela en C? J'ai regardé la bibliothèque standard de mise en œuvre de la fonction strlen dans la glibc, et je ne pouvais pas comprendre la plupart de la partie. Où puis-je trouver de meilleures informations sur la façon d'écrire très optimisé le code?

Êtes-vous sûr que c'est une question d'optimisation? Ou tout simplement la norme de problème de sécurité?
Ne croyez pas tout ce que vous lisez. Cette fonction est rapide assez.
il a été question d'optimisation.
Une fois, j'ai écrit strlen() en assembleur pour un système i386 qui a utilisé le CPU chaîne (REP) opcodes, et a couru 6x plus rapide que le code C optimisé.
J'avais objet de la caste des ptrdiff_t à int oui, vous n'êtes probablement pas en passant de 2 go de chaînes à strlen() mais c'est toujours bâclé. Aussi le compilateur peut produire un meilleur code de int i=0; while(s[i]) i++; return i; parce qu'il peut en dire plus sur ce que vous faites avec le pointeur (c'est à dire qu'il peut analyser cette boucle de mieux en mieux).

OriginalL'auteur Victor | 2011-07-05

  1. 14

    De L'optimisation de strlen(), un billet de blog par Colm MacCarthaigh:

    Malheureusement en C, nous sommes condamnés à un O(n) de la mise en œuvre, dans le meilleur des cas, mais nous ne sommes toujours pas fait ... nous pouvons faire quelque chose à propos de la taille de n.

    Il donne le bon exemple dans ce sens, vous pouvez travailler pour l'accélérer. Et une autre citation de ce

    Parfois aller très très vite, vous rend vraiment fou.

    Excellent lien! Merci!

    OriginalL'auteur Mojo Risin

  2. 3

    Victor, jetez un oeil à ceci:

    http://en.wikipedia.org/wiki/Strlen#Implementation

    P. S. La raison pour laquelle vous ne comprenez pas la version de la glibc est probablement parce qu'il utilise le décalage de bits à trouver le \0.

    Donc, comment est-ce plus rapide ?
    Ma conjecture est qu'avec un modéré compilateur, cela produira exactement sur le même byte-code de la Fpo mise en œuvre...
    Wikipédia hors-ligne? Je ne peux pas ouvrir le lien.........
    vous ne pouvez pas vérifier un " mot " contre zéro, ça ne marchera pas
    En fait, je comprends comment décalage de bits fonctionne.

    OriginalL'auteur gkrogers

  3. 3

    Pour commencer, c'est sans valeur pour les encodages comme de l'UTF-8... qui est, en calculant le nombre de caractères dans une chaîne UTF-8 est plus compliqué, alors que le nombre d'octets est, bien sûr, tout aussi facile à calculer que dans, disons, une chaîne de caractères ASCII.

    En général, vous pouvez optimiser, sur certaines plateformes, par la lecture dans de grands registres. Étant donné que les autres liens postés jusqu'à présent n'ont pas un exemple, voici un peu de pseudo-pseudo-code pour le bas-endian:

    int size = 0;
int x;
int *caststring = (int *) yourstring;
while (int x = *caststring++) {
  if (!(x & 0xff)) /* first byte in this int-sized package is 0 */ return size;
  else if (!(x & 0xff00)) /* second byte etc. */ return size+1;
  /* rinse and repeat depending on target architecture, i.e. twice more for 32 bit */
  size += sizeof (int);
}
    C'est probablement de ne pas améliorer les performances, j'ai le sentiment que ça va juste empirer les choses.
    Inconvénients: une personne supplémentaire ET par octet. Avantages: 75% moins de charges à partir de la mémoire, 75% moins de sauts. De quel côté remporte le concours est presque certainement spécifique à l'architecture. Je n'ai aucune connaissance concrète de la façon dont il serait effectuer sur les architectures, de sorte que vous peut-être bien droit. Mais on pourrait tout aussi bien être faux. 😉
    c'est en fait 75% moins de charge à partir de la ligne de cache, comme ce sont des octets consécutifs.
    Yep. Tout à fait correcte. Peut-être que je devrais reconsidérer à rester éveillé chose.

    OriginalL'auteur Jan Krüger

  4. 3

    Comme d'autres l'ont souligné, un algorithme plus rapide lit les mots entiers plutôt que des caractères individuels et utilise les opérations bit à bit pour trouver la valeur null. Être conscient de la parole-l'alignement de votre pointeur si vous prenez cette approche, comme certains des architectures des processeurs ne vous laisseront pas de lire les mots à partir d'un cas de non-alignement de l'adresse (et c'est un excellent moyen pour déclencher une erreur de segmentation, même sur des architectures qui ne nécessitent pas d'alignement).

    Ligne du bas:

    Grand code souligne lisibilité sur vitesse dans l'ensemble, mais la plupart des critiques des performances des cas. Écrire votre code, aussi clairement que possible et d'optimiser les pièces qui s'avèrent être des goulets d'étranglement.

    Je suppose que l'argument de "grand code est lisible par un lecteur de code" ne tient pas dans le cas de C Std bibliothèque qui vise la performance.
    Depuis le std bibliothèques sont si largement et fréquemment utilisés, la performance est critique" l'exception " est approprié. Encore, la plupart d'entre eux pourraient mieux utiliser de la documentation...

    OriginalL'auteur Tony the Pony

  5. 1

    La lecture d'une variable qui n'est pas de la même taille que les données de l'ordinateur la taille d'un bus est cher, parce que la machine ne peut lire que les variables de taille. Par conséquent, chaque fois que quelque chose de différente taille (disons que le plus petit) est demandé, la machine doit faire des travaux pour la faire ressembler à une variable de la taille demandée (comme changer les bits).
    Afin de mieux vous lire les données dans la machine de la taille des mots, et d'utiliser ensuite l'opération pour vérifier 0s. Aussi, lors de la numérisation de la chaîne, assurez-vous de commencer à une aligné adresse de départ.

    OriginalL'auteur Freek

  6. 1

    Répondre à l'OP de la question de savoir où trouver des suggestions sur la manière d'écrire du code pour les performances, voici lien MIT OpenCourse sur l'écriture de Code C Optimisé (voir "Documents" lien sur la gauche de la page).

    OriginalL'auteur Victor Sorokin

  7. 1

    La suite devrait être plus rapide que l'algorithme naïf et de travail pour les architectures 32 et 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);
}

    OriginalL'auteur mightymouse