> vs.> = bei der Blasensortierung verursacht einen signifikanten Leistungsunterschied

Question 1

Ich bin gerade auf etwas gestoßen. Zuerst dachte ich, es könnte sich um eine Fehlvorhersage für Zweige handeln, wie dies in diesem Fall der Fall ist , aber ich kann nicht erklären, warum eine Fehlvorhersage für Zweige dieses Verhalten verursachen sollte.

Ich habe zwei Versionen von Bubble Sort in Java implementiert und einige Leistungstests durchgeführt:

import java.util.Random;

public class BubbleSortAnnomaly {

    public static void main(String... args) {
        final int ARRAY_SIZE = Integer.parseInt(args[0]);
        final int LIMIT = Integer.parseInt(args[1]);
        final int RUNS = Integer.parseInt(args[2]);

        int[] a = new int[ARRAY_SIZE];
        int[] b = new int[ARRAY_SIZE];
        Random r = new Random();
        for (int run = 0; RUNS > run; ++run) {
            for (int i = 0; i < ARRAY_SIZE; i++) {
                a[i] = r.nextInt(LIMIT);
                b[i] = a[i];
            }

            System.out.print("Sorting with sortA: ");
            long start = System.nanoTime();
            int swaps = bubbleSortA(a);

            System.out.println(  (System.nanoTime() - start) + " ns. "
                               + "It used " + swaps + " swaps.");

            System.out.print("Sorting with sortB: ");
            start = System.nanoTime();
            swaps = bubbleSortB(b);

            System.out.println(  (System.nanoTime() - start) + " ns. "
                               + "It used " + swaps + " swaps.");
        }
    }

    public static int bubbleSortA(int[] a) {
        int counter = 0;
        for (int i = a.length - 1; i >= 0; --i) {
            for (int j = 0; j < i; ++j) {
                if (a[j] > a[j + 1]) {
                    swap(a, j, j + 1);
                    ++counter;
                }
            }
        }
        return (counter);
    }

    public static int bubbleSortB(int[] a) {
        int counter = 0;
        for (int i = a.length - 1; i >= 0; --i) {
            for (int j = 0; j < i; ++j) {
                if (a[j] >= a[j + 1]) {
                    swap(a, j, j + 1);
                    ++counter;
                }
            }
        }
        return (counter);
    }

    private static void swap(int[] a, int j, int i) {
        int h = a[i];
        a[i] = a[j];
        a[j] = h;
    }
}

Wie wir sehen können, ist der einzige Unterschied zwischen diesen beiden Sortierverfahren die >vs. >=. Wenn man das Programm mit ausführt java BubbleSortAnnomaly 50000 10 10, würde man offensichtlich erwarten, dass dies sortBlangsamer ist als sortAweil es mehr swap(...)s ausführen muss . Aber ich habe die folgende (oder ähnliche) Ausgabe auf drei verschiedenen Maschinen erhalten:

Sorting with sortA: 4.214 seconds. It used  564960211 swaps.
Sorting with sortB: 2.278 seconds. It used 1249750569 swaps.
Sorting with sortA: 4.199 seconds. It used  563355818 swaps.
Sorting with sortB: 2.254 seconds. It used 1249750348 swaps.
Sorting with sortA: 4.189 seconds. It used  560825110 swaps.
Sorting with sortB: 2.264 seconds. It used 1249749572 swaps.
Sorting with sortA: 4.17  seconds. It used  561924561 swaps.
Sorting with sortB: 2.256 seconds. It used 1249749766 swaps.
Sorting with sortA: 4.198 seconds. It used  562613693 swaps.
Sorting with sortB: 2.266 seconds. It used 1249749880 swaps.
Sorting with sortA: 4.19  seconds. It used  561658723 swaps.
Sorting with sortB: 2.281 seconds. It used 1249751070 swaps.
Sorting with sortA: 4.193 seconds. It used  564986461 swaps.
Sorting with sortB: 2.266 seconds. It used 1249749681 swaps.
Sorting with sortA: 4.203 seconds. It used  562526980 swaps.
Sorting with sortB: 2.27  seconds. It used 1249749609 swaps.
Sorting with sortA: 4.176 seconds. It used  561070571 swaps.
Sorting with sortB: 2.241 seconds. It used 1249749831 swaps.
Sorting with sortA: 4.191 seconds. It used  559883210 swaps.
Sorting with sortB: 2.257 seconds. It used 1249749371 swaps.

Wenn ich den Parameter LIMITauf zB 50000( java BubbleSortAnnomaly 50000 50000 10) setze , erhalte ich die erwarteten Ergebnisse:

Sorting with sortA: 3.983 seconds. It used  625941897 swaps.
Sorting with sortB: 4.658 seconds. It used  789391382 swaps.

Ich habe das Programm nach C ++ portiert, um festzustellen, ob dieses Problem Java-spezifisch ist. Hier ist der C ++ - Code.

