c++ - Benchmarking, reordenamiento de código, volátil.

compiler-optimization volatile

Question

Decido que quiero comparar una función en particular, por lo que escribo ingenuamente un código como este:

#include <ctime>
#include <iostream>

int SlowCalculation(int input) { ... }

int main() {
    std::cout << "Benchmark running..." << std::endl;
    std::clock_t start = std::clock();
    int answer = SlowCalculation(42);
    std::clock_t stop = std::clock();
    double delta = (stop - start) * 1.0 / CLOCKS_PER_SEC;
    std::cout << "Benchmark took " << delta << " seconds, and the answer was "
              << answer << ''.'' << std::endl;
    return 0;
}

Un colega señaló que debería declarar las variables de start y stop como volatile para evitar la reordenación del código. Sugirió que el optimizador podría, por ejemplo, reordenar efectivamente el código de esta manera:

    std::clock_t start = std::clock();
    std::clock_t stop = std::clock();
    int answer = SlowCalculation(42);

Al principio, era escéptico de que se permitiera tal reordenación extrema, pero después de algunas investigaciones y experimentación, supe que así era.

Pero volatile no se sentía como la solución correcta; ¿no es volátil realmente solo para memoria I / O asignada?

Sin embargo, agregué volatile y descubrí que no solo el índice de referencia se demoraba mucho más, sino que también era muy inconsistente de una ejecución a otra. Sin volatilidad (y tener suerte para asegurar que el código no se reordenó), el punto de referencia consistentemente tomó 600-700 ms. Con la volatilidad, a menudo tomaba 1200 ms y, a veces, más de 5000 ms. Los listados de desmontaje para las dos versiones no mostraron virtualmente más diferencia que una selección diferente de registros. Esto me hace preguntarme si hay otra manera de evitar el reordenamiento del código que no tenga efectos secundarios tan abrumadores.

Mi pregunta es:

¿Cuál es la mejor manera de evitar que el código se reordene en un código de referencia como este?

Mi pregunta es similar a esta (que trataba sobre el uso de volatile para evitar la elisión en lugar de reordenar), esta (que no respondió cómo evitar la reordenación), y esta (que debatió si el problema era la reordenación del código o el código muerto). eliminación). Mientras que los tres están en este tema exacto, ninguno responde a mi pregunta.

Actualización : la respuesta parece ser que mi colega se equivocó y que reordenar así no es consistente con el estándar. He subestimado a todos los que lo dijeron y estoy otorgando la recompensa a Maxim.

He visto un caso (basado en el código en esta pregunta ) en el que Visual Studio 2010 reordenó las llamadas del reloj como ilustré (solo en versiones de 64 bits). Estoy tratando de hacer un caso mínimo para ilustrar eso, de modo que pueda presentar un error en Microsoft Connect.

Para aquellos que dijeron que la volatilidad debería ser mucho más lenta porque obliga a las lecturas y escrituras en la memoria, esto no es muy consistente con el código que se está emitiendo. En mi respuesta a esta pregunta , muestro el desmontaje del código con y sin volatilidad. Dentro del bucle, todo se mantiene en registros. Las únicas diferencias significativas parecen ser la selección de registros. No entiendo el ensamblaje x86 lo suficientemente bien como para saber por qué el rendimiento de la versión no volátil es consistentemente rápido, mientras que la versión volátil es inconsistente (y en ocasiones dramáticamente) más lenta.

Answer 1

Un colega señaló que debería declarar las variables de inicio y detención como volátiles para evitar la reordenación del código.

Lo siento, pero su colega está equivocado.

El compilador no reordena las llamadas a funciones cuyas definiciones no están disponibles en tiempo de compilación. Simplemente imagine la hilaridad que se produciría si el compilador reordenara llamadas tales como fork y exec o el código movido alrededor de éstas.

En otras palabras, cualquier función sin definición es una barrera de memoria de tiempo de compilación, es decir, el compilador no mueve las declaraciones posteriores antes de la llamada o las declaraciones anteriores después de la llamada.

En su código, las llamadas a std::clock terminan llamando a una función cuya definición no está disponible.

No puedo recomendar lo suficiente ver armas atómicas: el modelo de memoria C ++ y el hardware moderno, ya que analiza las ideas erróneas acerca de las barreras de la memoria (tiempo de compilación) y la volatile entre otras muchas cosas útiles.

Sin embargo, agregué volatile y descubrí que no solo el índice de referencia se demoraba mucho más, sino que también era muy inconsistente de una ejecución a otra. Sin volatilidad (y tener suerte para asegurar que el código no se reordenó), el punto de referencia consistentemente tomó 600-700 ms. Con la volatilidad, a menudo tomaba 1200 ms y, a veces, más de 5000 ms.

