Fast ??? Opcodes vs. CodeTrees

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 5-6 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 "5-6 times slower than C" barrier when using my
evaluator/debugger.


                                                                                            SpeedUp Factor
------------------------------------------------------------
Compiled Partial Evaluated C 1.5-4.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.