Respecter l'ordre des instructions en C++

Question

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

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é. 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;

Answer 1

J'aimerais essayer de fournir une réponse un peu plus complète après que cette question ait été discutée 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 quelconque 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 connu à l'implémentation. Elle peut les simuler, elle sait qu'elles ne peuvent pas être observées par des programmes corrects, et elle est toujours libre de les déplacer.

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

Tout d'abord, la seule façon d'empêcher cela dans le compilateur est de lui dire que toutes ces opérations de base sont observables. Le problème est que cela exclurait alors l'écrasante majorité des optimisations du compilateur. À l'intérieur du compilateur, nous n'avons essentiellement pas de bons mécanismes pour modéliser que les timing est observable, mais rien d'autre. Nous n'avons même pas un bon modèle de quelles opérations prennent du temps . Par exemple, la conversion d'un nombre entier non signé de 32 bits en un nombre entier non signé de 64 bits prend-elle du temps ? Le temps est nul sur x86-64, mais sur d'autres architectures, il est non nul. Il n'y a pas de réponse génériquement correcte ici.

Mais même si nous parvenons, par des moyens héroïques, à empêcher le compilateur de réordonner ces opérations, il n'est pas certain que cela soit suffisant. Considérons une façon 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. Il peut notamment effectuer des optimisations en ligne, et il est même capable d'exécuter de manière spéculative toute la gamme des instructions arithmétiques de base en dehors du timing. Et ce comportement n'est pas propre aux évaluateurs dynamiques, le CPU x86 actuel spéculera également (un nombre beaucoup plus petit d') instructions et les réordonnera dynamiquement.

La prise de conscience essentielle est que le fait que l'arithmétique ne soit pas observable (même au niveau du timing) est quelque chose qui imprègne toutes 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 considérablement le compilateur, mais aussi 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 disposons de techniques bien étudiées qui fonctionnent de manière fiable. En général, ces techniques sont utilisées pour faire micro-benchmarking . J'ai donné une conférence à ce sujet à la CppCon2015 : https://youtu.be/nXaxk27zwlk

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

La clé de ces techniques est de se concentrer sur les données. Il faut rendre 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. Examinons une version réaliste de l'exemple de la question originale, mais avec la définition de foo entièrement visible à la mise en œuvre. J'ai également extrait une version (non portable) de DoNotOptimize de 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 c'est seulement autour de ces marqueurs que les temps sont calculés. Puisque vous utilisez des données pour pincer le calcul, il est garanti de rester entre les deux timings et pourtant le calcul lui-même est autorisé à être optimisé. L'assemblage x86-64 résultant généré par une construction 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 que le compilateur optimise l'appel à foo(input) en une seule instruction, addl %eax, %eax mais sans le déplacer en dehors du timing ou l'éliminer complètement malgré l'apport constant.

J'espère que cela vous aidera. Le comité de normalisation C++ étudie la possibilité de normaliser des API similaires à DoNotOptimize ici.

Answer 2

Résumé :

Il semble qu'il n'y ait pas de moyen garanti d'empêcher le réordonnancement, 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 être un bon pari. . (Au moins avec GCC, bien que la logique voudrait que ce soit probable avec d'autres compilateurs aussi). Cela se fait au détriment de l'appel de fonction - le code inlined est par définition dans la même unité de compilation et ouvert à la réorganisation.

Réponse originale :

GCC réordonne 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é avec -flto (link-time optimisation) :

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

Answer 3

Le réordonnancement peut être effectué par le compilateur ou par le processeur.

La plupart des compilateurs offrent une méthode spécifique à la plate-forme pour empêcher le réordonnancement des instructions de lecture-écriture. Sur gcc, cette méthode est

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

( Plus d'informations ici )

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

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

Il n'est cependant pas rare que la fonction testée soit évaluée au moment de la compilation. Pour imposer une exécution "réaliste", vous pouvez avoir besoin de dériver l'entrée de foo() d'E/S ou d'un volatile lire.

---

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

Sous 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 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 comparable les horaires : assurez-vous qu'ils sont reproductible avec une faible marge d'erreur. Cela les rend quelque peu artificiels.

Les performances d'exécution d'un "cache chaud" par rapport à celles d'un "cache froid" peuvent facilement différer d'un ordre de grandeur - mais en réalité, elles seront quelque chose d'intermédiaire ("tiède" ?).

Answer 4

Le langage C++ définit ce qui est observable de plusieurs façons.

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

Si foo() a interagi avec un fichier ou l'écran, et le compilateur ne peut pas prouver que Clock::now() fait no interagissent avec le fichier ou l'écran, alors la réorganisation ne peut pas être effectuée, car l'interaction avec un fichier ou un écran est un comportement observable.

Bien que vous puissiez utiliser des astuces spécifiques au compilateur pour forcer le code à ne pas se déplacer (comme l'assemblage en ligne), une autre approche consiste à essayer d'être plus malin que votre compilateur.

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

Cette bibliothèque expose une chose :

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

et l'enroule 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 nullaire et utilise la bibliothèque dynamique pour l'exécuter dans un contexte que le compilateur ne peut pas comprendre.

Dans la bibliothèque dynamique, nous le faisons :

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

ce qui est assez simple.

Maintenant, il faut réorganiser les appels à execute il doit comprendre la bibliothèque dynamique, ce qu'il ne peut pas faire en compilant votre code de test.

Il peut encore éliminer foo() sans aucun effet secondaire, mais on en gagne et on en perd.

Answer 5

Non, ce n'est pas possible. Selon la norme C++ [intro.execution] :

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

Une expression complète est essentiellement une déclaration terminée par un point-virgule. Comme vous pouvez le constater, la règle ci-dessus stipule que les instructions doivent être exécutées dans l'ordre. Il s'agit sur les instructions pour lesquelles le compilateur a une plus grande liberté d'action (c'est-à-dire qu'il est autorisé, dans certaines circonstances, à évaluer les expressions qui composent une instruction dans un ordre autre que de gauche à droite ou tout autre ordre spécifique).

Notez que les conditions d'application de la règle as-if ne sont pas remplies ici. Il est déraisonnable de penser que n'importe quel compilateur serait capable de prouver que réordonner les appels pour obtenir l'heure du système n'affecterait pas le comportement observable du programme. S'il existait une circonstance dans laquelle deux appels pour obtenir l'heure pourraient être réordonnés sans changer le comportement observé, il serait extrêmement inefficace de produire un compilateur qui analyse un programme avec suffisamment de compréhension pour pouvoir le déduire avec certitude.