On Sun, 2007-10-28 at 12:01 -0700, Don Stewart wrote:
jerzy.karczmarczuk:
Stefan O'Rear adds to the dialogue:
Prabhakar Ragde wrote:
Jerzy Karczmarczuk wrote:
Just a trivial comment... 1. Don't speak about comparing *languages* when you compare *algorithms*, and in particular data structures. 2. Please, DO code the above in C, using linked lists. Compare then. 3. Check the influence of bare printing, separated from the computation.
Isn't GHC clever enough to optimize away the entire computation if there is no I/O?
Yes, but GHC is not clever enough to solve the perfect number classification problem. 'length' will suffice, and is prefered for most enumeratioon benchmarks.
My point didn't concern that point. Haskell compiler cannot change an algorithm using lists into something which deals with indexable arrays, usually faster. Indexing may be faster than the indirection, and the allocation of memory costs. And there is laziness... That's why I proposed to check what happens if one uses linked links in "C". Well, the follow-ups seem to suggest that the main time eater was the overloading. I must say that I am really astonished. It is hard to believe that such a signature can make a factor of 8. Never seen that before.
That fits with my experience writing low level numeric code -- Integer can be a killer.
Inline machine operations v. out-of-line calls to an arbitrary precision integer C library: there shouldn't be any surprise here. I could make it even slower by making a Nat type and giving it the type Nat -> [Nat]. Also, this is a well known issue. It is common for people to, for example, write naive fib and then say that Haskell is useless because it's orders of magnitude slower than naive fib in C or whatever. Then you tell them to add an Int -> Int type signature and all of a sudden Haskell is beating C soundly.