Vous rencontrez probablement une sorte d’effet d’alignement de code. Les processeurs modernes x86-64 sont relativement robustes en ce qui concerne l’alignement, mais l’alignement peut affecter les twigs qui se croisent dans les prédicteurs de twig (comme @rcgldr mentionné) et divers effets frontaux.

Voir https://agner.org/optimize/ et les liens de performance dans le wiki des balises x86 . Mais honnêtement, je ne pense pas qu’il y ait une explication utile ici, si ce n’est que vous avez découvert que votre boucle est sensible aux effets d’alignement, que ce soit de la prédiction frontale ou de la twig. Cela signifie que même un code machine identique à différents alignements dans votre programme principal pourrait avoir des performances différentes.

C’est un phénomène connu. Une réponse sur l’ alignement de code dans un fichier object affecte les performances d’une fonction dans un autre fichier object. Elle contient quelques commentaires généraux sur l’importance de l’alignement, et voir également Pourquoi l’introduction d’instructions MOV inutiles accélérerait-elle une boucle étroite dans l’assemblage x86_64? Il y a un article quelque part sur la façon dont la liaison de fichiers object dans un ordre différent peut affecter les performances (et qu’il s’agit d’un effet inattendu de la chaîne d’outils), mais je ne pouvais pas le trouver.

Vous pouvez utiliser des compteurs de performance matérielles pour mesurer les taux de prédiction erronée des succursales afin de voir si cela explique pourquoi une version est plus lente que l’autre. Ou s’il y a un autre effet frontal.

Mais malheureusement, vous ne pouvez pas faire grand chose. Les différences de source sortingviales, si elles affectent l’asm, modifieront l’alignement pour tout.

Vous pouvez parfois modifier la conception des éléments pour qu’ils soient moins sensibles à la prédiction de twig en remplaçant les twigs par du code sans twig . Par exemple, générez toujours 16 octets de lettres aléatoires et tronquez-les à une longueur aléatoire. (Il est probablement inévitable de créer des twigs sur la taille lors de la copie, à moins de créer un std::ssortingng 16 octets, puis de le tronquer, cela peut être sans twig.)

Vous pouvez accélérer le xorshift+ avec SIMD, par exemple, utilisez un PRNG vectorisé, comme avec un SSE2 ou AVX2 xorshift+ pour générer 16 octets de lettres aléatoires à la fois. (Obtenir efficacement une dissortingbution uniforme de 0..25 avec des opérations à paquets d’octets peut être délicat, mais peut-être la même technique que la dissortingbution 0..9 que j’avais utilisée pour générer 1GiB de chiffres ASCII aléatoires séparés par des espaces par ~ 0.03 secondes sur une valeur de 3.9 Skylake en GHz serait utile, mais elle n’est pas parfaitement uniforme car 65536% 10 a un solde (comme 65536/25), mais vous pouvez probablement modifier le compromis qualité-vitesse tout en restant rapide.)

Comparaison de la sortie du compilateur des deux versions

L’asm des deux versions de la boucle interne de la fonction runtest est essentiellement identique , du moins si la sortie asm du compilateur que nous voyons sur l’explorateur du compilateur Godbolt correspond à ce que vous obtenez réellement dans l’exécutable de MSVC. (Contrairement à gcc / clang, sa sortie asm ne peut pas nécessairement être assemblée dans un fichier object de travail.) Si votre version réelle de la version utilise une optimisation en temps de lien pouvant intégrer du code de bibliothèque, elle pourrait effectuer des choix d’optimisation différents dans la version finale. exécutable.

J’ai mis un #ifdef afin que je puisse utiliser -DUSE_RL pour avoir deux sorties -DUSE_RL 2017 qui construisent la même source de différentes manières et pour alimenter ces sorties asm dans un volet diff. ( Le volet Diff est situé au bas de la présentation malpropre que j’ai liée; cliquez sur la case plein écran pour montrer cela .)

Les seules différences dans la fonction entière sont:

• commander et enregistrer le choix de quelques instructions telles que mov edx, DWORD PTR _tls_index et mov QWORD PTR run_length$GSCopy$1$[rbp-121], rcx en haut de la fonction, qui ne s’exécute qu’une seule fois. (Mais pas en taille de code pour ne pas affecter l’alignement ultérieurement). Cela ne devrait avoir aucun effet sur le code ultérieur et ils finissent par apporter les mêmes modifications à l’état d’architecture, en utilisant simplement un autre registre de travail qui n’est pas utilisé à nouveau.
• disposition de la stack (position des variables locales par rapport à RBP). Mais tous les décalages sont inférieurs à +127, ils peuvent donc toujours utiliser un mode d’adressage [rbp + disp8] .