#include <cstdlib>
#include <iostream>

#include <omp.h>

#ifndef ARRAY_SIZE
#define ARRAY_SIZE 50000
#endif

#ifndef LIMIT
#define LIMIT 10
#endif

#ifndef RUNS
#define RUNS 10
#endif

void swap(int * a, int i, int j)
{
    int h = a[i];
    a[i] = a[j];
    a[j] = h;
}

int bubbleSortA(int * a)
{
    const int LAST = ARRAY_SIZE - 1;
    int counter = 0;
    for (int i = LAST; 0 < i; --i)
    {
        for (int j = 0; j < i; ++j)
        {
            int next = j + 1;
            if (a[j] > a[next])
            {
                swap(a, j, next);
                ++counter;
            }
        }
    }
    return (counter);
}

int bubbleSortB(int * a)
{
    const int LAST = ARRAY_SIZE - 1;
    int counter = 0;
    for (int i = LAST; 0 < i; --i)
    {
        for (int j = 0; j < i; ++j)
        {
            int next = j + 1;
            if (a[j] >= a[next])
            {
                swap(a, j, next);
                ++counter;
            }
        }
    }
    return (counter);
}

int main()
{
    int * a = (int *) malloc(ARRAY_SIZE * sizeof(int));
    int * b = (int *) malloc(ARRAY_SIZE * sizeof(int));

    for (int run = 0; RUNS > run; ++run)
    {
        for (int idx = 0; ARRAY_SIZE > idx; ++idx)
        {
            a[idx] = std::rand() % LIMIT;
            b[idx] = a[idx];
        }

        std::cout << "Sorting with sortA: ";
        double start = omp_get_wtime();
        int swaps = bubbleSortA(a);

        std::cout << (omp_get_wtime() - start) << " seconds. It used " << swaps
                  << " swaps." << std::endl;

        std::cout << "Sorting with sortB: ";
        start = omp_get_wtime();
        swaps = bubbleSortB(b);

        std::cout << (omp_get_wtime() - start) << " seconds. It used " << swaps
                  << " swaps." << std::endl;
    }

    free(a);
    free(b);

    return (0);
}

Dieses Programm zeigt das gleiche Verhalten. Kann jemand erklären, was genau hier los ist?

sortBErstes Ausführen und dann sortAnichts ändert die Ergebnisse.

Question 2

Ich denke, es kann tatsächlich an der Verzweigungsvorhersage liegen. Wenn Sie die Anzahl der Swaps im Vergleich zur Anzahl der inneren Sortieriterationen zählen, finden Sie:

Limit = 10

A = 560 Millionen Swaps / 1250 Millionen Loops
B = 1250 Millionen Swaps / 1250 Millionen Loops (0,02% weniger Swaps als Loops)

Limit = 50000

A = 627 Millionen Swaps / 1250 Millionen Loops
B = 850 Millionen Swaps / 1250 Millionen Loops

In dem Limit == 10Fall wird der Swap also 99,98% der Zeit in der B-Sortierung durchgeführt, was offensichtlich für den Verzweigungsprädiktor günstig ist. In dem Limit == 50000Fall, dass der Swap nur zufällig zu 68% getroffen wird, ist der Verzweigungsprädiktor weniger vorteilhaft.

Question 3

Ich denke, dies kann in der Tat durch eine falsche Vorhersage der Branche erklärt werden.

Betrachten Sie zum Beispiel LIMIT = 11 und sortB. Bei der ersten Iteration der äußeren Schleife stößt sie sehr schnell auf eines der Elemente gleich 10. Es wird a[j]=10also definitiv a[j]so sein >=a[next], da es keine Elemente gibt, die größer als 10 sind. Daher wird ein Tausch durchgeführt , dann machen Sie nur einen Schritt j, um das a[j]=10wieder zu finden (der gleiche getauschte Wert). So wird es wieder sein a[j]>=a[next], und so eins. Jeder Vergleich mit Ausnahme einiger am Anfang wird wahr sein. Ebenso wird es bei den nächsten Iterationen der äußeren Schleife ausgeführt.

Nicht dasselbe für sortA. Es wird ungefähr auf die gleiche Weise beginnen, stolpern a[j]=10, einige Swaps auf ähnliche Weise durchführen, aber nur bis zu einem Punkt, an dem es auch findet a[next]=10. Dann ist die Bedingung falsch und es wird kein Tausch durchgeführt. a[next]=10Und so weiter: Jedes Mal, wenn es stolpert , ist die Bedingung falsch und es werden keine Swaps durchgeführt. Daher ist diese Bedingung 10 Mal von 11 wahr (Werte a[next]von 0 bis 9) und in 1 Fall von 11 falsch. Nichts Seltsames, dass die Verzweigungsvorhersage fehlschlägt.

Question 4

