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.8	Ruby 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.8	9m26.377s
Chicken (interpretado)	5m21.635s
Python puro	2m21.908s
Ruby 1.9	1m14.576s
Python + Psyco	0m6.998s
C	0m1.374s
Chicken (compilado)	0m1.088s

As seguintes versões de interpretadores e compiladores foram usadas:

Python	2.6.4
Psyco	1.6
Ruby	1.8 e 1.9
Chicken	4.4.4
GCC	4.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.