> vs> = en la clasificación de burbujas provoca una diferencia de rendimiento significativa

Question 1

Me encontré con algo. Al principio pensé que podría ser un caso de predicción errónea de rama como es en este caso , pero no puedo explicar por qué la predicción errónea de la rama debería causar este comportamiento.

Implementé dos versiones de Bubble Sort en Java e hice algunas pruebas de rendimiento:

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

Como podemos ver, la única diferencia entre los dos métodos de clasificación es el >frente >=. Cuando se ejecuta el programa con java BubbleSortAnnomaly 50000 10 10, obviamente se esperaría que sortBsea más lento que sortAporque tiene que ejecutar más swap(...)s. Pero obtuve la siguiente salida (o similar) en tres máquinas diferentes:

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.

Cuando configuro el parámetro para LIMIT, por ejemplo, 50000( java BubbleSortAnnomaly 50000 50000 10), obtengo los resultados esperados:

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

Porté el programa a C ++ para determinar si este problema es específico de Java. Aquí está el código C ++.

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

Este programa muestra el mismo comportamiento. ¿Alguien puede explicar qué está pasando exactamente aquí?

Ejecutar sortBprimero y luego sortAno cambia los resultados.

Question 2

Creo que de hecho puede deberse a la predicción de ramas. Si cuenta el número de intercambios en comparación con el número de iteraciones de ordenación interna, encontrará:

Límite = 10

A = 560 millones de intercambios / 1250 millones de bucles
B = 1250M intercambios / 1250M bucles (0.02% menos intercambios que bucles)

Límite = 50000

A = 627 millones de intercambios / 1250 millones de bucles
B = 850 millones de intercambios / 1250 millones de bucles

Entonces, en el Limit == 10caso de que el swap se realice el 99,98% del tiempo en el tipo B, lo que obviamente es favorable para el predictor de sucursales. En el Limit == 50000caso de que el swap solo se golpee aleatoriamente en un 68%, el predictor de sucursales es menos beneficioso.

Question 3

Creo que, de hecho, esto puede explicarse por una mala predicción de las ramas.

Considere, por ejemplo, LIMIT = 11 y sortB. En la primera iteración del bucle externo, se topará muy rápidamente con uno de los elementos igual a 10. Por lo tanto, tendrá a[j]=10, y por lo tanto definitivamente a[j]lo será >=a[next], ya que no hay elementos que sean mayores que 10. Por lo tanto, realizará un intercambio , luego da un paso jsolo para encontrar eso a[j]=10una vez más (el mismo valor intercambiado). Así que una vez más seráa[j]>=a[next] , y así uno. Todas las comparaciones, excepto algunas al principio, serán ciertas. De manera similar, se ejecutará en las próximas iteraciones del ciclo externo.

No es lo mismo para sortA. Comenzará aproximadamente de la misma manera, tropezará a[j]=10, hará algunos intercambios de manera similar, pero solo hasta un punto en el que a[next]=10también lo encuentre . Entonces la condición será falsa y no se realizará ningún intercambio. Y así sucesivamente: cada vez que se tropieza a[next]=10, la condición es falsa y no se realizan intercambios. Por lo tanto, esta condición es verdadera 10 de 11 veces (valores de a[next]0 a 9) y falsa en 1 caso de 11. No hay nada extraño en que falle la predicción de rama.

Question 4

Usando el código C ++ provisto (el conteo de tiempo eliminado) con el perf stat comando obtuve resultados que confirman la teoría de brach-miss.

Con Limit = 10, BubbleSortB se beneficia enormemente de la predicción de rama (0,01% de fallos) pero con la Limit = 50000predicción de rama falla aún más (con 15,65% de fallos) que en BubbleSortA (12,69% y 12,76% de fallos respectivamente).

Límite de BubbleSortA = 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

Límite de BubbleSortA = 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

Límite de BubbleSortB = 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

Límite de BubbleSortB = 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

Edición 2: esta respuesta probablemente sea incorrecta en la mayoría de los casos, más baja cuando digo que todo lo anterior es correcto sigue siendo cierto, pero la parte inferior no es cierta para la mayoría de las arquitecturas de procesador, consulte los comentarios. Sin embargo, diré que todavía es teóricamente posible que exista alguna JVM en algún SO / Arquitectura que haga esto, pero que la JVM probablemente esté mal implementada o sea una arquitectura extraña. Además, esto es teóricamente posible en el sentido de que la mayoría de las cosas concebibles son teóricamente posibles, por lo que tomaría la última porción con un grano de sal.

