Example of LazyEvaluation -- implemented in Assembly language
[Extracted from LazyEvaluationOverhead. See RonJeffries' comments on that page for conclusions.]
Suppose we want to calculate (a + b) + (c + d) + (a + b) using lazy evaluation.
We must build a data structure, something like
#1: + a b
#2: + c d
#3: + #1 #2
#4: + #3 #1
perhaps, with a place to store a calculated result where each #n: is. Creation of this structure is generally part of the expression compilation process, though it need not be. The compiler then generates code like this:
lw,1 a
aw,1 b
lw,2 c
aw,2 d
aw,2 1
aw,2 1
(it's a fairly decent compiler).
The time to build the above code is subtracted from the tree version. Instead, the tree is interpreted by entering with the address of the desired result, #4, in, say, register 9, and a stack pointer in register 8, calling on register 7:
interp res 0
lw,1 data,9 // load data cell for subexpression
cw,1 NULL
be returnResult
lw,1 data+1,9 // index of opcode
call,10 opcodes,1 // opcode
stw,2 data,9 // save result
returnResult res 0 // result in register 2
return,7
opcodes res 0
addOpcode
subOpcode
...
addOpcode res 0 // reg 9 points to my entry
lw,1 operand1,9 // operand 1 address
call,11 getOperand
stw,2 temp
lw,1 operand0,9 // operand 0 address
call,11 getOperand
aw,2 temp // *** this is the actual add ***
return
getOperand res 0 // register 1 contains my operand address. return = 11
cw,1 varTable // is it a variable
bne calc
lw,2 0,1 // it's a variable, load to register 2
return
calc res 0 // it's an expression, recur
stw,9 stack,8 // push register 9.
aw, 8 =1
lw,9 1 // address of expression to 9
call,7 interp
return,11
Now there's no way this code works, I don't have unit tests for it. But hopefully it's approximately right. The *** line is the actual add, the rest is interpretation overhead, which turns out to be about 10 instructions per value. Hmm, that was an accident.
Yes, thats the basic overhead. But there are some 'considerations':
- The compiler can 'inline' those lazy operations, that are strict, especially math operations.
- Many operations require more than one instruction anyway (e.g. memory allocation).