• Code-gen différent de la différence de source réelle:

    mov rdx, QWORD PTR word_list$[rbp-113] sub rdx, QWORD PTR word_list$[rbp-121] ; word_list.size() = end - start ... sar rdx, 5 ; >> 5 arithmetic right shift 

  contre.

    mov rdx, rsi ; copy run_length from another register 

  Et non, ces instructions ne peuvent à elles seules expliquer la différence de vitesse. Ils ne sont exécutés qu’une fois par intervalle de temps, avant certaines E / S.

• Un npad 7 supplémentaire pour l’alignement avant une twig cible située près du bas de la fonction (après un call _Xtime_get_ticks ), après la différence de code ci-dessus.

Il existe un gros bloc de différences rouge / vert, mais celles-ci ne proviennent que d’une numérotation différente des étiquettes, à l’exception de ces trois instructions au début de la fonction.

Mais avant runtest , la version word_list.size() inclut du code pour une fonction ??$?6_K@@YAAEAVPrinter@@AEAV0@$QEA_K@Z PROC qui n’apparaît nulle part pour la version utilisant run_length . (C ++ name-mangling transforme les types en caractères géniaux dans les noms asm des fonctions.) Cela fait quelque chose pour la class Printer .

Vous avez dit que supprimer le std::ssortingng filename de std::ssortingng filename inutilisé de Printer supprimait la différence code-gen. Eh bien, cette fonction disparaît probablement avec ce changement. IDK pourquoi MSVC a décidé de l’émettre, et encore moins dans une version par rapport à une autre.

Probablement que g++ -O3 n’a pas cette différence code-gen, et c’est pourquoi vous ne voyez pas de différence. (En supposant que votre machine virtuelle soit une virtualisation matérielle, le code machine généré par g ++ fonctionne toujours de manière native sur le processeur. Obtenir une nouvelle page de mémoire à partir du système d’exploitation peut prendre un peu plus de temps dans la machine virtuelle, mais le temps principal consacré à la boucle est probablement plus long. dans l’espace utilisateur dans ce code.)

