[Haskell-cafe] GHC vs GCC

Rafael Cunha de Almeida almeidaraf at gmail.com
Fri Mar 26 13:46:58 EDT 2010


During a talk with a friend I came up with two programs, one written in
C and another in 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

	    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);
				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));
			return acc;
	rangeI(i, acc)
		if (i < 1000)
			return rangeI(i+1, acc + rangeJ(i, 0, 0));
			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.

More information about the Haskell-Cafe mailing list