5
: A Basis For Comparison

The pJHI is now capable of running both statement-based and instruction-based programs. It is now time to select a set of benchmark programs which can be encoded under the two schemes, and their efficiency compared.

Before selecting specifications for appropriate benchmark programs, it is worth observing that the instruction-based interpreter as developed in Chapter 4 will be greatly disadvantaged when compared to the statement-based interpreter developed in Chapter 3. The main reason for this is:

• The instruction-based interpreter must use the operand stack at least twice for each operand required in a computation. The statement-based interpreter merely uses the features of the Java language to pass operands up through the method invocations in the program tree. The instruction-based interpreter therefore uses an explicit stack implemented in the Java language while the statement based interpreter makes use of the implicit stacks which are part of the Java VM.

It is important to realise that it is a fair and legitimate advantage of a tree-based approach for the operand stack to become implicit and encodable within the interpreter itself rather than being inherent to the encoding of the program being executed. However, it is not fair and legitimate for an implementation of a tree-based interpreter which is to be compared with an instruction-based interpreter to use a native language mechanism to provide for its stack requirements while the instruction-based interpreter is saddled with the overhead of using an explicit class to deal with its stacks.

This leads to a dilemma, as it inconvenient to write a tree-based interpreter without using native stacks, because it is natural for statements to call their substatements, and take advantage of the implicit method invocation stack of a class-based language. Approaching the problem from the other side, it is impossible to write an emulated Java VM without using an explicit stack- the stack is inherent to the definition of the instruction-based approach of the Java VM, and hence is also inherent to the Picojava instruction interpreter which attempts to emulate it (see Chapter 2).

This dilemma is noted, and in Chapter 7 some future projects will be discussed which might alleviate the difficulty. But for the purposes of this thesis, however, it will suffice to create a modified version of the tree interpreter which uses both the implicit stack of method invocations provided by Java as well as the explicit stack used in the instruction based interpreter.

This stacking tree interpreter, which will be described relative to the existing tree-based interpreter in §5.1, is effectively unfairly disadvantaged, because the explicit stack is not required. However, it will provide a low water mark that can be thought of as providing an indication of the "worst case" efficiency for a tree interpreter. Our optimized tree interpreter (developed in Chapter 3) will provide the corresponding high water mark of "best case" efficiency for a tree interpreter. In this way, we will be able to make statements like "a tree interpreter is, in the worst case, still faster than an instruction interpreter, and in the best case it is x percent faster."

5.1 Stacking Tree Interpreter

The Picojava stacking tree interpreter follows the definition of any other Picojava tree interpreter as given in Chapter 2. However, its implementation differs from the tree interpreter developed in Chapter 3, in that it maintains an explicit operand stack. This explicit operand stack and its implementation is largely borrowed from the instruction interpreter developed in Chapter 4. In this way, the stacking tree interpreter implementation fills the middle-ground between the optimized tree interpreter implementation of Chapter 3 and the comparable code interpreter developed in Chapter 4.

Many existing classes from the optimized need to be modified. The new classes will be defined as subclasses of the existing classes, in much the same way as we used the Code prefix for the implementations of classes in the instruction interpreter, discussed in §4.3. The prefix used for subclasses used within the stacking tree interpreter will be Stacking.^[9]

To differentiate the implementations of Statements in the stacking tree interpreter, which will use an explicit operand stack, from those of the optimized tree interpreter developed previously, we will call the classes which implement Statements in the stacking tree interpreter Instructment classes.

5.1.1 Inclusion Of Operand Stack

The definition of StackingSymbolTable shares some of the methods of CodeSymbolTable:

• push(AlgebraicOrStructured): places a new data value on the current operand stack.
• pop(): returns the AlgebraicOrStructured value on top of the current operand stack, removing it from that stack.
• peek(): returns the AlgebraicOrStructured value on top of the current operand stack, preserving that stack.
• pushStack(): creates a new operand stack and makes it the current stack.
• popStack(): restores the previous operand stack.

The stack of operand stacks, and the operand stacks themselves are both implemented using instances of java.util.Stack.

5.1.2 Modified Implementation Of Methods

StackingMethods are constructed using calls analogous to those in §3.4.10. The methods provided are also similar, with the obvious alterations to ensure that Instructment_Action and StackingSymbolTable are the classes used as parameters.

A functional change occurs in the setParameter method. The actual parameter expressions are still calculated, but as Instructment_Action objects place their results on the operand stack, an additional pop is required.

