Lazy Evaluation Example In Assembly

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).

---

CategoryLazyPattern