BTW, avertit gcc

 :72:24: warning: comparison of integer expressions of different signedness: 'int' and 'size_t' {aka 'long unsigned int'} [-Wsign-compare] for (auto i = 0; i < run_length; i++) { ~~^~~~~~~~~~~~ 

Je n'ai pas examiné de près la sortie asm pour voir si cela conduisait à une détérioration du code avec gcc ou MSVC, ou si cela risquerait d'être dangereux si vous transmettez de grandes entrées.

J’ai rencontré une situation similaire, des modifications mineures du code avaient des effets significatifs sur le temps d’exécution. Après avoir converti le code en assembleur pour contrôler l’emplacement du code, j’ai trouvé une différence significative sur un processeur Intel 3770K 3,5 GHz, en fonction du lieu où les appels et les boucles serrées sont situés en mémoire. La différence la plus significative que j’ai trouvée est une différence de temps de 36,5%, mentionnée dans la question que j’ai posée et qui concernait à l’origine l’utilisation de la création de twigs indexées dans le code de chute par le code par rapport à une boucle étroite. Encore plus étrange, il dépend de la combinaison d’emplacements, comme indiqué dans les commentaires du code d’assemblage (peut-être un conflit dans le cache d’instructions?), La durée de la version de la boucle allant de 1,465 seconde à 2 000 secondes, un code identique, seule différence entre nops entre les fonctions utilisées pour aligner le code sur des limites spécifiques.

Supplément de twig indexé en mode X86 64 bits

Je ne sais pas si d’autres processeurs subiraient cette différence de performances en raison de l’emplacement du code.

Je ne peux pas expliquer cela, vous devrez probablement en parler à Microsoft pour aller au fond des mystères. J’ai pris votre code et compilé un programme qui avait les deux versions de runtest() , dont l’une utilisait cette ligne:

 printer << /*run_length*/ word_list.size() << " words, and " 

et l'autre en utilisant

 printer << run_length /* word_list.size() */ << " words, and " 

Pour mémoire, je construisais x64 dans la communauté Visual Studio 2017. Je n'ai pas la possibilité de construire x86, car j'ai effacé la chaîne d'outils x86 et les bibliothèques (ainsi que des éléments ARM inutiles) pour gagner un gigaoctet ou plus. l'espace arrière.

Mes résultats de référence sont cohérents avec les vôtres. J'ai effectué une série de tests plus petite mais suffisante pour toujours montrer la différence:

Version plus lente:

 Running test... 50000000 words, and 749981638 total characters, were built in 16.3966 seconds. Running test... 50000000 words, and 750037396 total characters, were built in 15.9712 seconds. Running test... 50000000 words, and 749999562 total characters, were built in 16.0094 seconds. Running test... 50000000 words, and 749990566 total characters, were built in 15.8863 seconds. Running test... 50000000 words, and 749998381 total characters, were built in 15.8728 seconds. Running test... 50000000 words, and 749997199 total characters, were built in 15.8799 seconds. 

Version plus rapide:

 Running test... 50000000 words, and 750000053 total characters, were built in 15.3437 seconds. Running test... 50000000 words, and 750014937 total characters, were built in 15.4479 seconds. Running test... 50000000 words, and 750054238 total characters, were built in 15.2631 seconds. Running test... 50000000 words, and 750012691 total characters, were built in 15.5289 seconds. Running test... 50000000 words, and 750013435 total characters, were built in 15.3742 seconds. Running test... 50000000 words, and 749969960 total characters, were built in 15.3682 seconds. 

Cela dit, l'assembleur résultant pour les deux routines est différent. Pas beaucoup, mais il y a des différences. En comparant les deux côtés par taille, une différence notable est que l’un d’eux utilise r14 alors que l’autre utilise rdi, plus quelques autres différences mineures.

Voici un étrange. La version "word_list.size ()" a ceci pour l'itération de la boucle externe principale:

  for (auto i = 0; i < run_length; i++) 00007FF7C77D2CF9 inc r13d 00007FF7C77D2CFC mov dword ptr [rbp-79h],r13d 00007FF7C77D2D00 movsxd rax,r13d 00007FF7C77D2D03 cmp rax,qword ptr [rbp-31h] 00007FF7C77D2D07 mov r14d,0FFFFFFFFh 00007FF7C77D2D0D lea rcx,[word_sz_generator (07FF7C77D70F0h)] 00007FF7C77D2D14 jb runtest+130h (07FF7C77D2B40h) int64_t execution_time_usec = timer(); // stop timer 

alors que la version "run_length" fait ceci:

  for (auto i = 0; i < run_length; i++) 00007FF7C77D270B inc r13d 00007FF7C77D270E mov dword ptr [rbp-79h],r13d 00007FF7C77D2712 movsxd rax,r13d 00007FF7C77D2715 mov r14,qword ptr [rbp-31h] 00007FF7C77D2719 cmp rax,r14 00007FF7C77D271C mov edi,0FFFFFFFFh 00007FF7C77D2721 lea rcx,[word_sz_generator (07FF7C77D9820h)] 00007FF7C77D2728 jb runtest2+130h (07FF7C77D2550h) int64_t execution_time_usec = timer(); // stop timer 

Remarquez comment la version la plus rapide charge explicitement [rbp-31h] dans r14 avant de la comparer à rax . Probablement pour pouvoir l'utiliser plus tard. Et il met ensuite 0FFFFFFFFh dans edi . En attendant, la version la plus lente compare directement rax à la mémoire, puis charge la même constante dans r14d .

Assez pour créer une différence de performance de 3%? Apparemment oui.

TL; DR Les différences sont là. Je suis complètement perdu pour les expliquer.

L’parsing comparative est souvent rendue très difficile par les compilateurs qui vous simplifient la vie.

Je suggérerais de tout marquer au soleil comme étant «volatil» et de voir si vous obtenez toujours des résultats sporadiques.

Si cela élimine tout le hasard, il est probable que votre compilateur optimise votre code en arrière-plan (volatile dira essentiellement au compilateur de bourdonner avec ses optimisations).

J’espère que cela t’aides. A couru dans un problème similaire en comparant un microcontrôleur PIC32 il y a quelques années. Volatile sauve des vies.