[Haskell-cafe] GHC vs GCC

[Rafael Cunha de Almeida]

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.