online - Hacer cumplir el orden de las instrucciones en C++

operator precedence java

Question

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 cierto 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 declaraciones 1-3 se ejecuten en el orden dado. 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;

Answer 1

El compilador o el procesador pueden reordenar.

La mayoría de los compiladores ofrecen un método específico de plataforma para evitar la reordenación 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 en el que la llamada al sistema en 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 se evalúe durante el tiempo de compilación. Para imponer la ejecución "realista", es posible que deba derivar la entrada para foo() de E / S o una lectura volatile .

Otra opción sería deshabilitar la alineació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: ¿qué tan realista es esta medición?

El tiempo de ejecución se ve afectado por muchos factores: uno es el hardware real en el que estamos funcionando, 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 "caché en caliente" frente a "caché en frío" puede diferir fácilmente en un orden de magnitud, pero en realidad, será algo intermedio (¿"tibio"?)

Answer 2

El lenguaje C ++ define lo que es observable 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 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 al mover las llamadas Clock::now() .

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

Si bien puede usar hacks 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.

Crea una biblioteca cargada dinámicamente. Cárguelo antes del 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 nulary 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);
}

Lo cual es bastante simple.

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

Todavía puede eliminar foo() s con cero efectos secundarios, pero gana algunos, pierde algunos.

Answer 3

Me gustaría tratar de proporcionar una respuesta algo más completa después de que esto se haya discutido 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 así como una suma entera es totalmente conocida por la implementación. Puede simularlos, sabe que no pueden ser observados por los programas correctos y siempre es libre de moverlos.

Podríamos intentar evitar 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 impediría la abrumadora 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, ¿la conversión de un entero sin signo de 32 bits en un entero sin signo de 64 bits lleva tiempo? Lleva tiempo cero en x86-64, pero en otras arquitecturas toma tiempo distinto de cero. No hay una respuesta genéricamente correcta aquí.

Pero incluso si tenemos éxito a través de algunos heroicos en evitar 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 de máquina del programa. Una cosa que puede hacer es optimizaciones en línea, e incluso es capaz de ejecutar especulativamente todo el rango 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 es observable (incluso en el 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. Forzarlo a ser observable restringiría drásticamente el compilador, pero también restringiría drásticamente el hardware.

Pero todo esto no debería hacerte perder 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, 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 proporcionadas 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. Hace que la entrada al cálculo sea opaca para el optimizador y el resultado del cálculo sea opaco para el optimizador. Una vez que haya hecho eso, puede cronometrarlo de manera confiable. Veamos una versión realista del ejemplo en la pregunta original, pero con la definición de foo totalmente visible para la implementación. También he extraído una 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 <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, y solo alrededor de esos marcadores se calculan los tiempos. Debido a que está utilizando datos para pinzar el cálculo, se garantiza que se mantendrá entre los dos tiempos y, sin embargo, el cálculo en sí mismo puede optimizarse. 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 el compilador 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á estudiando la posibilidad de estandarizar API similares a DoNotOptimize aquí.

Answer 4

No, no puede. De acuerdo con 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 por un punto y coma. Como puede ver, la regla anterior estipula que las declaraciones deben ejecutarse en orden. Es dentro de las declaraciones que al compilador se le permite más rienda suelta (es decir, bajo ciertas circunstancias se le permite evaluar expresiones que componen una declaración en órdenes distintas a las 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 as-if. No es razonable pensar que cualquier compilador podría probar 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.

Answer 5

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 dicho reordenamiento sin cambiar la semántica del programa.

Mover una llamada del sistema que obtiene la hora actual obviamente no satisface esa condición. Un compilador que a sabiendas o sin saberlo no cumple 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 agresivamente optimizador. Simplemente no sabe lo suficiente sobre lo que hace esa llamada al sistema.

Answer 6

Resumen:

Parece que no hay una forma garantizada de evitar la reordenación, pero mientras la optimización del tiempo de enlace / programa completo no esté habilitada, 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 para reordenar.

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

CCG 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 <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

Answer 7

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

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

De esta manera, estoy bastante seguro de que la reordenación no puede suceder, ya que la noinline "vincula" el ::now y 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__("" : "+m"(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 = 10000;
}
// 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 "
<< std::chrono::duration_cast<std::chrono::nanoseconds>(t2 - t1).count()
<< std::endl;
}

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 instrucción callq adicional sobre un método en inline . objdump -CD muestra que main contiene:

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

así que vemos que foo estaba en línea, pero get_clock no lo estaba y lo rodeaba.

get_clock embargo, get_clock 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 limitada, creo que es poco probable que pueda notar los efectos de sincronización de un jmpq adicional. Tenga en cuenta que se requiere una call independientemente de que ::now() esté en una biblioteca compartida.

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

Esta sería la solución más eficiente posible, superando incluso el jmpq adicional mencionado 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 de tiempo se puede hacer directamente en el ensamblaje en línea sin una llamada, entonces esta técnica se puede utilizar. Este es el caso, por ejemplo, de las instrucciones de instrumentación mágica de gem5 , x86 RDTSC (no estoy seguro si esto ya es representativo) y posiblemente otros contadores de rendimiento.

Probado con GCC 8.3.0, Ubuntu 19.04.