No estoy seguro de si la volatile es la culpable aquí.

El tiempo de ejecución informado depende de cómo se ejecuta el punto de referencia. Asegúrese de deshabilitar la escala de frecuencia de la CPU para que no active el modo turbo o cambie la frecuencia en medio de la ejecución. Además, los micro-puntos de referencia deben ejecutarse como procesos de prioridad en tiempo real para evitar la programación de ruido. Podría ser que, durante otra ejecución, algún indexador de archivos de fondo comience a competir con su punto de referencia por el tiempo de CPU. Vea this para más detalles.

Una buena práctica es medir los tiempos que se tarda en ejecutar la función varias veces e informar los números de tiempo de min / avg / median / max / stdev / total. Una desviación estándar alta puede indicar que las preparaciones anteriores no se realizan. La primera ejecución a menudo es la más larga porque la memoria caché de la CPU puede estar fría y puede tomar muchas fallas de memoria caché y fallos de página y también resolver los símbolos dinámicos de las bibliotecas compartidas en la primera llamada (la resolución perezosa de símbolos es el modo de enlace predeterminado en tiempo de ejecución en Linux , por ejemplo), mientras que las llamadas subsiguientes se ejecutarán con mucho menos sobrecarga.

Answer 2

El reordenamiento descrito por su colega acaba de romper 1.9 / 13

La secuencia anterior es una relación asimétrica, transitiva y por pares entre las evaluaciones ejecutadas por un solo hilo (1.10), que induce un orden parcial entre esas evaluaciones. Dadas las dos evaluaciones A y B, si A está secuenciada antes de B, entonces la ejecución de A deberá preceder a la ejecución de B. Si A no está secuenciada antes de que B y B no estén secuenciadas antes de A, entonces A y B no tienen secuencia. [Nota: La ejecución de evaluaciones no secuenciales puede superponerse. —Descripción final] Las evaluaciones A y B se secuencian de forma indeterminada cuando A se secuencia antes de que B o B se secuencian antes de A, pero no se especifica cual. [Nota: las evaluaciones con secuencias indeterminadas no pueden superponerse, pero cualquiera de las dos podría ejecutarse primero. "Nota final"

Así que, básicamente, no debes pensar en reordenar mientras no uses hilos.

Answer 3

Hay un par de maneras en las que puedo pensar. La idea es crear barreras de tiempo de compilación para que el compilador no reordene un conjunto de instrucciones.

Una posible forma de evitar la reordenación sería imponer la dependencia entre las instrucciones que el compilador no puede resolver (por ejemplo, pasar un puntero a la función y usar ese puntero en una instrucción posterior). No estoy seguro de cómo afectaría eso al rendimiento del código real que está interesado en la evaluación comparativa.

Otra posibilidad es realizar la función SlowCalculation(42); una función extern (defina esta función en un archivo .c / .cpp separado y vincule el archivo a su programa principal) y declare el start y la stop como variables globales. No sé cuáles son las optimizaciones ofrecidas por el optimizador de tiempo de enlace / inter-procedimientos de su compilador.

Además, si compilas en O1 u O0, lo más probable es que el compilador no se moleste en reordenar las instrucciones. Su pregunta está algo relacionada con ( compilación de barreras de tiempo, reordenación del código del compilador, gcc y pthreads )

Answer 4

La forma correcta de hacer esto en C ++ es usar una clase , por ejemplo, algo como

class Timer
{
    std::clock_t startTime;
    std::clock_t* targetTime;

public:
    Timer(std::clock_t* target) : targetTime(target) { startTime = std::clock(); }
    ~Timer() { *target = std::clock() - startTime; }
};

y úsalo así:

std::clock_t slowTime;
{
    Timer timer(&slowTime);
    int answer = SlowCalculation(42);
}

Eso sí, no creo que su compilador se vuelva a ordenar de esta manera.

Answer 5

La forma habitual de evitar el reordenamiento es una barrera de compilación, es decir, asm volatile ("":::"memory"); (con gcc). Esta es una instrucción asm que no hace nada, pero le decimos al compilador que pegará memoria, por lo que no está permitido reordenar el código. El costo de esto es solo el costo real de eliminar el pedido, que obviamente no es el caso para cambiar el nivel de optimización, etc., como se sugiere en otros lugares.

Creo que _ReadWriteBarrier es equivalente para las cosas de Microsoft.

Sin embargo, según la respuesta de Maxim Yegorushkin, es poco probable que la reordenación sea la causa de sus problemas.

Answer 6

La volatilidad garantiza una cosa, y una sola cosa: las lecturas de una variable volátil se leerán de la memoria cada vez que el compilador no asumirá que el valor se puede almacenar en caché en un registro. Y así mismo, las escrituras serán escritas a través de la memoria. El compilador no lo guardará en un registro "por un tiempo, antes de escribirlo en la memoria".

Para evitar que se vuelva a ordenar el compilador, puede utilizar las denominadas cercas de compilación. MSVC incluye 3 cercas de compilación:

_ReadWriteBarrier () - cerca completa

_ReadBarrier () - cerca de dos lados para cargas

_WriteBarrier () - cerca de dos caras para tiendas

ICC incluye __memory_barrier () cerca completa.

Las cercas completas son generalmente la mejor opción porque no hay necesidad de una granularidad más fina en este nivel (las cercas del compilador son básicamente sin costo en tiempo de ejecución).

La reordenación de declaraciones (lo que la mayoría de los compiladores hace cuando la optimización está habilitada), esa es la razón principal por la que ciertos programas no funcionan correctamente cuando se compilan con la optimización del compilador.

Le sugeriré que lea http://preshing.com/20120625/memory-ordering-at-compile-time para ver los problemas potenciales que podemos enfrentar al reordenar el compilador, etc.

Answer 7

Podría hacer dos archivos C, SlowCalculation compilado con g++ -O3 (alto nivel de optimización), y el de referencia compilado con g++ -O1 (nivel inferior, todavía optimizado, que puede ser suficiente para esa parte del benchmarking).

De acuerdo con la página de manual , la reordenación del código ocurre durante los niveles de optimización de -O2 y -O2 .

Dado que la optimización se produce durante la compilación, no en el enlace, el lado del punto de referencia no debe verse afectado por la reordenación del código.

Suponiendo que está utilizando g++ , pero debería haber algo equivalente en otro compilador.

Answer 8

Problema relacionado: cómo evitar que el compilador levante un pequeño cálculo repetido fuera de un bucle

No pude encontrar esto en ninguna parte, por lo que agregué mi propia respuesta 11 años después de que se formuló la pregunta;).

