¿Por qué un ciclo de búsqueda de matrices de enteros es más lento en C++que en Java?

performance visual-c++

Question

Tengo el mismo programa escrito en C ++ y Java. Para C ++ estoy usando VS 2019 y para Java usando Eclipse 2019-03.

Aquí está el programa en C ++.

#define InputSize 500000

int FindDuplicate::FindDuplicateNaive(int* input, int size)
{
    int j;
    for (int i = 0; i < size-1; i++)
    {
        for ( j= i+1; j < size; j++)
        {
            if (input[i] == input[j])
                return input[i];
        }
    }
    return -1;
}

int* FindDuplicate::CreateTestCase(int size)
{
    int* output = new int[size];
    int i;
    for ( i= 0; i < size-1; i++)
    {
        output[i] = i + 1;
    }
    output[i] = i;
    return output;
}

int main()
{

    int* input= FindDuplicate::CreateTestCase(InputSize);
    auto start = std::chrono::system_clock::now();//clock start 
    int output = FindDuplicate::FindDuplicateNaive(input, InputSize);
    auto end = std::chrono::system_clock::now();//clock end
    cout<<"Output is: "<<output<<endl;
    std::chrono::duration<double> elapsed_seconds = end - start;
    cout<< "elapsed time: " << elapsed_seconds.count() << "s/n";

}

Aquí está el programa de Java ...

public class FindDuplicate {

public static int FindDuplicateNaive(int[] input) {
    for (int i = 0; i < input.length - 1; i++) {
        for (int j = i + 1; j < input.length; j++) {
            if (input[i] == input[j])
                return input[i];
        }
    }
    return -1;
}

