Argh! Java?! Que nojo!

Um amigo me passou essa… Um código em C++, usando STL e um código em Java que fazem a mesmíssima coisa: Somar 32768 inteiros aleatórios de colocados num array… Ordenados e não ordenados… Eis o resultado do tempo gasto:

Array ordenado, C++: 2.56 segundos
Array não ordenado, C++: 2.56 segundos

Array ordenado, Java: 4.25 segundos
Array não ordenado, Java: 7.84 segundos

Sério que Java consome duas vezes mais tempo para percorrer um array, de maneira linear, se o CONTEÚDO estiver fora de ordem?! PUTS!

UPDATE:  Um comportamento similar pode ser observado se compilarmos com nível de otimização -O2 ou inferior. E a explicação é simples… A distribuição dos valores menores que 128 nos itens do array é de, mais ou menos, 50%. No caso do array fora de ordem o processador não tem chance de manter o reconhecimento de padrão do branch prediction atualizado dentro do loop de teste. Ele erra tando quanto acerta. Com a opção de compilação -O3 o if dentro do loop sob teste é substituido por uma instrução CMOV, eliminando o if… O pedaço do código dos ifs ficam assim:

; 'if', com -O2                    ; 'if', com -O3

; EBX = sum                        ; EBX = sum
; EAX = arraySize                  ; EAX = arraySize
; RDX = &data[0]               ; RDX = &data[0]
;                                  ;
  movsx rcx,dword [rdx]              mov    ecx,[rdx]
  cmp   rcx,128                      movsx  r8,ecx
  jl    .skip                        add    r8,rbx
  add   ebx,ecx                      cmp    ecx,128
.skip:                               cmovge rbx,r8

Ou seja, eliminando um salto condicional melhoramos a performance consideravelmente!!!

Os códigos:

/* Em C++: SortedArrayTest.cc

   Compilar com:
     g++ -O3 -mtune=native SortedArrayTest.cc \
         -o SortedArrayTest 
*/
#include <algorithm>
#include <ctime>
#include <iostream>

int main(void)
{
  const unsigned arraySize = 32768;
  int data[arraysize];

  for (unsigned c = 0; c < arraySize; c++)
    data[c] = std::rand() % 256;

  /* Retire essa linha para testar com o 
     array desordenado. */
  std::sort(data, data + arraySize);

  clock_t start = clock();
  long sum = 0;

  for (unsigned i = 0; i < 100000; i++)
  {
    for (unsigned c = 0; c < arraySize; c++)
      if (data[c] >= 128)
        sum += data[c];
  }

  double elapsedTime = 
    static_cast<double>(clock() - start) / CLOCKS_PER_SEC;

  std::cout << elapsedTime << '\n';
  std::cout << "sum = " << sum << '\n';
}

E agora o MESMO código, em Java:

// Em Java: SortedArrayTest.java
//
// Compile com:
//   javac SortedArrayTest.java
//
import java.util.Arrays;
import java.util.Random;

public class SortedArrayTest {
  public static void main(String[] args) {
    int arraySize = 32768;
    int data[] = new int[arraySize];

    Random rnd = new Random(0);
    for (int c = 0; c < arraySize; c++)
      data[c] = rnd.nextInt() % 256;

    /* Retire essa linha para testar o 
       array desordenado. */
    Arrays.sort(data);

    long start = System.nanoTime();
    long sum = 0;

    for (int i = 0; i < 100000; i++) {
      for (int c = 0; c < arraySize; c++) {
        if (data[c] >= 128)
          sum += data[c];
      }
    }

    System.out.println(
      (System.nanoTime() - start) / 1000000000.0);
    System.out.println("sum = " + sum);
  }
}
Anúncios

Deixe um comentário

Faça o login usando um destes métodos para comentar:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s