terça-feira, 30 de março de 2010

Lies, damn lies and benchmarks

Esses dias me deparei com um texto que mostra um benchmark simplificado (bastante ingênuo, na verdade) cujo título é "Holy Shmoly, Ruby 1.9 smokes Python away!". O benchmark baseia-se na execução do cálculo da série de Fibonacci. A implementação é recursiva e exercita, basicamente, chamadas de função e aritmética básica. São comparadas as implementações de Python e Ruby.

Embora seja muito simplificado, este benchmark desencadeou várias surpresas.

Surpresa 1 -- A implementação de Ruby está ficando mais rápida



Esta surpresa, na realidade, foi dupla para mim. Eu tinha idéia de que a implementação de Ruby era "meio lenta", mas não sabia que era tão lenta. A parte boa da surpresa é que a versão 1.9 está consideravelmente mais rápida.

Como referência para as próximas medições, abaixo estão os tempos de execução que obtive na minha máquina com as implementações em Ruby para Fibonacci de 0 a 39 (Ruby 1.8 e 1.9):
def fib(n)
if n == 0 || n == 1
n
else
fib(n-1) + fib(n-2)
end
end

40.times do |i|
puts "n=#{i} => #{fib(i)}"
end
Ruby 1.8Ruby 1.9
real    9m26.377s
user 8m11.039s
sys 1m15.273s
real    1m14.576s
user 1m14.565s
sys 0m0.020s

Surpresa 2 -- O desempenho de Python



Ao longo deste texto vou mostrar algumas extensões que fiz ao benchmark original, o que acabou gerando mais surpresas. A primeira dela foi medir o desempenho de Python usando o JIT Psyco. Abaixo estão o código utilizado e os resultados obtidos na minha máquina:

Python puro (sem Psyco)


#! /usr/bin/env python
def fib(n):
if n == 0 or n == 1:
return n
else:
return fib(n-1) + fib(n-2)


for i in xrange(40):
print "n=%d => %d" % (i, fib(i))
time ./fib.py
n=0 => 0
n=1 => 1
...
n=39 => 63245986

real 2m21.908s
user 2m21.349s
sys 0m0.016s


Python com Psyco


#! /usr/bin/env python
import psyco
psyco.full()

def fib(n):
if n == 0 or n == 1:
return n
else:
return fib(n-1) + fib(n-2)


for i in xrange(40):
print "n=%d => %d" % (i, fib(i))
time ./fib.py
n=0 => 0
n=1 => 1
...
n=39 => 63245986

real 0m6.998s
user 0m6.948s
sys 0m0.008s

Com o uso de Psyco, o tempo de execução foi de ~2m22s para ~7s. Impressionante.


Surpresa 3 -- O desempenho de Chicken



Decidi estender o benchmark um pouco mais e implementar o algoritmo em Scheme, com Chicken:
(define (fib n)
(if (or (= n 0) (= n 1))
n
(+ (fib (- n 1)) (fib (- n 2)))))

(let loop ((n 0))
(when (< n 40)
(print "n=" n " => " (fib n))
(loop (+ n 1))))


O desempenho de Chicken, quando interpretando código, é violentamente lento (e esperado, pelo menos por mim):
time csi -s fib.scm
n=0 => 0
n=1 => 1
...
n=39 => 63245986

real 5m21.635s
user 5m20.696s
sys 0m0.916s

Quando o código é compilado com Chicken, há uma melhora significativa no desempenho:
$ csc fib.scm
time ./fib
n=0 => 0
n=1 => 1
...
n=39 => 63245986

real 0m29.996s
user 0m29.938s
sys 0m0.060s

Usando um pouco de agressividade na otimização:
$ csc -O5 fib.scm
time ./fib
n=0 => 0
n=1 => 1
...
n=39 => 63245986

real 0m21.506s
user 0m21.405s
sys 0m0.012s

Com a compilação do código em Chicken, foi possível baixar o tempo de execução de mais de 5 minutos para pouco mais de 20 segundos.