Unter Verwendung des mit dem perf statBefehl bereitgestellten C ++ - Codes (Zeitzählung entfernt) erhielt ich Ergebnisse, die die Brach-Miss-Theorie bestätigen.

Mit Limit = 10profitiert BubbleSortB stark von der Verzweigungsvorhersage (0,01% Fehler), aber mit der Limit = 50000Verzweigungsvorhersage schlägt die Vorhersage noch mehr fehl (mit 15,65% Fehlern) als bei BubbleSortA (12,69% bzw. 12,76% Fehler).

BubbleSortA Limit = 10:

Performance counter stats for './bubbleA.out':

   46670.947364 task-clock                #    0.998 CPUs utilized          
             73 context-switches          #    0.000 M/sec                  
             28 CPU-migrations            #    0.000 M/sec                  
            379 page-faults               #    0.000 M/sec                  
117,298,787,242 cycles                    #    2.513 GHz                    
117,471,719,598 instructions              #    1.00  insns per cycle        
 25,104,504,912 branches                  #  537.904 M/sec                  
  3,185,376,029 branch-misses             #   12.69% of all branches        

   46.779031563 seconds time elapsed

BubbleSortA Limit = 50000:

Performance counter stats for './bubbleA.out':

   46023.785539 task-clock                #    0.998 CPUs utilized          
             59 context-switches          #    0.000 M/sec                  
              8 CPU-migrations            #    0.000 M/sec                  
            379 page-faults               #    0.000 M/sec                  
118,261,821,200 cycles                    #    2.570 GHz                    
119,230,362,230 instructions              #    1.01  insns per cycle        
 25,089,204,844 branches                  #  545.136 M/sec                  
  3,200,514,556 branch-misses             #   12.76% of all branches        

   46.126274884 seconds time elapsed

BubbleSortB Limit = 10:

Performance counter stats for './bubbleB.out':

   26091.323705 task-clock                #    0.998 CPUs utilized          
             28 context-switches          #    0.000 M/sec                  
              2 CPU-migrations            #    0.000 M/sec                  
            379 page-faults               #    0.000 M/sec                  
 64,822,368,062 cycles                    #    2.484 GHz                    
137,780,774,165 instructions              #    2.13  insns per cycle        
 25,052,329,633 branches                  #  960.179 M/sec                  
      3,019,138 branch-misses             #    0.01% of all branches        

   26.149447493 seconds time elapsed

BubbleSortB-Limit = 50000:

Performance counter stats for './bubbleB.out':

   51644.210268 task-clock                #    0.983 CPUs utilized          
          2,138 context-switches          #    0.000 M/sec                  
             69 CPU-migrations            #    0.000 M/sec                  
            378 page-faults               #    0.000 M/sec                  
144,600,738,759 cycles                    #    2.800 GHz                    
124,273,104,207 instructions              #    0.86  insns per cycle        
 25,104,320,436 branches                  #  486.101 M/sec                  
  3,929,572,460 branch-misses             #   15.65% of all branches        

   52.511233236 seconds time elapsed

Question 5

Bearbeiten 2: Diese Antwort ist wahrscheinlich in den meisten Fällen falsch. Niedriger, wenn ich sage, dass alles oben korrekt ist, ist immer noch wahr, aber der untere Teil gilt nicht für die meisten Prozessorarchitekturen, siehe die Kommentare. Ich werde jedoch sagen, dass es theoretisch immer noch möglich ist , dass es auf einem Betriebssystem / einer Architektur eine JVM gibt, die dies tut, aber dass JVM wahrscheinlich schlecht implementiert ist oder eine seltsame Architektur ist. Dies ist auch theoretisch in dem Sinne möglich, dass die denkbarsten Dinge theoretisch möglich sind, also würde ich die letzte Portion mit einem Körnchen Salz nehmen.

Erstens bin ich mir über C ++ nicht sicher, aber ich kann etwas über Java sprechen.

Hier ist ein Code,

public class Example {

    public static boolean less(final int a, final int b) {
        return a < b;
    }

    public static boolean lessOrEqual(final int a, final int b) {
        return a <= b;
    }
}

Wenn javap -cich darauf laufe, bekomme ich den Bytecode

public class Example {
  public Example();
    Code:
       0: aload_0
       1: invokespecial #8                  // Method java/lang/Object."<init>":()V
       4: return

  public static boolean less(int, int);
    Code:
       0: iload_0
       1: iload_1
       2: if_icmpge     7
       5: iconst_1
       6: ireturn
       7: iconst_0
       8: ireturn

  public static boolean lessOrEqual(int, int);
    Code:
       0: iload_0
       1: iload_1
       2: if_icmpgt     7
       5: iconst_1
       6: ireturn
       7: iconst_0
       8: ireturn
}

Sie werden feststellen, dass der einzige Unterschied if_icmpge(wenn der Vergleich größer / gleich ist) gegenüber if_icmpgt(wenn der Vergleich größer als) ist.

