sentencia - ¿Por qué los optimizadores de C++ tienen problemas con estas variables temporales o, más bien, por qué ''v[]'' debería evitarse en bucles cerrados?

sentencia if en c (4)

Aquí hay información adicional para ampliar la respuesta de @deniss, que diagnosticó correctamente el problema.

Por cierto, esto está relacionado con las preguntas y respuestas más populares de C ++ de todos los tiempos "¿Por qué se procesa una matriz ordenada más rápido que una matriz sin clasificar?" .

El problema principal es que el compilador debe respetar el operador lógico AND (&&) y no cargar desde v [i + 1] a menos que la primera condición sea verdadera. Esto es una consecuencia de la semántica del operador lógico AND, así como de la semántica del modelo de memoria reforzada introducida con C ++ 11, las cláusulas relevantes en el borrador del estándar son

5.14 Operador lógico AND [expr.log.and]

A diferencia de & , && garantiza la evaluación de izquierda a derecha: el segundo operando no se evalúa si el primer operando es falso .
_{Norma ISO C ++ 14 (borrador N3797)}

y para lecturas especulativas

1.10 Ejecuciones multiproceso y carreras de datos [intro.multithread]

23 [ Nota: las transformaciones que introducen una lectura especulativa de una ubicación de memoria potencialmente compartida pueden no preservar la semántica del programa C ++ como se define en este estándar, ya que potencialmente introducen una carrera de datos. Sin embargo, generalmente son válidos en el contexto de un compilador de optimización que se dirige a una máquina específica con una semántica bien definida para carreras de datos. Serían inválidos para una máquina hipotética que no tolera las carreras o proporciona detección de carrera por hardware. - nota final ]
_{Norma ISO C ++ 14 (borrador N3797)}

Supongo que los optimizadores juegan con seguridad y actualmente eligen no emitir cargas especulativas a la memoria potencialmente compartida en lugar de un caso especial para cada procesador objetivo si la carga especulativa podría introducir una carrera de datos detectable para ese objetivo.

Para implementar esto, el compilador genera una rama condicional. Por lo general, esto no se nota porque los procesadores modernos tienen una predicción de rama muy sofisticada, y la tasa de predicción errónea suele ser muy baja. Sin embargo, los datos aquí son aleatorios: esto mata la predicción de rama. El costo de una predicción errónea es de 10 a 20 ciclos de CPU, teniendo en cuenta que la CPU generalmente retira 2 instrucciones por ciclo, esto equivale a 20 a 40 instrucciones. Si la tasa de predicción es del 50% (aleatoria), cada iteración tiene una penalización errónea equivalente a 10 a 20 instrucciones: ENORME .

Nota: El compilador podría probar que los elementos v[0] a v[v.size()-2] serán referenciados, en ese orden, independientemente de los valores que contengan. Esto permitiría al compilador en este caso generar código que cargue incondicionalmente todo excepto el último elemento del vector. El último elemento del vector, en v [v.size () - 1], solo se puede cargar en la última iteración del bucle y solo si la primera condición es verdadera. Por lo tanto, el compilador podría generar código para el bucle sin la ramificación de cortocircuito hasta la última iteración, luego usar un código diferente con la ramificación de cortocircuito para la última iteración; eso requeriría que el compilador supiera que los datos son aleatorios y la predicción de ramificación es inútil y por lo tanto, vale la pena molestarse con eso (los compiladores no son tan sofisticados) todavía.

Para evitar la rama condicional generada por el AND lógico (&&) y evitar cargar las ubicaciones de la memoria en variables locales, podemos cambiar el operador AND lógico en un fragmento de código AND bit a bit aquí , el resultado es casi 4 veces más rápido cuando los datos son aleatorios