5.1.3 Modified Implementation Of Blocks

StackingBlocks are constructed using calls analogous to those in §3.4.11, but the name of addStatement(Statement) becomes addInstructment(Instructment). The methods provided are also similar, but getNumberStatements() becomes getNumberInstructments().

A functional change occurs in the run method. Before the Instructments comprising a Block are executed, a new operand stack is created using pushStack. After the Instructments complete, the operand stack is removed with a call to popStack.

5.1.4 Modified Implementation Of Flow Control Statements

The flow control Statements are merely recast as Instructments. Statement_Conditional becomes Instructment_Conditional, while Statement_ Iteration becomes Instructment_Iteration.

5.1.5 Modified Implementation Of Constant Value Expressions

A constant value expression is now implemented by placing the constant value encoded within the statement on the operand stack (c.f. §3.4.13). This is achieved using the push method within the augmented StackingSymbolTable class. Consider Instructment_Action_ Evaluate_Constant_SignedInteger5 as an example:

abstract class Instructment_Action_Evaluate_Constant_

    Algebraic extends Instructment_Action_Evaluate_ 

    Constant
{

  protected Algebraic value;

  public Instructment_Action_Evaluate_Constant_

      Algebraic(Algebraic newValue)
  {
    value=newValue;
  }

  public void run(StackingSymbolTable symbolTable)

  {
    symbolTable.push((AlgebraicOrStructured)value);
  }
}

class Instructment_Action_Evaluate_Constant_Algebraic_

    SignedInteger5 extends Instructment_Action_ 

    Evaluate_Constant_Algebraic
{

  public Instructment_Action_Evaluate_Constant_ 

      Algebraic_SignedInteger5(Algebraic newValue)
  {
    super(newValue);
  }

  public void list(StackingSymbolTable symbolTable)

  {
    System.out.print("("+((Algebraic_SignedInteger5)
                          value).getValue()+")");
  }
}

5.1.6 Modified Implementation Of Unary And Binary Operations

The unary and binary operations are implemented by code based upon that of Instructment_Action_Evaluate_Constant (§5.1.5), except that these two operations must also use the StackingSymbolTable's pop operation to obtain their operands.

Consider the run method for Instructment_Action_Evaluate_BinaryOp_ Sum (c.f. §3.4.14):

  public void run(StackingSymbolTable symbolTable)

  {
    operand2.run(symbolTable);
    operand1.run(symbolTable);
    symbolTable.push((AlgebraicOrStructured)new
                       Algebraic_SignedInteger5(
                         ((Algebraic_SignedInteger5)
                          symbolTable.pop())
                         .getValue()+

                         ((Algebraic_SignedInteger5)
                          symbolTable.pop())
                         .getValue()));
  }

5.1.7 Modified Implementation Of Data Transfer Statements

The data transfer statements operate on a value from the variable dictionary, either replacing it with a new value taken from the operand stack (Instructment_Action_Reference), or placing its value on the operand stack for use in a computation (Instructment_Action_Assign). They therefore use the pop and push methods of StackingSymbolTable, used for manipulating the current operand stack.

A modified version of Instructment_Action_Assign is used where the value used in an assignment is not used in further calculations: Instructment_Assign. This is more usually the case. There is no corresponding Statement_Assign because it carries no significant overhead in the optimized tree interpreter to return the value of assignment to an enclosing superexpression as required.

The implementation of Instructment_Action_Reference (c.f. §3.4.15) is:

class Instructment_Action_Reference extends

    Instructment_Action
{

  private QualifiedIdentifier identifier;

  ...

  public void run(StackingSymbolTable symbolTable)

  {
    symbolTable.push(symbolTable.getQualifiedValue
                                   (identifier));
  }

  ...
}

The implementation of Instructment_Action_Assign is:

class Instructment_Action_Assign extends 

    Instructment_Action
{

  private Instructment_Action_Reference reference;

  private Instructment_Action value;

  ...
  

  public void run(StackingSymbolTable symbolTable)

  {
    value.run(symbolTable);
    if (reference==null) {
      symbolTable.push(symbolTable.setReturnValue
                         (symbolTable.pop()));
    } else {
      symbolTable.push(symbolTable.setQualifiedValue
                         (reference.getIdentifier(),
                          symbolTable.pop()));
    }
  }

  ...
}

For Instructment_Assign, there is no push made.