Alles oben Genannte ist eine Tatsache, der Rest ist meine beste Vermutung, wie if_icmpgeund if_icmpgtbasierend auf einem College-Kurs, den ich in Assemblersprache belegt habe, gehandhabt wird. Um eine bessere Antwort zu erhalten, sollten Sie nachschlagen, wie Ihre JVM damit umgeht. Ich vermute, dass C ++ auch bis zu einer ähnlichen Operation kompiliert wird.

Bearbeiten: Dokumentation zu if_i<cond>ist hier

Die Art und Weise Computer vergleichen Zahlen ist eine von dem anderen subtrahiert und prüfen , ob diese Zahl 0 ist oder nicht, so dass , wenn tun , a < bwenn Subtraktionen baus aund sieht , wenn das Ergebnis kleiner als 0 durch das Vorzeichen des Wertes Prüfung ( b - a < 0). Um dies a <= bzu tun, muss ein zusätzlicher Schritt ausgeführt und 1 ( b - a - 1 < 0) subtrahiert werden .

Normalerweise ist dies ein sehr winziger Unterschied, aber das ist nicht irgendein Code, diese Blase Art ist freaking! O (n ^ 2) ist die durchschnittliche Häufigkeit, mit der wir diesen speziellen Vergleich durchführen, da er sich in der innersten Schleife befindet.

Ja, es kann etwas mit der Vorhersage von Zweigen zu tun haben. Ich bin mir nicht sicher, ich bin kein Experte in diesem Bereich, aber ich denke, dass dies auch eine nicht unbedeutende Rolle spielen kann.

Answer 1

Ich bin gerade auf etwas gestoßen. Zuerst dachte ich, es könnte sich um eine Fehlvorhersage für Zweige handeln, wie dies in diesem Fall der Fall ist , aber ich kann nicht erklären, warum eine Fehlvorhersage für Zweige dieses Verhalten verursachen sollte.

Ich habe zwei Versionen von Bubble Sort in Java implementiert und einige Leistungstests durchgeführt:

import java.util.Random;

public class BubbleSortAnnomaly {

    public static void main(String... args) {
        final int ARRAY_SIZE = Integer.parseInt(args[0]);
        final int LIMIT = Integer.parseInt(args[1]);
        final int RUNS = Integer.parseInt(args[2]);

        int[] a = new int[ARRAY_SIZE];
        int[] b = new int[ARRAY_SIZE];
        Random r = new Random();
        for (int run = 0; RUNS > run; ++run) {
            for (int i = 0; i < ARRAY_SIZE; i++) {
                a[i] = r.nextInt(LIMIT);
                b[i] = a[i];
            }

            System.out.print("Sorting with sortA: ");
            long start = System.nanoTime();
            int swaps = bubbleSortA(a);

            System.out.println(  (System.nanoTime() - start) + " ns. "
                               + "It used " + swaps + " swaps.");

            System.out.print("Sorting with sortB: ");
            start = System.nanoTime();
            swaps = bubbleSortB(b);

            System.out.println(  (System.nanoTime() - start) + " ns. "
                               + "It used " + swaps + " swaps.");
        }
    }

    public static int bubbleSortA(int[] a) {
        int counter = 0;
        for (int i = a.length - 1; i >= 0; --i) {
            for (int j = 0; j < i; ++j) {
                if (a[j] > a[j + 1]) {
                    swap(a, j, j + 1);
                    ++counter;
                }
            }
        }
        return (counter);
    }

    public static int bubbleSortB(int[] a) {
        int counter = 0;
        for (int i = a.length - 1; i >= 0; --i) {
            for (int j = 0; j < i; ++j) {
                if (a[j] >= a[j + 1]) {
                    swap(a, j, j + 1);
                    ++counter;
                }
            }
        }
        return (counter);
    }

    private static void swap(int[] a, int j, int i) {
        int h = a[i];
        a[i] = a[j];
        a[j] = h;
    }
}

Wie wir sehen können, ist der einzige Unterschied zwischen diesen beiden Sortierverfahren die >vs. >=. Wenn man das Programm mit ausführt java BubbleSortAnnomaly 50000 10 10, würde man offensichtlich erwarten, dass dies sortBlangsamer ist als sortAweil es mehr swap(...)s ausführen muss . Aber ich habe die folgende (oder ähnliche) Ausgabe auf drei verschiedenen Maschinen erhalten:

Sorting with sortA: 4.214 seconds. It used  564960211 swaps.
Sorting with sortB: 2.278 seconds. It used 1249750569 swaps.
Sorting with sortA: 4.199 seconds. It used  563355818 swaps.
Sorting with sortB: 2.254 seconds. It used 1249750348 swaps.
Sorting with sortA: 4.189 seconds. It used  560825110 swaps.
Sorting with sortB: 2.264 seconds. It used 1249749572 swaps.
Sorting with sortA: 4.17  seconds. It used  561924561 swaps.
Sorting with sortB: 2.256 seconds. It used 1249749766 swaps.
Sorting with sortA: 4.198 seconds. It used  562613693 swaps.
Sorting with sortB: 2.266 seconds. It used 1249749880 swaps.
Sorting with sortA: 4.19  seconds. It used  561658723 swaps.
Sorting with sortB: 2.281 seconds. It used 1249751070 swaps.
Sorting with sortA: 4.193 seconds. It used  564986461 swaps.
Sorting with sortB: 2.266 seconds. It used 1249749681 swaps.
Sorting with sortA: 4.203 seconds. It used  562526980 swaps.
Sorting with sortB: 2.27  seconds. It used 1249749609 swaps.
Sorting with sortA: 4.176 seconds. It used  561070571 swaps.
Sorting with sortB: 2.241 seconds. It used 1249749831 swaps.
Sorting with sortA: 4.191 seconds. It used  559883210 swaps.
Sorting with sortB: 2.257 seconds. It used 1249749371 swaps.

Wenn ich den Parameter LIMITauf zB 50000( java BubbleSortAnnomaly 50000 50000 10) setze , erhalte ich die erwarteten Ergebnisse:

Sorting with sortA: 3.983 seconds. It used  625941897 swaps.
Sorting with sortB: 4.658 seconds. It used  789391382 swaps.

Ich habe das Programm nach C ++ portiert, um festzustellen, ob dieses Problem Java-spezifisch ist. Hier ist der C ++ - Code.

#include <cstdlib>
#include <iostream>

#include <omp.h>

#ifndef ARRAY_SIZE
#define ARRAY_SIZE 50000
#endif

#ifndef LIMIT
#define LIMIT 10
#endif

#ifndef RUNS
#define RUNS 10
#endif

void swap(int * a, int i, int j)
{
    int h = a[i];
    a[i] = a[j];
    a[j] = h;
}

int bubbleSortA(int * a)
{
    const int LAST = ARRAY_SIZE - 1;
    int counter = 0;
    for (int i = LAST; 0 < i; --i)
    {
        for (int j = 0; j < i; ++j)
        {
            int next = j + 1;
            if (a[j] > a[next])
            {
                swap(a, j, next);
                ++counter;
            }
        }
    }
    return (counter);
}

int bubbleSortB(int * a)
{
    const int LAST = ARRAY_SIZE - 1;
    int counter = 0;
    for (int i = LAST; 0 < i; --i)
    {
        for (int j = 0; j < i; ++j)
        {
            int next = j + 1;
            if (a[j] >= a[next])
            {
                swap(a, j, next);
                ++counter;
            }
        }
    }
    return (counter);
}

int main()
{
    int * a = (int *) malloc(ARRAY_SIZE * sizeof(int));
    int * b = (int *) malloc(ARRAY_SIZE * sizeof(int));

    for (int run = 0; RUNS > run; ++run)
    {
        for (int idx = 0; ARRAY_SIZE > idx; ++idx)
        {
            a[idx] = std::rand() % LIMIT;
            b[idx] = a[idx];
        }

        std::cout << "Sorting with sortA: ";
        double start = omp_get_wtime();
        int swaps = bubbleSortA(a);

        std::cout << (omp_get_wtime() - start) << " seconds. It used " << swaps
                  << " swaps." << std::endl;

        std::cout << "Sorting with sortB: ";
        start = omp_get_wtime();
        swaps = bubbleSortB(b);

        std::cout << (omp_get_wtime() - start) << " seconds. It used " << swaps
                  << " swaps." << std::endl;
    }

    free(a);
    free(b);

    return (0);
}

Dieses Programm zeigt das gleiche Verhalten. Kann jemand erklären, was genau hier los ist?

sortBErstes Ausführen und dann sortAnichts ändert die Ergebnisse.

Answer 2

1

Wie haben Sie die Zeit gemessen? Wenn Sie die Zeit nur für einen Fall messen, hängt das Timing stark von den Zufallssequenzen ab und >vs >=hat nur geringe Auswirkungen. Um wirklich aussagekräftige Zahlen für Zeiten zu erhalten, müssen Sie viele verschiedene Sequenzen und Durchschnittswerte messen

größter_prime_is_463035818

Answer 3

@ tobi303 schau dir den Code an. Sie können es in einer Schleife über den 3. Laufzeitparameter (Java) oder -DRUNS=XXX(C ++, Compiler-Direktive) ausführen . Und die Ergebnisse sind reproduzierbar.

Turing85

Answer 4

3

Ihre C ++ - Version wird ain beiden Läufen sortiert (und berührt nicht b).

TC

Answer 5

@TC Danke, den Tippfehler korrigiert.

Turing85

