Hacer cumplir el orden de las instrucciones en C ++

Supongamos que tengo varias declaraciones que quiero ejecutar en un orden fijo. Quiero usar g ++ con el nivel de optimización 2, por lo que algunas declaraciones podrían reordenarse. ¿Qué herramientas tiene uno para hacer cumplir un determinado orden de declaraciones?

Considere el siguiente ejemplo.

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;

En este ejemplo, es importante que las instrucciones 1-3 se ejecuten en el orden indicado. Sin embargo, ¿no puede el compilador pensar que la declaración 2 es independiente de 1 y 3 y ejecutar el código de la siguiente manera?

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;

Me gustaría intentar proporcionar una respuesta algo más completa después de que esto se discutiera con el comité de estándares de C ++. Además de ser miembro del comité de C ++, también soy desarrollador de los compiladores LLVM y Clang.

Fundamentalmente, no hay forma de usar una barrera o alguna operación en la secuencia para lograr estas transformaciones. El problema fundamental es que la semántica operativa de algo como una suma de números enteros es totalmente conocida en la implementación. Puede simularlos, sabe que no pueden ser observados por los programas correctos y siempre es libre de moverlos.

Podríamos intentar prevenir esto, pero tendría resultados extremadamente negativos y finalmente fracasaría.

Primero, la única forma de evitar esto en el compilador es decirle que todas estas operaciones básicas son observables. El problema es que esto evitaría la inmensa mayoría de las optimizaciones del compilador. Dentro del compilador, esencialmente no tenemos buenos mecanismos para modelar que el tiempo es observable, pero nada más. Ni siquiera tenemos un buen modelo de qué operaciones llevan tiempo . Como ejemplo, ¿lleva tiempo convertir un entero sin signo de 32 bits en un entero sin signo de 64 bits? No lleva tiempo en x86-64, pero en otras arquitecturas toma un tiempo distinto de cero. Aquí no hay una respuesta genéricamente correcta.

Pero incluso si logramos evitar con algunos actos heroicos que el compilador reordene estas operaciones, no hay garantía de que esto sea suficiente. Considere una forma válida y conforme de ejecutar su programa C ++ en una máquina x86: DynamoRIO. Este es un sistema que evalúa dinámicamente el código máquina del programa. Una cosa que puede hacer son optimizaciones en línea, e incluso es capaz de ejecutar especulativamente toda la gama de instrucciones aritméticas básicas fuera del tiempo. Y este comportamiento no es exclusivo de los evaluadores dinámicos, la CPU x86 real también especulará (un número mucho menor de) instrucciones y las reordenará dinámicamente.

La comprensión esencial es que el hecho de que la aritmética no sea observable (incluso a nivel de tiempo) es algo que impregna las capas de la computadora. Es cierto para el compilador, el tiempo de ejecución y, a menudo, incluso el hardware. Obligarlo a ser observable restringiría drásticamente el compilador, pero también restringiría drásticamente el hardware.

Pero todo esto no debería hacer que pierda la esperanza. Cuando desee cronometrar la ejecución de operaciones matemáticas básicas, tenemos técnicas bien estudiadas que funcionan de manera confiable. Por lo general, se utilizan al realizar microevaluaciones comparativas . Di una charla sobre esto en CppCon2015: https://youtu.be/nXaxk27zwlk

Las técnicas que se muestran allí también las proporcionan varias bibliotecas de microevaluaciones como las de Google: https://github.com/google/benchmark#preventing-optimization

La clave de estas técnicas es centrarse en los datos. Usted hace que la entrada del cálculo sea opaca para el optimizador y el resultado del cálculo opaco para el optimizador. Una vez que haya hecho eso, puede cronometrarlo de manera confiable. Veamos una versión realista del ejemplo de la pregunta original, pero con la definición de foocompletamente visible para la implementación. También extraje una versión (no portátil) de DoNotOptimizela biblioteca de Google Benchmark que puede encontrar aquí: 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;
}

