Duas linguagens, dois laços e desempenhos incomparáveis

Duas linguagens, dois laços e desempenhos incomparáveis

Nesse post mostramos uma diferença de desempenho intrigante que percebemos quando implementamos um algoritmo em Java e Ruby. Observe que não é nosso objetivo chegar à conclusão de que uma linguagem é mais rápida do que a outra, mas sim tentar entender o porquê da diferença apresentada. Também precisamos comentar que o problema ainda está em aberto. Temos somente alguns indícios que mostram um possível caminho para encontrar a resposta. Go go go!!


Há uns dias atrás estávamos discutindo a solução para um desafio de programação que recebe como entrada um vetor contendo 100.000 elementos. O algoritmo que encontramos é O(n2), contendo de dois laços, um deles aninhado. Fizemos duas implementações, uma em Java a outra em Ruby. O algoritmo escrito em Java resolveu o problema em 7 segundos enquanto que a implementação em Ruby levou 9 minutos! Ficamos pasmos com esse resultado porque nunca tinhamos pego uma diferença desse tamanho, com ordem de grandeza diferente. Aí surgiu a questão: por que dessa diferença? Perceba que esse foi um caso isolado, pois a diferença é esperada pela própria natureza das linguagens, implementações, etc., mas não esperávamos algo desse tipo. Tivemos caso inclusive da solução em Ruby até ser mais rápida do que a em Java, mas esse caso em especial chamou a atenção.

Após fazer alguns testes, percebemos que esse comportamento poderia ser facilmente simulado só colocando os dois laços aninhados e fazendo as iterações. Fizemos então o seguinte código Java:

public class TwoLoops {  
  public static void main(String[] args) {
    int i = 0, j;
    while (i < 100000) {
      j = i;
      while (j < 100000) {
        j++;
      }
      i++;
    }
  }
}

Observe que esse código não imprime nada, não faz nenhum outro tipo de IO e simplesmente executa as iterações…na prática não faz nada :-) Utilizando o time para medir, obtivemos os seguintes resultados:

Java (1.8.0_45)  
real 0m0.187s  
user 0m0.125s  
sys  0m0.067s  

187 ms. Construímos então o seguinte código em Ruby:

i = 0  
while i < 100_000 do  
  j = i
  while j < 100_000 do
    j = j + 1
  end
  i = i + 1
end  

Com esse código obtivemos os seguintes tempos de execução:

Ruby (MRI 2.3.0)  
real 1m47.654s  
user 1m43.762s  
sys  0m0.518s  

Isso mesmo, 1 minuto e 47 segundos! Isso é aproximadamente 576 vezes mais lento que o código em Java. Essa diferença em ordem de grandeza é bem estranha. Até é compreensível que exista a diferença mas nada desse tipo.

Para tentar entender esse comportamento, pensamos na hipótese da JVM fazer algum tipo de otimização mágica, ou diabólica, que faça com que o código execute muito mais rápido. Mas se é assim, podemos supor que qualquer código rodando na JVM se beneficie dessa otimização. Assim, se rodarmos esse código Ruby com o JRuby deveríamos ter resultados mais próximos. Fizemos esse teste a obtivemos os seguintes tempos:

JRuby (9.0.4.0)  
real 1m23.196s  
user 1m22.167s  
sys  0m1.304s  

Realmente melhorou, mas não foi tanto assim! Por volta de 445 vezes mais lento que o código Java. Assim, tem-se a impressão que a JVM sozinha não consegue otimizar o código. Bem, ainda temos outra suposição, o compilador Java, aquele tal de javac para os íntimos, deve fazer a otimização. Pois bem, se isso acontece então usando outro compilador que gera bytecode o tempo de execução deve ficar alto também, supondo que tal otimização não é feita! Implementamos o seguinte código em Groovy:

i = 0  
while (i < 100000) {  
  j = i
  while (j < 100000) {
    j++
  }
  i++
}

e ao executarmos obtivemos o seguinte resultado:

Groovy (2.4.5)  
real 3m1.856s  
user 2m53.785s  
sys  0m2.151s  

Terrivelmente pior que o Ruby! Ok, parece que o compilador faz a diferença nesse caso. Para comprovar isso, fizemos mais uma implementação em Clojure para ver o que acontece.

((fn []
  (loop [i 0]
    (if (< i 100000)
      (do
        (loop [j i]
          (if (< j 100000)
            (recur (inc j))))
        (recur (inc i)))))))

Pasmem no tempo de execução obtido:

Clojure (1.7.0)  
real 0m5.480s  
user 0m5.641s  
sys  0m0.196s  

Isso mesmo, em Clojure foram gastos 5,5 segundos para executar o mesmo código.

Aparentemente, esses resultados sugerem que há algum tipo de otimização feita em certos compiladores mas que não acontece em outros. Precisaremos ir mais a fundo no assunto para descobrir o que acontece por baixo dos panos de cada compilador e interpretador. De qualquer forma, podemos descartar aqui que a JVM por si só conseguiria otimizar o código, mas aparentemente isso não acontece. Continuaremos as nossas pesquisas para tentar descobrir mais detalhes a respeito dessa diferença.

Só para descontrair fizemos os testes com Python e Node. A tabela abaixo mostra os resultados obtidos.



linguagem\estatística real user sys
Java (1.8.0_45) 0m0.187s 0m0.125s 0m0.067s
Ruby (MRI 2.3.0) 1m47.654s 1m43.762s 0m0.518s
JRuby (9.0.4.0) 1m23.196s 1m22.167s 0m1.304s
Groovy (2.4.5) 3m1.856s 2m53.785s 0m2.151s
Groovy (compiled) 2m44.115s 2m40.296s 0m1.682s
Clojure 0m5.480s 0m5.641s 0m0.196s
Python (3.5.1) 10m48.692s 10m34.555s 0m2.892s
Node (5.3.0) 0m2.786s 0m2.649s 0m0.029s

 


Subscribe to