[Haskell-cafe] newbie optimization question

[Derek Elkins]

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.