Answer 6

Es wäre interessant, die Anzahl der Swaps in beiden Fällen zu zählen, um zu sehen, wie sich dies auf die Laufzeit auswirkt. Ich meine, falls A langsamer ist, liegt dies definitiv nicht an der Anzahl der Swaps. Wenn A also schneller ist, liegt der Grund möglicherweise nicht nur in der Anzahl der Swaps, sondern auch in subtileren Effekten

größter_prime_is_463035818

Answer 7

45

Ich denke, es kann tatsächlich an der Verzweigungsvorhersage liegen. Wenn Sie die Anzahl der Swaps im Vergleich zur Anzahl der inneren Sortieriterationen zählen, finden Sie:

Limit = 10

A = 560 Millionen Swaps / 1250 Millionen Loops
B = 1250 Millionen Swaps / 1250 Millionen Loops (0,02% weniger Swaps als Loops)

Limit = 50000

A = 627 Millionen Swaps / 1250 Millionen Loops
B = 850 Millionen Swaps / 1250 Millionen Loops

In dem Limit == 10Fall wird der Swap also 99,98% der Zeit in der B-Sortierung durchgeführt, was offensichtlich für den Verzweigungsprädiktor günstig ist. In dem Limit == 50000Fall, dass der Swap nur zufällig zu 68% getroffen wird, ist der Verzweigungsprädiktor weniger vorteilhaft.

uesp
quelle

2

Ihr Argument scheint vernünftig. Gibt es eine Möglichkeit, Ihre Hypothese zu testen?

Turing85

1

Eine schnelle Antwort besteht darin, die Eingabearrays so zu steuern, dass die Sortierungen für A / B dieselben Swaps in derselben Reihenfolge ausführen (zumindest grob). Wie das genau geht, weiß ich nicht. Sie können auch sehen, wie zufällig die Swap-Reihenfolge "irgendwie" ist und ob dies mit den Sortierzeiten korreliert.

uesp

1

Für Fälle, in denen LIMIT >= ARRAY_SIZESie einen Testfall durchführen können, in dem das Array aus eindeutigen Zahlen besteht. Zum Beispiel, wenn a[i] = ARRAY_SIZE - iSie einen Swap für jede Schleife und identische Zeiten für die A / B-Sortierungen erhalten.

uesp

@ Turing85, beachte, dass meine Antwort tatsächlich erklärt, warum dieser Unterschied in der Anzahl der Swaps liegt.

Petr

@Petr warum es eine größere Anzahl von Swaps gibt, war für mich offensichtlich. Ich war einfach nicht in der Lage, diese Tatsache mit der Fehlvorhersage der Branche zu korrelieren. Und die gewählte Antwort gab (in meinen Augen) die beste Erklärung mit der besten Argumentation.

Turing85

Answer 8

2

Ihr Argument scheint vernünftig. Gibt es eine Möglichkeit, Ihre Hypothese zu testen?

Turing85

Answer 9

1

Eine schnelle Antwort besteht darin, die Eingabearrays so zu steuern, dass die Sortierungen für A / B dieselben Swaps in derselben Reihenfolge ausführen (zumindest grob). Wie das genau geht, weiß ich nicht. Sie können auch sehen, wie zufällig die Swap-Reihenfolge "irgendwie" ist und ob dies mit den Sortierzeiten korreliert.

uesp

Answer 10

1

Für Fälle, in denen LIMIT >= ARRAY_SIZESie einen Testfall durchführen können, in dem das Array aus eindeutigen Zahlen besteht. Zum Beispiel, wenn a[i] = ARRAY_SIZE - iSie einen Swap für jede Schleife und identische Zeiten für die A / B-Sortierungen erhalten.

uesp

Answer 11

@ Turing85, beachte, dass meine Antwort tatsächlich erklärt, warum dieser Unterschied in der Anzahl der Swaps liegt.

Petr

Answer 12

@Petr warum es eine größere Anzahl von Swaps gibt, war für mich offensichtlich. Ich war einfach nicht in der Lage, diese Tatsache mit der Fehlvorhersage der Branche zu korrelieren. Und die gewählte Antwort gab (in meinen Augen) die beste Erklärung mit der besten Argumentation.

Turing85

Answer 13

Ich denke, dies kann in der Tat durch eine falsche Vorhersage der Branche erklärt werden.

Betrachten Sie zum Beispiel LIMIT = 11 und sortB. Bei der ersten Iteration der äußeren Schleife stößt sie sehr schnell auf eines der Elemente gleich 10. Es wird a[j]=10also definitiv a[j]so sein >=a[next], da es keine Elemente gibt, die größer als 10 sind. Daher wird ein Tausch durchgeführt , dann machen Sie nur einen Schritt j, um das a[j]=10wieder zu finden (der gleiche getauschte Wert). So wird es wieder sein a[j]>=a[next], und so eins. Jeder Vergleich mit Ausnahme einiger am Anfang wird wahr sein. Ebenso wird es bei den nächsten Iterationen der äußeren Schleife ausgeführt.

