roblema de desempenho com problema de Euler e recursão nos tipos Int
Atualmente estou aprendendo Haskell usando os problemas do projeto Euler como playground. Fiquei espantado com a lentidão dos meus programas Haskell em comparação com programas similares escritos em outros idiomas. Gostaria de saber se já vi alguma coisa ou se esse é o tipo de penalização de desempenho que se espera quando se usa o Haskel
O programa a seguir é inspirado no Problema 331, mas eu o mudei antes de postar para não estragar nada para outras pessoas. Ele calcula o comprimento do arco de um círculo discreto desenhado em uma grade 2 ^ 30 x 2 ^ 30. É uma implementação recursiva simples da cauda e garanto que as atualizações da variável de acumulação que acompanham o comprimento do arco sejam rigorosas. No entanto, leva quase um minuto e meio para ser concluído (compilado com o sinalizador -O com ghc
import Data.Int
arcLength :: Int64->Int64
arcLength n = arcLength' 0 (n-1) 0 0 where
arcLength' x y norm2 acc
| x > y = acc
| norm2 < 0 = arcLength' (x + 1) y (norm2 + 2*x +1) acc
| norm2 > 2*(n-1) = arcLength' (x - 1) (y-1) (norm2 - 2*(x + y) + 2) acc
| otherwise = arcLength' (x + 1) y (norm2 + 2*x + 1) $! (acc + 1)
main = print $ arcLength (2^30)
Aqui está uma implementação correspondente em Java. Demora cerca de 4,5 segundos para concluir.
public class ArcLength {
public static void main(String args[]) {
long n = 1 << 30;
long x = 0;
long y = n-1;
long acc = 0;
long norm2 = 0;
long time = System.currentTimeMillis();
while(x <= y) {
if (norm2 < 0) {
norm2 += 2*x + 1;
x++;
} else if (norm2 > 2*(n-1)) {
norm2 += 2 - 2*(x+y);
x--;
y--;
} else {
norm2 += 2*x + 1;
x++;
acc++;
}
}
time = System.currentTimeMillis() - time;
System.err.println(acc);
System.err.println(time);
}
}
EDIT: Após as discussões nos comentários, fiz algumas modificações no código Haskell e fiz alguns testes de desempenho. Primeiro mudei n para 2 ^ 29 para evitar estouros. Então tentei 6 versões diferentes: Com Int64 ou Int e com franja antes de norm2 ou de ambos e norm2 e acc na declaraçãoarcLength' x y !norm2 !acc
. Todos são compilados com
ghc -O3 -prof -rtsopts -fforce-recomp -XBangPatterns arctest.hs
Aqui estão os resultados:
(Int !norm2 !acc)
total time = 3.00 secs (150 ticks @ 20 ms)
total alloc = 2,892 bytes (excludes profiling overheads)
(Int norm2 !acc)
total time = 3.56 secs (178 ticks @ 20 ms)
total alloc = 2,892 bytes (excludes profiling overheads)
(Int norm2 acc)
total time = 3.56 secs (178 ticks @ 20 ms)
total alloc = 2,892 bytes (excludes profiling overheads)
(Int64 norm2 acc)
arctest.exe: out of memory
(Int64 norm2 !acc)
total time = 48.46 secs (2423 ticks @ 20 ms)
total alloc = 26,246,173,228 bytes (excludes profiling overheads)
(Int64 !norm2 !acc)
total time = 31.46 secs (1573 ticks @ 20 ms)
total alloc = 3,032 bytes (excludes profiling overheads)
Estou usando o GHC 7.0.2 em um Windows 7 de 64 bits (distribuição binária da plataforma Haskell). De acordo com os comentários, o problema não ocorre ao compilar sob outras configurações. Isso me faz pensar que o tipo Int64 está quebrado na versão do Windows.