5.1.8 Modified Implementation Of Method Invocation Statements

Method invocation changes from that given in §3.4.16, in that the result value returned by a method is placed on the operand stack, in line with other operations in the stacking tree interpreter.

By calling the setParameter method of the StackingMethod class, the interpreter is effecively pushing the parameters required for the method call onto the stack. These are then retrieved as the run method of StackingMethod executes.

class Instructment_Action_Evaluate_Method extends 

    Instructment_Action_Evaluate
{

  private QualifiedIdentifier identifier;

  private Instructment_Action[] actualParameter;

  // Constructor to create an action statement which 
  // calls a specified method from a specified symbol 
  // table

  public Instructment_Action_Evaluate_Method

      (QualifiedIdentifier newIdentifier, Method 
       newMethod)
  {
    identifier=newIdentifier;

    actualParameter=new Instructment_Action

      [newMethod.getNumberParameters()];
  }

  // Modifier to specify the actual parameter to be 
  // substituted for the nth formal parameter of the 
  // method when invoked

  public void setParameter(int index, 

      Instructment_Action value)
  {
    actualParameter[index]=value;
  }

  // Destructor which returns the result of invoking a
  // method

  public void run(StackingSymbolTable symbolTable)

  {
    AlgebraicOrStructured result;
    ObjectInterface object;
    StackingMethod method;

    // Obtain reference to object and make current
    object=symbolTable.setCurrentObject
      (symbolTable.getParentObject(identifier));

    // Obtain reference to method
    method=(StackingMethod)(object.getParentClass())
             .getMethod(identifier.getIdentifier());

    // Set formal parameters for method

    for (int i=0; i<actualParameter.length; i++)

      method.setParameter(symbolTable,i,
                          actualParameter[i]);

    // Execute method
    result=method.run(symbolTable);

    // Pop current object
    symbolTable.popCurrentObject();
    
    // Push result onto operand stack
    symbolTable.push(result);    
  }

  // Destructor which writes a method call to the 
  // output stream

  public void list(StackingSymbolTable symbolTable)

  {
    // Write identifier
    System.out.print("("+symbolTable
                         .getQualifiedSymbolName
                            (identifier)+"(");

    // Write parameter list

    for (int i=0; i<actualParameter.length; i++)

    {
      actualParameter[i].list(symbolTable);

      if (i<(actualParameter.length-1)) 

        System.out.print(",");
    }
    System.out.print("))");
  }
}

5.1.9 Modified Implementation Of Class Instance Creation Statements

Class instance creation changes from that given in §3.4.17, in that the newly created object returned by a constructor is placed on the operand stack, in line with the behaviour of other operations in the stacking tree interpreter.

By calling the setParameter method of the StackingMethod class, the interpreter is effecively pushing the parameters required for the constructor call onto the stack. These are then retrieved as the run method of StackingMethod executes.

class Instructment_Action_Create_Object extends 

    Instructment_Action_Create
{

  private Identifier prototypeClass;

  private int constructorSignature;

  private Instructment_Action[] constructionParameter;

  // Constructor to create an object

  public Instructment_Action_Create_Object

      (SymbolTable symbolTable,
       Identifier newPrototypeClass,

       int newConstructorSignature)

  {
    prototypeClass=newPrototypeClass;
    constructorSignature=newConstructorSignature;

    constructionParameter=new Instructment_Action

      [((symbolTable.getClass(prototypeClass))
        .getMethodAt(constructorSignature))
       .getNumberParameters()];
  }

  // Modifier to specify the actual parameter to be 
  // substituted for the nth formal parameter of the 
  // method when invoked

  public void setParameter(int index, 

      Instructment_Action value)
  {
    constructionParameter[index]=value;
  }

  // Destructor which returns the result of invoking a
  // method

  public void run(StackingSymbolTable symbolTable)

  {
    ClassInterface prototype;
    ObjectInterface object;
    StackingMethod method;

    // Obtain reference to prototype class
    prototype=symbolTable.getClass(prototypeClass);

    // Create object

    object=symbolTable.setCurrentObject(new 

             Structured_Object(prototype));

    // Obtain reference to method
    method=(StackingMethod)prototype.getMethodAt
             (constructorSignature);

    // Set formal parameters for method
    for (int i=0; i<constructionParameter.length; i++)
      method.setParameter(symbolTable,i,
      constructionParameter[i]);

    // Execute method
    method.run(symbolTable);

    // Return created object
    symbolTable.push((AlgebraicOrStructured)
                     symbolTable.popCurrentObject());
  }

  // Destructor which writes a method call to the 
  // output stream

  public void list(StackingSymbolTable symbolTable)

  {
    // Write identifier of prototype class
    System.out.print("(new "+symbolTable.getSymbolName
                               (prototypeClass)+"(");

    // Write parameter list

    for (int i=0; i<constructionParameter.length; i++)

    {
      constructionParameter[i].list(symbolTable);
      

      if (i<(constructionParameter.length-1)) 

        System.out.print(",");
    }
    System.out.print("))");
  }
}

