¿Es “==” en una matriz ordenada no más rápido que una matriz no ordenada? [duplicate]

Nota: creo que la supuesta pregunta duplicada está relacionada principalmente con la comparación ““, pero no con la comparación “==” y, por lo tanto, no responde a 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 una matriz no ordenada porque, supongo, de cómo funciona la predicción de ramas:

SIN CLASIFICAR:

5 == 100 F
43 == 100 F
100 == 100 T
250 == 100 F
6 == 100 F
(other elements to check)

CLASIFICADO:

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 usé el código para generar 2 matrices en un encabezado para probar, y la predicción de bifurcación parecía no funcionar como pensaba.

Generé una matriz sin ordenar 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();

así que 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:

SIN CLASIFICAR

0.005376
0.005239
0.005220

CLASIFICADO

0.005334
0.005120
0.005223

parece una pequeña diferencia de rendimiento, así que no lo creí y luego traté de cambiar “SORTEDARRAY[i]==RAND_MAX/2” a “SORTEDARRAY[i]>RAND_MAX/2” para ver si hizo una diferencia:

SIN CLASIFICAR

0.008407
0.008363
0.008606

CLASIFICADO

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 una matriz ordenada es más rápido que una matriz no ordenada pero “==” no lo es?

Una cosa que me viene a la mente de inmediato es el algoritmo de predicción de bifurcaciones de la CPU.

En caso de > En comparación, en una matriz ordenada, el comportamiento de ramificación es muy consistente: primero, el if condición es consistentemente falsa, entonces es consistentemente verdadera. Esto se alinea muy bien incluso con la predicción de rama más simple.

En una matriz desordenada el resultado de > la condición es esencialmente aleatoria, frustrando así cualquier predicción de bifurcación.

Esto es lo que hace que la versión ordenada sea más rápida.

En caso de == comparación, la mayoría de las veces la condición es falsa y muy rara vez es verdadera. Esto funciona bien con la predicción de ramas, independientemente de si la matriz está ordenada o no. Los tiempos son esencialmente los mismos.

^{NB: estoy respondiendo esto porque es demasiado largo para un comentario.}

El efecto aquí es exactamente lo que ya se explica con gran detalle en las abundantes respuestas a esta pregunta. El procesamiento de una matriz ordenada fue más rápido en ese caso debido a la predicción de ramificación.

Aquí, el culpable es nuevamente la predicción de ramas. los == La prueba rara vez es cierta, por lo que la predicción de bifurcación funciona de la misma manera 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 [an ]matriz sin ordenar.

Necesitas saber por qué. Esta no es una regla mágica, y no siempre es cierta.

La comparación == tiene menos relación con ordenar que > lo hace. Predecir correcta o incorrectamente == solo dependería del número de valores duplicados y su distribución.

Puedes 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