Hacer cumplir el orden de las instrucciones en C ++

111

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;
S2108887
fuente
34
Si el compilador cree que son independientes cuando no lo son, el compilador está roto y debería usar un compilador mejor.
David Schwartz
1
podría __sync_synchronize()ser de alguna ayuda?
vsz
3
@HowardHinnant: El poder semántico del estándar C mejoraría enormemente si se definiera tal directiva y si se ajustaran las reglas de aliasing para eximir las lecturas realizadas después de una barrera de datos que se escribieron antes.
supercat
4
@DavidSchwartz En este caso, se trata de medir el tiempo que se footarda en ejecutarse, que el compilador puede ignorar al reordenar, al igual que se le permite ignorar la observación de un hilo diferente.
CodesInChaos

Respuestas:

100

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í.

Chandler Carruth
fuente
1
Gracias por su respuesta. Lo he marcado como la nueva mejor respuesta. Podría haber hecho esto antes, pero no he leído esta página de stackoverflow durante muchos meses. Estoy muy interesado en usar el compilador de Clang para crear programas en C ++. Entre otras cosas, me gusta que se puedan usar caracteres Unicode en nombres de variables en Clang. Creo que haré más preguntas sobre Clang en Stackoverflow.
S2108887
5
Si bien entiendo cómo esto evita que foo se optimice por completo, ¿puede explicar un poco por qué esto evita que las llamadas Clock::now()se reordenen en relación con foo ()? ¿Tiene el optimizador que asumir eso DoNotOptimizey Clock::now()tener acceso y podría modificar algún estado global común que a su vez los vincularía a la entrada y salida? ¿O confía en algunas limitaciones actuales de la implementación del optimizador?
MikeMB
2
DoNotOptimizeen este ejemplo es un evento sintéticamente "observable". Es como si imprimiera teóricamente una salida visible en algún terminal con la representación de la entrada. Dado que leer el reloj también es observable (está observando el paso del tiempo), no se pueden reordenar sin cambiar el comportamiento observable del programa.
Chandler Carruth
1
Todavía no tengo muy claro el concepto "observable", si la foofunción está realizando algunas operaciones como leer desde un socket que puede estar bloqueado por un tiempo, ¿esto cuenta como una operación observable? Y dado readque no es una operación "totalmente conocida" (¿verdad?), ¿El código se mantendrá en orden?
ravenisadesk
"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". Pero me parece que el problema no es la semántica de la suma de enteros, es la semántica de llamar a la función foo (). A menos que foo () esté en la misma unidad de compilación, ¿cómo sabe que foo () y clock () no interactúan?
Dave
59

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
Jeremy
fuente
3
También lo hacen MSVC e ICC. Clang es el único que parece conservar la secuencia original.
Cody Gray
3
no usa t1 y t2 en ningún lugar, por lo que puede pensar que el resultado se puede descartar y reordenar el código
phuclv
3
@Niall: no puedo ofrecer nada más concreto, pero creo que mi comentario alude a la razón subyacente: el compilador sabe que foo () no puede afectar ahora (), ni viceversa, y también lo hace el reordenamiento. Varios experimentos que involucran funciones y datos de alcance externo parecen confirmar esto. Esto incluye que foo () estático dependa de una variable de alcance de archivo N: si N se declara como estático, se produce un reordenamiento, mientras que si se declara no estático (es decir, es visible para otras unidades de compilación y, por lo tanto, está potencialmente sujeto a los efectos secundarios de funciones externas como now ()) no se reordenan.
Jeremy
3
@ Lưu Vĩnh Phúc: Excepto que las llamadas en sí mismas no se eliminan. Una vez más, sospecho que esto se debe a que el compilador no sabe cuáles podrían ser sus efectos secundarios, pero sabe que esos efectos secundarios no pueden influir en el comportamiento de foo ().
Jeremy
3
Y una nota final: especificar -flto (optimización del tiempo de enlace) provoca el reordenamiento incluso en casos que de otro modo no se reordenarán.
Jeremy
20

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"?)

Peterchen
fuente
2
Su truco asmafecta el tiempo de ejecución de las declaraciones entre llamadas de temporizador: el código después del golpe de memoria tiene que recargar todas las variables de la memoria.
Ruslan
@Ruslan: Su truco, no el mío. Hay diferentes niveles de purga, y hacer algo así es inevitable para obtener resultados reproducibles.
peterchen
2
Tenga en cuenta que el truco con 'asm' solo ayuda como barrera para las operaciones que tocan la memoria, y el OP está interesado en más que eso. Vea mi respuesta para más detalles.
Chandler Carruth
11

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.

