Supposons que vous travaillez un système X86 32 bits. Votre tâche consiste à mettre en œuvre la SHLEN aussi vite que possible.
Il y a deux problèmes à prendre soin de: 1. Alignement de l'adresse. 2. Lire la mémoire avec une longueur de mot de la machine (4 octets).
Il n'est pas difficile de trouver la première adresse d'alignement de la chaîne donnée.
Ensuite, nous pouvons lire la mémoire une fois avec les 4 octets et compter la longueur totale. Mais nous devrions nous arrêter une fois qu'il y a un octet zéro dans les 4 octets et compter les octets de gauche avant zéro octet. Afin de vérifier l'octet zéro de manière rapide, un extrait de code de glibc: Je l'ai utilisé dans Visual C ++, comparer avec la mise en œuvre de CRT. Le CRT est beaucoup plus rapide que celui ci-dessus. Je ne connais pas la mise en œuvre de CRT, ont-ils utilisé un moyen plus rapide de vérifier l'octet zéro?
7 Réponses :
Le premier CRT est écrit C: \ Program Files \ Microsoft Visual Studio 9.0 \ VC \ CRT \ SRC \ Intel \ strlen.asm (Ceci est pour vs 2008)
Vous pouvez enregistrer la longueur de la chaîne avec la chaîne lors de la création, comme cela est fait à Pascal.
+1 Je ne suis pas tout à fait sûr que cela aborde la question, mais, sérieusement, les chaînes de terminaison nulle sont parmi les plus grandes faiblesses du langage C et conduisent à des temps de performance de Big-O ridicules avec du code naïf. Mieux pour les éviter entièrement.
Ouais. Vous ne devriez jamais calculer SHLEN une fois, puis mettre en cache ce résultat. Un avantage d'utiliser des classes de chaîne en C ++. Bien sûr, comme indiqué, cela n'aide pas votre problème.
et, comme tant d'autres choses, cette faiblesse de C ++ est devenue enracinée dans d'autres langues et systèmes d'exploitation, AD INFINITUM
@Blueraja: cette faiblesse de C , C ++ a std :: string qui a souvent une taille de temps constant Fonction des membres ... bien que cela ne soit pas requis par la norme.
@Matthieu: "abcd" a type char [] , pas std :: string , qui cause la faiblesse d'être toujours omniprésente
@ Blueaja-dannyypflughoeft: C ++ 14 offre de vrais littéraux à chaîne, de sorte que vous n'ayez pas à utiliser C chaîne littéraux presque aussi souvent (et que vous avez vérifié la sortie du compilateur, il fait la bonne chose, passant la longueur du littéral calculé à la compilation. Temps au constructeur de sorte que cela ne recompite pas la longueur et que le littéral peut avoir incorporé nul s). Il suffit de changer "abcd" sur "abcd" s .
Cela dépend. La bibliothèque de Microsoft a vraiment deux versions différentes de Strlen. L'une est une version portable en C qui concerne la version la plus triviale de Strlen possible, assez proche (et probablement équivalente) à: l'autre est dans la langue d'assemblage (utilisée uniquement pour Intel X86) et assez similaire à ce que vous avez ci-dessus, au moins jusqu'à la charge 4 octets, la vérification de l'un d'entre elles est nulle et réagissez de manière appropriée. La seule différence évidente est que, au lieu de soustraire, ajoutez essentiellement de pré-nier les octets et ajoutez. C'est à dire. Au lieu de Word-0x0101010101 , ils utilisent Word + 0x7efefeff .
Puis-je trouver le code source de la mise en œuvre de SHLEN de Microsoft en langage d'assemblage sans MS-VS Installer sur ma machine? Je ne suis pas sur MS-Windows, mais je suis très curieux d'essayer de comprendre votre dernier commentaire et vérifie à quelle vitesse c'est rapide.
@Jack: Je suppose que vous pourriez regarder sur leur site Web, mais je ne suis pas sûr que si c'est là. Je suppose que le moyen le plus simple / le plus fiable de trouver est d'installer VS (mais je crois que VS Express devrait fonctionner, si vous ne voulez pas l'acheter).
Merci. Je vais obtenir Windows et vs.
En supposant que vous connaissez la longueur maximale possible et que vous avez initié la mémoire à \ 0 avant utilisation, vous pouvez faire une scission binaire et aller à gauche / à droite en fonction de la valeur (\ 0, divisée à gauche, sinon scindinal. droit). De cette façon, vous réduisiez considérablement la quantité de chèques dont vous aurez besoin pour trouver la longueur. Pas optimal (nécessite une certaine configuration), mais devrait être vraiment rapide.
// eric
Cela implique que vous appendez des caractères nul jusqu'à la fin du tampon chaque fois que vous modifiez le contenu de la chaîne.
Il existe également des versions intrinsèques compilatrices qui utilisent la paire d'instructions SCAS de la députation, bien que celles-ci sont généralement sur des compilateurs plus anciens, ils peuvent toujours être assez rapides. Il existe également des versions SSE2 de Strlen, telles que La mise en œuvre de la bibliothèque de performance de la DR AGNER FOG, ou quelque chose tels que Ceci
Évidemment, la fabrication d'une boucle serrée comme celle-ci dans l'assembleur serait la plus rapide, cependant, si vous voulez le garder davantage lisible et / ou portable dans C (++), vous pouvez toujours augmenter la vitesse de la norme. Fonction en utilisant le Notez cependant que le < Code> Enregistrement Le mot-clé n'est qu'une suggestion et le compilateur est libre de l'ignorer si elle le pense peut faire mieux, surtout si certaines options d'optimisation sont utilisées. Cela dit, alors qu'il va certainement être ignoré pour une variable de classe locale dans une triple for-boucle, elle est susceptible d'être honorée pour le code ci-dessous, améliorant ainsi les performances un peu (presque à égalité avec la version de l'assembleur ): enregistrer mot-clé . < p> the registre invite le mot-clé invite le compilateur à stocker le compteur dans un registre de la CPU au lieu de la mémoire qui accélérera de manière significative la boucle.
Aucun compilateur Sane ne voudrait envisager de stocker une telle itératrice de boucle pas dans un registre ...
C'est pourquoi, comme je l'ai dit clairement - le mot clé est juste un indice , pas une commande Iron-Clad.
Supprimer ces suffixes "L" et voir ... Vous promouvez tous les calculs à "long"! sur mes tests de 32 bits, cela double double le coût. Je fais aussi Deux micro-optimisations: Depuis la plupart des cordes, nous utilisons la balayage consistent d'ASCII de caractères dans la plage 0 ~ 127, le bit incrément un index plutôt qu'un pointeur , qui est moins cher sur certaines architectures (notamment x86) et vous donner la longueur pour "GRATUIT" ...
La branche supplémentaire ajoutée par le conditionnel && perd probablement plus que ce que vous économisez en sautant une opération. Difficile de savoir avec certitude sans analyse comparative.
Avez-vous des chiffres sur les différences? Avez-vous activé une optimisation complète lors de la compilation du code ci-dessus?
Y a-t-il une raison pour laquelle vous ne pouvez pas simplement utiliser le SHLEN fourni avec votre compilateur / bibliothèque respectif? Les chances sont les écrivains de la bibliothèque ont passé du temps à obtenir toutes les optimisations possibles. Également aussi arrêté dans une réponse depuis ce type de Tagged C ++ pouvez-vous utiliser STD :: String qui devrait stocker la longueur?
@Mark, c'était probablement une mission de devoirs, d'où la "Votre tâche est de mettre en œuvre Strlen" . Bien que la performance ne semble pas avoir fait partie de la question, l'OP essayait de déterminer pourquoi la mise en œuvre qu'ils ont proposée si lentement.
Avez-vous compilé votre code avec optimisations activées et en mode de sortie? Vérifiez également ce code source .
Ces 'l' suffixes font de votre compilateur Mettez à niveau toutes les opérations à 64 bits! Supprimez-les et voyez ma réponse complète ci-dessous [ Stackoverflow.com/a/24805807/501336]
Pour plus de détails sur l'assertion de @ gatopeich, voir logiciel.intel.com/en-us/articles/... . Drôle que vous trouviez ce code dans GLIBC, car il devrait fonctionner sur des architectures avec des types long 64 bits.