Por curiosidade, resolvi ver o tempo que uma implementação em C, nos mesmos moldes, levaria:
#include <stdio.h>

int fib(int n) {
if (n == 0 || n == 1) {
return n;
} else {
return fib(n - 1) + fib(n - 2);
}
}


int main() {
int n;
for (n=0; n<40; n++) {
printf("n=%d => %d\n", n, fib(n));
}
}
$ gcc -O3 -ffast-math -fomit-frame-pointer -o fib-c fib-c.c
$ time ./fib-c
n=0 => 0
n=1 => 1
...
n=39 => 63245986

real 0m1.374s
user 0m1.372s
sys 0m0.004s


Até aqui, temos C, Python + Psyco e Chicken (compilado) nas três primeiras colocações em tempo de execução. Porém, há um detalhe na implementação em Chicken que faz uma certa diferença: o operadores numéricos (e.g., +, =) aceitam um número arbitrário de argumentos, diferentemente dos operadores numéricos das outras linguagens, que são binários. Obviamente, há um custo para isso. Entretanto, Chicken dispõe de procedimentos binários para operações numéricas com inteiros (com prefixo fx):
(define (fib n)
(if (or (fx= n 0) (fx= n 1))
n
(fx+ (fib (fx- n 1)) (fib (fx- n 2)))))

(let loop ((n 0))
(when (fx< n 40)
(print "n=" n " => " (fib n))
(loop (fx+ n 1))))


compilando e executando este código, temos:
$ csc -O5 fibfx.scm
$ time ./fibfx
n=0 => 0
n=1 => 1
...
n=39 => 63245986

real 0m1.088s
user 0m1.088s
sys 0m0.000s

A surpresa aqui é que o tempo de execução de uma implementação em Scheme é menor do que o de uma implementação em C. E, mais intrigante ainda, é que Chicken compila para C. :-) Porém, a estratégia de compilação usada por Chicken gera código C mais otimizado do que um humano programando.

No final das contas, temos os seguintes tempos, ordenados por ordem decrescente de tempo de execução:
Ruby 1.89m26.377s
Chicken (interpretado)5m21.635s
Python puro2m21.908s
Ruby 1.91m14.576s
Python + Psyco0m6.998s
C0m1.374s
Chicken (compilado)0m1.088s


As seguintes versões de interpretadores e compiladores foram usadas:
Python2.6.4
Psyco1.6
Ruby1.8 e 1.9
Chicken4.4.4
GCC4.4.1

As medições foram feitas em um processador de 2.4GHz com sistema operacional Ubuntu Linux.

Vale ressaltar, novamente, que esse benchmark, embora tenha gerado algumas surpresas, representa muito pouco para avaliação de desempenho de implementações de linguagens de programação.

4 comentários:

Anônimo disse...

Olá. Seria interessante ver uma implementação em Lua, usando o LuaJIT... :-)

mario disse...

Anônimo:

Executei o seguinte código na mesma máquina em que as outras implementações foram executadas:

function fib(n) return n<2 and n or fib(n-1)+fib(n-2) end
for i=0, 39 do print(i, fib(i)) end

(me desculpe pela formatação -- em comentários do blogger não dá para esperar muito...)

Os resultados foram:

Lua (5.1, sem JIT): 1m1.687s
LuaJIT (1.1.6): 0m15.703s

Resultados interessantes. No ranking, LuaJIT ficaria na quarta posição, entre Ruby 1.9 e Python com Psyco.

Obrigado pela sugestão.

Leonardo disse...

Talvez o gargalo do C esteja nos printf's. Não tem muito o que otimizar na função fib, mas em 40 chamadas a printf talvez tenha. Tens o código gerado pelo Chicken?

Mario Domenech Goulart disse...

Alô Leonardo

Acho pouco provável que o gargalo sejo o printf de C, até porque Chicken usa print 40 vezes também.

O que faz a diferença é a estratégia de compilação usada por Chicken.

Coloquei o código C gerado a partir de Scheme em http://parenteses.org/mario/misc/fib.c (gerado com chicken 4.5.0rc4).

Um abraço.