5.2 Notes On The Three Interpreter Paradigms

For each benchmark program described in §5.3, equivalent functional representations will be created using each of the three paradigms discussed below.

5.2.1 The Picojava Code Interpreter

The language of the Picojava code interpreter is given in Appendix B and discussed in Chapter 2. A concrete representation is discussed there, although programs created for the Picojava code interpreter are created in an abstract way, from the classes implemented in Chapter 4.

A Picojava code program is defined by a class which implements the interface Compilable. Given an empty SymbolTable, all that is necessary is to call compile(SymbolTable) to obtain a CompilationUnit for the program. The symbol table is used to allocate the Identifiers and to record the mapping between class identifiers and classes. When the CompilationUnit's run method is called with the same symbol table as specified in compile, the instructions comprising the program are executed.

The naming convention for the classes implementing benchmarks for the Picojava code interpreter is <benchmark>_pJC. The method getName of a Compilable code class will return this name.

5.2.2 The Picojava Tree Interpreter

The language of the Picojava tree interpreter is given in Appendix A and discussed in Chapter 2. A concrete representation is discussed there, although programs created for the Picojava tree interpreter are created in an abstract way, from the classes implemented in Chapter 3.

A Picojava tree program is defined by a class which implements the interface Compilable. Given an empty SymbolTable, all that is necessary is to call compile(SymbolTable) to obtain a CompilationUnit for the program. The symbol table is used to allocate the Identifiers and to record the mapping between class identifiers and classes. When the CompilationUnit's run method is called with the same symbol table as specified in compile, the statements comprising the program are executed.

The naming convention for the classes implementing benchmarks for the Picojava tree interpreter is <benchmark>_pJT. The method getName of a Compilable code class will return this name.

5.2.3 The Picojava Stacking Tree Interpreter

The language of the Picojava stacking tree interpreter is the same as that for the tree interpreter (§5.2.2). The concrete representation is also the same. However, stacking tree programs are created from the classes implemented in §5.1.

A Picojava stacking tree program is defined by a class which implements the interface Compilable. Given an empty SymbolTable, all that is necessary is to call compile(SymbolTable) to obtain a CompilationUnit for the program. The symbol table is used to allocate the Identifiers and to record the mapping between class identifiers and classes. When the CompilationUnit's run method is called with the same symbol table as specified in compile, the statements comprising the program are executed.

The naming convention for the classes implementing benchmarks for the Picojava stacking tree interpreter is <benchmark>_pJS. The method getName of a Compilable code class will return this name.

5.3 Benchmark Programs Overview

This section discusses the benchmarks selected for comparing the efficiency of the three interpreter paradigms, what components of the interpreters they compare and why they were selected.

5.3.1 Empty Loop Overview

The EmptyLoop benchmark executes a loop with an empty body 1000 times. The body is only "empty" in the sense it contains no more than a piece of code to increment the loop counter.

It is constructed by creating a Picojava class containing an empty constructor and a method named main whose body implements the loop in whatever paradigm is of concern.

It tests the following interpreter components:

• Constructor Method execution (once)
• Method execution (once)
• Block execution (twice for instructions; 1002 times for statements)
• Flow control (1001 times for instructions; once for statements)
• Data transfer (3001 times)
• Constant generation (2001 times)
• Binary operation (2001 times)

If there is an advantage to be obtained from removing the necessity for removing the need for branch instructions from a program encoding and placing the loop mechanics in the code of the interpreter itself, then EmptyLoop will show it strongly.

5.3.2 Deep Empty Loop Overview

