How is lazy evaluation implemented in a way that doesn't require more overhead than gains produced?

Question

I understand that there are places where lazy evaluation prevents calculations from being needed. For example, adding two numbers then passing them into a function argument that ends up never being used.

But it seems to me like there would be a lot of overhead to storing and loading the operations that are to be used later and that more often than not that overhead would cancel out any gains.

Can someone address this?

Answer 1

You're right. Lazy evaluation does have significant overhead, and most of the time you won't get practical performance gains from it. The main reason for lazy evaluation is that it is convenient -- it makes Haskell's language semantics cleaner, and (for example) lazy/infinite lists can sometimes be handy for the programmer.

Fortunately, the compiler can often optimize lazy mechanics out of the inner loop, where a naive implementation would otherwise incur a substantial performance penalty.

Answer 2

Unexpectedly, it turns out that GHC's implementation of lazy evaluation doesn't introduce appreciable overhead over similar strict runtime systems. The apparent "overhead" of creating a thunk for lazy evaluation (i.e., "storing" the operation to be used later) and eventually forcing its evaluation (i.e., "loading" it) replaces the strict evaluation "overhead" of creating a stack frame, calling the function, and returning. As a result, the cost of a function call is shifted in time but not significantly increased.

It is true that strictness (either explicitly introduced by the programmer or automatically identified by the compiler) is sometimes necessary for good performance, but that's usually because strictness allows unboxing and related optimizations or, in some cases, avoids costly memory leaks which lead to excessive garbage collection overhead. Lazy evaluation itself is not significantly more costly than strict evaluation.

In this answer I provide a somewhat detailed comparison of function calls in the GHC RTS and a typical Java VM implementation. That answer is focused on memory usage (because the question was about garbage collection), but much of the discussion applies to performance more generally.

Summarizing the relevant bits, if you are trying to determine the overhead in calling a function to multiply two numbers:

bar :: Int -> Int -> Int
bar a b = a * b

as invoked by some other function:

foo :: Int -> Int -> Int -> Int
foo x y z = let u = bar y z in x + u

then in a typical strict implementation, like the Java JVM, the byte code would probably look something like:

public static int bar(int, int);
  Code:
    stack=2, locals=2, args_size=2
       0: iload_0   // push a
       1: iload_1   // push b
       2: imul      // multiply and push result
       3: ireturn   // pop result and return it

public static int foo(int, int, int);
  Code:
    stack=2, locals=4, args_size=3
       0: iload_1   // push y
       1: iload_2   // push z
       2: invokestatic bar   // call bar, pushing result
       5: istore_3  // pop and save to "u"
       6: iload_0   // push x
       7: iload_3   // push u
       8: iadd      // add and push result
       9: ireturn   // pop result and return it

The overhead of the bar function call (i.e., the difference between the above and if bar was inlined) looks like it's two argument pushes, the call itself, and the return.

For the lazy version, GHC (without optimization) compiles this code as something like the following pseudocode:

foo [x, y, z] =
    u = new THUNK(sat_u)                   // thunk, 32 bytes on heap
    jump: (+) x u

sat_u [] =                                 // saturated closure for "bar y z"
    push UPDATE(sat_u)                     // update frame, 16 bytes on stack
    jump: bar y z

bar [a, b] =
    jump: (*) a b

The overhead of the lazy bar function call is the creation of a thunk on the bump heap (as fast as stack) that includes two arguments and a pointer to sat_u (plus room for the return value, though there's no "cost" for this), and a "call" (not visible in the above code) when the (+) function forces the value u by jumping to sat_u. The update frame more or less replaces the return. (In this case, it can be optimized away.)

The bottom line is that, at least to a first approximation, lazy evaluation as implemented in GHC is roughly as fast as strict evaluation, even when everything is actually evaluated.

Answer 3

It works because compiler optimization try to remove laziness when it isn't necessary.

if it sees that next computation will consume results of previous computation it just generate code strict code.

Answer 4

Since Haskell is pure language, lazy evalutions plays an important role. This is not just a feature of the language that allows the programmer to write in a diclarative style without worrying about the sequence of calculations.

Let's take an example.

`sum $ map (^2) [0..100]`

What will happen here in strict semantics. The map function is evaluated first. It will use the entire input list and generate (with allocation because Haskell is pure) output list. Then sum will calculate the result.

But in lazy semantics, the intermediate list in this example will not be constructed. So there will be no unnecessary work with memory. Means less work for the garbage collector.

Therefore, for pure languages, lazy semantics is one way to avoid overheads of constructing intermediate objects.