Primero, no estoy seguro sobre C ++, pero puedo hablar un poco sobre Java.

Aquí hay un código

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

Al ejecutarlo javap -c, obtengo el código de bytes

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
}

Notará que la única diferencia es if_icmpge(si compara mayor / igual) versusif_icmpgt (si compara mayor que).

Todo lo anterior es hecho, el resto es mi mejor conjetura en cuanto a la forma if_icmpgey if_icmpgtse manejan en base a una universidad curso que tomé en lenguaje ensamblador. Para obtener una mejor respuesta, debe buscar cómo su JVM los maneja. Supongo que C ++ también se compila en una operación similar.

Editar: la documentación if_i<cond>está aquí

Los ordenadores manera se comparan los números restando uno del otro y comprobando si ese número es 0 o no, por lo que al hacer a < bsi resta bde ay ve si el resultado es menor que 0 comprobando el signo del valor de ( b - a < 0). Para hacerlo a <= bhay que hacer un paso adicional y restar 1 ( b - a - 1 < 0).

Normalmente, esta es una diferencia muy minúscula, pero esto no es ningún código, ¡es un maldito tipo de burbuja! O (n ^ 2) es el número promedio de veces que estamos haciendo esta comparación en particular porque está en el bucle más interno.

Sí, puede que tenga algo que ver con la predicción de ramas. No estoy seguro, no soy un experto en eso, pero creo que esto también puede desempeñar un papel importante.

Answer 1

Me encontré con algo. Al principio pensé que podría ser un caso de predicción errónea de rama como es en este caso , pero no puedo explicar por qué la predicción errónea de la rama debería causar este comportamiento.

Implementé dos versiones de Bubble Sort en Java e hice algunas pruebas de rendimiento:

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

Como podemos ver, la única diferencia entre los dos métodos de clasificación es el >frente >=. Cuando se ejecuta el programa con java BubbleSortAnnomaly 50000 10 10, obviamente se esperaría que sortBsea más lento que sortAporque tiene que ejecutar más swap(...)s. Pero obtuve la siguiente salida (o similar) en tres máquinas diferentes:

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.

Cuando configuro el parámetro para LIMIT, por ejemplo, 50000( java BubbleSortAnnomaly 50000 50000 10), obtengo los resultados esperados:

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

Porté el programa a C ++ para determinar si este problema es específico de Java. Aquí está el código C ++.

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

Este programa muestra el mismo comportamiento. ¿Alguien puede explicar qué está pasando exactamente aquí?

Ejecutar sortBprimero y luego sortAno cambia los resultados.

Answer 2

1

¿Cómo mediste el tiempo? Si mide el tiempo solo para un caso, el tiempo dependerá en gran medida de las secuencias aleatorias y >vs >=tendrá un impacto menor. Para obtener números muy significativos para los tiempos que tiene que medir muchos diferentes secuencias y media

largest_prime_is_463035818

Answer 3

@ tobi303 mira el código. Puede ejecutarlo en un bucle a través del tercer parámetro de tiempo de ejecución (Java) o -DRUNS=XXX(C ++, directiva del compilador). Y los resultados son reproducibles.

Turing85

Answer 4

Sería interesante contar el número de intercambios en ambos casos para ver cómo esto se relaciona con el tiempo de ejecución. Quiero decir, en caso de que A sea más lento, esto definitivamente no se debe a la cantidad de intercambios, por lo que tal vez en caso de que A sea más rápido, la razón tampoco es simplemente la cantidad de intercambios, sino algunos efectos más sutiles

larger_prime_is_463035818

Answer 5

@ Turing85: ¿Pero volviste a realizar la prueba?

user2357112 apoya a Monica

Answer 6

También sería interesante ver si los resultados se mantienen al llamar bubbleSortB()primero y luego bubbleSortA(). Con Java, a menudo sospecho que la asignación de memoria y gc provocan resultados inesperados. Aunque obtener los mismos resultados en C ++ sugeriría que algo más general está sucediendo aquí.

Kevin Condon

Answer 7

45

Creo que de hecho puede deberse a la predicción de ramas. Si cuenta el número de intercambios en comparación con el número de iteraciones de ordenación interna, encontrará:

Límite = 10