The DeepEmptyLoop benchmark executes ten nested loops, with the innermost loop body executing 1024 times. The loops are "empty" only in the sense that their sole function is to increment their own loop counter and possibly to execute an embedded loop. This benchmark is a variation on the EmptyLoop benchmark (§5.3.1&#138;) that tests statement based interpreters' flow control more heavily.

It is constructed by creating a Picojava class containing an empty constructor and a method named main whose body implements the nested loops in whatever paradigm is of concern.

It tests the following interpreter components:

• Constructor Method execution (once)
• Method execution (once)
• Block execution (twice for instructions; 2049 times for statements)
• Flow control (3069 times for instructions; 1023 times for statements)
• Data transfer (7168 times)
• Constant generation (5120 times)
• Binary operation (5120 times)

DeepEmptyLoop will show if deeply nested program structures are better executed under a tree-based or instruction-based instruction paradigm. By comparing with EmptyLoop, we can see if nested loops negate or enhance any benefit seen in the efficiency of EmptyLoop when comparing one paradigm to another.

5.3.3 Field Access Overview

The FieldAccess benchmark executes an object field access 1000 times. This tests the field access methods within Structured_Object, and provides us with a loop body which is starting to do a little more than merely incrementing a loop counter.

It is constructed by creating two Picojava classes. The main class contains an empty constructor and a method named main whose body implements the field access loop in whatever paradigm is of concern. The other class is instantiated by the main method of the main class, and merely contains a single public Algebraic_SignedInteger5 field.

It tests the following interpreter components:

• Constructor Method execution (twice)
• Method execution (once)
• Class instance creation (once)
• Block execution (three times for instructions; 1003 times for statements)
• Flow control (1001 times for instructions; once for statements)
• Data transfer (5000 times, including 1000 field accesses)
• Constant generation (2000 times)
• Binary operation (2000 times)

FieldAccess or a variation of it is a commonly used benchmark for comparing the speed of Java intepreters. It is expected its results will be like that of a diluted EmptyLoop test (§5.3.1), with less emphasis being placed on loop mechanics. However, these results will begin to more closely approximate benefits which might be expected from real-world programs running under each different interpreter paradigm. This is because repeated field access is a process which might conceivably form part of a useful application.

5.3.4 Method Call Overview

Continuing in the same vein as FieldAccess (§5.3.3), the MethodCall benchmark calls a method 1000 times. This tests the method invocation operations and method implementations of the various interpreter paradigms.

It is constructed by creating two Picojava classes. The main class contains an empty constructor and a method named main whose body implements the method call loop in whatever paradigm is of concern. The other class is instantiated by the main method of the main class, and merely contains a single method which increments the loop counter passed in as a parameter.

It tests the following interpreter components:

• Constructor Method execution (twice)
• Method execution (1001 times)
• Class instance creation (once)
• Block execution (three times for instructions; 2003 times for statements)
• Flow control (1001 times for instructions; once for statements)
• Method call (1000 times)
• Data transfer (4000 times)
• Constant generation (2000 times)
• Binary operation (2000 times)

MethodCall or a variation of it is a commonly used benchmark for comparing the speed of Java intepreters. It is expected its results will be similar to that of EmptyLoop, as the only difference is that the loop counter increment operation is moved into a method.

5.3.5 Often True Overview

The OftenTrue benchmark runs a conditional clause 1000 times, which executes every second time. The conditional clause performs field access (c.f. §5.3.3) This tests the implementations of conditional clauses and deeply nested algebraic operations under the various interpreter paradigms.

It is constructed by creating a Picojava class containing an empty constructor and a method named main whose body implements the loop containing the conditional clause in whatever paradigm is of concern. A second Picojava class implementing a single instance variable is used in the field access.

It tests the following interpreter components:

• Constructor Method execution (twice)
• Class instance creation (once)
• Block execution (three times for instructions; 1503 times for statements)
• Flow control (1501 times for instructions; 1001 times for statements)
• Data transfer (6000 times, including 500 field accesses)
• Constant generation (5000 times)
• Binary operation (6000 times, maximum 4 levels of operands)

OftenTrue is designed to fill the gap in terms of emphasizing areas which aren't tested by other benchmarks. Like FieldAccess, it is potentially more representative of real-world programs than other benchmarks, because a partition operation involves a loop which performs a conditional test for a set of entities.

5.3.6 Fibonacci Overview

The Fibonacci benchmark generates the first 47 Fibonacci numbers. This tests object creation and provides the closest benchmark to a real-world application.

It is constructed by creating two Picojava classes. The main class contains an empty constructor and a method named main whose body implements the loop which generates instances of Fibonacci numbers using whatever paradigm is of concern. The other class, FibonacciNumber, is instantiated once for each Fibonacci number generated.

It tests the following interpreter components:

• Constructor Method execution (48 times)
• Method execution (91 times)
• Class instance creation (47 times)
• Block execution (140 times for instructions; 185 times for statements)
• Flow control (46 times for instructions; once for statements)
• Method call (91 times)
• Data transfer (391 times, including 259 field accesses)
• Constant generation (91 times)
• Binary operation (135 times)

Fibonacci is commonly used as a benchmark for Java interpreters. It is the closest benchmark of those selected to test this thesis to program fragments that might be used in a real-world application. The result of this test will represent the "average case" of what performance improvement should be expected under each of the tested paradigms.

5.4 Code Implementation Of Benchmarks

This section discusses how the instruction-based versions of each of the benchmarks discussed in §5.3 were built. In each case, care has been taken to write the most efficient code possible while still obeying the parameters of the functional specifications.

5.4.1 Empty Loop Code Implementation

The EmptyLoop benchmark is simply a "spinner" loop, and as such is quite elementary to code. The only point to note is that the first instruction is a branch, because it is actually less expensive to have the loop condition tested at the bottom of the loop rather than immediately at the top. The alternative would be:

• Test the loop condition.
• If false, branch to the end of the loop.
• Execute the loop body.
• Branch to the top of the loop to test the condition again.

All of these steps need to be carried out each time around the loop. In the encoding used, the equivalent of step four (branch to the bottom of the loop to test the condition the first time) is only needed once, not every time around the loop.

The code for EmptyLoop_pJC is then:

class EmptyLoop

{
  EmptyLoop()
  {
  }
  

  void main()

  {

    int count;

    0 goto 5

    1 iload (count)

    2 iconst (1)

    3 iadd

    4 istore (count)

    5 iconst (1000)

    6 iload (count)

    7 icmplt

    8 iftrue 1

  }
}

5.4.2 Deep Empty Loop Code Implementation

DeepEmptyLoop consists of several "spinner" loops nested within one another. As such, it is automatically generated by the computer using a similar approach to that taken in EmptyLoop_pJC (§5.4.1).

The code follows the following pattern:

class DeepEmptyLoop

{
  DeepEmptyLoop()
  {
  }
  

  void main()

  {

    int count0;

    int count1;

    ...

    int count9;

    0 goto 104

    1 iload (count9)

    2 iconst (1)

    3 iadd

    4 istore (count9)

    5 iconst (0)

    6 istore (count8)

    7 goto 100

    8 iload (count8)

    9 iconst (1)

    10 iadd

    11 istore (count8)

    12 iconst (0)

    13 istore (count7)

    14 goto 96

    ...

    56 goto 72

    57 iload (count1)

    58 iconst (1)

    59 iadd

    60 istore (count1)

    61 iconst (0)

    62 istore (count0)

    63 goto 68

    64 iload (count0)

    65 iconst (1)

    66 iadd

    67 istore (count0)

    68 iconst (2)

    69 iload (count0)

    70 icmplt

    71 iftrue 64

    72 iconst (2)

    73 iload (count1)

    74 icmplt

    75 iftrue 57

    ...

    96 iconst (2)

    97 iload (count7)

    98 icmplt

    99 iftrue 15

    100 iconst (2)

    101 iload (count8)

    102 icmplt

    103 iftrue 8

    104 iconst (2)

    105 iload (count9)

    106 icmplt

    107 iftrue 1

  }  
}

5.4.3 Field Access Code Implementation

The FieldAccess benchmark code implementation is basically EmptyLoop_pJC (§5.4.1) with an augmented loop body and an additional class declaration and class instance creation clause.

FieldAccess_pJC looks like:

class FieldAccess

{
  FieldAccess()
  {
  }
  

  void main()

  {
    Field field;

    int count;

    int temp;

    0 new_0 (Field)

    1 astore (field)

    2 goto 9

    3 aload (field.value)

    4 astore (temp)

    5 iload (count)

    6 iconst (1)

    7 iadd

    8 istore (count)

    9 iconst (1000)

    10 iload (count)

    11 icmplt

    12 iftrue 3

  }
}

class Field

{

  int value;

  
  Field()
  {
  }
}

5.4.4 Method Call Code Implementation

Note that method call in the Picojava instruction interpreter requires only the parameters to the method be placed on the operand stack, and not the object containing the method.

The code for MethodCall_pJC is:

class MethodCall

{
  MethodCall()
  {
  }
  

  void main()

  {
    MethodTest method;

    int count;

    0 new_0 (MethodTest)

    1 astore (method)

    2 goto 6

    3 iload (count)

    4 invokevirtual_1 (method.addOne)

    5 istore (count)

    6 iconst (1000)

    7 iload (count)

    8 icmplt

    9 iftrue 3

  }
}

class MethodTest

{
  MethodTest()
  {
  }
  

  int addOne(int number)

  {

    0 iload (number)

    1 iconst (1)

    2 iadd

    3 ireturn

  }
}

5.4.5 Often True Code Implementation

A conditional clause is encoded in instructions by testing a condition and branching over the code which is part of the clause if that condition is false. Therefore, the code for OftenTrue_pJC is like an version of FieldAccess_pJC (§5.4.3) with part of the loop body bracketed by the instructions forming a conditional clause:

class OftenTrue

{
  OftenTrue()
  {
  }
  

  void main()

  {
    Field field;

    int count;

    int temp;

    0 new_0 (Field)

    1 astore (field)

    2 goto 19

    3 iconst (0)

    4 iconst (2)

    5 iconst (2)

    6 iload (count)

    7 idiv

    8 imul

    9 iload (count)

    10 isub

    11 icmpeq

    12 iffalse 15

    13 aload (field.value)

    14 astore (temp)

    15 iload (count)

    16 iconst (1)

    17 iadd

    18 istore (count)

    19 iconst (1000)

    20 iload (count)

    21 icmplt

    22 iftrue 3

  }
}

class Field

{

  int value;

  
  Field()
  {
  }
}

5.4.6 Fibonacci Code Implementation

The Fibonacci benchmark combines elements from all the foregoing benchmarks. It also uses a variety of constructor calls. Note that class instance creation instructions in Picojava do the job of several Java VM instructions.

The Fibonacci_pJC benchmark is coded as follows:

class Fibonacci

{
  Fibonacci()
  {
  }
  

  void main()

  {
    FibonacciNumber number;

    int count;

    0 new_0 (FibonacciNumber)

    1 astore (number)

    2 aload (number)

    3 new_1 (FibonacciNumber)

    4 astore (number)

    5 goto 14

    6 aload (number.oneAgo)

    7 aload (number)

    8 new_2 (FibonacciNumber)

    9 astore (number)

    10 iload (count)

    11 iconst (1)

    12 iadd

    13 istore (count)

    14 iconst (45)

    15 iload (count)

    16 icmplt

    17 iftrue 6

  }
}

class FibonacciNumber

{

  int value;

  FibonacciNumber twoAgo;
  FibonacciNumber oneAgo;
  
  FibonacciNumber()
  {

    0 iconst (1)

    1 istore (this.value)

  }
  
  FibonacciNumber(FibonacciNumber oneAgo)
  {

    0 iload (oneAgo)

    1 istore (this.oneAgo)

    2 invokevirtual_0 (oneAgo.getValue)

    3 istore (this.value)

    
  }
  
  FibonacciNumber(FibonacciNumber oneAgo, 
                  FibonacciNumber twoAgo)
  {

    0 iload (oneAgo)

    1 istore (this.oneAgo)

    2 iload (twoAgo)

    3 istore (this.twoAgo)

    4 invokevirtual_0 (oneAgo.getValue)

    5 invokevirtual_0 (twoAgo.getValue)

    6 iadd

    7 istore (this.value)

  }
  

  int getValue()

  {

    0 iload (this.value)

    1 ireturn

  }
}

5.5 Tree Implementation Of Benchmarks

This section discusses how the statement-based versions of each of the benchmarks discussed in §5.3 were built. In each case, care has been taken to write the most efficient code possible while still obeying the parameters of the functional specifications.

In all cases, the benchmark code arises directly from the specification, so no commentary will be given. It is left as an exercise for the reader to convince herself that the programs given here are functionally equivalent to those in §5.4 according to the language semantics given in Chapter 2.

5.5.1 Empty Loop Tree Implementation

The code for EmptyLoop_pJT and EmptyLoop_pJS is:

class EmptyLoop

{
  EmptyLoop()
  {
  }
  

  void main()

  {

    int count;

    while (((count)<(1000))) {

      (count=((count)+(1)));
    }
  }
}

5.5.2 Deep Empty Loop Tree Implementation

The code for DeepEmptyLoop_pJT and DeepEmptyLoop_pJS is:

class DeepEmptyLoop

{
  DeepEmptyLoop()
  {
  }
  

  void main()

  {

    int count0;

    int count1;

    ...

    int count9;

    while (((count0)<(2))) {

      (count0=((count0)+(1)));
      (count1=(0));

      while (((count1)<(2))) {

        (count1=((count1)+(1)));
        (count2=(0));

        while (((count2)<(2))) {

          (count2=((count2)+(1)));
          (count3=(0));

          ...

                  while (((count7)<(2))) {

                    (count7=((count7)+(1)));
                    (count8=(0));

                    while (((count8)<(2))) {

                      (count8=((count8)+(1)));
                      (count9=(0));

                      while (((count9)<(2))) {

                        (count9=((count9)+(1)));
                      }
                    }
                  }

          ...

        }
      }
    }
  }
}

5.5.3 Field Access Tree Implementation

The code for FieldAccess_pJT and FieldAccess_pJS is:

class FieldAccess

{
  FieldAccess()
  {
  }
  

  void main()

  {
    Field field;

    int count;

    int temp;

    (field=(new Field()));

    while (((count)<(1000))) {

      (temp=(field.value));
      (count=((count)+(1)));
    }
  }
}

class Field

{

  int value;

  
  Field()
  {
  }
}

5.5.4 Method Call Tree Implementation

The code for MethodCall_pJT and MethodCall_pJS is:

class MethodCall

{
  MethodCall()
  {
  }
  

  void main()

  {
    MethodTest method;

    int count;

    (method=(new MethodTest()));

    while (((count)<(1000))) {

      (count=(method.addOne((count))));
    }
    
  }
  
}

class MethodTest

{
  MethodTest()
  {
  }
  

  int addOne(int number)

  {

    (Result'=((number)+(1)));

  }
}

5.5.5 Often True Tree Implementation

The code for OftenTrue_pJT and OftenTrue_pJS is:

class OftenTrue

{
  OftenTrue()
  {
  }
  

  void main()

  {
    Field field;

    int count;

    int temp;

    (field=(new Field()));

    while (((count)<(1000))) {

      if ((((count)-(((count)/(2))*(2)))==(0))) {

        (temp=(field.value));
      }
      (count=((count)+(1)));
    }
  }
}

class Field

{
  int value;
  
  Field()
  {
  }
}

5.5.6 Fibonacci Tree Implementation

The code for Fibonacci_pJT and Fibonacci_pJS is:

class Fibonacci

{
  Fibonacci()
  {
  }
  

  void main()

  {
    FibonacciNumber number;

    int count;

    (number=(new FibonacciNumber()));

    (number=(new FibonacciNumber((number))));

    while (((count)<(45))) {

      (number=(new FibonacciNumber((number),

                                   (number.oneAgo))));
      (count=((count)+(1)));
    }
  }
}

class FibonacciNumber

{

  int value;

  FibonacciNumber twoAgo;
  FibonacciNumber oneAgo;
  
  FibonacciNumber()
  {

    (this.value=(1));

  }
  
  FibonacciNumber(FibonacciNumber oneAgo)
  {

    (this.oneAgo=(oneAgo));

    (this.value=(oneAgo.getValue()));

  }
  
  FibonacciNumber(FibonacciNumber oneAgo, 
                  FibonacciNumber twoAgo)
  {

    (this.oneAgo=(oneAgo));

    (this.twoAgo=(twoAgo));

    (this.value=((oneAgo.getValue())+        

                 (twoAgo.getValue())));
  }
  

  int getValue()

  {

    (Result'=(this.value));

  }
}

^[9]  For example. StackingSymbolTable is a subinterface of SymbolTable, analogous to TreeSymbolTable from the optimized tree interpreter; HashingStackingSymbolTable is a subclass of HashingSymbolTable which implements StackingSymbolTable and is analogous to HashingTreeSymbolTable. The other classes which are changed are subclassed and subinterfaced in similar ways. See also footnote 8.

  Previous Chapter     Next Chapter     Top of Chapter

Java- Trees Versus Bytes is a BComp Honours thesis written by Kade Hansson.

Copyright 1998 Kade "Archer" Hansson; e-mail: archer@dialix.com.au

Last updated: Monday 12th February 2001