Nicht dasselbe für sortA. Es wird ungefähr auf die gleiche Weise beginnen, stolpern a[j]=10, einige Swaps auf ähnliche Weise durchführen, aber nur bis zu einem Punkt, an dem es auch findet a[next]=10. Dann ist die Bedingung falsch und es wird kein Tausch durchgeführt. a[next]=10Und so weiter: Jedes Mal, wenn es stolpert , ist die Bedingung falsch und es werden keine Swaps durchgeführt. Daher ist diese Bedingung 10 Mal von 11 wahr (Werte a[next]von 0 bis 9) und in 1 Fall von 11 falsch. Nichts Seltsames, dass die Verzweigungsvorhersage fehlschlägt.

Answer 14

Unter Verwendung des mit dem perf statBefehl bereitgestellten C ++ - Codes (Zeitzählung entfernt) erhielt ich Ergebnisse, die die Brach-Miss-Theorie bestätigen.

Mit Limit = 10profitiert BubbleSortB stark von der Verzweigungsvorhersage (0,01% Fehler), aber mit der Limit = 50000Verzweigungsvorhersage schlägt die Vorhersage noch mehr fehl (mit 15,65% Fehlern) als bei BubbleSortA (12,69% bzw. 12,76% Fehler).

BubbleSortA Limit = 10:

Performance counter stats for './bubbleA.out':

   46670.947364 task-clock                #    0.998 CPUs utilized          
             73 context-switches          #    0.000 M/sec                  
             28 CPU-migrations            #    0.000 M/sec                  
            379 page-faults               #    0.000 M/sec                  
117,298,787,242 cycles                    #    2.513 GHz                    
117,471,719,598 instructions              #    1.00  insns per cycle        
 25,104,504,912 branches                  #  537.904 M/sec                  
  3,185,376,029 branch-misses             #   12.69% of all branches        

   46.779031563 seconds time elapsed

BubbleSortA Limit = 50000:

Performance counter stats for './bubbleA.out':

   46023.785539 task-clock                #    0.998 CPUs utilized          
             59 context-switches          #    0.000 M/sec                  
              8 CPU-migrations            #    0.000 M/sec                  
            379 page-faults               #    0.000 M/sec                  
118,261,821,200 cycles                    #    2.570 GHz                    
119,230,362,230 instructions              #    1.01  insns per cycle        
 25,089,204,844 branches                  #  545.136 M/sec                  
  3,200,514,556 branch-misses             #   12.76% of all branches        

   46.126274884 seconds time elapsed

BubbleSortB Limit = 10:

Performance counter stats for './bubbleB.out':

   26091.323705 task-clock                #    0.998 CPUs utilized          
             28 context-switches          #    0.000 M/sec                  
              2 CPU-migrations            #    0.000 M/sec                  
            379 page-faults               #    0.000 M/sec                  
 64,822,368,062 cycles                    #    2.484 GHz                    
137,780,774,165 instructions              #    2.13  insns per cycle        
 25,052,329,633 branches                  #  960.179 M/sec                  
      3,019,138 branch-misses             #    0.01% of all branches        

   26.149447493 seconds time elapsed

BubbleSortB-Limit = 50000:

Performance counter stats for './bubbleB.out':

   51644.210268 task-clock                #    0.983 CPUs utilized          
          2,138 context-switches          #    0.000 M/sec                  
             69 CPU-migrations            #    0.000 M/sec                  
            378 page-faults               #    0.000 M/sec                  
144,600,738,759 cycles                    #    2.800 GHz                    
124,273,104,207 instructions              #    0.86  insns per cycle        
 25,104,320,436 branches                  #  486.101 M/sec                  
  3,929,572,460 branch-misses             #   15.65% of all branches        

   52.511233236 seconds time elapsed

Answer 15

Bearbeiten 2: Diese Antwort ist wahrscheinlich in den meisten Fällen falsch. Niedriger, wenn ich sage, dass alles oben korrekt ist, ist immer noch wahr, aber der untere Teil gilt nicht für die meisten Prozessorarchitekturen, siehe die Kommentare. Ich werde jedoch sagen, dass es theoretisch immer noch möglich ist , dass es auf einem Betriebssystem / einer Architektur eine JVM gibt, die dies tut, aber dass JVM wahrscheinlich schlecht implementiert ist oder eine seltsame Architektur ist. Dies ist auch theoretisch in dem Sinne möglich, dass die denkbarsten Dinge theoretisch möglich sind, also würde ich die letzte Portion mit einem Körnchen Salz nehmen.

Erstens bin ich mir über C ++ nicht sicher, aber ich kann etwas über Java sprechen.

Hier ist ein Code,

public class Example {