Usar volatile en variables no es lo que quieres para eso. Eso hará que el compilador cargue y almacene esas variables desde y hacia la RAM cada vez (asumiendo que hay un efecto secundario de eso que debe conservarse: también conocido como bueno para los registros de E / S). Cuando está marcando en el banco, no está interesado en medir cuánto tiempo se tarda en obtener algo de la memoria, o escribirlo allí. A menudo solo quieres que tu variable esté en los registros de la CPU.

volatile se puede usar si se le asigna una vez fuera de un bucle que no se optimiza (como sumar una matriz), como alternativa a la impresión del resultado. (Al igual que la función de larga duración en la pregunta). Pero no dentro de un pequeño bucle; eso introducirá las instrucciones de almacenamiento / recarga y la latencia de envío de la tienda.

Creo que la ÚNICA manera de enviar su compilador para que no optimice su código de referencia al infierno es mediante el uso de asm . Esto le permite engañar al compilador para que piense que no sabe nada sobre el contenido o el uso de sus variables, por lo que tiene que hacer todo cada vez, con la frecuencia que el bucle lo solicite.

Por ejemplo, si quisiera comparar m & -m donde m es algo uint64_t , podría intentar:

uint64_t const m = 0x0000080e70100000UL;
for (int i = 0; i < loopsize; ++i)
{
  uint64_t result = m & -m;
}

El compilador obviamente diría: ni siquiera voy a calcular eso; ya que no estás usando el resultado. Aka, en realidad haría:

for (int i = 0; i < loopsize; ++i)
{
}

Entonces puedes probar:

uint64_t const m = 0x0000080e70100000UL;
static uint64_t volatile result;
for (int i = 0; i < loopsize; ++i)
{
  result = m & -m;
}

y el compilador dice: ok, así que quieres que escriba el resultado cada vez y lo haga

uint64_t const m = 0x0000080e70100000UL;
uint64_t tmp = m & -m;
static uint64_t volatile result;
for (int i = 0; i < loopsize; ++i)
{
  result = tmp;
}

Dedicar mucho tiempo a escribir en la dirección de memoria de los tiempos de loopsize de result , tal como lo solicitó.

Finalmente, también podría hacer que m volátil, pero el resultado se vería así en el ensamblaje:

507b:   ba e8 03 00 00          mov    $0x3e8,%edx
  # top of loop