    public static int[] CreateTestCase(int n) {
    // 1, 2, 3, 4, 5, 1 = n = 6
    int[] output = new int[n];
    int i;
    for (i = 0; i < n - 1; i++) {
        output[i] = i + 1;
    }
    output[i] = i;
    return output;
}
    public static void main(String[] args) 
{
    //Here also args[0] is 5,00,000
    int number = Integer.parseInt(args[0]);

    int[] input = CreateTestCase(number);

    long start = System.currentTimeMillis();

    int output = FindDuplicateNaive(input);

    long end = System.currentTimeMillis();

    System.out.println("Total time taken is: " + (end - start) / 1000.0 + " secs");

    System.out.println(output);
}

Te sorprenderá saber que el mismo tiempo que toma el mismo programa la misma entrada tanto en c ++ como en Java.

En Java:

El tiempo tomado es de 41.876 seg.
499999

En CPP:

Después de habilitar la optimización y en modo de lanzamiento,

La salida es: 499999
tiempo transcurrido: 64.0293s

Cualquier pensamiento sobre esto, ¿cuál podría ser la razón? ¿Por qué Java está tomando 41.876 segundos mientras que CPP toma 64.0293 segundos?

Answer 1

Dado que la vectorización no puede realizarse fácilmente, la mayor parte del tiempo se pasa en el control de bucle.
Gracias al uso de #pragma GCC unroll N en el bucle interno, que ayuda a investigar, el desenrollado del bucle proporciona una explicación de los resultados del OP.

Obtengo estos resultados promedio (consola excluida de los tiempos):

gcc 8.3, -03, unroll 64    1.63s
gcc 8.3, -03, unroll 32    1.66s
gcc 8.3, -03, unroll 16    1.71s
gcc 8.3, -03, unroll 8     1.81s
gcc 8.3, -03, unroll 4     1.97s
gcc 8.3, -03, unroll 2     2.33s
gcc 8.3, -03, no unroll    3.06s
openjdk 10.0.2             1.93s

edición: estas pruebas se ejecutaron con InputSize = 100''000 como en la pregunta original (se cambió a 500''000 después)

Answer 2

Esta no es una respuesta completa, no puedo explicar por qué en realidad se ejecuta más rápido en Java que en C ++; pero puedo explicar un par de cosas que retienen el rendimiento de la versión de C ++. No seleccione esta como la respuesta correcta en caso de que alguien tenga una explicación real de la diferencia total en el rendimiento.

Esta respuesta ha sido discutida en meta y acordó que dejarla como una respuesta parcial es la mejor opción.

Primero y más importante, como mencionan otros en los comentarios, el código Java ya está optimizado cuando lo prueba, mientras que en C ++ debe especificar el nivel de optimización como un argumento de la línea de comandos (desde el estudio visual ide compile as release), y mientras esto mucha diferencia, en mis pruebas Java todavía está en la parte superior (todos los resultados en la parte inferior).

Pero quiero señalar una falla importante en su prueba, que puede parecer poco significativa en este caso específico, ya que hace poca diferencia cuando se miran los números, pero sigue siendo importante: las operaciones de entrada-salida agregan demoras notables. Para una comparación precisa del tiempo de ejecución, debe excluir las operaciones de entrada-salida de su temporizador en ambos idiomas. Aunque en este caso no hace mucha diferencia, el hecho de que un idioma realice la función y la salida mientras el temporizador se está ejecutando, y el otro que realiza solo la función, hace que la prueba sea parcial y no tenga sentido.

Para que sea más equivalente a la versión de Java, cambie su main de c ++ a

int main()
    {
    int* input = FindDuplicate::CreateTestCase(InputSize);   

    int result;
    auto start = std::chrono::system_clock::now(); //clock start 
    result = FindDuplicate::FindDuplicateNaive(input, InputSize);
    auto end = std::chrono::system_clock::now(); //clock end

    std::chrono::duration<double> elapsed_seconds = end - start;
    cout << "Output is: " << result << endl;
    cout << "elapsed time: " << elapsed_seconds.count() << "s/n";
    }

Tenga en cuenta que, por defecto, la E / S de la consola de C ++ (iostream, cin / cout) es incluso más lenta de lo que podría ser, porque la sincronización con la E / S de la consola de C (stdio, scanf / printf) está habilitada para permitir que un programa no haga cosas raras si Se utilizan tanto cout como printf. Here puede leer sobre el rendimiento de cout cuando la sincronización está desactivada. No solo usó E / S dentro de sus restricciones de temporizador, sino que incluso lo usó en su peor modo de rendimiento posible.

Aquí están mis resultados, que aún le dan a Java una ventaja, muestra cuánta diferencia pueden hacer ciertas opciones de compilación y manipulaciones de E / S en C ++ (para un solo cout 0.03s de diferencia en promedio al desactivar la sincronización es más grande de lo que parece) . Todos los valores en segundos son el promedio de 10 pruebas.

1. Java print in timer                   1.52s
2. Java                                  1.36s
3. C++  debug, cout in timer            11.78s
4. C++  debug                           11.73s
5. C++  release, cout in timer           3.32s
6. C++  release cout syncronization off  3.29s
7. C++  release                          3.26s

Quiero que entiendas que de todas estas pruebas, la única comparación que tendría sentido es 1 con 6 y 2 con 7 . Todos los demás (3, 4, 5) harán una comparación sesgada, independientemente de cuántas veces repita la prueba.

Answer 3

La principal diferencia es el desenrollado de bucle.

Java desenrolló el bucle interno de manera muy inteligente, mientras que GCC / clang / MSVC / ICC no lo desenrolla (esto es una optimización perdida de estos compiladores).

Si desenrollas manualmente el bucle, puedes acelerarlo para tener una velocidad similar a la de la versión Java, algo como esto:

for ( j= i+1; j < size-3; j+=4)
{
    if (input[i] == input[j])
        return input[i];
    if (input[i] == input[j+1])
        return input[i];
    if (input[i] == input[j+2])
        return input[i];
    if (input[i] == input[j+3])
        return input[i];
}
for (; j < size; j++)
{
    if (input[i] == input[j])
        return input[i];
}

A modo de prueba, aquí está el bucle interno de la versión java (8x desenrollar):