    public static boolean less(final int a, final int b) {
        return a < b;
    }

    public static boolean lessOrEqual(final int a, final int b) {
        return a <= b;
    }
}

Wenn javap -cich darauf laufe, bekomme ich den Bytecode

public class Example {
  public Example();
    Code:
       0: aload_0
       1: invokespecial #8                  // Method java/lang/Object."<init>":()V
       4: return

  public static boolean less(int, int);
    Code:
       0: iload_0
       1: iload_1
       2: if_icmpge     7
       5: iconst_1
       6: ireturn
       7: iconst_0
       8: ireturn

  public static boolean lessOrEqual(int, int);
    Code:
       0: iload_0
       1: iload_1
       2: if_icmpgt     7
       5: iconst_1
       6: ireturn
       7: iconst_0
       8: ireturn
}

Sie werden feststellen, dass der einzige Unterschied if_icmpge(wenn der Vergleich größer / gleich ist) gegenüber if_icmpgt(wenn der Vergleich größer als) ist.

Alles oben Genannte ist eine Tatsache, der Rest ist meine beste Vermutung, wie if_icmpgeund if_icmpgtbasierend auf einem College-Kurs, den ich in Assemblersprache belegt habe, gehandhabt wird. Um eine bessere Antwort zu erhalten, sollten Sie nachschlagen, wie Ihre JVM damit umgeht. Ich vermute, dass C ++ auch bis zu einer ähnlichen Operation kompiliert wird.

Bearbeiten: Dokumentation zu if_i<cond>ist hier

Die Art und Weise Computer vergleichen Zahlen ist eine von dem anderen subtrahiert und prüfen , ob diese Zahl 0 ist oder nicht, so dass , wenn tun , a < bwenn Subtraktionen baus aund sieht , wenn das Ergebnis kleiner als 0 durch das Vorzeichen des Wertes Prüfung ( b - a < 0). Um dies a <= bzu tun, muss ein zusätzlicher Schritt ausgeführt und 1 ( b - a - 1 < 0) subtrahiert werden .

Normalerweise ist dies ein sehr winziger Unterschied, aber das ist nicht irgendein Code, diese Blase Art ist freaking! O (n ^ 2) ist die durchschnittliche Häufigkeit, mit der wir diesen speziellen Vergleich durchführen, da er sich in der innersten Schleife befindet.

Ja, es kann etwas mit der Vorhersage von Zweigen zu tun haben. Ich bin mir nicht sicher, ich bin kein Experte in diesem Bereich, aber ich denke, dass dies auch eine nicht unbedeutende Rolle spielen kann.

Answer 16

Ich glaube nicht, dass Sie Recht haben <, schneller zu sein als <=. Prozessoranweisungen werden diskretisiert; Jeder Befehl muss eine ganzzahlige Anzahl von Taktzyklen benötigen - es wird keine "Zeit gespart", es sei denn, Sie können eine ganze Uhr herausdrücken. Siehe stackoverflow.com/a/12135533

kevinsa5

Answer 17

Beachten Sie, dass ich nur über nativen Code spreche. Ich nehme an, es ist möglich, dass eine JVM-Implementierung diese "Optimierung" durchführt, aber ich würde vermuten, dass sie nur die nativen Anweisungen verwendet, anstatt eine eigene Lösung zu entwickeln. Aber das ist nur eine Vermutung.

Kevinsa5

Answer 18

4

Worauf stützen Sie Ihre Behauptung, dass <= einen zusätzlichen Schritt verwendet, um eine zusätzliche 1 zu subtrahieren? Auf der x86-Ebene dauert beispielsweise ein cmpgefolgt von a jlgenau so lange, wie es eine erfolgreiche Verzweigungsvorhersage zulässt, cmpgefolgt von einem jle. stackoverflow.com/questions/12135518/is-faster-than enthält weitere Details.

ClickRick

Answer 19

@ClickRick Die Assembly, die ich gelernt habe, war für SPARC, das einen reduzierten Befehlssatz verwendete. Vielleicht hatte es nicht jle? Oder vielleicht habe ich diese falsche Annahme auch irgendwo gehört. Ich bin mir nicht 100% sicher, woher ich das jetzt habe, da ich es wirklich in Betracht ziehe. Ich nehme theoretisch an, dass die Interpretation der JVM eines bestimmten Betriebssystems / einer bestimmten Architektur einen Unterschied machen könnte, aber ich würde jetzt annehmen, dass alle dies in einem einzigen Zyklus tun.

Captain Man

Answer 20

2

@CaptainMan Laut cs.northwestern.edu/~agupta/_projects/sparc_simulator/… unterstützt der SPARC sowohl blals auch bleAnweisungen, was für mich völlig überraschend ist.

ClickRick

> vs.> = bei der Blasensortierung verursacht einen signifikanten Leistungsunterschied

Antworten: