Hacer cumplir el orden de extracto en C ++

Supongamos que tengo una serie de declaraciones que quiero ejecutar en un orden fijo. Quiero usar g ++ con nivel de optimización 2, por lo que algunas declaraciones podrían reordenarse. ¿Qué herramientas se necesitan para hacer cumplir un cierto orden de declaraciones?

Considera 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 declaraciones 1-3 se ejecuten en el orden dado. Sin embargo, ¿no puede el comstackdor pensar que la statement 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 tratar de proporcionar una respuesta un poco más completa después de que esto fue discutido con el comité de estándares de C ++. Además de ser miembro del comité C ++, también soy desarrollador de los comstackdores 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 operacional de algo así como una adición entera es totalmente conocida por la implementación. Puede simularlos, sabe que no pueden ser observados por los progtwigs correctos, y siempre es libre de moverlos.

Podríamos tratar de evitar esto, pero tendría resultados extremadamente negativos y finalmente fallaría.

Primero, la única manera de evitar esto en el comstackdor es decirle que todas estas operaciones básicas son observables. El problema es que esto evitaría la abrumadora mayoría de las optimizaciones del comstackdor. Dentro del comstackdor, esencialmente no tenemos buenos mecanismos para modelar que el tiempo sea ​​observable, pero nada más. Ni siquiera tenemos un buen modelo de lo que las operaciones toman tiempo . A modo de ejemplo, ¿la conversión de un entero sin signo de 32 bits a un entero sin signo de 64 bits lleva tiempo? Lleva tiempo cero en x86-64, pero en otras architectures toma un tiempo no nulo. No hay una respuesta genéricamente correcta aquí.

Pero incluso si tenemos éxito gracias a algunos actos heroicos para evitar que el comstackdor vuelva a ordenar estas operaciones, no hay garantía de que esto sea suficiente. Considere una forma válida y conforme para ejecutar su progtwig C ++ en una máquina x86: DynamoRIO. Este es un sistema que evalúa dinámicamente el código de máquina del progtwig. Una cosa que puede hacer es 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 dynamics, la CPU x86 real también especulará (una cantidad mucho menor de) instrucciones y las reordenará dinámicamente.

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

Pero todo esto no debería hacer que pierdas la esperanza. Cuando desee cronometrar la ejecución de operaciones matemáticas básicas, hemos estudiado técnicas que funcionan de manera confiable. Por lo general, estos se utilizan al hacer micro-benchmarking . Di una charla sobre esto en CppCon2015: https://youtu.be/nXaxk27zwlk

Las técnicas que se muestran allí también son provistas por varias bibliotecas de micro-benchmark como Google: https://github.com/google/benchmark#preventing-optimisation

La clave de estas técnicas es centrarse en los datos. Usted hace que la entrada al cálculo sea opaca para el optimizador y el resultado del cálculo opaco para el optimizador. Una vez que hayas hecho eso, puedes cronometrarlo de manera confiable. Veamos una versión realista del ejemplo en la pregunta original, pero con la definición de foo completamente visible para la implementación. También DoNotOptimize versión (no portátil) de DoNotOptimize de la biblioteca de Google Benchmark que puede encontrar aquí: https://github.com/google/benchmark/blob/master/include/benchmark/benchmark_api.h#L208

 #include  template  __attribute__((always_inline)) inline void DoNotOptimize(const T &value) { asm volatile("" : "+m"(const_cast(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 foo cálculo, y solo alrededor de esos marcadores están los tiempos calculados. Debido a que está utilizando datos para pincer el cálculo, se garantiza que se mantendrá entre los dos tiempos y, sin embargo, se permite optimizar el cálculo en sí. El ensamblaje x86-64 resultante generado por una comstackció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 comstackdor optimizando la llamada a foo(input) a una sola instrucción, addl %eax, %eax , pero sin moverlo fuera del tiempo o eliminarlo por completo a pesar de la entrada constante.

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

Resumen:

Parece que no hay una forma garantizada de evitar el reordenamiento, pero mientras la optimización de tiempo de enlace / progtwig completo no esté habilitada, la localización de la función llamada en una unidad de comstackción separada parece una buena apuesta . (Al menos con GCC, aunque la lógica sugeriría que esto también es probable con otros comstackdores). Esto se produce a costa de la llamada a la función: el código en línea es, por definición, en la misma unidad de comstackción y está abierto para reordenar.

Respuesta original:

GCC reordena las llamadas en optimización de -O2:

 #include  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 una función externa:

 #include  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 
: 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 hacerla el comstackdor o el procesador.

La mayoría de los comstackdores 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 reordenamiento, siempre que dependan de las lecturas / escrituras.

En la práctica , aún no he visto un sistema donde la llamada al sistema en Clock::now() tenga el mismo efecto que dicha barrera. Puede inspeccionar el ensamblaje resultante para estar seguro.

No es raro, sin embargo, que la función bajo prueba se evalúe durante el tiempo de comstackción. Para hacer cumplir la ejecución “realista”, es posible que deba derivar la entrada para foo() desde E / S o una lectura volatile .


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

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


@Ruslan plantea un problema 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 se está 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 : asegúrese de que sean reproducibles con un margen de error bajo. Esto los hace algo artificiales.

El rendimiento de ejecución de “memoria caché activa” frente a “memoria 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 se puede observar de varias maneras.

Si foo() no hace nada observable, entonces puede eliminarse por completo. Si foo() solo hace un cálculo que almacena valores en estado “local” (ya sea en la stack o en algún objeto), y el comstackdor puede probar que ningún puntero derivado de forma segura puede entrar en el Clock::now() código, entonces no hay consecuencias observables para mover las llamadas Clock::now() .

Si foo() interactuó con un archivo o la pantalla, y el comstackdor no puede probar que Clock::now() no interactúa con el archivo o la pantalla, no se puede realizar el reordenamiento, porque la interacción con un archivo o pantalla es un comportamiento observable .

Si bien puede usar hacks específicos del comstackdor para forzar al código a no moverse (como el ensamblaje en línea), otro enfoque es intentar ser más listo que su comstackdor.

Crea una biblioteca cargada dinámicamente. Cargarlo antes del código en cuestión.

Esa biblioteca expone una cosa:

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

y lo envuelve así:

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

que empaqueta un nullary lambda y usa la biblioteca dinámica para ejecutarlo en un contexto que el comstackdor 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, que no puede al comstackr el código de prueba.

Todavía puede eliminar foo() s con cero efectos secundarios, pero si ganas algo, pierdes algo.

No, no puede. De acuerdo con el estándar C ++ [intro.execution]:

14 Cada cómputo de valor y efecto secundario asociado con una expresión completa se secuencia antes de que se evalúe cada cálculo de valor y efecto secundario asociado con la siguiente expresión completa.

Una expresión completa es básicamente una statement terminada por punto y coma. Como puede ver, la regla anterior estipula que las declaraciones se deben ejecutar en orden. Es dentro de las declaraciones que al comstackdor se le permite más rienda suelta (es decir, se le permite, bajo ciertas circunstancias, evaluar expresiones que componen una instrucció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 la aplicación de la regla de si. No es razonable pensar que cualquier comstackdor pueda probar que reordenar llamadas para obtener el tiempo del sistema no afectaría el comportamiento observable del progtwig. 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 realmente un comstackdor que analice un progtwig con suficiente comprensión para poder inferir esto con certeza.

No.

A veces, según la regla “como si”, las declaraciones pueden ser reordenadas. Esto no se debe a que sean lógicamente independientes entre sí, sino porque esa independencia permite que ocurra tal reordenamiento sin cambiar la semántica del progtwig.

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

En general, no esperaría ninguna expresión que provoque que una llamada al sistema sea “cuestionada” incluso por un comstackdor que optimice agresivamente. Simplemente no sabe lo suficiente sobre lo que hace la llamada al sistema.