Finalmente Java mais rápido que C++
Pois é… o temido dia chegou!
Em algum momento isso ia acontecer… ia aparecer algum código Java específico que rodasse mais rápido que o equivalente em C++. E não adianta nada, nem escovar bits, nem reza braba, nem compilador Intel… esse código aí embaixo roda bem mais rápido em Java!!!!
Código Fonte Java:
public class Teste {
static int fib( int n ) {
return n > 1 ? fib(n-1)+fib(n-2) : n;
}
public static void main(String[] args) {
System.out.println(fib(45));
}
}
|
Código Fonte C++:
#include <iostream>
using namespace std;
inline int fib( int n ) {
return n > 1 ? fib(n-1)+fib(n-2) : n;
}
int main(int argc, char *argv[]) {
cout << fib(45) << endl;
return 0;
}
|
Tempos:
Java (client): 14.74 segundos
Java (server): 10.17 segundos
C++ (g++ opção k8): 19.83 segundos
C++ (g++ opção core2): 14.39 segundos
C++ (Intel): 23.83 segundos
Note que dessa vez o compilador Intel perdeu pro g++… pros dois g++, 3.4 e 4.4. Mas todos perderam pro Java -server, e o g++ -core2 empatou com o Java -client. De alguma forma a chamada de funções estáticas no Java é mais otimizada… ou deve ter a ver com recursividade, passagem de parâmetros sei lá. Não entendo de bytecodes pra olhar o código gerado. Só sei que o C++ ficou cerca de 40% mais lento.
Enfim, é uma coisa a se investigar. Mas de qualquer forma, para Fibonacci e outras funçõe recursivas o C++ oferece metaprogramação… e aí… bem e aí o tempo cai pra 1.4 segundos. Mas isso é assunto de outro post.
“Though this be madness, yet there is method in ‘t. Will you walk out of the air, my lord?”
Não sei se é o caso, mas a máquina virtual do Java pode fazer uma otimização absurda em tempo de execução pra casos como esse… apesar de que como o parâmetro é constante, o próprio compilador de C++ poderia. Enfim… o que acontece é que o valor de retorno da função é determinado unicamente pelos parâmetros (o compilador/JVM vê que o código não acessa nada externo) então o JIT pode mudar o código de forma que pegue de uma tabela de cache os resultados já calculados, já que essa recursão gera uma árvore de tamanho exponencial onde vários valores são calculados várias vezes sem necessidade. Seria como uma auto-Programação Dinâmica
Não é o caso…
se fosse assim o tempo de execução seria mínimo, pois seriam calculados apenas 45 valores.
Primeiro… esse código de fibonacci é horrivel, quero ver o java superar em um exemplo util
Outra coisa, é evidente que os dois códigos estão fazendo algo diferente. Eu não conheço muito java mas vou chutar…
Desconfio que no programa C++ quanto fib(n) é chamada o valor de n é copiado pra pilha como em qualquer chamada de função, normal, mas na recepção do parametro o codigo c++ deve estar realizando uma cópia de n da pilha para algum outro registrador ou pra memória; O Java pode estar realizando n > 1 diretamente com o valor da pilha e só copiando quando for necessário calcular n-1 e n-2 para chamada de fib() recursiva. Esse caso acontece em 50% das chamadas da função fibonacci, então é provavelmente o que explica a diferença de performance.
Outra teoria que eu tenho seria com relação à diferença é chamada da função fib(), é possível que o programa C++ esteja por algum motivo bizarro utilizando mais bytes para endereçar fib() do que realmente é necessário. Acho meio dificil isso mas é algo que pode acontecer especialmente porque os compiladores às vezes tem coisas default desse tipo que passam despercebidas num programa grande mas num teste como esse fazem diferença.
No geral Zimbrão, achei bem interessante seus posts recentes sobre a performance dos compiladores, parabéns e obrigado
E vamos torcer pra aparecer um cara insano em assembly pra olhar o código gerado nesse exemplo aqui e descobrir o que que está havendo
O exemplo do Fibonacci recursivo foi só por que ele faz milhares de chamadas recursivas para calcular o 45º elemento da lista. E o que eu queria era encontrar um exemplo onde o Java fosse mais rápido que o C++. No post anterior, das matrizes, ocorre o oposto.
O problema deve ser algo em relação ao que é empilhado: por algum motivo o C++ deve estar empilhando mais coisas que o Java. Ambos os otimizadores conhecem a técnica de passar parâmetros por registradores – pode ser por aí o problema também, já que logo em seguida os parâmetos têm de ser empilhados.
E se alguém quiser olhar o assembly do Java, não tenho a menor idéia de como fazer… rodar o JVM em um debugger para ver o que ele carrega na memória? Certamente essa otimização não foi nos bytecodes, senão não haveria diferença de tempo entre java -client e java -server.
E obrigado pelos parabéns!
A proposito o que o Tinnus falou não deve ser o que ocorre, pois se fosse o código java rodaria em 1 segundo. A primeira função resolvida seria fib(1), em seguida fib(0), e a partir dai o suposto otimizador inteligente iria calcular f(2) instantaneamente, e f(3), e assim por diante, tendo performance geral praticamente idêntica ao algoritmo não recursivo.
Mas no geral é uma idéia é bem interessante, o compilador hipotético poderia ter um recurso automatico para cachear a resposta de certas funções, à luz do que ocorre com seno, cosseno, e outras funções matemáticas tradicionais, q tem sua implementação completamente tabelada. O programador passava um keyword ou HINT e o compilador gerava codigo automatico pra cachear a resposta. Em tempo de execução, o software iria executar mais rapido com o passar do tempo. Se bobear isso já existe, mas eu desconheço
As linguagens funcionais se comportam dessa forma: esse Fibonacci em Lisp é rapidísssimo.
[...] This post was mentioned on Twitter by Victor V. S. and Eduan Lenine, Pedro Herrera. Pedro Herrera said: finalmente Java mais rápido que C++ http://www.zimbrao.com/cpp/?p=282 [...]
O que me leva a refletir: qual o custo de se empilhar várias funções inline?
Você chegou a tentar com a opção -O3?
Usei as seguintes opções (que também foram usadas no post das matrizes):
java -client Fibonacci
java -server Fibonacci
g++ -O3 -funroll-loops -fprefetch-loop-arrays -fomit-frame-pointer -march=k8 -mpni Fibonacci.cpp -o fibonacci.exe
g++ -O3 -funroll-loops -fprefetch-loop-arrays -fomit-frame-pointer -march=core2 -msse4 Fibonacci.cpp -o fibonacci.exe
icl /O3 /QxHost Fibonacci.cpp
Note que -O3 normalmente habilita -fomit-frame-pointer se isso não atrapalhar a depuração – como não sei se atrapalha no Windows, resolvi forçar essa opção.
O inline nesse caso não serviu pra nada, já que a função é recursiva.
@Gabriel
Acho que Java costuma ser mais rápido em chamadas de métodos. Em sistemas OO convencionais bem modularizados e desacoplados encontra-se muitas chamadas de métodos entre as classes com muito pouco código em cada, o que poderia, em tese, tornar um software em Java mais rápido que em C/C++.
A propósito, o Jake2 ficou tão rápido quanto ou mais que o Quake2 em determinadas situações:
http://bytonic.de/html/benchmarks.html Acredito que atualmente, com a JVM 6 e com o hardware novo, talvez rode mais rápido ainda.
@Zimbrão
Só a chamada de métodos static que é mais rápida?
Só posso afirmar sobre esse teste: nesse caso foi mais rápido!
Legal essa comparação.
Você rodou em linux ou windows?
Windows.
Em linux pode ser diferente, pois há uma versão mais nova do g++ disponível que ainda não foi portada para Windows.
Qual versão? A princípio, o GCC só libera uma versão quando ela funciona igualmente em todas as plataformas, por isso a pergunta…
MingW com g++ 4.4.0
Pegue o número de horas que foram dedicadas a otimizar o Jake2 e dedique igualmente a otimizar o código C e refaça o benchmark….
Dê uma olhada nos posts anteriores sobre otimização de matrizes. Certamente otimização deve ser usada como último recurso pois consome muito tempo. O ideal é deixar a otimização básica para o otimizador.
Nesse exemplo de Fibonacci o otimizador mesmo não tem muito o que fazer. É a forma de passagem de parâmetros que deve ter influenciado o tempo. Vou olhar o assmbly do C++ para ter uma idéia.
Aqui uma implementação eficiente do mesmo algoritmo recursivo de Fibonacci em C++.
Legal,
Tenta isso:
static long sum_it(long n) {
long a = 0;
for (long i = 0; i 0 ? sum_rec(n-1) + n: 0;
}
int main(int argc, char** argv) {
cout << sum_it(7550) << endl;
//cout << sum_rec(7550) << endl;
return 0;
}
Wow, porquê em Java não funciona o sum_rec para valores maiores que 7750?
Abraços
Poxa, devorou o meu código…
http://pastebin.com/f4b5bb9d9
http://pastebin.com/m3c42a64d
Em operações iterativas o C++ dá uma surra em Java.
Ou seja, aquela velha história: “depende”…
Não me pergunte o motivo, mas não consegui testar em java passando mais que 4096 no método recursivo. Valores maiores ora funcionm ora não funcionam. Em C++ testei com mais de um milhão e calculou com um barramento nas costas
Ambos os otimizadores usam técnicas para otimizar chamadas recursivas. No g++ é a opção:
-foptimize-sibling-calls
Optimize sibling and tail recursive calls.
Enabled at levels -O2, -O3, -Os.
No Java, deve ser default. Porém o limite do otimizador do Java deve ser bem menor.
Esse algoritmo Fibonacci foi escolhido justamente por que ele não permite esse tipo de otimização.
Quanto as surras… muito relativo, o otimizador Java é bem eficiente com os milhões de dólares que foram gastos nele pela SUN e IBM. Java perde muito com a verificação de índices de arrays por definição da própria linguagem, mas no final, assembly é assembly, e tudo é otimizado.
Na minha humilde opinião, essa não é uma discussão objetivamente produtiva. Serve mais para exercitar o poder de argumentação quando se tem uma linguagem como religião…
Bem, mas de qualquer maneira, a discussão é sempre interessante porque a gente sempre aprende coisas novas de alguma maneira, seja com a própria mantéria ou com os comentários.
Nenhuma linguagem é absolutamente melhor que outra. É melhor ou pior em algum contexto. Elas também não foram pensadas para serem melhores, foram pensadas para cobrir algo que nenhuma outra cobria ainda ou para ser usada em um contexto que não existia quando uma antecessora fora criada.
Abraço.
O objetivo desse post era só mostrar que é falsa a afirmação de que Java é sempre mais lento que C++. Depende muito do código e do otimizador.
Não pretendo mostrar que uma linguagem é melhor ou pior – até porquê abomino essa estória de religiões em programação.
Se uma linguagem fosse melhor que todas as outras em tudo, só haveria ela…
Abraço e obrigado pela contribuição!
Eu ainda diria que a escolha ainda depende do que você vai fazer.
Se um dia eu for fazer um programa curto de fibonacci, eu uso Java
Mas para programar um jogo inteiro, prefiro ficar com meu C+ (meio termo entre C e C++
) que eu sei exatamente o que a máquina está fazendo… Da mais trabalho, mas se o programa ficar lento eu sei que a culpa é realmente minha…
Mas nada impede de eu usar outras linguagens
Apesar de que eu não gosto de linguagens interpretadas ou linguagens com JIT, eu também já fiz coisas em J2ME e C# ^^
Eu penso que a escolha de uma linguagem deve ser feita pelos requisitos que você tem. Velocidade é um requisito que nem sempre é tão importante. Outras coisas devem ser levadas em conta, por exemplo a disponibilidade de mercado: ferramentas, programadores, salários de programadores (rs) etc.
E o Fibonacci em C++ fica muito rápido usando metaprogramação sem ter de trocar o algoritmo hehe
Obtive resultados parecidos sem otimização. Mas um simples -O2 no gcc já deu a vitória para o C++:
$ g++ -O2 x.cpp
$ time ./a.out
1134903170
real 0m9.269s
user 0m8.977s
sys 0m0.008s
$ javac -server Teste.java
$ time java -server Teste
1134903170
real 0m11.379s
user 0m10.861s
sys 0m0.036s
(Ubuntu 9.04, gcc 4.3.3, java 1.6.0)
Mas o exemplo não deixa de ser interessante!
Interessante!
Estava esperando que alguém rodasse no Linux para confirmar minhas suspeitas que lá seria mais rápido! Embora possa ser também a versão do g++: estou usandoo 4.4.0, porte do MingW, rodando tudo em Windows. Vou baixar e testar com a versão 4.3.
Para adicionar aos sistemas testados, aqui mais um:
Notebook com AMD Turion64 X2 cada núcleo com 1.6 Ghz.
Arch Linux x64 (64-bits puro, sem bibliotecas de 32-bits)
g++ -v: gcc version 4.4.1 (GCC)
java -version:
java version “1.6.0_0″
OpenJDK Runtime Environment (IcedTea6 1.6.1) (ArchLinux-1.6.1-1-x86_64)
OpenJDK 64-Bit Server VM (build 14.0-b16, mixed mode)
Testes:
Java:
[bruno@smoker temp]$ javac -server Teste.java
[bruno@smoker temp]$ time java -server Teste
1134903170
real 0m17.368s
user 0m16.882s
sys 0m0.010s
G++ -O0:
[bruno@smoker temp]$ g++ -o fib fib.cpp -O0
[bruno@smoker temp]$ time ./fib
1134903170
real 0m28.605s
user 0m28.235s
sys 0m0.077s
G++ -O1 (aqui ja esta mais rapido que o Java):
[bruno@smoker temp]$ g++ -o fib fib.cpp -O1
[bruno@smoker temp]$ time ./fib
1134903170
real 0m12.831s
user 0m12.779s
sys 0m0.000s
G++ -O2 (passou a demorar mais do que com -O1):
[bruno@smoker temp]$ time ./fib
1134903170
real 0m16.831s
user 0m16.622s
sys 0m0.000s
G++ -O3:
[bruno@smoker temp]$ g++ -o fib fib.cpp -O3
[bruno@smoker temp]$ time ./fib
1134903170
real 0m17.288s
user 0m17.062s
sys 0m0.003s
Por algum motivo, aqui apenas com -O1 fica de fato mais rápido. Com -O2 ou -O3 ficou praticamente a mesma coisa e com -O0 ficou mais lento.
Porem gostaria de ressaltar aqui que também depende da implementação do JDK utilizada.
Como indicado pela saída do java -version, aqui é utilizada a OpenJDK, algo que eu acho que também acontece com o Ubuntu do Narcélio. A OpenJDK é um port opensource da JDK original. Talvez a JDK e o compilador/vm para windows, sejam muito mais otimizados que a OpenJDK.
Certamente!
As JVMs mais otimizadas são a BEA Jrockit (Oracle), a da IBM e a da Sun. São as que recebem todo ano milhões de dólares de investimentos no otimizador.
E há quem fale bem da Jet também em alguns benchmarks.
Eu fiz os testes com o JDK da Sun.
Em C++ :
#include
using namespace std;
int fib( int n )
{
return n > 2 ? fib(n-1)+fib(n-2) : 1;
}
int main(int argc, char *argv[])
{
cout << fib(45) < 2 ? fib(n-1)+fib(n-2) : 1;
}
public static void main(String[] args) {
System.out.println(fib(45));
}
}
compilação:
javac Teste.java
Tempos:
5.73 user
0.01 system
0:05.89 elapsed
Conclusão:
Faz uma grande diferença escovar bits e conhecer os compiladores…
Tempos de execução do programa compilado em C++:
3.50 user
0.00 system
0:03.58 elapsed
Olá,
Obrigado pelo comentário, mas tenho algumas observações:
1) Apliquei a sua mesma transformação no programa Java e ele continuou mais rápido: 6.89 do Java contra 7.54 do C++, usando o g++ opção core2. A chamada recursiva de funções do Java nesse caso é mais rápida que a do C++. Usei a linha de comando “java -server -XBatch Teste”, que usa a opção de Java modo servidor, recomendada pela Sun quando se quer desempenho.
2) Você modificou o algoritmo em C++ usando o fato de que fib(2) = 1 e fib(0) = 0, eliminando uma soma desnecessária. No algoritmo original, fib(2) = fib(1) + fib(0). Dessa forma você conseguiu eliminar duas chamadas em cada cadeia de recursão. No algoritmo original, temos 3.672.623.805 de chamadas à função fib (quase 4 bilhões…). Na versão modificada, são 2.269.806.339 chamadas – cerca de um bilhão e quatrocentos milhões de chamadas a menos, o que corresponde a 38% menos chamadas. Daí o ganho de desempenho. A minha idéia não era calcular Fibonacci de forma eficiente, existem outros algoritmos para isso, mas sim testar o desempenho do compilador/otimizador com um grande número de chamadas recursivas.
3) Minha máquina é um i7 com Windows XP, usei o g++ 4.4.0 e JVM SUN 1.6. Note nos comentários acima que a OpenJDK é bem mais lenta que a JVM da Sun.
4) Para deixar como registro, você poderia descrever as versões do SO, JVM, g++ e opções de compilação usadas?
No mais, você está certíssimo, sempre é bom executar os testes nós mesmos: é ver para crer, não podemos acreditar em qualquer coisa que alguém (no caso eu…) escreve em um blog… rs
Abraços!
SO: Mandriva Linux 2009.1
Máquina: Core 2 duo, 3.2 GHz, RAM 4GB
Compilação C++, detalhe importante que não saiu na última postagem:
g++ -O03 Teste.cpp
compilador c++: g++ 4.4
JVM : Sun 1.6,
Obrigado pelas suas explanações, de fato, houve uma melhora expressiva devido à modificação do algoritmo original. Mas, o fato é que a modificação foi feita para aproveitar os recursos de otimização da opção -O03 do gcc.
O que acontece é que geralmente não temos muito tempo para explorar todos os recursos de um compilador tão flexível como o gcc, nem de testar todas as possibilidades pensando no algoritmo e na otimização conseguida em conjunto com as opções do compilador.
O fato é que sempre que a camada JVM é eliminada, qualquer que seja a implementação, compilando-se em código nativo, o limite não é a mais a JVM e sim a própria máquina real. Compiladores podem sempre ser aperfeiçoados, mas este fato físico não pode mudar. Ou seja, a única possibilidade real de JAVA realmente ser mais rápido do que C++ é que a máquina real rode o próprio bytecode, diretamente, sem JVM.
Oi,
Tem como você realizar o teste usando a mesma modificação em Java e com a opção “Java -server”?
[]s
Como resultado, o tempo da aplicação java baixou para: 4.82 user, ainda superior ao resultado em C++, devo salientar que ainda dá pra enxugar muito o resultado em C++, a opção -O03 do gcc ainda é genérica, se começarmos a ajustar flags específicos, opções tipo –flag-xxxxxxx ainda podemos baixar muito.
Sei disso porque eu trabalho com aplicações embarcadas(pequenos dispositivos) e sou obrigado a conheçer otimizações a fundo.
Já li em algum lugar, não lembro muito bem, que sinalizaram a possibilidade de criar um processador que roda bytecode, aí sim pode ser que isso mude.
Oi,
Na main, vc escreveu:
int main(int argc, char *argv[])
{
cout << fib(45) < 2 ? fib(n-1)+fib(n-2) : 1;
}
Esse código dá que “n” não foi declarado… o que vc queria escrever? cout << fib(45) << endl; ?
Olá,
Isso deve ter sido erro de postagem, na verdade o programa que compilei é uma cópia do seu apenas retirando o inline da função e substituindo a comparação e segundo valor do operador ternário.
Ou seja:
#include
using namespace std;
int fib( int n ) {
return n > 2 ? fib(n-1)+fib(n-2) : 1;
}
int main(int argc, char *argv[]) {
cout << fib(45) << endl;
return 0;
}
Que estranho!!!
Aconteceu de novo… O “iostream” do código desapareceu, por acaso este blog aceita formatação em html? parece que ele está ocultando o que fica entre maior e menor…
Xiii!
Sou novo no WordPress, não faça pergunta difícil!
Valeu, vou rodar os testes de novo com essa versão do programa. Ontem quando rodei o Java continuou mais rápido… estou no Windows e a versão do g++ é 4.4.0, talvez seja isso.
[]s
Pois é, isso varia muito.
Varia de sistema para sistema, varia de um compilador para o outro, varia de uma opção de compilação para outra, enfim…
Se for rodar em um sistema embarcado simples então, aí Java não vai conseguir chegar nem perto, porque o programa está acessível diretamente pelo processador e o código de máquina nativo vai rodar sem interferência de nenhum SO.
Cheers for the useful page – I loved reading it! I always love this blog.
Olá estava de passagem pelo blog e encontrei essa interessante discussão. Uma coisa que pode estar influenciando
é o padrão de chamada de função utilizado pelo C++. Não sei se aplica ao g++, porém nos compiladores VC e BCC o padrão
é o cdecl que passam os parametros da direita para esquerda pela pilha. Um outro padrão de chamada é o fastcall que passa
os dois primeiros parametros por registrador direto. No VC e BCC basta colocar a palavra __fastcall antes do nome da
função. Talvez fosse interessante testar essa padrão de chamada no código de teste e ver o resultado obtido.
[]’s
Testei o __fastcall, é exatamente da mesma forma que vc falou. Não alterou tempo!
[]s
Reproduzi o teste no meu computador (Core 2 duo, 2.1GHz, Windows)
e o resultado com Java também foi mais rápido:
C++ compilador VC Express, chamada padrao cdecl: 20,343 segundos
C++ compilador VC Express, chamada fastcall: 15,038
Java -server (JDK 1.6): 11,263
Porém utilizando uma opção do compilador VC para expandir funções recursivas inline (#pragma inline_recursion(on)), o tempo baixou para 5,57 (menos da metade do tempo de Java).
Essa opção expande inline uma funcão recursiva até um limite especificado, no caso usei a expansão 16 vezes que é o máximo suportado.
É bem possível que exista uma opção semelhante no g++.
[]’s
Interessante!
O g++ faz uma expansão de recursividade, mas apenas para o caso “tail” (caso do fatorial por exemplo). Quando tem duas chamadas recursivas na mesma função ele não expande.
[]s
Segue a versão static.
#include
template struct fib {
static const int result = fib::result + fib::result;
};
template struct fib {
static const int result = 0;
};
template struct fib {
static const int result = 1;
};
int main(int ac, char *av[])
{
std::cout << "Fib(10) = " << fib::result << std::endl;
return 0;
}
Eduardo,
Por favor dê uma editada pois os sinais de maior e menor foram confundidos com tags html…
Num outro post tem uma versão com templates: “A volta por cima…”
[]s
Então tá tudo bem, depois eu dei uma lida geral eu vi q já tem outro post já explicando.