Hello,
During a talk with a friend I came up with two programs, one written in
C and another in haskell.
Haskell
main :: IO ()
main = print $ rangeI 0 0
rangeK :: Int -> Int -> Int -> Int -> Int
rangeK i j k acc
| k < 1000 =
if i * i + j * j + k * k `mod` 7 == 0
then rangeK i j (k+1) (acc+1)
else rangeK i j (k+1) acc
| otherwise = acc
rangeJ :: Int -> Int -> Int -> Int
rangeJ i j acc
| j < 1000 = rangeJ i (j+1) (acc + rangeK i j 0 0)
| otherwise = acc
rangeI :: Int -> Int -> Int
rangeI i acc
| i < 1000 = rangeI (i+1) (acc + (rangeJ i 0 0))
| otherwise = acc
C
main()
{
printf("%d\n", rangeI(0, 0));
return 0;
}
rangeK(i, j, k, acc)
{
if (k < 1000) {
if (i * i + j * j + k * k % 7 == 0)
return rangeK(i, j, k+1, acc+1);
else
return rangeK(i, j, k+1, acc);
} else
return acc;
}
rangeJ(i, j, acc)
{
if (j < 1000)
return rangeJ(i, j+1, acc + rangeK(i, j, 0, 0));
else
return acc;
}
rangeI(i, acc)
{
if (i < 1000)
return rangeI(i+1, acc + rangeJ(i, 0, 0));
else
return acc;
}
I tried to keep both programs as similar as possible. I'm pretty
confident that the algorithm being executed are exactly the same. That
is, there's no lists being used vs. arrays or anything like that. I even
used Int instead of Integer to make sure an equivalent version of +, *
and mod are called (perhaps that was what I did wrong?)
I compiled the haskell code with ghc -O3 and I compiled the C code with
gcc -O3. The execution time of the programs were dramatically different.
You can test it yourselves, but here is the time I've got in my system:
The Haskell version:
real 0m45.335s
user 0m45.275s
sys 0m0.004s
against the C version:
real 0m6.021s
user 0m6.004s
sys 0m0.004s
Also, I found it interesting that a iterative version of that algorithm
in C ran in the same time as the recursive version. So it seems like gcc
was successfuly able to make those tail recursive functions into iterations.
It strikes me as surprising that Haskell would perform so much slower in
that example. I was expecting maybe a few seconds due to the garbage
collector or something like that, but not more than 7 times slower.
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
