[tcljava-dev] Prototype Jacl Runtime Compiler

[Bruce J. <nm...@ma...>]

Dear Jacl folk,

I've been doing some work recently to prototype some methods for
increasing the performance of Jacl.  Originally I did a protoype
that  focussed on actually compiling Jacl code to Java byte codes.
While this looked feasible it was quite complicated and looked
like it would take quite a bit of effort to complete.  I've spent
some time recently looking at a different approach.  This consists
of compiling Jacl code to a series of Instruction objects
which are then executed by iterating through the list of
instructions and calling the "exec" method for each.  The code is
relatively simple and at present simple, artificial benchmarks are
sped up by about 2-10x.

For example:

proc tproc {} {
string length abc
string length abc
... repeat to a total of 30 lines
}

is sped up 10x, with a StringInstruction that  explicitly executes
the "string length" command.

proc tproc {} {
set a1 duck
set a2 $a1
set a3 $a2
set a4 $a3
set a5 $a4
set a6 $a5
set a7 $a6
set a8 $a7
set a9 $a8
set a10 $a9
}

is sped up about 3x, and is ultimately limited by the lack of
explicit optimization of local variable lookup.  Implementation
of a local variable table should substantially increase this 
performance.


Note that these calculations are done after first executing the
procedure multiple times.  The initial speed increase is lower.
I'm guessing this is an effect of the Java Hot Spot compiler.


My company has some money available to fund some work on Jacl
optimization and am currently considering the best way to proceed.  The
protoype work I describe here may not be the best solution and may not
be developed beyond this stage. There are certainly alternative 
approaches.
I thought I'd make this code available and get some feedback on it.
I'd welcome opinions on whether people think this approach is 
reasonable.

Note that the code is written simply to get a quick idea of the value 
in this
approach and could be substantially rewritten.  Also note that only the 
"if" and
"for" flow instructions are implemented.  Jacl code within loops such 
as the "foreach"
command is not yet compiled so no performance increase will be seen.

Running the test suite (with certain tests disabled) gives the 
following results:

all.tcl:        Total   4912    Passed  4565    Skipped 294     Failed  
53

I disabled about 5 test files that caused the testing to crash and have 
not yet
investigated the source of these problems.

Note: running the code gives the following message when procedures are 
created:

WARNING: This code running with experimental Jacl runtime compiler 
support!
It is not now ready, and may never be ready, for production use!


I'll be posting the code shortly at my web site, but if anyone would 
like it sooner just email me
and I'll send you a copy (the compressed code is only 46Kb).
It consists of 11 modified or new Java source files that can just be 
copied into
the Jacl 1.3.2 distribution that Mo recently released.

best regards,

Bruce

Bruce A. Johnson
One Moon Scientific, Inc.
EDC III
211 Warren St
Newark, NJ 07103

Phone 908 517-5105
Fax      908 517-5107
Email  br...@on...
Web    www.onemoonscientific.com



More details on the methodology follow:


Compilation proceedes by parsing Jacl scripts using code translated 
from the C version of Tcl.
During compilation, instructions are added to a list of instructions.  
Instructions consist of
Java objects that are instances of classes that extend an abstract 
Instruction class:

    static public abstract class Instruction {
         private String name = null;
         private int stackEffect = 0;
         Instruction(String name,int stackEffect) {
             this.name = name;
             this.stackEffect = stackEffect;
         }
         public String toString() {return name;}

         abstract int exec(CompileEnv env,Object instructions[], int iC) 
throws TclException;
     }

Each Instruction class provides a concrete implementation of the "exec" 
method.

For example, the PUSH Instruction:

         public static final Instruction PUSH =   new 
Instruction("push", 1) {
             int exec(CompileEnv env,Object instructions[],int iC) {
                 int index = ((Integer) instructions[iC+1]).intValue();
                 env.stack.push(env.literalsArray[index]);
                 return 1;
             }
         };


More complicated instructions, for example, those that implement flow 
control extend the
Instruction class.

For example, the If instruction is implemented as follows (note that at 
present the expressions in the If command
are not compiled, though the execution bodies are:

     class IfInstruction extends Instruction {
         IfInstruction(String name,int stackEffect) {
             super(name,stackEffect);
         }
         ArrayList branches = new ArrayList();
         ArrayList expressions = new ArrayList();
         void addInstructionBranch(ArrayList branch) {
             branches.add(branch);
         }
         void addExpression(String expression) {
             expressions.add(expression);
         }

         int exec(CompileEnv env,Object instructions[],int iC) throws 
TclException {
             int i = 0;
             for (i=0;i<expressions.size();i++) {
                 boolean value = interp.expr.evalBoolean(interp,(String) 
expressions.get(i));
                 if (value) {
                     break;
                 }
             }
             if (i < branches.size()) {
                 Object myInstructions[] = ((ArrayList) 
branches.get(i)).toArray();
                 execInstructionList(interp,myInstructions, false);
             } else {

             }
             return 1;
         }
     }

At present there are only about 16 instructions implemented.

Execution of a compiled script proceeds by incrementing through the 
list of instructions and calling
the "exec" method of each.  This relies on the simple use of Javas 
intrinsic method dispatch capabilities, rather
than complicated if/then or switch statements.


Actual Java source files used to implement the compiler/execution 
system are described below:


  src/jacl/tcl/lang/Procedure.java
       Modified to call compiler when procedure is created.
       If global Tcl variable CompileProc(procedureName) is present and 
set to false
           then the procedure will not be compiled.
       If procedure has been compiled, then when it is executed the 
compiled instructions will be executed.

src/jacl/tcl/lang/VarType.java
       Used by compiler in managing variables, Note: there is no 
optimized support yet for local variables

src/jacl/tcl/lang/Compiler.java
     Compiles procedures

src/jacl/tcl/lang/CompileEnvjava
     Compilation environemnt.
     Containts subclasses for an Execution stack and Instructions to 
execute.
     Current instructions are:
          Instructions for manipulating objects on stack
              PUSH, DISCARD, POP, DUP, CONCAT,
          Instructions for invoking execution
              INVOKE,
          Instructions for moving stack elements between stack and 
variables
              LOAD_SCALAR_STK, STORE_SCALAR_STK, STORE_ARRAY_STK, 
LOAD_ARRAY_STK, LOAD_SCALAR, LOAD_ARRAY
          Prototype of a math instruction:
              MULT
          Flow control execution
              IfInstruction, ForInstruction
          Compiled Tcl commands
              StringInstruction (only implements "string length" at 
present

src/jacl/tcl/lang/CTclParse.java
     Modified version of TclParse for use with Compiler

src/jacl/tcl/lang/CParser.java
     Translation of Parser for C version to parse scripts prior to 
compilation


the following are present, but not complete, functional or used yet

src/jacl/tcl/lang/OperatorDesc.java
    Math and Boolean operators for compiling expressions
src/jacl/tcl/lang/MathFunc.java
    Math functions for compiling expressions
src/jacl/tcl/lang/ParseExpr.java
     Used to parse expressions
src/jacl/tcl/lang/ParseExpr.java
     Used to compile expressions
src/jacl/tcl/lang/CompCommand.java
     Interface for commands that are compiled (this is not now used, and 
may not be used)