Related articles 

Fast ??? Opcodes vs. CodeTrees varvell@isi.com (19930323) 
Newsgroups:  comp.compilers 
From:  varvell@isi.com (Dave Varvell) 
Keywords:  interpreter, performance, question 
Organization:  Integrated Systems, Inc. 
Date:  Tue, 23 Mar 1993 23:00:42 GMT 
Hello compiler folks,
I'm wandering what the fastest data structure / code evaluator is. I've
tried various ways to express the intermediate form for a simple language
that has "For ... endFor", "If ... elseIf ... else ... endIf" and "While
... endWhile" constructs. The language also allows Logical, Integer and
Float datatypes with Scalar, Vector and Matrix shapes.
The four different scenarios that I've investigated are illustrated by
example. The example script is for a general vector sum as shown below
with inputs, u(*) and outputs, y(*).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%
extern: int nIn, nOut, signs(1..nOut);
nbranch = nIn / nOut;
For i = 1 : nOut do
If signs(1) > 0 then
y(i) = u(i);
else
y(i) = u(i);
endIf;
j = nOut;
For k = 2 : nbranch do
If signs(k) > 0 then
y(i) = y(i) + u(j+i);
else
y(i) = y(i)  u(j+i);
endIf;
j = j + nOut;
endFor;
endFor;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%
The script can be instantiated multiple times in a software component.
One particular instantiation could be as follows.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%
nIn = 36
nOut = 9
signs = [ 1, 1, 1, 1 ]
%%%%%%%%%%%%%%%%%%%%%%%%%%%%
I. Compiled C

A simple mechanical translation of the script to C, then compile,
link and run. The translation is as follows.
nbranch = 36 / 9;
for (i=0; i < 9; i++) {
if (signs[0] > 0)
y[i] = u[i];
else
y[i] = u[i];
j = 8;
for (k=1; k < nbranch; k++) {
if (signs[k] > 0)
y[i] = y[i] + u[j+i];
else
y[i] = y[i]  u[j+i];
j = j + 9;
}
}
II. Compiled Partial Evaluated C

Unroll loops with constant ranges and evaluate Ifs with constant
expressions. Evaluate statements with constant expressions and
join "x = 0" and "x = x + y" statements. Since the signs are known,
the following code is emitted.
y[0] = u[0]  u[9] + u[18]  u[27];
y[1] = u[1]  u[10] + u[19]  u[28];
y[2] = u[2]  u[11] + u[20]  u[29];
y[3] = u[3]  u[12] + u[21]  u[30];
y[4] = u[4]  u[13] + u[22]  u[31];
y[5] = u[5]  u[14] + u[23]  u[32];
y[6] = u[6]  u[15] + u[24]  u[33];
y[7] = u[7]  u[16] + u[25]  u[34];
y[8] = u[8]  u[17] + u[26]  u[35];
III. Opcodes for both Control Flow and Expressions

Use Reverse Polish Notation opcodes for expressions and evaluate
them with a stack machine.
> Load nIn; Load nOut; Divide; Store nbranch;
Also use instructions for Control Flow constructs.
> Load signs(1); Load 0; GreaterThan
> Test #InstructionWordsToJumpIfFalse
> Load u(i); Store y(i)
> Jump #InstructionWordsToJumpOverElse
> Load u(i); Negate; store y(i)
IV. Hybrid Statement Tree with Opcode Expressions

Use Reverse Polish Notation opcodes for expressions and evaluate
them with a stack machine, but, the control flow structures are
represented by a Statement Tree. The Statement Tree is traversed
by a recursive visit to statement nodes.
For "i"  <Load 1; Load 9; DefineRange>

 [0] If  <Load signs(1); Load 0; GreaterThan>
 
  [0] <Load u(i); Store y(i)>
 
 else
 
  [0] <Load u(i); Negate; Store y(i)>

 [1] <Load nOut; Store j>

...
My experience has shown that recursive tree node visiting software used in
the Statement Tree is about 20% slower than the RPN machine code emulation
used in III. I also find that my machine code version is 56 times slower
than a straight forward translation to C. I haven't tried mapping the
Statement Tree into a linear array and eliminating the recursive calls
because I haven't found a style for coding it this way that looks
comfortable to me.
I would like to break the "56 times slower than C" barrier when using my
evaluator/debugger.
SpeedUp Factor

Compiled Partial Evaluated C 1.54.0
Compiled C 1.0
Opcodes for both Control Flow and Expressions 0.18
Hybrid Statement Tree with Opcode Expressions 0.15
Any related experiences or hints would be appreciated. I can be reached
directly by email.

dave
varvell@isi.com

Return to the
comp.compilers page.
Search the
comp.compilers archives again.