int f2() { int n = 0; for (int i = 1; i < v.size()-1; ++i) n += (v[i-1] < v[i]) & (v[i] < v[i+1]); // Bitwise AND return n; }

Salida

3.642443ms min 3.779982ms median Result: 166634 3.725968ms min 3.870808ms median Result: 166634 1.052786ms min 1.081085ms median Result: 166634 done

El resultado en gcc 5.3 es 8 veces más rápido ( vive en Coliru aquí )

g++ --version g++ -std=c++14 -O3 -Wall -Wextra -pedantic -pthread -pedantic-errors main.cpp -lm && ./a.out g++ (GCC) 5.3.0 Copyright (C) 2015 Free Software Foundation, Inc. This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 3.761290ms min 4.025739ms median Result: 166634 3.823133ms min 4.050742ms median Result: 166634 0.459393ms min 0.505011ms median Result: 166634 done

Quizás se pregunte cómo el compilador puede evaluar la comparación v[i-1] < v[i] sin generar una rama condicional. La respuesta depende del objetivo, para x86 esto es posible debido a la instrucción SETcc , que genera un resultado de un byte, 0 o 1, dependiendo de una condición en el registro EFLAGS, la misma condición que podría usarse en una rama condicional, pero sin ramificaciones En el código generado por @deniss puede ver setl generado, que establece el resultado en 1 si se cumple la condición "menor que", que se evalúa mediante la instrucción de comparación anterior:

cmp edx, edi ; a < b ? setl r10b ; r10b = a < b ? 1 : 0 mov ecx, dword ptr [r8 + 4*rsi + 4] ; c = v[i+1] lea rsi, [rsi + 1] ; ++i cmp edi, ecx ; b < c ? setl dl ; dl = b < c ? 1 : 0 and dl, r10b ; dl &= r10b movzx edx, dl ; edx = zero extended dl add eax, edx ; n += edx

En este fragmento de código , comparo el rendimiento de dos bucles funcionalmente idénticos:

for (int i = 1; i < v.size()-1; ++i) { int a = v[i-1]; int b = v[i]; int c = v[i+1]; if (a < b && b < c) ++n; }

for (int i = 1; i < v.size()-1; ++i) if (v[i-1] < v[i] && v[i] < v[i+1]) ++n;

El primero se ejecuta significativamente más lento que el segundo en varios compiladores de C ++ diferentes con el indicador de optimización establecido en O2 :

el segundo ciclo es aproximadamente un 330% más lento ahora con Clang 3.7.0
el segundo ciclo es aproximadamente un 2% más lento con gcc 4.9.3
el segundo ciclo es aproximadamente un 2% más lento con Visual C ++ 2015

Me sorprende que los optimizadores modernos de C ++ tengan problemas para manejar este caso. ¿Alguna pista de por qué? ¿Tengo que escribir código feo sin usar variables temporales para obtener el mejor rendimiento?

El uso de variables temporales hace que el código sea más rápido, a veces dramáticamente, ahora. Que esta pasando?

El código completo que estoy usando se proporciona a continuación:

#include <algorithm> #include <chrono> #include <random> #include <iomanip> #include <iostream> #include <vector> using namespace std; using namespace std::chrono; vector<int> v(1''000''000); int f0() { int n = 0; for (int i = 1; i < v.size()-1; ++i) { int a = v[i-1]; int b = v[i]; int c = v[i+1]; if (a < b && b < c) ++n; } return n; } int f1() { int n = 0; for (int i = 1; i < v.size()-1; ++i) if (v[i-1] < v[i] && v[i] < v[i+1]) ++n; return n; } int main() { auto benchmark = [](int (*f)()) { const int N = 100; volatile long long result = 0; vector<long long> timings(N); for (int i = 0; i < N; ++i) { auto t0 = high_resolution_clock::now(); result += f(); auto t1 = high_resolution_clock::now(); timings[i] = duration_cast<nanoseconds>(t1-t0).count(); } sort(timings.begin(), timings.end()); cout << fixed << setprecision(6) << timings.front()/1''000''000.0 << "ms min/n"; cout << timings[timings.size()/2]/1''000''000.0 << "ms median/n" << "Result: " << result/N << "/n/n"; }; mt19937 generator (31415); // deterministic seed uniform_int_distribution<> distribution(0, 1023); for (auto& e: v) e = distribution(generator); benchmark(f0); benchmark(f1); cout << "/ndone/n"; return 0; }

Ninguna de las respuestas hasta ahora ha dado una versión de f() que gcc o clang puedan optimizar por completo. Todos generan asm que compara ambas iteraciones. Vea el código con salida asm en Godbolt Compiler Explorer . (Conocimientos previos importantes para predecir el rendimiento a partir de la salida asm: la guía de microarquitectura de Agner Fog y otros enlaces en el wiki de etiquetas x86 . Como siempre, generalmente funciona mejor perfilar con contadores de rendimiento para encontrar puestos).

v[i-1] < v[i] es un trabajo que ya hicimos la última iteración, cuando evaluamos v[i] < v[i+1] . En teoría, ayudar al compilador a asimilarlo que le permitiría optimizar mejor (ver f3() ). En la práctica, eso termina derrotando la auto-vectorización en algunos casos, y gcc emite código con paradas de registro parcial, incluso con -mtune=core2 donde ese es un gran problema.

v.size() - 1 manualmente el v.size() - 1 fuera de la verificación del límite superior del bucle parece ayudar. Los OP f0 y f1 realidad no vuelven a calcular v.size() desde los punteros de inicio / finalización en v , pero de alguna manera aún se optimiza menos que cuando se calcula un size_t upper = v.size() - 1 fuera del bucle ( f2() y f4() ).

Otro problema es que el uso de un contador de bucle int con un límite superior size_t significa que el bucle es potencialmente infinito. No estoy seguro de cuánto impacto tiene esto en otras optimizaciones.

En pocas palabras: los compiladores son bestias complejas . Predecir qué versión se optimizará bien no es nada obvio o directo.

Resultados en 64 bits Ubuntu 15.10, en Core2 E6600 (microarquitectura Merom / Conroe).

Los resultados serían diferentes en el hardware de la familia Intel SnB, especialmente. IvyBridge y más tarde, donde no habría ralentizaciones parciales del registro. Core2 está limitado por cargas lentas no alineadas y solo una carga por ciclo. Sin embargo, los bucles pueden ser lo suficientemente pequeños como para que la decodificación no sea un problema.

f0 y f1 :

gcc 5.2: Los f0 y f1 del OP forman bucles ramificados y no se vectorizan automáticamente. f0 solo usa una rama, sin embargo, y usa un setl sil / cmp sil, 1 extraño cmp sil, 1 / sbb eax, -1 para hacer la segunda mitad de la comparación de cortocircuito. Por lo tanto, sigue haciendo ambas comparaciones en cada iteración.

clang 3.8: f0 : solo una carga por iteración, pero las compara and las combina juntas. f1 : ambos comparan cada iteración, una con una rama para preservar la semántica en C. Dos cargas por iteración.

int f2() { int n = 0; size_t upper = v.size()-1; // difference from f0: hoist upper bound and use size_t loop counter for (size_t i = 1; i < upper; ++i) { int a = v[i-1], b = v[i], c = v[i+1]; if (a < b && b < c) ++n; } return n; }

gcc 5.2 -O3 : auto-vectoriza, con tres cargas para obtener los tres vectores de desplazamiento necesarios para producir un vector de 4 resultados de comparación. Además, después de combinar los resultados de dos instrucciones pcmpgtd , los compara con un vector de todo cero y luego enmascara eso. Zero ya es el elemento de identidad para la suma, por lo que es realmente tonto.

clang 3.8 -O3 : desenrolla: cada iteración realiza dos cargas, tres cmp / setcc, dos ys, y dos add s.

int f4() { int n = 0; size_t upper = v.size()-1; for (size_t i = 1; i < upper; ++i) { int a = v[i-1], b = v[i], c = v[i+1]; bool ab_lt = a < b; bool bc_lt = b < c; n += (ab_lt & bc_lt); // some really minor code-gen differences from f2: auto-vectorizes to better code that runs slightly faster even for this large problem size } return n; }

gcc 5.2 -O3 : se autovectoriza como f2 , pero sin el pcmpeqd adicional.
gcc 5.2 -O2 : no investigó por qué esto es dos veces más rápido que f2 .
clang -O3 : aproximadamente el mismo código que f2 .

Intento de agarre manual del compilador

int f3() { int n = 0; int a = v[0], b = v[1]; // These happen before checking v.size, defeating the loop vectorizer or something bool ab_lt = a < b; size_t upper = v.size()-1; for (size_t i = 1; i < upper; ++i) { int c = v[i+1]; // only one load and compare inside the loop bool bc_lt = b < c; n += (ab_lt & bc_lt); ab_lt = bc_lt; a = b; // unused inside the loop, only the compare result is needed b = c; } return n; }

clang 3.8 -O3: se desenrolla con 4 cargas dentro del bucle (al clang generalmente le gusta desenrollar en 4 cuando no hay dependencias complejas transportadas por el bucle).
4 cmp / setcc, 4x y / movzx, 4x add. Así que el sonido metálico hizo exactamente lo que esperaba, e hizo un código escalar casi óptimo. Esta era la versión no vectorizada más rápida , y (en core2 donde las cargas no alineadas movups son lentas) es tan rápida como las versiones vectorizadas de gcc.
gcc 5.2 -O3 : no se auto-vectoriza. Mi teoría sobre eso es que acceder a la matriz fuera del ciclo confunde el vectorizador automático. Tal vez porque lo hacemos antes de verificar v.size() , o tal vez solo en general.

Compila el código escalar que esperamos, con una carga, un cmp / setcc y uno and por iteración. Pero gcc crea un bloqueo de registro parcial , incluso con -mtune=core2 donde es un gran problema (bloqueo de 2 a 3 ciclos para insertar un UOP de fusión al leer un registro amplio después de escribir solo una parte). ( setcc solo está disponible con un tamaño de operando de 8 bits, IMO es algo que AMD debería haber cambiado cuando diseñaron el AMD64 ISA). Es la razón principal por la cual el código de gcc se ejecuta 2.5 veces más lento que el de clang.

## the loop in f3(), from gcc 5.2 -O3 (same code with -O2) .L31: add rcx, 1 # i, mov edi, DWORD PTR [r10+rcx*4] # a, MEM[base: _19, index: i_13, step: 4, offset: 0] cmp edi, r8d # a, a # gcc''s verbose-asm comments are a bit bogus here: one of these `a`s is from the last iteration, so this is really comparing c, b mov r8d, edi # a, a setg sil #, tmp124 and edx, esi # D.111089, tmp124 # PARTIAL-REG STALL: reading esi after writing sil movzx edx, dl # using movzx to widen sil to esi would have solved the problem, instead of doing it after the and add eax, edx # n, D.111085 # n += ... cmp r9, rcx # upper, i mov edx, esi # ab_lt, tmp124 jne .L31 #, ret

Parece que el compilador carece de conocimiento sobre la relación entre std::vector<>::size() y el tamaño interno del búfer de vectores. Considere std::vector como nuestro objeto personalizado bugged_vector vector bugged_vector con un ligero error: su ::size() veces puede ser uno más que el tamaño interno del búfer n , pero solo entonces v[n-2] >= v[n-1]

Luego, dos fragmentos tienen una semántica diferente nuevamente: el primero tiene un comportamiento indefinido, ya que accedemos al elemento v[v.size() - 1] . Sin embargo, el segundo no tiene: debido a la naturaleza de cortocircuito de && , nunca leemos v[v.size() - 1] en la última iteración.

Entonces, si el compilador no puede probar que nuestra v no es un bugged_vector , debe hacer un cortocircuito, lo que introduce un salto adicional en un código de máquina.

Al observar la salida de ensamblaje de clang , podemos ver que realmente sucede.

Desde Godbolt Compiler Explorer , con clang 3.7.0 -O2, el bucle en f0 es:

### f0: just the loop .LBB1_2: # =>This Inner Loop Header: Depth=1 mov edi, ecx cmp edx, edi setl r10b mov ecx, dword ptr [r8 + 4*rsi + 4] lea rsi, [rsi + 1] cmp edi, ecx setl dl and dl, r10b movzx edx, dl add eax, edx cmp rsi, r9 mov edx, edi jb .LBB1_2

Y para f1 :

### f1: just the loop .LBB2_2: # =>This Inner Loop Header: Depth=1 mov esi, r10d mov r10d, dword ptr [r9 + 4*rdi] lea rcx, [rdi + 1] cmp esi, r10d jge .LBB2_4 # <== This is Extra Jump cmp r10d, dword ptr [r9 + 4*rdi + 4] setl dl movzx edx, dl add eax, edx .LBB2_4: # %._crit_edge.3 cmp rcx, r8 mov rdi, rcx jb .LBB2_2

He señalado el salto extra en f1 . Y como sabemos (con suerte), los saltos condicionales en un circuito cerrado son malos para el rendimiento. (Consulte las guías de rendimiento en el wiki de etiquetas x86 para obtener más detalles).

~~GCC y Visual Studio son conscientes de que std::vector se comporta bien y produce un ensamblaje casi idéntico para ambos fragmentos.~~ Editar Resulta que el clang hace un mejor trabajo optimizando el código. Los tres compiladores no pueden probar que es seguro leer v[i + 1] antes de la comparación en el segundo ejemplo (o elegir no hacerlo), pero solo clang logra optimizar el primer ejemplo con la información adicional que lee v[i + 1] es válido o UB.

Una diferencia de rendimiento del 2% es insignificante puede explicarse por un orden diferente o la elección de algunas instrucciones.

f0 y f1 son semánticamente diferentes.

x() && y() implica un cortocircuito en el caso de que x () sea falso como sabemos. Esto significa que si x () es falso, entonces y () no debe evaluarse.

Esto evita la captación previa de los datos para evaluar y () y (al menos en el sonido de claxon) está provocando la inserción de un salto condicional, lo que resulta en errores de predicción de rama.

Agregar otras 2 pruebas prueba el punto.

#include <algorithm> #include <chrono> #include <random> #include <iomanip> #include <iostream> #include <vector> using namespace std; using namespace std::chrono; vector<int> v(1''000''000); int f0() { int n = 0; for (int i = 1; i < v.size()-1; ++i) { int a = v[i-1]; int b = v[i]; int c = v[i+1]; if (a < b && b < c) ++n; } return n; } int f1() { int n = 0; auto s = v.size() - 1; for (size_t i = 1; i < s; ++i) if (v[i-1] < v[i] && v[i] < v[i+1]) ++n; return n; } int f2() { int n = 0; auto s = v.size() - 1; for (size_t i = 1; i < s; ++i) { auto t1 = v[i-1] < v[i]; auto t2 = v[i] < v[i+1]; if (t1 && t2) ++n; } return n; } int f3() { int n = 0; auto s = v.size() - 1; for (size_t i = 1; i < s; ++i) { n += 1 * (v[i-1] < v[i]) * (v[i] < v[i+1]); } return n; } int main() { auto benchmark = [](int (*f)()) { const int N = 100; volatile long long result = 0; vector<long long> timings(N); for (int i = 0; i < N; ++i) { auto t0 = high_resolution_clock::now(); result += f(); auto t1 = high_resolution_clock::now(); timings[i] = duration_cast<nanoseconds>(t1-t0).count(); } sort(timings.begin(), timings.end()); cout << fixed << setprecision(6) << timings.front()/1''000''000.0 << "ms min/n"; cout << timings[timings.size()/2]/1''000''000.0 << "ms median/n" << "Result: " << result/N << "/n/n"; }; mt19937 generator (31415); // deterministic seed uniform_int_distribution<> distribution(0, 1023); for (auto& e: v) e = distribution(generator); benchmark(f0); benchmark(f1); benchmark(f2); benchmark(f3); cout << "/ndone/n"; return 0; }

resultados (sonido de manzana, -O2):

1.233948ms min 1.320545ms median Result: 166850 3.366751ms min 3.493069ms median Result: 166850 1.261948ms min 1.361748ms median Result: 166850 1.251434ms min 1.353653ms median Result: 166850