[Haskell-cafe] does the compiler optimize repeated calls?

John Hughes rjmh at cs.chalmers.se
Wed Sep 6 10:42:10 EDT 2006



On 9/6/06, Tamas K Papp <tpapp at princeton.edu> wrote:
  

>> or does the compiler perform this optimization?  More generally, if a
>> function is invoked with the same parameters again (and it doesn't
>> involve anything like monads), does does it makes sense
>> (performancewise) to "store" the result somewhere?
>    
>

I was wondering something like this too, and then I found this email:
http://www.haskell.org/pipermail/glasgow-haskell-bugs/2004-December/004530.html

So I guess it is as Stephane said: theoretically possible but not actually done?

--eric the perpetual newbie

  

The trouble is that this isn't always an optimisation. Try these two 
programs:

powerset [] = [[]]
powerset (x:xs) = powerset xs++map (x:) (powerset xs)

and

powerset [] = [[]]
powerset (x:xs) = pxs++map (x:) pxs
  where pxs = powerset xs

Try computing length (powerset [1..n]) with each definition. For small 
n, the second is faster. As n gets larger, the second gets slower and 
slower, but the first keeps chugging along. The problem is that the 
second has exponentially higher peak memory requirements than the first. 
Round about n=25, on my machine, all other programs stop responding 
while the second one runs. You don't really want a compiler to make that 
kind of "pessimisation" to your program, which is why it's a deliberate 
decision to leave most CSE to the programmer. You can still write the 
second version, and suffer the consequences, but at least you know it's 
your own fault!

John



More information about the Haskell-Cafe mailing list