Application de l'ordre des instructions en C ++

Supposons que je dispose d'un certain nombre d'instructions que je souhaite exécuter dans un ordre fixe. Je veux utiliser g ++ avec le niveau d'optimisation 2, donc certaines instructions pourraient être réorganisées. De quels outils dispose-t-on pour imposer un certain ordre des déclarations?

Prenons l'exemple suivant.

using Clock = std::chrono::high_resolution_clock;

auto t1 = Clock::now(); // Statement 1
foo();                  // Statement 2
auto t2 = Clock::now(); // Statement 3

auto elapsedTime = t2 - t1;

Dans cet exemple, il est important que les instructions 1-3 soient exécutées dans l'ordre donné. Cependant, le compilateur ne peut-il pas penser que l'instruction 2 est indépendante de 1 et 3 et exécuter le code comme suit?

using Clock=std::chrono::high_resolution_clock;

foo();                  // Statement 2
auto t1 = Clock::now(); // Statement 1
auto t2 = Clock::now(); // Statement 3

auto elapsedTime = t2 - t1;

Je voudrais essayer de fournir une réponse un peu plus complète après que cela ait été discuté avec le comité des normes C ++. En plus d'être membre du comité C ++, je suis également développeur sur les compilateurs LLVM et Clang.

Fondamentalement, il n'y a aucun moyen d'utiliser une barrière ou une opération dans la séquence pour réaliser ces transformations. Le problème fondamental est que la sémantique opérationnelle de quelque chose comme une addition d'entiers est totalement connue de l'implémentation. Il peut les simuler, il sait qu'ils ne peuvent pas être observés par des programmes corrects et est toujours libre de les déplacer.

Nous pourrions essayer d'éviter cela, mais cela aurait des résultats extrêmement négatifs et finirait par échouer.

Tout d'abord, la seule façon d'éviter cela dans le compilateur est de lui dire que toutes ces opérations de base sont observables. Le problème est que cela empêcherait alors l'écrasante majorité des optimisations du compilateur. À l'intérieur du compilateur, nous n'avons pratiquement aucun bon mécanisme pour modéliser que le timing est observable mais rien d'autre. Nous n'avons même pas un bon modèle de ce que les opérations prennent du temps . Par exemple, la conversion d'un entier non signé de 32 bits en un entier non signé de 64 bits prend du temps? Cela ne prend aucun temps sur x86-64, mais sur d'autres architectures, cela prend un temps différent de zéro. Il n'y a pas de réponse générique correcte ici.

Mais même si nous réussissons grâce à certains actes héroïques à empêcher le compilateur de réorganiser ces opérations, rien ne garantit que cela suffira. Considérez un moyen valide et conforme d'exécuter votre programme C ++ sur une machine x86: DynamoRIO. Il s'agit d'un système qui évalue dynamiquement le code machine du programme. Une chose qu'il peut faire est des optimisations en ligne, et il est même capable d'exécuter de manière spéculative toute la gamme d'instructions arithmétiques de base en dehors du timing. Et ce comportement n'est pas unique aux évaluateurs dynamiques, le processeur x86 réel spéculera également (un nombre beaucoup plus petit) d'instructions et les réorganisera dynamiquement.

La réalisation essentielle est que le fait que l'arithmétique ne soit pas observable (même au niveau de la synchronisation) est quelque chose qui imprègne les couches de l'ordinateur. C'est vrai pour le compilateur, le runtime et souvent même le matériel. Le forcer à être observable contraindrait à la fois considérablement le compilateur, mais cela contraindrait également considérablement le matériel.

Mais tout cela ne doit pas vous faire perdre espoir. Lorsque vous souhaitez chronométrer l'exécution d'opérations mathématiques de base, nous avons des techniques bien étudiées qui fonctionnent de manière fiable. Ils sont généralement utilisés lors du micro-benchmarking . J'ai donné une conférence à ce sujet à CppCon2015: https://youtu.be/nXaxk27zwlk

Les techniques présentées ici sont également fournies par diverses bibliothèques de micro-benchmark telles que celles de Google: https://github.com/google/benchmark#preventing-optimization

La clé de ces techniques est de se concentrer sur les données. Vous rendez l'entrée du calcul opaque pour l'optimiseur et le résultat du calcul opaque pour l'optimiseur. Une fois que vous avez fait cela, vous pouvez le chronométrer de manière fiable. Regardons une version réaliste de l'exemple dans la question d'origine, mais avec la définition de fooentièrement visible pour l'implémentation. J'ai également extrait une version (non portable) de DoNotOptimizede la bibliothèque Google Benchmark que vous pouvez trouver ici: https://github.com/google/benchmark/blob/master/include/benchmark/benchmark_api.h#L208

