Lazy Evaluation Overhead

Wow, this page is strange. It talks very much about the feasibility of lazy evaluation as an optimisation technique, whereas I deem lazy evaluation mostly a design technique. And it doesn't even touch the subject where lazy evaluation overhead is really big, namely, memory consumption. -- PanuKalliokoski

[From LazyEvaluation]

From TransfoldPattern: "Unfortunately, LazyEvaluation usually carries a performance penalty."

Why is that? I thought that LazyEvaluation was supposed to make things more efficient, not less. -- PhilGoodwin

To support LazyEvaluation one has to build suspended calculations (usually implemented with closures). These suspended calculations take time to create, consume memory (i.e., may make garbage collection slower), and have to be detected and evaluated when encountered. If all of this is supported by a your programming language then the penalties can be very small but if you have to emulate some of this you may notice a higher penalty. I have no concrete figures but I am assuming that you still would not care unless you were doing real time stuff. -- ThomasKuehne

If you have "no concrete figures," then what is your argument based on? For any given operation, there are multiple ways to code it, often with trivial differences in the number of machine cycles required; evaluation is no different. If the time differences between Lazy Evaluation and Full Evaluation are critical to the success of a project, I would suggest the project is already in risk of failure.

Actually, for HardRealTime, you usually care less about average execution time than worst-case execution time. Any amount of overhead makes the worst-case even worse, so LazyEvaluation will usually be a BadIdea in hard real time projects. -- DougKing

Modern compilers for LazyLanguages? use StrictnessAnalysis to determine what code must be executed, and that code is implemented with StrictEvaluation, avoiding the overhead of closure creation. -- NoelWelsh

If the calculation is expensive, and you only really need the result some of the time, LazyEvaluation is faster. But if the calculation is relatively cheap (relative to object overhead and flag checking) and all computations must actually be done, then LazyEvaluation is slower -- possibly much slower. -- JeffGrigg

What is the mechanism by which you are envisioning LazyEvaluation being implemented? It doesn't seem like there has to be much if any penalty at all depending on the situation. -- PhilGoodwin

It definitely depends. If you have an interpreter anyway, LazyEvaluation is easy to add and will almost certainly speed things up. You'd add result-caching first, of course, and then with recursive descent evaluation, LazyEvaluation is essentially free. -- RonJeffries

. . . . .

Suppose we want to calculate (a + b) + (c + d) + (a + b) using lazy evaluation.

: [See LazyEvaluationExampleInAssembly for the example code that was extracted from this point.]

So the raw interpretation overhead is approximate 10x, as always. The cost of running the code optimizer was saved. Does a code optimizer take more than 10 instructions per instruction generated? Well, quite possibly yes - certainly no less.

So if the expression is entered and compiled on the fly, LazyEvaluation is about the same, and much easier to code. If the expression is entered once and used every day, LazyEvaluation probably isn't the way to go.

On the other hand, if the expression computes a whole tax form's bottom line and is used twice, LazyEvaluation pays off big time, especially since you probably don't know how to compile a tax form. But that's another story. -- RonJeffries

I never thought about employing interpretation to realize LazyEvaluation. With an object oriented language it is very easy to do by using objects as closures for the suspended calculations. Often Smalltalk dialects already come with a little LazyEvaluation framework, i.e., a class LazyValue? or UninitializedObject?, which sets you up nicely to use LazyEvaluation. -- ThomasKuehne

. . . . .

See LazyEvaluationExampleInVisualBasic for an example of using LazyEvaluation in a VisualBasic program.

(The objective of this exercise is to show that LazyEvaluation is complex and slow: That you shouldn't use it unless the computation is expensive/difficult, and the result won't be needed in many cases.) -- JeffGrigg

i.e.: YouArentGonnaNeedIt - anon

What I get from looking at this is that the runtime overhead consists of: allocating and initializing an object, making a method call to trigger the calculation, testing for a cached result and caching the result if needed (assuming CallByNeedSemantics). I see that this is not trivial, certainly most calculations won't benefit from this treatment. However, it doesn't seem like a very high price to pay for situations that could make even trivial use of LazyEvaluation. Like when you want to delay a calculation, execute it optionally, or reuse it's result. I think I'm really saying the same thing as Jeff except that I'm excited about the benefits while he's worried about the costs. -- PhilGoodwin

Although there are slight performance drawbacks in emulating LazyEvaluation, when it is appropriate (see section Applicability in my thesis) it is just fantastic. You'll be able to avoid huge intermediate data structures, reconcile modularization with calculation speed, and reduce the complexity of algorithms by the way you use them. -- ThomasKuehne

From any language I have used, you can always rewrite code from using Lazy Evaluation to Full Evaluation or vice-versa whenever you wish. I recommend the following principles. First, use the natural evaluation method of the language, unless you have a measurable end user performance problem. Second, never rely on Lazy Evaluation to guarantee operations will not be performed; explicitly code this need.

CategoryLazyPattern