java - speed - programação orientada a objetos c++ pdf




Por que um loop de pesquisa de matriz de número inteiro é mais lento em C++que em Java? (2)

Eu tenho o mesmo programa escrito em C ++ e Java. Para C ++, estou usando o VS 2019 e para Java usando o Eclipse 2019-03.

Aqui está o programa em 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";

}

Aqui está o programa 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);
}

Você ficará chocado ao saber o tempo gasto pelo mesmo programa a mesma entrada em ambos os c + + e Java.

Em Java:

Toal tempo tomado é: 41.876 seg
499999

No CPP:

Depois de ativar a otimização e no modo de liberação,

A saída é: 499999
tempo decorrido: 64.0293s

Qualquer pensamento sobre isso, qual poderia ser o motivo? Por que o Java está levando 41.876 segundos, enquanto o CPP leva 64.0293 segundos ??


A principal diferença é o desenrolamento do loop.

Java desenrolou o loop interno de forma muito inteligente, enquanto o GCC / clang / MSVC / ICC não o desenrolou (essa é uma otimização perdida desses compiladores).

Se você manualmente desenrolar o loop, você pode acelerar para ter a velocidade semelhante à versão java, algo como isto:

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

Para a prova, aqui está o loop interno da versão java (8x desenrolar):

  0x00007f13a5113f60: mov     0x10(%rsi,%rdx,4),%ebx  ;*iaload
                                                ; - FindDuplicate::[email protected] (line 6)

  0x00007f13a5113f64: cmp     %ebx,%ecx
  0x00007f13a5113f66: je      0x7f13a5113fcb    ;*if_icmpne
                                                ; - FindDuplicate::[email protected] (line 6)

  0x00007f13a5113f68: movsxd  %edx,%rdi
  0x00007f13a5113f6b: mov     0x14(%rsi,%rdi,4),%ebx  ;*iaload
                                                ; - FindDuplicate::[email protected] (line 6)

  0x00007f13a5113f6f: cmp     %ebx,%ecx
  0x00007f13a5113f71: je      0x7f13a5113fc9    ;*if_icmpne
                                                ; - FindDuplicate::[email protected] (line 6)

  0x00007f13a5113f73: mov     0x18(%rsi,%rdi,4),%ebx  ;*iaload
                                                ; - FindDuplicate::[email protected] (line 6)

  0x00007f13a5113f77: cmp     %ebx,%ecx
  0x00007f13a5113f79: je      0x7f13a5113fed    ;*if_icmpne
                                                ; - FindDuplicate::[email protected] (line 6)

  0x00007f13a5113f7b: mov     0x1c(%rsi,%rdi,4),%ebx  ;*iaload
                                                ; - FindDuplicate::[email protected] (line 6)

  0x00007f13a5113f7f: cmp     %ebx,%ecx
  0x00007f13a5113f81: je      0x7f13a5113ff2    ;*if_icmpne
                                                ; - FindDuplicate::[email protected] (line 6)

  0x00007f13a5113f83: mov     0x20(%rsi,%rdi,4),%ebx  ;*iaload
                                                ; - FindDuplicate::[email protected] (line 6)

  0x00007f13a5113f87: cmp     %ebx,%ecx
  0x00007f13a5113f89: je      0x7f13a5113ff7    ;*if_icmpne
                                                ; - FindDuplicate::[email protected] (line 6)

  0x00007f13a5113f8b: mov     0x24(%rsi,%rdi,4),%ebx  ;*iaload
                                                ; - FindDuplicate::[email protected] (line 6)

  0x00007f13a5113f8f: cmp     %ebx,%ecx
  0x00007f13a5113f91: je      0x7f13a5113ffc    ;*if_icmpne
                                                ; - FindDuplicate::[email protected] (line 6)

  0x00007f13a5113f93: mov     0x28(%rsi,%rdi,4),%ebx  ;*iaload
                                                ; - FindDuplicate::[email protected] (line 6)

  0x00007f13a5113f97: cmp     %ebx,%ecx
  0x00007f13a5113f99: je      0x7f13a5114001    ;*if_icmpne
                                                ; - FindDuplicate::[email protected] (line 6)

  0x00007f13a5113f9b: mov     0x2c(%rsi,%rdi,4),%ebx  ;*iaload
                                                ; - FindDuplicate::[email protected] (line 6)

  0x00007f13a5113f9f: cmp     %ebx,%ecx
  0x00007f13a5113fa1: je      0x7f13a5114006    ;*if_icmpne
                                                ; - FindDuplicate::[email protected] (line 6)

  0x00007f13a5113fa3: add     $0x8,%edx         ;*iinc
                                                ; - FindDuplicate::[email protected] (line 5)

  0x00007f13a5113fa6: cmp     %r8d,%edx
  0x00007f13a5113fa9: jl      0x7f13a5113f60    ;*if_icmpge
                                                ; - FindDuplicate::[email protected] (line 5)

Como a vetorização não pode ocorrer facilmente, a maior parte do tempo é gasta no controle de loop.
Graças ao uso do #pragma GCC unroll N no loop interno, o que ajuda a investigar, o desenrolamento de loop fornece uma explicação dos resultados do OP.

Eu obtenho estes resultados médios (consola excluída dos tempos):

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

edit: estes testes foram executados com InputSize = 100'000 como na pergunta original (alterado para 500'000 depois)







visual-c++