c - son - ¿"==" en la matriz ordenada no es más rápido que la matriz no ordenada?
matrices en c (3)
La comparación == tiene menos relación con ordenar que > does. La predicción correcta o incorrecta de == dependerá únicamente de la cantidad de valores duplicados y su distribución.
Puede usar perf stat para ver los contadores de rendimiento ...
jason@io /tmp $ lz4 -d ints | perf stat ./proc-eq >/dev/null
Successfully decoded 104824717 bytes
Performance counter stats for ''./proc-eq'':
5226.932577 task-clock (msec) # 0.953 CPUs utilized
31 context-switches # 0.006 K/sec
24 cpu-migrations # 0.005 K/sec
3,479 page-faults # 0.666 K/sec
15,763,486,767 cycles # 3.016 GHz
4,238,973,549 stalled-cycles-frontend # 26.89% frontend cycles idle
<not supported> stalled-cycles-backend
31,522,072,416 instructions # 2.00 insns per cycle
# 0.13 stalled cycles per insn
8,515,545,178 branches # 1629.167 M/sec
10,261,743 branch-misses # 0.12% of all branches
5.483071045 seconds time elapsed
jason@io /tmp $ lz4 -d ints | sort -n | perf stat ./proc-eq >/dev/null
Successfully decoded 104824717 bytes
Performance counter stats for ''./proc-eq'':
5536.031410 task-clock (msec) # 0.348 CPUs utilized
198 context-switches # 0.036 K/sec
21 cpu-migrations # 0.004 K/sec
3,604 page-faults # 0.651 K/sec
16,870,541,124 cycles # 3.047 GHz
5,300,218,855 stalled-cycles-frontend # 31.42% frontend cycles idle
<not supported> stalled-cycles-backend
31,526,006,118 instructions # 1.87 insns per cycle
# 0.17 stalled cycles per insn
8,516,336,829 branches # 1538.347 M/sec
10,980,571 branch-misses # 0.13% of all branches
jason@io /tmp $ lz4 -d ints | perf stat ./proc-gt >/dev/null
Successfully decoded 104824717 bytes
Performance counter stats for ''./proc-gt'':
5293.065703 task-clock (msec) # 0.957 CPUs utilized
38 context-switches # 0.007 K/sec
50 cpu-migrations # 0.009 K/sec
3,466 page-faults # 0.655 K/sec
15,972,451,322 cycles # 3.018 GHz
4,350,726,606 stalled-cycles-frontend # 27.24% frontend cycles idle
<not supported> stalled-cycles-backend
31,537,365,299 instructions # 1.97 insns per cycle
# 0.14 stalled cycles per insn
8,515,606,640 branches # 1608.823 M/sec
15,241,198 branch-misses # 0.18% of all branches
5.532285374 seconds time elapsed
jason@io /tmp $ lz4 -d ints | sort -n | perf stat ./proc-gt >/dev/null
15.930144154 seconds time elapsed
Performance counter stats for ''./proc-gt'':
5203.873321 task-clock (msec) # 0.339 CPUs utilized
7 context-switches # 0.001 K/sec
22 cpu-migrations # 0.004 K/sec
3,459 page-faults # 0.665 K/sec
15,830,273,846 cycles # 3.042 GHz
4,456,369,958 stalled-cycles-frontend # 28.15% frontend cycles idle
<not supported> stalled-cycles-backend
31,540,409,224 instructions # 1.99 insns per cycle
# 0.14 stalled cycles per insn
8,516,186,042 branches # 1636.509 M/sec
10,205,058 branch-misses # 0.12% of all branches
15.365528326 seconds time elapsed
Esta pregunta ya tiene una respuesta aquí:
Nota: la supuesta pregunta duplicada está, creo, relacionada principalmente con la comparación "<" y ">", pero no con la "==" comparación y, por lo tanto, no responde mi pregunta sobre el rendimiento del operador "==".
Durante mucho tiempo, he creído que "procesar" una matriz ordenada debería ser más rápido que una matriz no ordenada. Al principio, pensé que usar "==" en una matriz ordenada debería ser más rápido que en la matriz no ordenada porque, supongo, de cómo funciona la predicción de ramas:
UNSORTEDARRAY:
5 == 100 F
43 == 100 F
100 == 100 T
250 == 100 F
6 == 100 F
(other elements to check)
SORTEDARRAY:
5 == 100 F
6 == 100 F
43 == 100 F
100 == 100 T
(no need to check other elements, so all are F)
así que supongo que SORTEDARRAY debería ser más rápido que UNSORTEDARRAY, pero hoy utilicé el código para generar 2 matrices en un encabezado para probar, y la predicción de bifurcaciones no pareció funcionar como pensé.
Genere una matriz no ordenada y una matriz ordenada para probar:
srand(time(NULL));
int UNSORTEDARRAY[524288];
int SORTEDARRAY[sizeof(UNSORTEDARRAY)/sizeof(int)];
for(int i=0;i<sizeof(SORTEDARRAY)/sizeof(int);i++){
SORTEDARRAY[i]=UNSORTEDARRAY[i]=rand();
}
sort(SORTEDARRAY,SORTEDARRAY+sizeof(SORTEDARRAY)/sizeof(int));
string u="const int UNSORTEDARRAY[]={";
string s="const int SORTEDARRAY[]={";
for(int i=0;i<sizeof(UNSORTEDARRAY)/sizeof(int);i++){
u+=to_string(UNSORTEDARRAY[i])+",";
s+=to_string(SORTEDARRAY[i])+",";
}
u.erase(u.end()-1);
s.erase(s.end()-1);
u+="};/n";
s+="};/n";
ofstream out("number.h");
string code=u+s;
out << code;
out.close();
para probar, solo cuente si el valor es == RAND_MAX / 2 así:
#include "number.h"
int main(){
int count;
clock_t start = clock();
for(int i=0;i<sizeof(SORTEDARRAY)/sizeof(int);i++){
if(SORTEDARRAY[i]==RAND_MAX/2){
count++;
}
}
printf("%f/n",(float)(clock()-start)/CLOCKS_PER_SEC);
}
correr 3 veces:
UNSORTEDARRAY
0.005376
0.005239
0.005220
SORTEDARRAY
0.005334
0.005120
0.005223
parece una pequeña diferencia de rendimiento, así que no lo creí y luego intenté cambiar "SORTEDARRAY [i] == RAND_MAX / 2" por "SORTEDARRAY [i]> RAND_MAX / 2" para ver si hacía una diferencia:
UNSORTEDARRAY
0.008407
0.008363
0.008606
SORTEDARRAY
0.005306
0.005227
0.005146
esta vez hay una gran diferencia.
¿"==" en la matriz ordenada no es más rápido que una matriz no ordenada? En caso afirmativo, ¿por qué ">" en la matriz ordenada es más rápido que una matriz no ordenada pero "==" no?
Una cosa que viene inmediatamente a la mente es el algoritmo de predicción de bifurcación de la CPU.
En el caso de > comparación, en la matriz ordenada, el comportamiento de bifurcación es muy consistente: primero, if condición if es constantemente falsa, entonces es consistentemente verdadera. Esto se alinea muy bien incluso con la predicción de bifurcación más simple.
En una matriz no ordenada, el resultado de la condición es esencialmente aleatorio, frustrando así cualquier predicción de bifurcación.
Esto es lo que hace que la versión clasificada sea más rápida.
En el caso de == comparación, la mayoría de las veces la condición es falsa y solo muy raramente es verdadera. Esto funciona bien con la predicción de bifurcación, independientemente de si la matriz está ordenada o no. Los tiempos son esencialmente los mismos.
Nota: estoy haciendo una respuesta, ya que es demasiado tiempo para hacer un comentario.
El efecto aquí es exactamente lo que ya se explica en gran detalle en las abundantes respuestas a esta pregunta . Procesar una matriz ordenada fue más rápido en ese caso debido a la predicción de bifurcación.
Aquí, el culpable es nuevamente predicción de bifurcación. La prueba == es muy rara vez cierta, por lo que la predicción de bifurcaciones funciona igual para ambos. Cuando lo cambiaste a > , entonces obtuviste el comportamiento explicado en esa pregunta, y por la misma razón.
Moral:
Creo que "procesar" una matriz ordenada debería ser más rápido que [una] matriz no ordenada.
Necesitas saber por qué . Esta no es una regla mágica, y no siempre es verdad.