Ground Up

Jerzy Karczmarczuk
Thu, 28 Feb 2002 17:36:55 +0100

Hal Daume III about Haskell optimization problems:


> and in Haskell:
> sumProdTo n = (sumTo n, prodTo n)
>   where sumTo 1 = 1
>         sumTo n = n + sumTo (n-1)
>         prodTo...
> etc.
> Now, I want to optimize.  In C, I can fuse the loops so I'm only
> traversing once, which would give me moderate speed improcement.  In
> Haskell, I could also "fuse" the loops and say:
> sumProdTo 1 = (1,1)
> sumProdTo n = (n+s,n*p)
>     where (s,p) = sumProdTo (n-1)
> but this is actually *slower* but there's no way for me to know this
> without actually running it.  in fact, in the discussion about this on the
> list, no one was really able to give a definitive answer as to why.  there
> was a lot of handwaving about pointers to the heap to pointers to other
> things, and obviously it has to do with boxing and unboxing and stuff like
> that, but I think this is a problem.

I didn't follow that discussion, but let's be serious. Really.
Your second version constructs and destroys plenty of tuples, of
ephemeric data structures which live one step only, and this is
obviously costly. "No way to know this?" Are you sure?

WHAT is a problem?
I see only one: a Haskell user should master the essentials of 
a reasonably professional functional style.

sumProdTo n = spt n 1 1 where
 spt 1 s p = (s,p)
 spt n s p = spt (n-1) (n+s) (n*p)

The only touchy point in such circumstances may be the laziness which
can be dealt with. Then, the above is more equivalent to the optimized
C code than your version.

> i'm not sure what the moral is. ...

> i think the only real solution would be to put up a web page or something
> that contains things like "this looks like it would speed up your program
> but it will actually slow it down."  or at least some better tips on
> getting your programs to run quickly.

For me the moral is: I disagree with

> ... it's just that i don't think it's
> fair to say you don't have to understand what the compiler is doing to
> write code.

This is not the question of this or that *compiler*, but of understanding
the basics of data processing independent of the language. I am abhorred by
the idea of putting down: "this looks like it would speed up your program..."
in cases where it is rather clear that it might not. Please do the same 
experience in C with dynamically allocated tuples.

Jerzy Karczmarczuk