[Haskell-cafe] does the compiler optimize repeated calls?
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:
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
powerset  = []
powerset (x:xs) = powerset xs++map (x:) (powerset xs)
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!
More information about the Haskell-Cafe