5080:   48 8b 05 89 ef 20 00    mov    0x20ef89(%rip),%rax        # 214010 <m_test>
5087:   48 8b 0d 82 ef 20 00    mov    0x20ef82(%rip),%rcx        # 214010 <m_test>
508e:   48 f7 d8                neg    %rax
5091:   48 21 c8                and    %rcx,%rax
5094:   48 89 44 24 28          mov    %rax,0x28(%rsp)
5099:   83 ea 01                sub    $0x1,%edx
509c:   75 e2                   jne    5080 <main+0x120>

Leer de memoria dos veces y escribir en ella una vez, además del cálculo solicitado con registros.

La forma correcta de hacer esto es por lo tanto :

for (int i = 0; i < loopsize; ++i)
{
  uint64_t result = m & -m;
  asm volatile ("" : "+r" (m) : "r" (result));
}

que da como resultado el código de ensamblaje ( de gcc8.2 en el explorador del compilador de Godbolt ):

 # gcc8.2 -O3 -fverbose-asm
    movabsq $8858102661120, %rax      #, m
    movl    $1000, %ecx     #, ivtmp_9     # induction variable tmp_9
.L2:
    mov     %rax, %rdx      # m, tmp91
    neg     %rdx            # tmp91
    and     %rax, %rdx      # m, result
       # asm statement here,  m=%rax   result=%rdx
    subl    $1, %ecx        #, ivtmp_9
    jne     .L2
    ret     

Haciendo exactamente las tres instrucciones de ensamblaje solicitadas dentro del bucle, más un sub y un jne para la sobrecarga del bucle.

El truco aquí es que al usar el asm volatile ¹ y decirle al compilador

1. "r" entrada "r" : utiliza el valor del result como entrada para que el compilador tenga que materializarlo en un registro.
2. "+r" entrada / salida "+r" : m permanece en el mismo registro pero se modifica (potencialmente).
3. volatile : tiene algún efecto secundario misterioso y / o no es una función pura de las entradas; el compilador debe ejecutarlo tantas veces como lo haga la fuente. Esto obliga al compilador a dejar el fragmento de prueba solo y dentro del bucle. Consulte la sección Volatile Extended Asm # del manual de gcc .

nota al pie 1: aquí se requiere la volatile o el compilador la convertirá en un bucle vacío. Asm no volátil (con cualquier operando de salida) se considera una función pura de sus entradas que se puede optimizar si el resultado no se utiliza. O CSEd solo se ejecuta una vez si se usa varias veces con la misma entrada.

Todo lo que está abajo no es mío, y no necesariamente estoy de acuerdo con eso. --Carlo Wood

Si ha utilizado asm volatile ("" : "=r" (m) : "r" (result)); ( con una salida de solo escritura "=r" ), el compilador puede elegir el mismo registro para m y el result , creando una cadena de dependencia que se realiza en un bucle que comprueba la latencia, no el rendimiento, del cálculo.

De eso, obtendrías este asm:

5077:   ba e8 03 00 00          mov    $0x3e8,%edx
507c:   0f 1f 40 00             nopl   0x0(%rax)    # alignment padding
  # top of loop
5080:   48 89 e8                mov    %rbp,%rax    # copy m
5083:   48 f7 d8                neg    %rax         # -m
5086:   48 21 c5                and    %rax,%rbp    # m &= -m   instead of using the tmp as the destination.
5089:   83 ea 01                sub    $0x1,%edx
508c:   75 f2                   jne    5080 <main+0x120>

Esto se ejecutará a 1 iteración por 2 o 3 ciclos (dependiendo de si su CPU tiene eliminación de movimientos o no). La versión sin una dependencia de bucle se puede ejecutar a 1 por ciclo de reloj en Haswell y posteriores, y en Ryzen. Esas CPU tienen el rendimiento ALU para ejecutar al menos 4 uops por ciclo de reloj.

Este asm corresponde a C ++ que se ve así:

for (int i = 0; i < loopsize; ++i)
{
  m = m & -m;
}

Al inducir a error al compilador con una restricción de salida de solo escritura, hemos creado asm que no se parece a la fuente (que parecía que estaba calculando un nuevo resultado de una constante en cada iteración, sin usar el resultado como una entrada para la siguiente iteración..)

Es posible que desee hacer un microenlace de latencia, de modo que pueda detectar más fácilmente el beneficio de compilar con -mbmi o -march=haswell para permitir que el compilador use blsi %rax, %rax y calcule m &= -m; en una sola instrucción. Pero es más fácil hacer un seguimiento de lo que está haciendo si la fuente de C ++ tiene la misma dependencia que el asm, en lugar de engañar al compilador para que introduzca una nueva dependencia.