Yakk - Adam Nevraumont
fuente
19
"otro enfoque es intentar burlar a tu compilador" Si esa frase no es una señal de haber caído por la madriguera, no sé qué es. :-)
Cody Gray
1
Creo que podría ser útil señalar que el tiempo necesario para que se ejecute un bloque de código no se considera un comportamiento "observable" que los compiladores deben mantener . Si el tiempo para ejecutar un bloque de código fuera "observable", no se permitirían formas de optimización del rendimiento. Si bien sería útil para C y C ++ definir una "barrera de causalidad" que requeriría que un compilador esperara la ejecución de cualquier código después de la barrera hasta que todos los efectos secundarios anteriores a la barrera hubieran sido manejados por el código generado [código que quiere asegurarse de que los datos
estén
1
... propagado a través de cachés de hardware necesitaría usar medios específicos de hardware para hacer eso, pero un medio específico de hardware de esperar hasta que se completen todas las escrituras publicadas sería inútil sin una directiva de barrera para garantizar que todas las escrituras pendientes sean rastreadas por el compilador deben publicarse en el hardware antes de que se solicite al hardware que se asegure de que todas las escrituras publicadas estén completas]. No conozco ninguna forma de hacerlo en ninguno de los dos idiomas sin utilizar un volatileacceso ficticio o una llamada a un código externo.
supercat
4

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.

Smeeheey
fuente
12
Sin embargo, todavía existe la regla como si
MM
18
El compilador de reglas como si puede hacer cualquier cosa con el código siempre que no cambie el comportamiento observable. El tiempo de ejecución no es observable. Por lo tanto, puede reordenar líneas arbitrarias de código siempre que el resultado sea el mismo (la mayoría de los compiladores hacen cosas sensatas y no reordenan las llamadas de tiempo, pero no es necesario)
Revolver_Ocelot
6
El tiempo de ejecución no es observable. Esto es bastante extraño. Desde un punto de vista práctico, no técnico, el tiempo de ejecución (también conocido como "rendimiento") es muy observable.
Frédéric Hamidi
3
Depende de cómo midas el tiempo. No es posible medir el número de ciclos de reloj necesarios para ejecutar algún cuerpo de código en C ++ estándar.
Peter
3
@dba Estás mezclando algunas cosas. El vinculador ya no puede generar aplicaciones Win16, eso es cierto, pero eso se debe a que han eliminado el soporte para generar ese tipo de binario. Las aplicaciones WIn16 no usan el formato PE. Eso no implica que el compilador o el enlazador tengan conocimientos especiales sobre las funciones de la API. El otro problema está relacionado con la biblioteca en tiempo de ejecución. No hay absolutamente ningún problema para obtener la última versión de MSVC para generar un binario que se ejecute en NT 4. Lo he hecho. El problema surge tan pronto como intenta vincular en el CRT, que llama a funciones no disponibles.
Cody Gray
2

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.

Carreras de ligereza en órbita
fuente
5
Estoy de acuerdo en que sería una tontería, pero no lo llamaría no conforme . El compilador puede saber qué llamada del sistema en un sistema concreto hace exactamente y si tiene efectos secundarios. Esperaría que los compiladores no reordenen dicha llamada solo para cubrir el caso de uso común, lo que permite una mejor experiencia del usuario, no porque el estándar lo prohíba.
Revolver_Ocelot
4
@Revolver_Ocelot: Las optimizaciones que cambian la semántica del programa (está bien, excepto para elisión de copia) no cumplen con el estándar, ya sea que esté de acuerdo o no.
Lightness Races in Orbit
6
En el caso trivial de, int x = 0; clock(); x = y*2; clock();no hay formas definidas para que el clock()código interactúe con el estado de x. Bajo el estándar C ++, no tiene que saber qué clock()es lo que hace, podría examinar la pila (y notar cuándo ocurre el cálculo), pero ese no es el problema de C ++ .
Yakk - Adam Nevraumont
5
Para llevar el punto de Yakk más allá: es cierto que reordenar las llamadas al sistema, de modo que el resultado de la primera se asigne t2y el segundo t1, sería no conforme y tonto si se usan esos valores, lo que esta respuesta pierde es que un compilador conforme a veces puede reordenar otro código a través de una llamada al sistema. En este caso, siempre que sepa lo que foo()hace (por ejemplo, porque lo ha incluido) y, por lo tanto, (en términos generales) es una función pura, entonces puede moverlo.
Steve Jessop
1
.. nuevamente hablando libremente, esto se debe a que no hay garantía de que la implementación real (aunque no la máquina abstracta) no calcule especulativamente y*yantes de la llamada al sistema, solo por diversión. Tampoco hay garantía de que la implementación real no use el resultado de este cálculo especulativo más adelante en cualquier punto que xse use, por lo tanto, no hace nada entre las llamadas a clock(). Lo mismo ocurre con cualquier función en línea foo, siempre que no tenga efectos secundarios y no pueda depender del estado que pueda ser alterado clock().
Steve Jessop
0

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:

Probado con GCC 8.3.0, Ubuntu 19.04.

Ciro Santilli 郝海东 冠状 病 六四 事件 法轮功
fuente
1
Normalmente no es necesario forzar un derrame / recarga con "+m", usar "+r"es una forma mucho más eficiente de hacer que el compilador materialice un valor y luego asuma que la variable ha cambiado.
Peter Cordes