  0x00007f13a5113f60: mov     0x10(%rsi,%rdx,4),%ebx  ;*iaload
                                                ; - FindDuplicate::FindDuplicateNaive@25 (line 6)

  0x00007f13a5113f64: cmp     %ebx,%ecx
  0x00007f13a5113f66: je      0x7f13a5113fcb    ;*if_icmpne
                                                ; - FindDuplicate::FindDuplicateNaive@26 (line 6)

  0x00007f13a5113f68: movsxd  %edx,%rdi
  0x00007f13a5113f6b: mov     0x14(%rsi,%rdi,4),%ebx  ;*iaload
                                                ; - FindDuplicate::FindDuplicateNaive@25 (line 6)

  0x00007f13a5113f6f: cmp     %ebx,%ecx
  0x00007f13a5113f71: je      0x7f13a5113fc9    ;*if_icmpne
                                                ; - FindDuplicate::FindDuplicateNaive@26 (line 6)

  0x00007f13a5113f73: mov     0x18(%rsi,%rdi,4),%ebx  ;*iaload
                                                ; - FindDuplicate::FindDuplicateNaive@25 (line 6)

  0x00007f13a5113f77: cmp     %ebx,%ecx
  0x00007f13a5113f79: je      0x7f13a5113fed    ;*if_icmpne
                                                ; - FindDuplicate::FindDuplicateNaive@26 (line 6)

  0x00007f13a5113f7b: mov     0x1c(%rsi,%rdi,4),%ebx  ;*iaload
                                                ; - FindDuplicate::FindDuplicateNaive@25 (line 6)

  0x00007f13a5113f7f: cmp     %ebx,%ecx
  0x00007f13a5113f81: je      0x7f13a5113ff2    ;*if_icmpne
                                                ; - FindDuplicate::FindDuplicateNaive@26 (line 6)

  0x00007f13a5113f83: mov     0x20(%rsi,%rdi,4),%ebx  ;*iaload
                                                ; - FindDuplicate::FindDuplicateNaive@25 (line 6)

  0x00007f13a5113f87: cmp     %ebx,%ecx
  0x00007f13a5113f89: je      0x7f13a5113ff7    ;*if_icmpne
                                                ; - FindDuplicate::FindDuplicateNaive@26 (line 6)

  0x00007f13a5113f8b: mov     0x24(%rsi,%rdi,4),%ebx  ;*iaload
                                                ; - FindDuplicate::FindDuplicateNaive@25 (line 6)

  0x00007f13a5113f8f: cmp     %ebx,%ecx
  0x00007f13a5113f91: je      0x7f13a5113ffc    ;*if_icmpne
                                                ; - FindDuplicate::FindDuplicateNaive@26 (line 6)

  0x00007f13a5113f93: mov     0x28(%rsi,%rdi,4),%ebx  ;*iaload
                                                ; - FindDuplicate::FindDuplicateNaive@25 (line 6)

  0x00007f13a5113f97: cmp     %ebx,%ecx
  0x00007f13a5113f99: je      0x7f13a5114001    ;*if_icmpne
                                                ; - FindDuplicate::FindDuplicateNaive@26 (line 6)

  0x00007f13a5113f9b: mov     0x2c(%rsi,%rdi,4),%ebx  ;*iaload
                                                ; - FindDuplicate::FindDuplicateNaive@25 (line 6)

  0x00007f13a5113f9f: cmp     %ebx,%ecx
  0x00007f13a5113fa1: je      0x7f13a5114006    ;*if_icmpne
                                                ; - FindDuplicate::FindDuplicateNaive@26 (line 6)

  0x00007f13a5113fa3: add     $0x8,%edx         ;*iinc
                                                ; - FindDuplicate::FindDuplicateNaive@33 (line 5)

  0x00007f13a5113fa6: cmp     %r8d,%edx
  0x00007f13a5113fa9: jl      0x7f13a5113f60    ;*if_icmpge
                                                ; - FindDuplicate::FindDuplicateNaive@17 (line 5)