#include <chrono>

template <class T>
__attribute__((always_inline)) inline void DoNotOptimize(const T &value) {
  asm volatile("" : "+m"(const_cast<T &>(value)));
}

// The compiler has full knowledge of the implementation.
static int foo(int x) { return x * 2; }

auto time_foo() {
  using Clock = std::chrono::high_resolution_clock;

  auto input = 42;

  auto t1 = Clock::now();         // Statement 1
  DoNotOptimize(input);
  auto output = foo(input);       // Statement 2
  DoNotOptimize(output);
  auto t2 = Clock::now();         // Statement 3

  return t2 - t1;
}

Ici, nous nous assurons que les données d'entrée et les données de sortie sont marquées comme non optimisables autour du calcul foo, et seulement autour de ces marqueurs sont les timings calculés. Parce que vous utilisez des données pour pincer le calcul, il est garanti qu'il restera entre les deux synchronisations et pourtant le calcul lui-même peut être optimisé. L'assembly x86-64 résultant généré par une version récente de Clang / LLVM est:

% ./bin/clang++ -std=c++14 -c -S -o - so.cpp -O3
        .text
        .file   "so.cpp"
        .globl  _Z8time_foov
        .p2align        4, 0x90
        .type   _Z8time_foov,@function
_Z8time_foov:                           # @_Z8time_foov
        .cfi_startproc
# BB#0:                                 # %entry
        pushq   %rbx
.Ltmp0:
        .cfi_def_cfa_offset 16
        subq    $16, %rsp
.Ltmp1:
        .cfi_def_cfa_offset 32
.Ltmp2:
        .cfi_offset %rbx, -16
        movl    $42, 8(%rsp)
        callq   _ZNSt6chrono3_V212system_clock3nowEv
        movq    %rax, %rbx
        #APP
        #NO_APP
        movl    8(%rsp), %eax
        addl    %eax, %eax              # This is "foo"!
        movl    %eax, 12(%rsp)
        #APP
        #NO_APP
        callq   _ZNSt6chrono3_V212system_clock3nowEv
        subq    %rbx, %rax
        addq    $16, %rsp
        popq    %rbx
        retq
.Lfunc_end0:
        .size   _Z8time_foov, .Lfunc_end0-_Z8time_foov
        .cfi_endproc


        .ident  "clang version 3.9.0 (trunk 273389) (llvm/trunk 273380)"
        .section        ".note.GNU-stack","",@progbits

Ici, vous pouvez voir le compilateur optimiser l'appel à foo(input)une seule instruction addl %eax, %eax, mais sans le déplacer en dehors du timing ni l'éliminer complètement malgré l'entrée constante.

J'espère que cela vous aidera, et le comité des normes C ++ étudie la possibilité de standardiser des API similaires à DoNotOptimizeici.

Résumé:

Il ne semble pas y avoir de moyen garanti d'empêcher la réorganisation, mais tant que l'optimisation du temps de liaison / du programme complet n'est pas activée, localiser la fonction appelée dans une unité de compilation séparée semble un assez bon pari . (Au moins avec GCC, bien que la logique suggère que cela est probable avec d'autres compilateurs aussi.) Cela se fait au prix de l'appel de fonction - le code incorporé est par définition dans la même unité de compilation et ouvert à la réorganisation.

Réponse originale:

GCC réorganise les appels sous l'optimisation -O2:

#include <chrono>
static int foo(int x)    // 'static' or not here doesn't affect ordering.
{
    return x*2;
}
int fred(int x)
{
    auto t1 = std::chrono::high_resolution_clock::now();
    int y = foo(x);
    auto t2 = std::chrono::high_resolution_clock::now();
    return y;
}

GCC 5.3.0:

g++ -S --std=c++11 -O0 fred.cpp :

_ZL3fooi:
        pushq   %rbp
        movq    %rsp, %rbp
        movl    %ecx, 16(%rbp)
        movl    16(%rbp), %eax
        addl    %eax, %eax
        popq    %rbp
        ret
_Z4fredi:
        pushq   %rbp
        movq    %rsp, %rbp
        subq    $64, %rsp
        movl    %ecx, 16(%rbp)
        call    _ZNSt6chrono3_V212system_clock3nowEv
        movq    %rax, -16(%rbp)
        movl    16(%rbp), %ecx
        call    _ZL3fooi
        movl    %eax, -4(%rbp)
        call    _ZNSt6chrono3_V212system_clock3nowEv
        movq    %rax, -32(%rbp)
        movl    -4(%rbp), %eax
        addq    $64, %rsp
        popq    %rbp
        ret

Mais:

g++ -S --std=c++11 -O2 fred.cpp :

_Z4fredi:
        pushq   %rbx
        subq    $32, %rsp
        movl    %ecx, %ebx
        call    _ZNSt6chrono3_V212system_clock3nowEv
        call    _ZNSt6chrono3_V212system_clock3nowEv
        leal    (%rbx,%rbx), %eax
        addq    $32, %rsp
        popq    %rbx
        ret

Maintenant, avec foo () comme fonction externe:

#include <chrono>
int foo(int x);
int fred(int x)
{
    auto t1 = std::chrono::high_resolution_clock::now();
    int y = foo(x);
    auto t2 = std::chrono::high_resolution_clock::now();
    return y;
}

g++ -S --std=c++11 -O2 fred.cpp :

_Z4fredi:
        pushq   %rbx
        subq    $32, %rsp
        movl    %ecx, %ebx
        call    _ZNSt6chrono3_V212system_clock3nowEv
        movl    %ebx, %ecx
        call    _Z3fooi
        movl    %eax, %ebx
        call    _ZNSt6chrono3_V212system_clock3nowEv
        movl    %ebx, %eax
        addq    $32, %rsp
        popq    %rbx
        ret

MAIS, si cela est lié à -flto (optimisation du temps de liaison):

0000000100401710 <main>:
   100401710:   53                      push   %rbx
   100401711:   48 83 ec 20             sub    $0x20,%rsp
   100401715:   89 cb                   mov    %ecx,%ebx
   100401717:   e8 e4 ff ff ff          callq  100401700 <__main>
   10040171c:   e8 bf f9 ff ff          callq  1004010e0 <_ZNSt6chrono3_V212system_clock3nowEv>
   100401721:   e8 ba f9 ff ff          callq  1004010e0 <_ZNSt6chrono3_V212system_clock3nowEv>
   100401726:   8d 04 1b                lea    (%rbx,%rbx,1),%eax
   100401729:   48 83 c4 20             add    $0x20,%rsp
   10040172d:   5b                      pop    %rbx
   10040172e:   c3                      retq

La réorganisation peut être effectuée par le compilateur ou par le processeur.

La plupart des compilateurs proposent une méthode spécifique à la plate-forme pour empêcher la réorganisation des instructions de lecture-écriture. Sur gcc, c'est

asm volatile("" ::: "memory");

( Plus d'informations ici )

Notez que cela n'empêche qu'indirectement de réorganiser les opérations, tant qu'elles dépendent des lectures / écritures.

En pratique je n'ai pas encore vu de système où l'appel système Clock::now()a le même effet qu'une telle barrière. Vous pouvez inspecter l'assemblage résultant pour être sûr.

Cependant, il n'est pas rare que la fonction testée soit évaluée pendant la compilation. Pour appliquer une exécution «réaliste», vous devrez peut-être dériver des entrées pour foo()des E / S ou unvolatile lecture.

Une autre option serait de désactiver l'inlining pour foo()- encore une fois, c'est spécifique au compilateur et généralement pas portable, mais aurait le même effet.

Sur gcc, ce serait __attribute__ ((noinline))

@Ruslan soulève une question fondamentale: dans quelle mesure cette mesure est-elle réaliste?

Le temps d'exécution est affecté par de nombreux facteurs: l'un est le matériel réel sur lequel nous fonctionnons, l'autre est l'accès simultané aux ressources partagées comme le cache, la mémoire, le disque et les cœurs de processeur.

Donc, ce que nous faisons habituellement pour obtenir des timings comparables : assurez-vous qu'ils sont reproductibles avec une faible marge d'erreur. Cela les rend quelque peu artificiels.

Les performances d'exécution "hot cache" et "cold cache" peuvent facilement différer d'un ordre de grandeur - mais en réalité, ce sera quelque chose entre les deux ("tiède"?)

Le langage C ++ définit ce qui est observable de plusieurs manières.

S'il foo()ne fait rien d'observable, alors il peut être complètement éliminé. Si foo()seulement un calcul qui stocke des valeurs dans un état "local" (que ce soit sur la pile ou dans un objet quelque part) et que le compilateur peut prouver qu'aucun pointeur dérivé en toute sécurité ne peut entrer dans le Clock::now()code, alors il n'y a pas de conséquences observables pour déplacer les Clock::now()appels.

S'il foo()interagit avec un fichier ou l'affichage et que le compilateur ne peut pas prouver qu'il Clock::now()n'interagit pas avec le fichier ou l'affichage, la réorganisation ne peut pas être effectuée, car l'interaction avec un fichier ou un affichage est un comportement observable.

Bien que vous puissiez utiliser des hacks spécifiques au compilateur pour forcer le code à ne pas se déplacer (comme l'assemblage en ligne), une autre approche consiste à tenter de déjouer votre compilateur.

Créez une bibliothèque chargée dynamiquement. Chargez-le avant le code en question.

Cette bibliothèque expose une chose:

namespace details {
  void execute( void(*)(void*), void *);
}

et l'enveloppe comme ceci:

template<class F>
void execute( F f ) {
  struct bundle_t {
    F f;
  } bundle = {std::forward<F>(f)};

  auto tmp_f = [](void* ptr)->void {
    auto* pb = static_cast<bundle_t*>(ptr);
    (pb->f)();
  };
  details::execute( tmp_f, &bundle );
}

qui emballe un lambda nul et utilise la bibliothèque dynamique pour l'exécuter dans un contexte que le compilateur ne peut pas comprendre.

À l'intérieur de la bibliothèque dynamique, nous faisons:

void details::execute( void(*f)(void*), void *p) {
  f(p);
}

ce qui est assez simple.

Maintenant, pour réorganiser les appels execute, il doit comprendre la bibliothèque dynamique, ce qu'il ne peut pas lors de la compilation de votre code de test.

Il peut toujours éliminer les foo()s sans effets secondaires, mais vous en gagnez, vous en perdez.

Non, ça ne peut pas. Selon le standard C ++ [intro.execution]:

14 Chaque calcul de valeur et effet secondaire associé à une expression complète est séquencé avant chaque calcul de valeur et effet secondaire associé à la prochaine expression complète à évaluer.

Une expression complète est essentiellement une instruction terminée par un point-virgule. Comme vous pouvez le voir, la règle ci-dessus stipule que les instructions doivent être exécutées dans l'ordre. C'est à l' intérieur des instructions que le compilateur a plus de liberté (c'est-à-dire qu'il est autorisé dans certaines circonstances à évaluer les expressions qui composent une instruction dans des ordres autres que de gauche à droite ou autre chose spécifique).

Notez que les conditions d'application de la règle du «comme si» ne sont pas remplies ici. Il n'est pas raisonnable de penser qu'un compilateur serait capable de prouver que la réorganisation des appels pour obtenir l'heure système n'affecterait pas le comportement observable du programme. S'il y avait une circonstance dans laquelle deux appels pour obtenir l'heure pouvaient être réorganisés sans changer le comportement observé, il serait extrêmement inefficace de produire en fait un compilateur qui analyse un programme avec suffisamment de compréhension pour pouvoir en déduire avec certitude.

Non.

Parfois, par la règle du "comme si", les instructions peuvent être réordonnées. Ce n'est pas parce qu'ils sont logiquement indépendants les uns des autres, mais parce que cette indépendance permet à un tel réarrangement de se produire sans changer la sémantique du programme.

Déplacer un appel système qui obtient l'heure courante ne satisfait évidemment pas cette condition. Un compilateur qui le fait sciemment ou non est non conforme et vraiment stupide.

En général, je ne m'attendrais pas à ce qu'une expression qui aboutisse à un appel système soit "seconde-devinée" même par un compilateur optimisant de manière agressive. Il n'en sait tout simplement pas assez sur ce que fait cet appel système.

noinline fonction + boîte noire d'assemblage en ligne + dépendances de données complètes

Ceci est basé sur https://stackoverflow.com/a/38025837/895245 mais comme je n'ai vu aucune justification claire de la raison pour laquelle le ::now()ne peut pas être réorganisé là-bas, je préférerais être paranoïaque et le mettre dans une fonction noinline avec le asm.

De cette façon, je suis à peu près sûr que la réorganisation ne peut pas se produire, car les noinline"liens" entre le ::nowet la dépendance des données.

main.cpp

#include <chrono>
#include <iostream>
#include <string>

// noinline ensures that the ::now() cannot be split from the __asm__
template <class T>
__attribute__((noinline)) auto get_clock(T& value) {
    // Make the compiler think we actually use / modify the value.
    // It can't "see" what is going on inside the assembly string.
    __asm__ __volatile__ ("" : "+g" (value));
    return std::chrono::high_resolution_clock::now();
}

template <class T>
static T foo(T niters) {
    T result = 42;
    for (T i = 0; i < niters; ++i) {
        result = (result * result) - (3 * result) + 1;
    }
    return result;
}

int main(int argc, char **argv) {
    unsigned long long input;
    if (argc > 1) {
        input = std::stoull(argv[1], NULL, 0);
    } else {
        input = 1;
    }

    // Must come before because it could modify input
    // which is passed as a reference.
    auto t1 = get_clock(input);
    auto output = foo(input);
    // Must come after as it could use the output.
    auto t2 = get_clock(output);
    std::cout << "output " << output << std::endl;
    std::cout << "time (ns) "
              << std::chrono::duration_cast<std::chrono::nanoseconds>(t2 - t1).count()
              << std::endl;
}

GitHub en amont .

Compilez et exécutez:

g++ -ggdb3 -O3 -std=c++14 -Wall -Wextra -pedantic -o main.out main.cpp
./main.out 1000
./main.out 10000
./main.out 100000

Le seul inconvénient mineur de cette méthode est que nous ajoutons une callqinstruction supplémentaire sur une inlineméthode. objdump -CDmontre qui maincontient:

    11b5:       e8 26 03 00 00          callq  14e0 <auto get_clock<unsigned long long>(unsigned long long&)>
    11ba:       48 8b 34 24             mov    (%rsp),%rsi
    11be:       48 89 c5                mov    %rax,%rbp
    11c1:       b8 2a 00 00 00          mov    $0x2a,%eax
    11c6:       48 85 f6                test   %rsi,%rsi
    11c9:       74 1a                   je     11e5 <main+0x65>
    11cb:       31 d2                   xor    %edx,%edx
    11cd:       0f 1f 00                nopl   (%rax)
    11d0:       48 8d 48 fd             lea    -0x3(%rax),%rcx
    11d4:       48 83 c2 01             add    $0x1,%rdx
    11d8:       48 0f af c1             imul   %rcx,%rax
    11dc:       48 83 c0 01             add    $0x1,%rax
    11e0:       48 39 d6                cmp    %rdx,%rsi
    11e3:       75 eb                   jne    11d0 <main+0x50>
    11e5:       48 89 df                mov    %rbx,%rdi
    11e8:       48 89 44 24 08          mov    %rax,0x8(%rsp)
    11ed:       e8 ee 02 00 00          callq  14e0 <auto get_clock<unsigned long long>(unsigned long long&)>

nous voyons donc que fooc'était en ligne, mais get_clockne l'étaient pas et l'entourons.

get_clock lui-même est cependant extrêmement efficace, consistant en une instruction optimisée pour les appels à une seule feuille qui ne touche même pas la pile:

00000000000014e0 <auto get_clock<unsigned long long>(unsigned long long&)>:
    14e0:       e9 5b fb ff ff          jmpq   1040 <std::chrono::_V2::system_clock::now()@plt>

Étant donné que la précision de l'horloge est elle-même limitée, je pense qu'il est peu probable que vous puissiez remarquer les effets de synchronisation d'un supplément jmpq. Notez que l'un callest nécessaire, car il se ::now()trouve dans une bibliothèque partagée.

Appel ::now()depuis l'assembly en ligne avec une dépendance de données

Ce serait la solution la plus efficace possible, surmontant même le supplément jmpqmentionné ci-dessus.

Ceci est malheureusement extrêmement difficile à faire correctement, comme indiqué sur: Appel de printf dans l'ASM en ligne étendu

Si votre mesure du temps peut être effectuée directement dans l'assemblage en ligne sans appel, cette technique peut être utilisée. C'est le cas par exemple pour les instructions d'instrumentation gem5 magic , x86 RDTSC ( ne sais pas si c'est plus représentatif) et éventuellement d'autres compteurs de performance.

Fils associés:

• Est-il légal pour un optimiseur C ++ de réorganiser les appels à clock ()?

Testé avec GCC 8.3.0, Ubuntu 19.04.