Aquí nos aseguramos de que los datos de entrada y los datos de salida estén marcados como no optimizables alrededor del cálculo foo, y solo alrededor de esos marcadores se calculan los tiempos. Debido a que está utilizando datos para ajustar el cálculo, se garantiza que se mantendrá entre los dos tiempos y, sin embargo, se permite optimizar el cálculo en sí. El ensamblado x86-64 resultante generado por una compilación reciente de Clang / LLVM es:

% ./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

Aquí puede ver al compilador optimizando la llamada para foo(input)reducirla a una sola instrucción addl %eax, %eax, pero sin moverla fuera del tiempo o eliminarla por completo a pesar de la entrada constante.

Espero que esto ayude, y el comité de estándares de C ++ está estudiando la posibilidad de estandarizar API similares a DoNotOptimizeaquí.

Resumen:

Parece que no hay una forma garantizada de evitar el reordenamiento, pero mientras no se habilite la optimización de tiempo de enlace / programa completo, ubicar la función llamada en una unidad de compilación separada parece una apuesta bastante buena . (Al menos con GCC, aunque la lógica sugeriría que esto también es probable con otros compiladores). Esto tiene el costo de la llamada a la función: el código en línea está por definición en la misma unidad de compilación y está abierto a reordenamiento.

Respuesta original:

GCC reordena las llamadas bajo la optimización -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

Pero:

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

Ahora, con foo () como función externa:

#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

PERO, si esto está vinculado con -flto (optimización de tiempo de enlace):

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 reordenación puede realizarla el compilador o el procesador.

La mayoría de los compiladores ofrecen un método específico de la plataforma para evitar el reordenamiento de las instrucciones de lectura y escritura. En gcc, esto es

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

( Más información aquí )

Tenga en cuenta que esto solo evita indirectamente las operaciones de reordenación, siempre que dependan de las lecturas / escrituras.

En la práctica , todavía no he visto un sistema en el que la llamada al sistema Clock::now()tenga el mismo efecto que una barrera de este tipo. Puede inspeccionar el ensamblaje resultante para estar seguro.

Sin embargo, no es raro que la función bajo prueba sea evaluada durante el tiempo de compilación. Para imponer una ejecución "realista", es posible que deba derivar la entrada foo()de E / S o una volatilelectura.

Otra opción sería deshabilitar la inserción para foo(); nuevamente, esto es específico del compilador y generalmente no es portátil, pero tendría el mismo efecto.

En gcc, esto sería __attribute__ ((noinline))

@Ruslan plantea una cuestión fundamental: ¿Cuán realista es esta medida?

El tiempo de ejecución se ve afectado por muchos factores: uno es el hardware real en el que estamos ejecutando, el otro es el acceso concurrente a recursos compartidos como caché, memoria, disco y núcleos de CPU.

Entonces, lo que solemos hacer para obtener tiempos comparables : asegurarnos de que sean reproducibles con un margen de error bajo. Esto los hace algo artificiales.

El rendimiento de ejecución de "caché caliente" frente a "caché fría" puede diferir fácilmente en un orden de magnitud, pero en realidad, será algo intermedio (¿"tibio"?)

El lenguaje C ++ define lo que es observable de varias formas.

Si foo()no hace nada observable, entonces se puede eliminar por completo. Si foo()solo hace un cálculo que almacena valores en estado "local" (ya sea en la pila o en un objeto en algún lugar), y el compilador puede probar que ningún puntero derivado de forma segura puede ingresar al Clock::now()código, entonces no hay consecuencias observables para moviendo las Clock::now()llamadas.

Si foo()interactuado con un archivo o la pantalla, y el compilador no puede probar que Clock::now()lo hace no interactúan con el archivo o la pantalla, a continuación, la reordenación no se puede hacer, debido a la interacción con un archivo o pantalla es la conducta observable.

Si bien puede usar trucos específicos del compilador para forzar que el código no se mueva (como el ensamblaje en línea), otro enfoque es intentar burlar a su compilador.

Cree una biblioteca cargada dinámicamente. Cárguelo antes que el código en cuestión.

Esa biblioteca expone una cosa:

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

y lo envuelve así:

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 );
}

que empaqueta un lambda nular y usa la biblioteca dinámica para ejecutarlo en un contexto que el compilador no puede entender.

Dentro de la biblioteca dinámica, hacemos:

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