A = 560 millones de intercambios / 1250 millones de bucles
B = 1250M intercambios / 1250M bucles (0.02% menos intercambios que bucles)

Límite = 50000

A = 627 millones de intercambios / 1250 millones de bucles
B = 850 millones de intercambios / 1250 millones de bucles

Entonces, en el Limit == 10caso de que el swap se realice el 99,98% del tiempo en el tipo B, lo que obviamente es favorable para el predictor de sucursales. En el Limit == 50000caso de que el swap solo se golpee aleatoriamente en un 68%, el predictor de sucursales es menos beneficioso.

uesp
fuente

2

Tu argumento parece sensato. ¿Hay alguna forma de probar tu hipótesis?

Turing85

1

La respuesta rápida es controlar las matrices de entrada a algo tal que las clases para A / B hagan los mismos intercambios en el mismo orden (al menos aproximadamente). No sé exactamente cómo hacer esto. También puede ver qué tan aleatorio es el orden de intercambio "de alguna manera" y ver si eso se correlaciona con los tiempos de clasificación.

uesp

1

Para los casos en los LIMIT >= ARRAY_SIZEque puede realizar un caso de prueba en el que la matriz se compone de números únicos. Por ejemplo, en el caso de a[i] = ARRAY_SIZE - ique obtenga un intercambio en cada bucle y tiempos idénticos para las clases A / B.

uesp

@ Turing85, tenga en cuenta que mi respuesta de hecho explica por qué es esta diferencia en el número de intercambios.

Petr

@Petr, por qué hay una mayor cantidad de intercambios fue obvio para mí. Simplemente no pude correlacionar este hecho con la predicción errónea de la rama. Y la respuesta elegida dio (a mi modo de ver) la mejor explicación con la mejor argumentación.

Turing85

Answer 8

2

Tu argumento parece sensato. ¿Hay alguna forma de probar tu hipótesis?

Turing85

Answer 9

1

La respuesta rápida es controlar las matrices de entrada a algo tal que las clases para A / B hagan los mismos intercambios en el mismo orden (al menos aproximadamente). No sé exactamente cómo hacer esto. También puede ver qué tan aleatorio es el orden de intercambio "de alguna manera" y ver si eso se correlaciona con los tiempos de clasificación.

uesp

Answer 10

1

Para los casos en los LIMIT >= ARRAY_SIZEque puede realizar un caso de prueba en el que la matriz se compone de números únicos. Por ejemplo, en el caso de a[i] = ARRAY_SIZE - ique obtenga un intercambio en cada bucle y tiempos idénticos para las clases A / B.

uesp

Answer 11

@ Turing85, tenga en cuenta que mi respuesta de hecho explica por qué es esta diferencia en el número de intercambios.

Petr

Answer 12

@Petr, por qué hay una mayor cantidad de intercambios fue obvio para mí. Simplemente no pude correlacionar este hecho con la predicción errónea de la rama. Y la respuesta elegida dio (a mi modo de ver) la mejor explicación con la mejor argumentación.

Turing85

Answer 13

Creo que, de hecho, esto puede explicarse por una mala predicción de las ramas.

Considere, por ejemplo, LIMIT = 11 y sortB. En la primera iteración del bucle externo, se topará muy rápidamente con uno de los elementos igual a 10. Por lo tanto, tendrá a[j]=10, y por lo tanto definitivamente a[j]lo será >=a[next], ya que no hay elementos que sean mayores que 10. Por lo tanto, realizará un intercambio , luego da un paso jsolo para encontrar eso a[j]=10una vez más (el mismo valor intercambiado). Así que una vez más seráa[j]>=a[next] , y así uno. Todas las comparaciones, excepto algunas al principio, serán ciertas. De manera similar, se ejecutará en las próximas iteraciones del ciclo externo.

No es lo mismo para sortA. Comenzará aproximadamente de la misma manera, tropezará a[j]=10, hará algunos intercambios de manera similar, pero solo hasta un punto en el que a[next]=10también lo encuentre . Entonces la condición será falsa y no se realizará ningún intercambio. Y así sucesivamente: cada vez que se tropieza a[next]=10, la condición es falsa y no se realizan intercambios. Por lo tanto, esta condición es verdadera 10 de 11 veces (valores de a[next]0 a 9) y falsa en 1 caso de 11. No hay nada extraño en que falle la predicción de rama.

Answer 14

Usando el código C ++ provisto (el conteo de tiempo eliminado) con el perf stat comando obtuve resultados que confirman la teoría de brach-miss.

