Why can't Haskell optimize this duplicate function call?

user_12685665 0
Viewed 135

In my Haskell code i use a function that gets very often called and looks like this:

doSomething x y = (a, b)
where a = expensive1 x y
      b = expensive2 x y a

Compiled with GHC 8.10.3 and -O2 my program takes about 45 seconds to run. However if i write the same function like this:

doSomething x y = (a, b)
where a = expensive1 x y
      b = expensive2 x y (expensive1 x y)

my program takes about 60 seconds to run.

Shouldn't the compiler recognize the duplicate call of expensive1 x y and optimize it away? expensive1 and expensive2 are pure functions, so recalculating expensive1 x y shouldn't be necessary. Or is the GC too aggressive and garbage collects a before before b is needed later?

haskell
1 Answers

It is a tradeoff. The optimization you propose reduces runtime but increases memory usage. It's way too hard to automatically get that tradeoff right every time, so the programmer is given control of it -- name a thing, and it's shared, don't name it, and it's recomputed.

(...mostly. As always with these things, it's complicated. But this is the 10km view of the answer.)

By the way, the name of this optimization is "common subexpression elimination". Googling that should get you quite a lot more information about different compilers' choices in this domain.

user_7916040
Related