que es bastante simple.

Ahora, para reordenar las llamadas a execute, debe comprender la biblioteca dinámica, lo que no puede hacer mientras compila el código de prueba.

Todavía puede eliminar foo()mensajes de correo electrónico con cero efectos secundarios, pero ganas algunos y pierdes otros.

No, no puede. Según el estándar C ++ [intro.execution]:

14 Cada cálculo de valor y efecto secundario asociado con una expresión completa se secuencia antes de cada cálculo de valor y efecto secundario asociado con la siguiente expresión completa a evaluar.

Una expresión completa es básicamente una declaración terminada con un punto y coma. Como puede ver, la regla anterior estipula que las declaraciones deben ejecutarse en orden. Es dentro de las declaraciones donde el compilador tiene más rienda suelta (es decir, bajo alguna circunstancia se le permite evaluar expresiones que componen una declaración en órdenes que no sean de izquierda a derecha o cualquier otra cosa específica).

Tenga en cuenta que aquí no se cumplen las condiciones para que se aplique la regla como si. No es razonable pensar que cualquier compilador podría demostrar que reordenar las llamadas para obtener la hora del sistema no afectaría el comportamiento observable del programa. Si hubiera una circunstancia en la que dos llamadas para obtener el tiempo pudieran reordenarse sin cambiar el comportamiento observado, sería extremadamente ineficiente producir un compilador que analice un programa con suficiente comprensión para poder inferir esto con certeza.

No.

A veces, por la regla "como si", las declaraciones pueden reordenarse. Esto no se debe a que sean lógicamente independientes entre sí, sino a que esa independencia permite que se produzca tal reordenamiento sin cambiar la semántica del programa.

Mover una llamada al sistema que obtiene la hora actual, obviamente, no satisface esa condición. Un compilador que lo hace a sabiendas o sin saberlo no cumple con las normas y es realmente tonto.

En general, no esperaría que ninguna expresión que resulte en una llamada al sistema sea "cuestionada" incluso por un compilador de optimización agresiva. Simplemente no sabe lo suficiente sobre lo que hace esa llamada al sistema.

noinline función + caja negra de ensamblaje en línea + dependencias de datos completas

Esto se basa en https://stackoverflow.com/a/38025837/895245 pero como no vi ninguna justificación clara de por qué ::now()no se puede reordenar allí, preferiría ser paranoico y ponerlo dentro de una función noinline junto con el asm.

De esta manera, estoy bastante seguro de que el reordenamiento no puede ocurrir, ya que noinline"vincula" el ::nowy la dependencia de datos.

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 aguas arriba .

Compilar y ejecutar:

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

El único inconveniente menor de este método es que agregamos una callqinstrucción adicional sobre un inlinemétodo. objdump -CDmuestra que maincontiene:

    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&)>

entonces vemos que fooestaba alineado, pero get_clockno lo estaba y lo rodeamos.

get_clock en sí mismo, sin embargo, es extremadamente eficiente, y consiste en una instrucción optimizada de llamada de una sola hoja que ni siquiera toca la pila:

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>

Dado que la precisión del reloj es en sí misma limitada, creo que es poco probable que pueda notar los efectos de sincronización de uno adicional jmpq. Tenga en cuenta que callse requiere uno independientemente de que ::now()esté en una biblioteca compartida.

Llamar ::now()desde ensamblado en línea con una dependencia de datos

Esta sería la solución más eficiente posible, superando incluso el extra jmpqmencionado anteriormente.

Desafortunadamente, esto es extremadamente difícil de hacer correctamente, como se muestra en: Llamar a printf en ASM en línea extendido

Sin embargo, si su medición del tiempo se puede realizar directamente en el ensamblaje en línea sin una llamada, entonces se puede utilizar esta técnica. Este es el caso, por ejemplo, de las instrucciones de instrumentación mágica gem5 , RDTSC x86 (no estoy seguro de si esto ya es representativo) y posiblemente otros contadores de rendimiento.

Temas relacionados:

• ¿Es legal que un optimizador de C ++ reordene las llamadas a clock ()?

Probado con GCC 8.3.0, Ubuntu 19.04.