tipos - ¿Por qué esta función de C++ produce tantas fallas de predicción de ramas?
ejemplo de variable local en c++ (5)
Aquí están mis pensamientos sobre esto después de mirarlo por un tiempo. En primer lugar, el problema es fácilmente reproducible con -O2 , por lo que es mejor utilizarlo como referencia, ya que genera un código simple no desenrollado que es fácil de analizar. El problema con -O3 es esencialmente el mismo, es un poco menos obvio.
Entonces, para el primer caso (medio ceros con un patrón de medio uno) el compilador genera este código:
0000000000400a80 <_Z5test1i>:
400a80: 55 push %rbp
400a81: 53 push %rbx
400a82: 89 fb mov %edi,%ebx
400a84: 48 83 ec 08 sub $0x8,%rsp
400a88: 3b 3d 0e 07 20 00 cmp 0x20070e(%rip),%edi #
60119c <half>
400a8e: 74 4f je 400adf <_Z5test1i+0x5f>
400a90: 48 8b 15 09 07 20 00 mov 0x200709(%rip),%rdx #
6011a0 <A>
400a97: 48 63 c7 movslq %edi,%rax
400a9a: 48 8d 2c 85 00 00 00 lea 0x0(,%rax,4),%rbp
400aa1: 00
400aa2: 83 3c 82 01 cmpl $0x1,(%rdx,%rax,4)
400aa6: 74 37 je 400adf <_Z5test1i+0x5f>
400aa8: 8d 7f 01 lea 0x1(%rdi),%edi
400aab: e8 d0 ff ff ff callq 400a80 <_Z5test1i>
400ab0: 89 df mov %ebx,%edi
400ab2: f7 d7 not %edi
400ab4: 03 3d ee 06 20 00 add 0x2006ee(%rip),%edi #
6011a8 <size>
400aba: e8 c1 ff ff ff callq 400a80 <_Z5test1i>
400abf: 8b 05 e3 06 20 00 mov 0x2006e3(%rip),%eax #
6011a8 <size>
400ac5: 48 8b 15 d4 06 20 00 mov 0x2006d4(%rip),%rdx #
6011a0 <A>
400acc: 29 d8 sub %ebx,%eax
400ace: 48 63 c8 movslq %eax,%rcx
400ad1: 8b 44 2a 04 mov 0x4(%rdx,%rbp,1),%eax
400ad5: 03 44 8a fc add -0x4(%rdx,%rcx,4),%eax
400ad9: 01 05 b9 06 20 00 add %eax,0x2006b9(%rip) #
601198 <s>
400adf: 48 83 c4 08 add $0x8,%rsp
400ae3: 5b pop %rbx
400ae4: 5d pop %rbp
400ae5: c3 retq
400ae6: 66 2e 0f 1f 84 00 00 nopw %cs:0x0(%rax,%rax,1)
400aed: 00 00 00
Muy simple, tipo de lo que cabría esperar: dos ramas condicionales, dos llamadas. Nos proporciona esta (o similar) estadística sobre Core 2 Duo T6570, AMD Phenom II X4 925 y Core i7-4770:
$ perf stat -B -e branches,branch-misses ./a.out 111111
5555500
Performance counter stats for ''./a.out 111111'':
45,216,754 branches
5,588,484 branch-misses # 12.36% of all branches
0.098535791 seconds time elapsed
Si quiere hacer este cambio, mueva la tarea antes de las llamadas recursivas:
--- file.cpp.orig 2016-09-22 22:59:20.744678438 +0300
+++ file.cpp 2016-09-22 22:59:36.492583925 +0300
@@ -15,10 +15,10 @@
if(curIndex == half) return;
if(A[curIndex] == 1) return;
+ s += A[curIndex+1] + A[size-curIndex-1];
test1(curIndex+1);
test1(size - curIndex - 1);
- s += A[curIndex+1] + A[size-curIndex-1];
}
La imagen cambia:
$ perf stat -B -e branches,branch-misses ./a.out 111111
5555500
Performance counter stats for ''./a.out 111111'':
39,495,804 branches
54,430 branch-misses # 0.14% of all branches
0.039522259 seconds time elapsed
Y sí, como ya se señaló, está directamente relacionado con la optimización de la recursividad de cola, porque si compila el código parcheado con -fno-optimize-sibling-calls obtendrá los mismos resultados "malos". Entonces, veamos qué tenemos en ensamble con la optimización de la cola de llamadas:
0000000000400a80 <_Z5test1i>:
400a80: 3b 3d 16 07 20 00 cmp 0x200716(%rip),%edi #
60119c <half>
400a86: 53 push %rbx
400a87: 89 fb mov %edi,%ebx
400a89: 74 5f je 400aea <_Z5test1i+0x6a>
400a8b: 48 8b 05 0e 07 20 00 mov 0x20070e(%rip),%rax #
6011a0 <A>
400a92: 48 63 d7 movslq %edi,%rdx
400a95: 83 3c 90 01 cmpl $0x1,(%rax,%rdx,4)
400a99: 74 4f je 400aea <_Z5test1i+0x6a>
400a9b: 8b 0d 07 07 20 00 mov 0x200707(%rip),%ecx #
6011a8 <size>
400aa1: eb 15 jmp 400ab8 <_Z5test1i+0x38>
400aa3: 0f 1f 44 00 00 nopl 0x0(%rax,%rax,1)
400aa8: 48 8b 05 f1 06 20 00 mov 0x2006f1(%rip),%rax #
6011a0 <A>
400aaf: 48 63 d3 movslq %ebx,%rdx
400ab2: 83 3c 90 01 cmpl $0x1,(%rax,%rdx,4)
400ab6: 74 32 je 400aea <_Z5test1i+0x6a>
400ab8: 29 d9 sub %ebx,%ecx
400aba: 8d 7b 01 lea 0x1(%rbx),%edi
400abd: 8b 54 90 04 mov 0x4(%rax,%rdx,4),%edx
400ac1: 48 63 c9 movslq %ecx,%rcx
400ac4: 03 54 88 fc add -0x4(%rax,%rcx,4),%edx
400ac8: 01 15 ca 06 20 00 add %edx,0x2006ca(%rip) #
601198 <s>
400ace: e8 ad ff ff ff callq 400a80 <_Z5test1i>
400ad3: 8b 0d cf 06 20 00 mov 0x2006cf(%rip),%ecx #
6011a8 <size>
400ad9: 89 c8 mov %ecx,%eax
400adb: 29 d8 sub %ebx,%eax
400add: 89 c3 mov %eax,%ebx
400adf: 83 eb 01 sub $0x1,%ebx
400ae2: 39 1d b4 06 20 00 cmp %ebx,0x2006b4(%rip) #
60119c <half>
400ae8: 75 be jne 400aa8 <_Z5test1i+0x28>
400aea: 5b pop %rbx
400aeb: c3 retq
400aec: 0f 1f 40 00 nopl 0x0(%rax)
Tiene cuatro ramas condicionales con una llamada. Analicemos la información que tenemos hasta ahora.
Antes que nada, ¿qué es una instrucción de ramificación desde la perspectiva del procesador? Es cualquiera de call , ret , j* (incluido jmp directo) y loop . call y jmp son un poco intuitivos, pero son cruciales para contar las cosas correctamente.
En general, esperamos que esta función se llame 11111100 veces, una para cada elemento, que es aproximadamente 11M. En la versión optimizada para llamadas sin cola, vemos aproximadamente 45M ramas, la inicialización en main () es solo 111K, todas las otras cosas son menores, por lo que la principal contribución a este número proviene de nuestra función. Nuestra función es call -ed, evalúa la primera je , que es verdadera en todos los casos menos en uno, luego evalúa la segunda je , que es verdadera la mitad de las veces y luego se llama recursivamente (pero ya hemos contado que la función se invoca 11M veces) o regresa (como lo hace después de llamadas recursivas. Así que son 4 instrucciones de bifurcación por llamadas 11M, exactamente el número que vemos. Fuera de estas alrededor de 5,5M se pierden ramas, lo que sugiere que todas estas fallas vienen de una instrucción mal predicha, ya sea algo que se evalúa 11 millones de veces y se pierde alrededor del 50% del tiempo o algo que se evalúa la mitad del tiempo y se pierde siempre.
¿Qué tenemos en la versión de cola optimizada? Tenemos la función llamada alrededor de 5,5M veces, pero ahora cada invocación incurre en una call , dos ramas inicialmente (la primera es verdadera en todos los casos, excepto uno y la segunda siempre es falsa debido a nuestros datos), luego una jmp , luego una llamada (pero ya hemos contado que tenemos llamadas de 5.5M), luego una rama a 400ae8 y una rama a 400ab6 (siempre es verdad debido a nuestros datos), luego regrese. Entonces, en promedio, son cuatro ramas condicionales, un salto incondicional, una llamada y una rama indirecta (retorno de la función), 5.5M por 7 nos da un recuento total de alrededor de 39M de ramas, exactamente como lo vemos en la salida de perf.
Lo que sabemos es que el procesador no tiene ningún problema en predecir cosas en un flujo con una llamada de función (aunque esta versión tiene más ramas condicionales) y tiene problemas con dos llamadas de función. Entonces sugiere que el problema está en los retornos de la función.
Desafortunadamente, sabemos muy poco sobre los detalles de cómo funcionan exactamente los predictores de bifurcación de nuestros procesadores modernos. El mejor análisis que pude encontrar es este y sugiere que los procesadores tienen un buffer de pila de retorno de alrededor de 16 entradas. Si volvemos a nuestros datos nuevamente con este hallazgo, las cosas empiezan a aclararse un poco.
Cuando tiene medio ceros con patrón de la mitad uno, está recurriendo profundamente en test1(curIndex+1) , pero luego comienza a regresar y llama a test1(size-curIndex-1) . Esa recursión nunca es más profunda que una llamada, por lo que los retornos se predicen perfectamente. Pero recuerde que ahora tenemos 55555 invocaciones profundas y el procesador solo recuerda los últimos 16, por lo que no es sorprendente que no pueda adivinar nuestros retornos a partir de un nivel 55539 profundo, es más sorprendente que pueda hacerlo con tail-call- versión optimizada
En realidad, el comportamiento de la versión optimizada de la llamada de la cola sugiere que, al omitir otra información sobre los retornos, el procesador simplemente asume que el correcto es el último visto. También está probado por el comportamiento de la versión optimizada para llamadas sin cola, ya que entra 55555 llamadas en el test1(curIndex+1) y luego, al regresar, siempre tiene un nivel de profundidad en test1(size-curIndex-1) , así que cuando pasamos de 55555-deep a 55539-deep (o lo que sea que sea el buffer de retorno de su procesador) llama a test1(size-curIndex-1) , regresa de eso y no tiene absolutamente ninguna información sobre el próximo retorno, por lo se supone que debemos volver a la última dirección que se ve (que es la dirección a la que regresar desde test1(size-curIndex-1) ) y obviamente está mal. 55539 veces mal. Con 100 ciclos de la función, eso es exactamente lo que falla en la predicción de bifurcación de 5.5M.
Ahora veamos tu patrón alternativo y el código para eso. Este código es realmente muy diferente, si quieres analizar cómo se profundiza. Aquí tiene su test2(curIndex+1) siempre regresa inmediatamente y su test2(curIndex+2) para ir siempre más profundo. Así que los retornos de test2(curIndex+1) siempre se predicen perfectamente (simplemente no profundizan lo suficiente) y cuando vamos a terminar nuestra recursión en test2(curIndex+2) , siempre regresa al mismo punto, todos 55555 veces, por lo que el procesador no tiene problemas con eso.
Esto puede demostrarse aún más con este pequeño cambio en sus semicírgenes originales con código de la mitad:
--- file.cpp.orig 2016-09-23 11:00:26.917977032 +0300
+++ file.cpp 2016-09-23 11:00:31.946027451 +0300
@@ -15,8 +15,8 @@
if(curIndex == half) return;
if(A[curIndex] == 1) return;
- test1(curIndex+1);
test1(size - curIndex - 1);
+ test1(curIndex+1);
s += A[curIndex+1] + A[size-curIndex-1];
Así que ahora el código generado aún no está optimizado para la cola de llamada (en lo que respecta al ensamblaje, es muy similar al original), pero se obtiene algo como esto en la salida de perf:
$ perf stat -B -e branches,branch-misses ./a.out 111111
5555500
Performance counter stats for ''./a.out 111111'':
45 308 579 branches
75 927 branch-misses # 0,17% of all branches
0,026271402 seconds time elapsed
Como era de esperar, ahora nuestra primera llamada siempre regresa inmediatamente y la segunda llamada tiene 55555 de profundidad y luego solo regresa al mismo punto.
Ahora con eso resuelto déjame mostrar algo en mi manga. En un sistema, y es Core i5-5200U, los medios ceros originales sin cola optimizados con versiones de mitad de uno muestran los siguientes resultados:
$ perf stat -B -e branches,branch-misses ./a.out 111111
5555500
Performance counter stats for ''./a.out 111111'':
45 331 670 branches
16 349 branch-misses # 0,04% of all branches
0,043351547 seconds time elapsed
Entonces, aparentemente, Broadwell puede manejar este patrón fácilmente, lo que nos devuelve a la pregunta de cuánto sabemos sobre la lógica de predicción de bifurcación de nuestros procesadores modernos.
Deje A ser una matriz que contiene un número impar de ceros y unos. Si n es el tamaño de A , entonces A está construido de tal manera que los primeros elementos ceil(n/2) son 0 y los elementos restantes 1 .
Entonces, si n = 9 , A se vería así:
0,0,0,0,0,1,1,1,1
El objetivo es encontrar la suma de 1s en la matriz y lo hacemos usando esta función:
s = 0;
void test1(int curIndex){
//A is 0,0,0,...,0,1,1,1,1,1...,1
if(curIndex == ceil(n/2)) return;
if(A[curIndex] == 1) return;
test1(curIndex+1);
test1(size-curIndex-1);
s += A[curIndex+1] + A[size-curIndex-1];
}
Esta función es bastante tonta para el problema dado, pero es una simulación de una función diferente que quiero que se vea así y está produciendo la misma cantidad de errores de predicción de ramas.
Aquí está el código completo del experimento:
#include <iostream>
#include <fstream>
using namespace std;
int size;
int *A;
int half;
int s;
void test1(int curIndex){
//A is 0,0,0,...,0,1,1,1,1,1...,1
if(curIndex == half) return;
if(A[curIndex] == 1) return;
test1(curIndex+1);
test1(size - curIndex - 1);
s += A[curIndex+1] + A[size-curIndex-1];
}
int main(int argc, char* argv[]){
size = atoi(argv[1]);
if(argc!=2){
cout<<"type ./executable size{odd integer}"<<endl;
return 1;
}
if(size%2!=1){
cout<<"size must be an odd number"<<endl;
return 1;
}
A = new int[size];
half = size/2;
int i;
for(i=0;i<=half;i++){
A[i] = 0;
}
for(i=half+1;i<size;i++){
A[i] = 1;
}
for(i=0;i<100;i++) {
test1(0);
}
cout<<s<<endl;
return 0;
}
Para compilar, escriba g++ -O3 -std=c++11 file.cpp y ejecute escribiendo ./executable size{odd integer} .
Estoy usando una CPU Intel (R) Core (TM) i5-3470 @ 3.20GHz con 8 GB de RAM, caché L1 de 256 KB, caché L2 de 1 MB, caché L3 de 6 MB.
Ejecutar perf stat -B -e branches,branch-misses ./cachetests 111111 me da lo siguiente:
Performance counter stats for ''./cachetests 111111'':
32,639,932 branches
1,404,836 branch-misses # 4.30% of all branches
0.060349641 seconds time elapsed
si elimino la línea
s += A[curIndex+1] + A[size-curIndex-1];
Obtengo el siguiente resultado de perf:
Performance counter stats for ''./cachetests 111111'':
24,079,109 branches
39,078 branch-misses # 0.16% of all branches
0.027679521 seconds time elapsed
¿Qué tiene que ver esa línea con las predicciones de ramas cuando ni siquiera es una declaración if?
La forma en que lo veo, en el primer ceil(n/2) - 1 llamadas de test1() , ambas si las declaraciones serán falsas. En la llamada if(curIndex == ceil(n/2)) , if(curIndex == ceil(n/2)) será verdadero. En las llamadas n-ceil(n/2) restantes, la primera instrucción será falsa y la segunda será verdadera.
¿Por qué Intel no puede predecir un comportamiento tan simple?
Ahora veamos un segundo caso. Supongamos que A ahora tiene ceros y unos alternativos. Siempre comenzaremos desde 0. Entonces, si n = 9 A se verá así:
0,1,0,1,0,1,0,1,0
La función que vamos a usar es la siguiente:
void test2(int curIndex){
//A is 0,1,0,1,0,1,0,1,....
if(curIndex == size-1) return;
if(A[curIndex] == 1) return;
test2(curIndex+1);
test2(curIndex+2);
s += A[curIndex+1] + A[curIndex+2];
}
Y aquí está el código completo del experimento:
#include <iostream>
#include <fstream>
using namespace std;
int size;
int *A;
int s;
void test2(int curIndex){
//A is 0,1,0,1,0,1,0,1,....
if(curIndex == size-1) return;
if(A[curIndex] == 1) return;
test2(curIndex+1);
test2(curIndex+2);
s += A[curIndex+1] + A[curIndex+2];
}
int main(int argc, char* argv[]){
size = atoi(argv[1]);
if(argc!=2){
cout<<"type ./executable size{odd integer}"<<endl;
return 1;
}
if(size%2!=1){
cout<<"size must be an odd number"<<endl;
return 1;
}
A = new int[size];
int i;
for(i=0;i<size;i++){
if(i%2==0){
A[i] = false;
}
else{
A[i] = true;
}
}
for(i=0;i<100;i++) {
test2(0);
}
cout<<s<<endl;
return 0;
}
Ejecuto perf utilizando los mismos comandos que antes:
Performance counter stats for ''./cachetests2 111111'':
28,560,183 branches
54,204 branch-misses # 0.19% of all branches
0.037134196 seconds time elapsed
Y eliminar esa línea nuevamente mejoró un poco las cosas:
Performance counter stats for ''./cachetests2 111111'':
28,419,557 branches
16,636 branch-misses # 0.06% of all branches
0.009977772 seconds time elapsed
Ahora si analizamos la función, if(curIndex == size-1) será falso n-1 veces, y if(A[curIndex] == 1) se alternará de verdadero a falso.
Tal como lo veo, ambas funciones deberían ser fáciles de predecir, sin embargo, este no es el caso para la primera función. Al mismo tiempo, no estoy seguro de qué está pasando con esa línea y por qué desempeña un papel en la mejora del comportamiento de las sucursales.
Curiosamente, en la primera ejecución tiene aproximadamente un 30% más de sucursales que en la segunda ejecución (32 millones de sucursales frente a 24 millones de marcos).
He generado el código de ensamblaje para su aplicación usando gcc 4.8.5 y las mismas banderas (más -S ) y hay una diferencia significativa entre los ensamblajes. El código con la declaración en conflicto es de aproximadamente 572 líneas, mientras que el código sin la misma declaración es solo 409 líneas. Centrándonos en el símbolo _Z5test1i - el nombre decorado de C ++ para test1), la rutina tiene 367 líneas de longitud, mientras que el segundo caso ocupa solo 202 líneas. De todas esas líneas, el primer caso contiene 36 ramas (más 15 instrucciones de llamada) y el segundo caso contiene 34 ramas (más 1 instrucción de llamada).
También es interesante que la compilación de la aplicación con -O1 no expone esta divergencia entre las dos versiones (aunque el error de la bifurcación es mayor, aproximadamente 12%). El uso de -O2 muestra una diferencia entre las dos versiones (12% frente a 3% de -O2 de la bifurcación).
No soy un experto en compiladores para comprender los flujos de control y las lógicas utilizadas por el compilador, pero parece que el compilador puede lograr optimizaciones más inteligentes (tal vez incluyendo optimizaciones recursivas de cola según lo señala user1850903 en su respuesta) cuando esa parte del el código no está presente
El siguiente fragmento de código es recursivo de cola: la última línea de la función no requiere una llamada, simplemente una rama al punto donde la función comienza utilizando el primer argumento:
void f(int i) {
if (i == size) break;
s += a[i];
f(i + 1);
}
Sin embargo, si rompemos esto y lo hacemos no recurrente recursivo:
void f(int i) {
if (i == size) break;
f(i + 1);
s += a[i];
}
Hay una serie de razones por las cuales el compilador no puede deducir que este último sea recursivo de cola, pero en el ejemplo que usted ha dado,
test(A[N]);
test(A[M]);
s += a[N] + a[M];
las mismas reglas se aplican. El compilador no puede determinar que esto es recursivo de cola, pero más aún no puede hacerlo debido a las dos llamadas (ver before y after ).
Lo que parece esperar que el compilador haga con esto es una función que realiza un par de ramas condicionales simples, dos llamadas y algunas cargar / agregar / almacenar.
En cambio, el compilador está desenrollando este ciclo y generando código que tiene muchos puntos de ramificación. Esto se hace en parte porque el compilador cree que será más eficiente de esta manera (involucrando menos ramas) pero en parte porque disminuye la profundidad de recursión del tiempo de ejecución.
int size;
int* A;
int half;
int s;
void test1(int curIndex){
if(curIndex == half || A[curIndex] == 1) return;
test1(curIndex+1);
test1(size-curIndex-1);
s += A[curIndex+1] + A[size-curIndex-1];
}
produce:
test1(int):
movl half(%rip), %edx
cmpl %edi, %edx
je .L36
pushq %r15
pushq %r14
movslq %edi, %rcx
pushq %r13
pushq %r12
leaq 0(,%rcx,4), %r12
pushq %rbp
pushq %rbx
subq $24, %rsp
movq A(%rip), %rax
cmpl $1, (%rax,%rcx,4)
je .L1
leal 1(%rdi), %r13d
movl %edi, %ebp
cmpl %r13d, %edx
je .L42
cmpl $1, 4(%rax,%r12)
je .L42
leal 2(%rdi), %ebx
cmpl %ebx, %edx
je .L39
cmpl $1, 8(%rax,%r12)
je .L39
leal 3(%rdi), %r14d
cmpl %r14d, %edx
je .L37
cmpl $1, 12(%rax,%r12)
je .L37
leal 4(%rdi), %edi
call test1(int)
movl %r14d, %edi
notl %edi
addl size(%rip), %edi
call test1(int)
movl size(%rip), %ecx
movq A(%rip), %rax
movl %ecx, %esi
movl 16(%rax,%r12), %edx
subl %r14d, %esi
movslq %esi, %rsi
addl -4(%rax,%rsi,4), %edx
addl %edx, s(%rip)
movl half(%rip), %edx
.L10:
movl %ecx, %edi
subl %ebx, %edi
leal -1(%rdi), %r14d
cmpl %edx, %r14d
je .L38
movslq %r14d, %rsi
cmpl $1, (%rax,%rsi,4)
leaq 0(,%rsi,4), %r15
je .L38
call test1(int)
movl %r14d, %edi
notl %edi
addl size(%rip), %edi
call test1(int)
movl size(%rip), %ecx
movq A(%rip), %rax
movl %ecx, %edx
movl 4(%rax,%r15), %esi
movl %ecx, %edi
subl %r14d, %edx
subl %ebx, %edi
movslq %edx, %rdx
addl -4(%rax,%rdx,4), %esi
movl half(%rip), %edx
addl s(%rip), %esi
movl %esi, s(%rip)
.L13:
movslq %edi, %rdi
movl 12(%rax,%r12), %r8d
addl -4(%rax,%rdi,4), %r8d
addl %r8d, %esi
movl %esi, s(%rip)
.L7:
movl %ecx, %ebx
subl %r13d, %ebx
leal -1(%rbx), %r14d
cmpl %edx, %r14d
je .L41
movslq %r14d, %rsi
cmpl $1, (%rax,%rsi,4)
leaq 0(,%rsi,4), %r15
je .L41
cmpl %edx, %ebx
je .L18
movslq %ebx, %rsi
cmpl $1, (%rax,%rsi,4)
leaq 0(,%rsi,4), %r8
movq %r8, (%rsp)
je .L18
leal 1(%rbx), %edi
call test1(int)
movl %ebx, %edi
notl %edi
addl size(%rip), %edi
call test1(int)
movl size(%rip), %ecx
movq A(%rip), %rax
movq (%rsp), %r8
movl %ecx, %esi
subl %ebx, %esi
movl 4(%rax,%r8), %edx
movslq %esi, %rsi
addl -4(%rax,%rsi,4), %edx
addl %edx, s(%rip)
movl half(%rip), %edx
.L18:
movl %ecx, %edi
subl %r14d, %edi
leal -1(%rdi), %ebx
cmpl %edx, %ebx
je .L40
movslq %ebx, %rsi
cmpl $1, (%rax,%rsi,4)
leaq 0(,%rsi,4), %r8
je .L40
movq %r8, (%rsp)
call test1(int)
movl %ebx, %edi
notl %edi
addl size(%rip), %edi
call test1(int)
movl size(%rip), %ecx
movq A(%rip), %rax
movq (%rsp), %r8
movl %ecx, %edx
movl %ecx, %edi
subl %ebx, %edx
movl 4(%rax,%r8), %esi
subl %r14d, %edi
movslq %edx, %rdx
addl -4(%rax,%rdx,4), %esi
movl half(%rip), %edx
addl s(%rip), %esi
movl %esi, %r8d
movl %esi, s(%rip)
.L20:
movslq %edi, %rdi
movl 4(%rax,%r15), %esi
movl %ecx, %ebx
addl -4(%rax,%rdi,4), %esi
subl %r13d, %ebx
addl %r8d, %esi
movl %esi, s(%rip)
.L16:
movslq %ebx, %rbx
movl 8(%rax,%r12), %edi
addl -4(%rax,%rbx,4), %edi
addl %edi, %esi
movl %esi, s(%rip)
jmp .L4
.L45:
movl s(%rip), %edx
.L23:
movslq %ebx, %rbx
movl 4(%rax,%r12), %ecx
addl -4(%rax,%rbx,4), %ecx
addl %ecx, %edx
movl %edx, s(%rip)
.L1:
addq $24, %rsp
popq %rbx
popq %rbp
popq %r12
popq %r13
popq %r14
popq %r15
.L36:
rep ret
.L42:
movl size(%rip), %ecx
.L4:
movl %ecx, %ebx
subl %ebp, %ebx
leal -1(%rbx), %r14d
cmpl %edx, %r14d
je .L45
movslq %r14d, %rsi
cmpl $1, (%rax,%rsi,4)
leaq 0(,%rsi,4), %r15
je .L45
cmpl %edx, %ebx
je .L25
movslq %ebx, %rsi
cmpl $1, (%rax,%rsi,4)
leaq 0(,%rsi,4), %r13
je .L25
leal 1(%rbx), %esi
cmpl %edx, %esi
movl %esi, (%rsp)
je .L26
cmpl $1, 8(%rax,%r15)
je .L26
leal 2(%rbx), %edi
call test1(int)
movl (%rsp), %esi
movl %esi, %edi
notl %edi
addl size(%rip), %edi
call test1(int)
movl size(%rip), %ecx
movl (%rsp), %esi
movq A(%rip), %rax
movl %ecx, %edx
subl %esi, %edx
movslq %edx, %rsi
movl 12(%rax,%r15), %edx
addl -4(%rax,%rsi,4), %edx
addl %edx, s(%rip)
movl half(%rip), %edx
.L26:
movl %ecx, %edi
subl %ebx, %edi
leal -1(%rdi), %esi
cmpl %edx, %esi
je .L43
movslq %esi, %r8
cmpl $1, (%rax,%r8,4)
leaq 0(,%r8,4), %r9
je .L43
movq %r9, 8(%rsp)
movl %esi, (%rsp)
call test1(int)
movl (%rsp), %esi
movl %esi, %edi
notl %edi
addl size(%rip), %edi
call test1(int)
movl size(%rip), %ecx
movl (%rsp), %esi
movq A(%rip), %rax
movq 8(%rsp), %r9
movl %ecx, %edx
movl %ecx, %edi
subl %esi, %edx
movl 4(%rax,%r9), %esi
subl %ebx, %edi
movslq %edx, %rdx
addl -4(%rax,%rdx,4), %esi
movl half(%rip), %edx
addl s(%rip), %esi
movl %esi, s(%rip)
.L28:
movslq %edi, %rdi
movl 4(%rax,%r13), %r8d
addl -4(%rax,%rdi,4), %r8d
addl %r8d, %esi
movl %esi, s(%rip)
.L25:
movl %ecx, %r13d
subl %r14d, %r13d
leal -1(%r13), %ebx
cmpl %edx, %ebx
je .L44
movslq %ebx, %rdi
cmpl $1, (%rax,%rdi,4)
leaq 0(,%rdi,4), %rsi
movq %rsi, (%rsp)
je .L44
cmpl %edx, %r13d
je .L33
movslq %r13d, %rdx
cmpl $1, (%rax,%rdx,4)
leaq 0(,%rdx,4), %r8
movq %r8, 8(%rsp)
je .L33
leal 1(%r13), %edi
call test1(int)
movl %r13d, %edi
notl %edi
addl size(%rip), %edi
call test1(int)
movl size(%rip), %ecx
movq A(%rip), %rdi
movq 8(%rsp), %r8
movl %ecx, %edx
subl %r13d, %edx
movl 4(%rdi,%r8), %eax
movslq %edx, %rdx
addl -4(%rdi,%rdx,4), %eax
addl %eax, s(%rip)
.L33:
subl %ebx, %ecx
leal -1(%rcx), %edi
call test1(int)
movl size(%rip), %ecx
movq A(%rip), %rax
movl %ecx, %esi
movl %ecx, %r13d
subl %ebx, %esi
movq (%rsp), %rbx
subl %r14d, %r13d
movslq %esi, %rsi
movl 4(%rax,%rbx), %edx
addl -4(%rax,%rsi,4), %edx
movl s(%rip), %esi
addl %edx, %esi
movl %esi, s(%rip)
.L31:
movslq %r13d, %r13
movl 4(%rax,%r15), %edx
subl %ebp, %ecx
addl -4(%rax,%r13,4), %edx
movl %ecx, %ebx
addl %esi, %edx
movl %edx, s(%rip)
jmp .L23
.L44:
movl s(%rip), %esi
jmp .L31
.L39:
movl size(%rip), %ecx
jmp .L7
.L41:
movl s(%rip), %esi
jmp .L16
.L43:
movl s(%rip), %esi
jmp .L28
.L38:
movl s(%rip), %esi
jmp .L13
.L37:
movl size(%rip), %ecx
jmp .L10
.L40:
movl s(%rip), %r8d
jmp .L20
s:
half:
.zero 4
A:
.zero 8
size:
.zero 4
Para el caso de valores alternativos, asumiendo tamaño == 7:
test1(curIndex = 0)
{
if (curIndex == size - 1) return; // false x1
if (A[curIndex] == 1) return; // false x1
test1(curIndex + 1 => 1) {
if (curIndex == size - 1) return; // false x2
if (A[curIndex] == 1) return; // false x1 -mispred-> returns
}
test1(curIndex + 2 => 2) {
if (curIndex == size - 1) return; // false x 3
if (A[curIndex] == 1) return; // false x2
test1(curIndex + 1 => 3) {
if (curIndex == size - 1) return; // false x3
if (A[curIndex] == 1) return; // false x2 -mispred-> returns
}
test1(curIndex + 2 => 4) {
if (curIndex == size - 1) return; // false x4
if (A[curIndex] == 1) return; // false x3
test1(curIndex + 1 => 5) {
if (curIndex == size - 1) return; // false x5
if (A[curIndex] == 1) return; // false x3 -mispred-> returns
}
test1(curIndex + 2 => 6) {
if (curIndex == size - 1) return; // false x5 -mispred-> returns
}
s += A[5] + A[6];
}
s += A[3] + A[4];
}
s += A[1] + A[2];
}
Y imaginemos un caso donde
size = 11;
A[11] = { 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0 };
test1(0)
-> test1(1)
-> test1(2)
-> test1(3) -> returns because 1
-> test1(4)
-> test1(5)
-> test1(6)
-> test1(7) -- returns because 1
-> test1(8)
-> test1(9) -- returns because 1
-> test1(10) -- returns because size-1
-> test1(7) -- returns because 1
-> test1(6)
-> test1(7)
-> test1(8)
-> test1(9) -- 1
-> test1(10) -- size-1
-> test1(3) -> returns
-> test1(2)
... as above
o
size = 5;
A[5] = { 0, 0, 0, 0, 1 };
test1(0)
-> test1(1)
-> test1(2)
-> test1(3)
-> test1(4) -- size
-> test1(5) -- UB
-> test1(4)
-> test1(3)
-> test1(4) -- size
-> test1(5) -- UB
-> test1(2)
..
Los dos casos que seleccionó (alternancia y medio patrón) son extremos óptimos y el compilador seleccionó algunos casos intermedios que tratará de manejar mejor.
Eliminando la línea s += A[curIndex+1] + A[size-curIndex-1]; permite la optimización recursiva de la cola . Esta optimización solo puede ocurrir, entonces la llamada recursiva está en la última línea de la función.
el problema es este:
if(A[curIndex] == 1) return;
cada llamada de la función de prueba alterna el resultado de esta comparación, debido a algunas optimizaciones, ya que la matriz es, por ejemplo, 0,0,0,0,0,1,1,1,1
En otras palabras:
- curIndex = 0 -> A [0] = 0
- test1 (curIndex + 1) -> curIndex = 1 -> A [1] = 0
Pero entonces, la arquitectura del procesador MIGHT (un poder grande, porque depende, para mí esa optimización está desactivada - un i5-6400) tiene una función llamada runahead (realizada a lo largo de la predicción de bifurcación), que ejecuta las instrucciones restantes en la tubería antes de ingresar una rama; por lo que ejecutará test1(size - curIndex -1) antes de la declaración if ofensiva.
Al eliminar la atribución, ingresa a otra optimización, como dijo user1850903.