Con Limit = 10, BubbleSortB se beneficia enormemente de la predicción de rama (0,01% de fallos) pero con la Limit = 50000predicción de rama falla aún más (con 15,65% de fallos) que en BubbleSortA (12,69% y 12,76% de fallos respectivamente).

Límite de BubbleSortA = 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

Límite de BubbleSortA = 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

Límite de BubbleSortB = 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

Límite de BubbleSortB = 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

Edición 2: esta respuesta probablemente sea incorrecta en la mayoría de los casos, más baja cuando digo que todo lo anterior es correcto sigue siendo cierto, pero la parte inferior no es cierta para la mayoría de las arquitecturas de procesador, consulte los comentarios. Sin embargo, diré que todavía es teóricamente posible que exista alguna JVM en algún SO / Arquitectura que haga esto, pero que la JVM probablemente esté mal implementada o sea una arquitectura extraña. Además, esto es teóricamente posible en el sentido de que la mayoría de las cosas concebibles son teóricamente posibles, por lo que tomaría la última porción con un grano de sal.

Primero, no estoy seguro sobre C ++, pero puedo hablar un poco sobre Java.

Aquí hay un código

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

Al ejecutarlo javap -c, obtengo el código de bytes

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
}

Notará que la única diferencia es if_icmpge(si compara mayor / igual) versusif_icmpgt (si compara mayor que).

Todo lo anterior es hecho, el resto es mi mejor conjetura en cuanto a la forma if_icmpgey if_icmpgtse manejan en base a una universidad curso que tomé en lenguaje ensamblador. Para obtener una mejor respuesta, debe buscar cómo su JVM los maneja. Supongo que C ++ también se compila en una operación similar.

Editar: la documentación if_i<cond>está aquí

Los ordenadores manera se comparan los números restando uno del otro y comprobando si ese número es 0 o no, por lo que al hacer a < bsi resta bde ay ve si el resultado es menor que 0 comprobando el signo del valor de ( b - a < 0). Para hacerlo a <= bhay que hacer un paso adicional y restar 1 ( b - a - 1 < 0).

Normalmente, esta es una diferencia muy minúscula, pero esto no es ningún código, ¡es un maldito tipo de burbuja! O (n ^ 2) es el número promedio de veces que estamos haciendo esta comparación en particular porque está en el bucle más interno.

Sí, puede que tenga algo que ver con la predicción de ramas. No estoy seguro, no soy un experto en eso, pero creo que esto también puede desempeñar un papel importante.

Answer 16

No creo que tengas razón sobre <ser más rápido que <=. Las instrucciones del procesador están discretizadas; cada instrucción debe tomar un número entero de ciclos de reloj; no hay "tiempo ahorrado" a menos que pueda exprimir un reloj completo. Ver stackoverflow.com/a/12135533

kevinsa 5

Answer 17

Tenga en cuenta que estoy hablando solo de código nativo. Supongo que es posible que una implementación de JVM pueda realizar esa "optimización", pero supongo que solo usaría las instrucciones nativas en lugar de preparar su propia solución. Pero eso es solo una suposición.

kevinsa5

Answer 18

4

¿En qué basa su afirmación de que <= usa un paso adicional para restar un 1 adicional? En el nivel x86, por ejemplo, a cmpseguido de a jltomará exactamente la misma cantidad de tiempo, si la predicción de bifurcación exitosa lo permite, cmpseguido de a jle. stackoverflow.com/questions/12135518/is-faster-than tiene más detalles.

ClickRick

Answer 19

@ClickRick El ensamblaje que aprendí fue para SPARC que usaba un conjunto de instrucciones reducido. ¿Quizás no tenía jle? O tal vez también escuché esta falsa suposición en alguna parte. No estoy 100% seguro de dónde saqué esto ahora que realmente lo considero. Sin embargo, supongo teóricamente que la interpretación de la JVM de cualquier sistema operativo / arquitectura en particular podría hacer alguna diferencia, pero ahora supongo que todos hacen esto en un solo ciclo.

Captain Man

Answer 20

2

@CaptainMan De acuerdo con cs.northwestern.edu/~agupta/_projects/sparc_simulator/… el SPARC es compatible con instrucciones bly ble, lo cual no me sorprende en absoluto.

ClickRick

> vs> = en la clasificación de burbujas provoca una diferencia de rendimiento significativa

Respuestas: