Ist "==" im sortierten Array nicht schneller als unsortiertes Array?




arrays performance (3)

Diese Frage hat hier bereits eine Antwort:

Hinweis: Die angebliche Duplikatsfrage ist, glaube ich, meist auf "<" und ">" Vergleich bezogen, aber nicht auf "==" Vergleich und beantwortet somit meine Frage nach der Leistung des "==" Operators nicht.

Ich habe lange geglaubt, dass das "Verarbeiten" eines sortierten Arrays schneller als ein unsortiertes Array sein sollte. Zuerst dachte ich, dass die Verwendung von "==" in einem sortierten Array schneller sein sollte als in einem unsortierten Array, weil - wie ich vermute - die Verzweigungsvorhersage funktioniert:

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)

also denke ich, SORTEDARRAY sollte schneller sein als UNSORTEDARRAY, aber heute habe ich den Code verwendet, um 2 Arrays in einem Header zum Testen zu generieren, und die Verzweigungsvorhersage schien nicht so zu funktionieren, wie ich dachte.

Ich habe ein unsortiertes Array und ein sortiertes Array zum Testen erstellt:

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();

Zählen Sie einfach, wenn der Wert == RAND_MAX / 2 lautet:

#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);
}

Lauf 3 mal:

UNSORTEDARRAY

0.005376
0.005239
0.005220

SORTEDARRAY

0.005334
0.005120
0.005223

Es scheint ein kleiner Leistungsunterschied zu sein, also glaubte ich es nicht und versuchte dann, "SORTEDARRAY [i] == RAND_MAX / 2" zu "SORTEDARRAY [i]> RAND_MAX / 2" zu ändern, um zu sehen, ob es einen Unterschied machte:

UNSORTEDARRAY

0.008407
0.008363
0.008606

SORTEDARRAY

0.005306
0.005227
0.005146

dieses Mal gibt es einen großen Unterschied.

Ist "==" im sortierten Array nicht schneller als ein unsortiertes Array? Wenn ja, warum ist ">" im sortierten Array schneller als ein unsortiertes Array, aber "==" nicht?


Der Vergleich == hat weniger eine Beziehung zum Ordnen als > does. Die korrekte oder falsche Vorhersage von == würde nur von der Anzahl der doppelten Werte und deren Verteilung abhängen.

Mit perf stat können Sie die Leistungsindikatoren anzeigen ...

[email protected] /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

[email protected] /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

[email protected] /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

[email protected] /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

Eine Sache, die sofort in den Sinn kommt, ist der Verzweigungsvorhersagealgorithmus der CPU.

Im Fall von > Vergleich ist das Verzweigungsverhalten in sortierten Feldern sehr konsistent: Erstens ist die if Bedingung konsistent falsch, dann ist sie durchgehend wahr. Dies stimmt sehr gut mit der einfachsten Verzweigungsvorhersage überein.

In einem unsortierten Array ist das Ergebnis von > condition im Wesentlichen zufällig, wodurch jede Verzweigungsvorhersage vereitelt wird.

Dies macht die sortierte Version schneller.

Im Fall von == Vergleich ist die Bedingung meistens falsch und nur sehr selten ist es wahr. Dies funktioniert gut mit der Verzweigungsvorhersage unabhängig davon, ob das Array sortiert ist oder nicht. Die Zeiten sind im Wesentlichen gleich.


NB Ich mache das eine Antwort, da es für einen Kommentar zu lang ist.

Die Wirkung hier ist genau das, was bereits ausführlich in den zahlreichen Antworten auf diese Frage erklärt wurde . Die Verarbeitung eines sortierten Arrays war in diesem Fall wegen der Verzweigungsvorhersage schneller.

Hier ist der Schuldige wiederum eine Verzweigungsvorhersage. Der == Test ist sehr selten richtig, also funktioniert die Verzweigungsvorhersage für beide gleich. Wenn Sie es zu > geändert haben, dann haben Sie das Verhalten in dieser Frage und aus dem gleichen Grund erklärt.

Moral:

Ich glaube, dass das "Verarbeiten" eines sortierten Arrays schneller sein sollte als das eines unsortierten Arrays.

Sie müssen wissen, warum . Dies ist keine magische Regel, und es ist nicht immer wahr.





sortedlist