HomeDigital EditionSys-Con RadioSearch Java Cd
Advanced Java AWT Book Reviews/Excerpts Client Server Corba Editorials Embedded Java Enterprise Java IDE's Industry Watch Integration Interviews Java Applet Java & Databases Java & Web Services Java Fundamentals Java Native Interface Java Servlets Java Beans J2ME Libraries .NET Object Orientation Observations/IMHO Product Reviews Scalability & Performance Security Server Side Source Code Straight Talking Swing Threads Using Java with others Wireless XML

Java is often criticized for its performance, particularly in comparison to equivalent code written in languages such as C and C++. Advances in runtime performance have silenced many critics, but still there are times when no matter how fast Java is, it's just not fast enough.

Fortunately, Java does have some unique properties that make a class of optimizations accessible that are not easily applied to other platforms. One technique that can be used to great effect on certain types of tasks is dynamic code generation.

Dynamic code generation is the process of generating Java classes at runtime that can then be loaded into that same Java Virtual Machine (JVM) and accessed the same way as ordinary compiled Java classes. The usefulness of the technique might not be immediately apparent, but it's actually used to a great degree of success in several critical, high-profile Java technologies.

JavaServer Pages
Perhaps the best-known example of dynamic code generation in Java is JavaServer Pages (JSP). A servlet engine is capable of dispatching requests to a servlet for processing. Unfortunately, servlets are static in nature. They typically need to be precompiled and preconfigured in the servlet engine before server startup. Although they're quite useful, Web development often requires a more flexible solution.

JSP breaks these restrictions and allows servlets to be dynamically created at runtime based on the contents of a JSP file. When a request is made for a JSP file, the servlet engine makes a request to the JSP engine, which in turn will process the JSP file and send a result. A JSP is a textual representation of a set of actions to be performed to present a page to the user, and interpreting it anew for each request would be quite costly. Instead, the JSP engine will compile the JSP and dynamically create a servlet object. If the specification changes, a new servlet will be dynamically generated.

Dynamic code generation is a big win here because it brings dynamic behavior without a large performance penalty. The behavior of the runtime system doesn't need to be specified completely at compile time or even at the time the system starts. Yet, at the same time, we avoid the slothful response times that might be associated with interpreting the JSP file for each request.

XSLTC
A lesser known but more recent example of dynamic code generation is XSLTC. A subproject of the Apache XALAN project, XSLTC is a compiler for XSL stylesheets that can compile a stylesheet into a Java class to perform that specified transformation. XSLTC can function as a traditional compiler or can compile a stylesheet in memory to immediately process an XML input file with the full performance benefit of compiled code.

The power of this technique should not be overlooked. The flexibility of an XML-based specification (which is not necessarily available until runtime) is combined with the performance of executing Java code directly.

Methods for Code Generation
Now that we've seen two systems that make use of dynamic code generation, let's explore the code generation techniques of both systems by applying them to a simple problem domain. We'll develop a simple, four-function, stack-based integer expression evaluator with variable substitution.

Our expression evaluator will evaluate mathematical expressions such as "4 $0 + $1 *". Stack-based processing of this expression is trivial. We push 4 and variable 0 on the stack and then add the top two values on the stack, replacing both of the operands with the result of the addition. Next we push variable 1 on the stack and perform a multiple operation. In more familiar algebraic notation, this would be represented as "(4 + $0) * $1". If we were to evaluate this expression with the variable list of "[3, 6]", the result would be (4 + 3) * 6 = 42.

All of our expression evaluators will conform to the calculator interface. The calculator interface contains a single method, evaluate, that takes an array of integer arguments as input and returns the integer result of performing whatever calculation is required.

// Calculator.java
public interface Calculator
{
int evaluate(int[] arguments);
}

A Simple Expression Evaluator
For demonstration purposes, we'll consider a simple but inefficient expression interpreter that uses a Stack object to evaluate the expression (see Listing 1). The expression is parsed once for each evaluation. However, we will tokenize the expression only once, at object creation time, to avoid the overhead of the StringTokenizer class.

As you can see from the performance numbers, this method is quite slow. It may be adequate for evaluating an occasional expression, but we can do much better.

Parsing the Expression
If the expression is likely to be reused, a better technique would be to parse the expression and apply the Composite design pattern to create an expression tree (see Listing 2). The internal structure of the tree represents the logic of the expression to be evaluated.

The performance of the parsed calculator is an order of magnitude better than the simple interpreted version above. While there's still plenty of room for optimization, we're not far from the limits of what can be achieved without getting closer to the JVM.

Compiling the Expression
To make that step closer to the JVM, we'll attempt direct compilation of our expression. We'll generate a Java source file from our expression (in the same way a JSP engine would generate a Java source file) and then compile and load it.

Translating our mathematical expression into a Java expression isn't difficult. "$0 $1 $2 * +" can be represented by the Java expression "args[0] + (args[1] * args[2])". We need to choose a unique name for our class and write the generated code in a temporary file. The generated code for this expression would resemble the following:

public class [CLASSNAME]
implements Calculator
{
public int evaluate(int[] args) {
return args[0] + (args[1] * args[2]);
}
}
Next, we need to compile the Java code. Unfortunately, we can't count on any particular compiler to be installed on our machine. For this example we'll assume the javac compiler is available and is in our system PATH. If javac is not in our PATH or another compiler is desired, that can be specified with the "calc.compiler" property. For example, "-Dcalc.compiler=jikes".

If a compiler other than javac is used, we will almost always need to place the Java runtime JAR (rt.jar in the jre/lib directory) in the classpath passed to the compiler. We'll use the "calc.classpath" property to indicate additional classpath elements to be passed to the compiler. For example, "-Dcalc.classpath=/usr/local/java/jre/lib/rt.jar".

The compiler can be invoked as an external process using Runtime.exec(String[] cmd), which produces a Process object. The elements of the cmd array contain the system command to be executed. The first element should be the name of the program to execute. The remaining elements are the individual arguments to be passed to the compiler.

String[] cmd = {
_compiler,
"-classpath",
_classpath,
javafile.getName()
};

Process process = Runtime.get
Runtime().exec(cmd);

We need to wait for the compile process to end and then grab the return code from the compiler. A process return code of zero indicates a successful compile.

process.waitFor();
int val = process.exitValue();
if (val != 0) {
throw new RuntimeException(
"compile error. " +
"compiler return code is " +
val);
}
One final issue with compilation is that it's important to read the output and error streams of the external process. If the compiler generates enough output, the compile process could potentially block waiting for the output to be read. We'll ignore the issue here, but this should definitely be addressed in a production system.

If the compile was successful, we now have a Java class file in the current directory that can be read in. Our ClassLoader needs a byte array to load, so we read the contents into the byte array and ask the system to create a class for us.

byte[] buf = readBytes(classname +
".class");
Class c = defineClass(buf, 0,
buf.length);
Our ClassLoader is the minimal ClassLoader necessary to accomplish our task. It doesn't perform all the tasks that a production-level ClassLoader would. However, it serves for demonstration purposes.

Once the class is successfully loaded, we can create an instance of the class and return it for use.

return (Calculator)
c.newInstance();
The complete code is shown in Listing 3. The runtime performance of the compiled calculator represents another order of magnitude speed improvement over our first attempt. Our same 1,000,000 evaluations run in 100-200ms instead of 1-2 seconds as in the prior example. But there's still a big performance hit in compiling the code. Invoking javac to compile the code can take 1-2 seconds, negating our performance gain. However, javac is not a very high-performance compiler. When we switch to a fast compiler such as jikes, compile time drops significantly, to 100-200ms.

Generating Bytecode Directly
The ultimate solution would retain the runtime performance of compilation without incurring the cost of invoking an external compiler. An in-memory compiler would be one option, but we can also eliminate the overhead and messiness of compilation by generating the Java bytecode in memory.

While writing Java to a file is relatively simple, the Java class file format is tricky enough that we'll want to use an external bytecode library to generate the file. For this article we use BCEL, the Bytecode Engineering Library.

Using BCEL, we first need to create a ClassGen object to represent our class. As with the compiled example, we have to define a unique classname. Unlike Java code, we need to directly declare our super class of Java.lang.Object. ACC_PUBLIC specifies that our class is public. We also need to set the ACC_SUPER access flag that all Java 1.0.2 or higher Java classes should set. Finally, we specify that our class is to implement the Calculator interface.

ClassGen classgen =
new ClassGen(classname,
"java.lang.Object",
"",
Constants.ACC_PUBLIC |
Constants.ACC_SUPER,
new String[]
{"Calculator"});
Next, we need to ensure that our class has a default constructor. A Java compiler will normally insert a default constructor for us if no other constructors are defined. When generating bytecode directly, we need to explicitly perform these actions. Fortunately, BCEL has a convenient method for generating a default constructor.

classgen.addEmptyConstructor
(Constants.ACC_PUBLIC);
Finally, we want to generate our int evaluate(int[] arguments) method. It's a very simple task to translate directly to bytecode since the JVM is stack-based. Our stack-based calculator translates almost directly onto bytecodes. Instructions are gathered in order of execution in the InstructionList. We also need a reference to our class constant pool (Constant-PoolGen) in case pushing certain values requires us to create a constant pool reference.

Once the InstructionList is completed, we can proceed to create the MethodGen object. We want a public method whose return type is int and takes one argument, a list of ints. (Note that we used the internal representation for an array of ints, "[I".) Although it's not required, we'll also provide names for our parameters. In this case, our single parameter name is "args". Our method name is "evaluate". The final arguments are the classname, our instruction list, and the constant pool.

MethodGen method =
new MethodGen(Constants.ACC_
PUBLIC,
Type.INT,
new Type[]
{Type.getType("[I")},
new String[] {"args"},
"evaluate",
classgen.getClassName(),
il,
cp);
Java methods have strict requirements. For example, a method must declare how much space it requires on the operand stack and how much space it requires in the frame allocated for local variables. If these values are incorrect, the JVM will refuse to execute the method. In this example, it would be easy enough to compute these values. However, BCEL provides convenience functions that examine the bytecode and determine stack usage for us.

method.setMaxStack();
method.setMaxLocals();
Now we can add our new method to the class.

classgen.addMethod(method.getMethod());
The class is complete, so we can generate the associated bytecode and load the class into the JVM. Once we have the class structure in a byte array in memory, the ClassLoader can be invoked as we did for the compiled version. The complete code is available in Listing 4.

The code we generate directly performs as fast as the compiled code, but initial object creation time is significantly faster. Invoking the external compiler took (in the best case) over 100ms. Creating the class using BCEL took only 4ms on average.

Performance
Average object creation times for each type of object are shown in Table 1. I measured the total execution time for the following five expressions (see Table 2): each evaluated 1,000,000 times with slightly differing argument lists. The evaluation times for each type and expression are shown in Table 3.

Table 1

Table 2

Table 3

Relevance of These Results
This is an admittedly contrived example. It would be quite rare for us to need to evaluate a mathematical expression a million times. However, it's not rare to have to interpret data (XML, scripting languages, query languages, reflection, etc.) at runtime, and also to want a system that performs well. Dynamic code generation is not applicable to every task, but it does appear most useful when:

  • The computation is primarily driven by a definition available at runtime
  • The computation is to be performed many times
  • It would be costly to interpret the definition directly for each execution
Compilation vs Generation
If dynamic code generation can be applied to a task, there's still the issue of whether compilation or bytecode generation is better for the task. Generating Java source code for compilation is, in general, an easier task. You're probably more familiar with Java code than with JVM instructions; debugging code for which you have source is easier than debugging pure bytecode. Furthermore, a good compiler may be able to apply compile-time optimizations that would be difficult to code by hand. However, external compilation is a very slow process and configuring the compiler and classpath makes the resulting application more difficult to manage.

Bytecode generation has the distinct advantage of being very fast. But it requires the developer to have a detailed understanding of the class file format and JVM instructions. Compilers really do a lot of behind-the-scenes grunt work in generating code. If the code generated is very complicated, you might want to think twice before trying to generate bytecodes directly.

Resources

  • Lindholm, T., and Yellin, F. (1999). The Java Virtual Machine Specification, Second Edition. Addison-Wesley.
  • BCEL: http://bcel.sourceforge.net/
  • XSLTC: http://xml.apache.org/xalan-j/xsltc/

    Author Bio
    Norman Richards works at Commerce One Labs, the research division of Commerce One. [email protected]

    	
    
    
    Listing 1:
    
     SimpleCalculator.javaimport java.util.ArrayList;
     
    import java.util.Stack;
    import java.util.StringTokenizer;
    
    
    public class SimpleCalculator
      implements Calculator
    {
      String[] _toks;
    
    
      public SimpleCalculator(String expression) {
        ArrayList list =  new ArrayList();
        StringTokenizer tokenizer =
            new StringTokenizer(expression);
    
    
        while (tokenizer.hasMoreTokens()) {
          list.add(tokenizer.nextToken());
        }
    
    
        _toks = (String[]) list.toArray(
            new String[list.size()]);
      }
    
    
      public int evaluate(int[] args)
      {
        Stack stack = new Stack();
    
    
        for (int i=0; i < _toks.length; i++) {
          String tok = _toks[i];
    
    
          if (tok.startsWith("$")) {
            int varnum = Integer.
              parseInt(tok.substring(1));
            stack.push(new Integer(args[varnum]));
          } else {
            char opchar = tok.charAt(0);
            int  op = "+-*/".indexOf(opchar);
    
    
            if (op == -1) {
              stack.push(Integer.valueOf(tok));
            } else {
              int arg2 = ((Integer) stack.pop())
                  .intValue();
              int arg1 = ((Integer) stack.pop())
                  .intValue();
    
    
              switch(op) {
                case 0:
                  stack.push(new Integer(arg1 + arg2));
                  break;
    
    
                case 1:
                  stack.push(new Integer(arg1 - arg2));
                  break;
    
    
                case 2:
                  stack.push(new Integer(arg1 * arg2));
                  break;
    
    
                case 3:
                  stack.push(new Integer(arg1 / arg2));
                  break;
    
    
                default:
                  throw new RuntimeException(
                    "invalid operator: " + tok);
              }
            }
          }
        }
    
    
        return ((Integer) stack.pop()).intValue();
      }
    }
    
    
    
    
    Listing 2: CalculatorParser.java
    
    import java.util.Stack;
    import java.util.StringTokenizer;
    
    
    public class CalculatorParser
    {
      public Calculator parse(String expression)
      {
        Stack stack = new Stack();
        StringTokenizer toks =
          new StringTokenizer(expression);
    
    
        while (toks.hasMoreTokens()) {
          String tok = toks.nextToken();
    
    
          if (tok.startsWith("$")) {
            int varnum = Integer.
                parseInt(tok.substring(1));
            stack.push(new VariableValue(varnum));
    
    
          } else {
            int op = "+-*/".indexOf(tok.charAt(0));
    
    
            if (op == -1) {
              int val = Integer.parseInt(tok);
              stack.push(new ConstantValue(val));
            } else {
              Calculator node2 =
                (Calculator) stack.pop();
              Calculator node1 =
                (Calculator) stack.pop();
    
    
              stack.push(new Operation(tok.charAt(0),
                node1, node2));
            }
          }
        }
    
    
        return (Calculator) stack.pop();
      }
    
    
      static class ConstantValue
        implements Calculator
      {
        private int _value;
    
    
        ConstantValue(int value) {
          _value = value;
        }
    
    
        public int evaluate(int[] args) {
          return _value;
        }
      }
    
    
    
      static class VariableValue
        implements Calculator
      {
        private int _varnum;
    
    
        VariableValue(int varnum) {
          _varnum = varnum;
        }
    
    
        public int evaluate(int[] args) {
          return args[_varnum];
        }
      }
    
    
      static class Operation
        implements Calculator
      {
        char     _op;
        Calculator _arg1;
        Calculator _arg2;
    
    
        Operation(char op, Calculator arg1,
                  Calculator arg2)
        {
          _op   = op;
          _arg1 = arg1;
          _arg2 = arg2;
        }
    
    
        public int evaluate(int args[]) {
          int val1 = _arg1.evaluate(args);
          int val2 = _arg2.evaluate(args);
    
    
          if (_op == '+') {
            return val1 + val2;
          } else if (_op == '-') {
            return val1 - val2;
          } else if (_op == '*') {
            return val1 * val2;
          } else if (_op == '/') {
            return val1 / val2;
          } else {
            throw new RuntimeException(
              "invalid operator: " + _op);
          }
        }
      }
    
    
    }
    
    
    
    
    Listing 3:
    
     CalculatorCompiler.javaimport java.util.Stack;
     
    import java.util.StringTokenizer;
    
    
    import java.io.*;
    
    
    public class CalculatorCompiler
      extends ClassLoader
    {
      String _compiler;
      String _classpath;
    
    
      public CalculatorCompiler() {
        super(ClassLoader.getSystemClassLoader());
    
    
        _compiler = System.getProperty(
          "calc.compiler");
        if (_compiler == null) {
          _compiler = "javac";
        }
    
    
        _classpath = ".";
        String extraclasspath =
          System.getProperty("calc.classpath");
    
    
        if (extraclasspath != null) {
          _classpath = _classpath +
            System.getProperty("path.separator") +
            extraclasspath;
        }
      }
    
    
      public Calculator compile(String expression)
      {
        String jtext   = javaExpression(expression);
    
    
        String filename  = "";
        String classname = "";
    
    
        try {
          File javafile = File.createTempFile(
            "compiled_", ".java", new File("."));
    
    
          filename  = javafile.getName();
          classname = filename.substring(0,
            filename.lastIndexOf("."));
    
    
          generateJavaFile(javafile, classname,
            expression);
          invokeCompiler(javafile);
    
    
          byte[] buf = readBytes(classname + ".class");
          Class  c   = defineClass(buf, 0, buf.length);
          try {
            return (Calculator) c.newInstance();
          } catch (IllegalAccessException e) {
            throw new RuntimeException(e.getMessage());
          } catch (InstantiationException e) {
            throw new RuntimeException(e.getMessage());
          }
    
    
        } catch(IOException e) {
          throw new RuntimeException(e.getMessage());
        }
      }
    
    
      void generateJavaFile(File javafile,
        String classname, String expression)
        throws IOException
      {
        FileOutputStream out =
          new FileOutputStream(javafile);
    
    
        String text = "public class " + classname +
          " implements Calculator {" +
          "  public int evaluate(int[] args) {" +
          "    " + javaExpression(expression) +
          "  }" +
          "}";
    
    
        out.write(text.getBytes());
        out.close();
      }
    
    
    
      void invokeCompiler(File javafile)
        throws IOException
      {
        String[] cmd   = {_compiler, "-classpath",
          _classpath,  javafile.getName()};
        Process  process = Runtime.getRuntime()
          .exec(cmd);
    
    
        try {
          process.waitFor();
        } catch (InterruptedException e) {
        }
    
    
        int val = process.exitValue();
        if (val != 0) {
          throw new RuntimeException(
            "compile error: " +
            "compiler return code is " + val);
        }
      }
    
    
    
      byte[] readBytes(String filename)
        throws IOException
      {
        File classfile = new File(filename);
        byte[] buf =
          new byte[(int) classfile.length()];
    
    
        FileInputStream in =
          new FileInputStream(classfile);
        in.read(buf);
        in.close();
    
    
        return buf;
      }
    
    
    
      String javaExpression(String expression)
      {
        Stack stack = new Stack();
        StringTokenizer toks =
          new StringTokenizer(expression);
    
    
        while (toks.hasMoreTokens()) {
          String tok = toks.nextToken();
    
    
          if (tok.startsWith("$")) {
            stack.push("args[" +
              Integer.parseInt(tok.substring(1)) +
              "]");
    
    
          } else {
            int op = "+-*/".indexOf(tok.charAt(0));
    
    
            if (op == -1) {
              stack.push(tok);
            } else {
              String arg2 = (String) stack.pop();
              String arg1 = (String) stack.pop();
    
    
              stack.push("(" + arg1 + " " +
                tok.charAt(0) + " " + arg2 + ")");
            }
          }
        }
    
    
        return "return " + (String) stack.pop() + ";";
      }
    }
    
    
    
    Listing 4: CalculatorGenerator.java
    
    import java.io.*;
    
    
    import java.util.Stack;
    import java.util.StringTokenizer;
    
    
    import de.fub.bytecode.classfile.*;
    import de.fub.bytecode.generic.*;
    import de.fub.bytecode.Constants;
    
    
    public class CalculatorGenerator
      extends ClassLoader
    {
      public Calculator generate(String expression)
      {
        String   classname = "Calc_" +
          System.currentTimeMillis();
        ClassGen classgen  = new ClassGen(classname,
          "java.lang.Object", "",
          Constants.ACC_PUBLIC | Constants.ACC_SUPER,
          new String[] {"Calculator"});
    
    
        classgen.addEmptyConstructor(
            Constants.ACC_PUBLIC);
        addEvalMethod(classgen, expression);
    
    
        byte[] data = classgen.getJavaClass()
            .getBytes();
        Class  c  = defineClass(data, 0, data.length);
    
    
        try {
          return (Calculator) c.newInstance();
        } catch (IllegalAccessException e) {
          throw new RuntimeException(e.getMessage());
        } catch (InstantiationException e) {
          throw new RuntimeException(e.getMessage());
        }
      }
    
    
      private void addEvalMethod(ClassGen classgen,
        String expression)
      {
        ConstantPoolGen cp =
          classgen.getConstantPool();
        InstructionList il = new InstructionList();
        StringTokenizer toks =
          new StringTokenizer(expression);
        int stacksize = 0;
        int maxstack  = 0;
    
    
        while (toks.hasMoreTokens()) {
          String tok = toks.nextToken();
    
    
          if (tok.startsWith("$")) {
            int varnum = Integer.
              parseInt(tok.substring(1));
    
    
            // load array reference
            il.append(InstructionConstants.ALOAD_1);
            // load array index
            il.append(new PUSH(cp, varnum));
            // pull value from array
            il.append(InstructionConstants.IALOAD);
    
    
          } else {
            int op = "+-*/".indexOf(tok.charAt(0));
    
    
            switch(op) {
              case -1:
                int val = Integer.parseInt(tok);
                il.append(new PUSH(cp, val));
                break;
              case 0:
                il.append(InstructionConstants.IADD);
                break;
              case 1:
                il.append(InstructionConstants.ISUB);
                break;
              case 2:
                il.append(InstructionConstants.IMUL);
                break;
              case 3:
                il.append(InstructionConstants.IDIV);
                break;
              default:
                throw new RuntimeException(
                  "invalid operator");
            }
          }
        }
    
    
        il.append(InstructionConstants.IRETURN);
    
    
    
        MethodGen method = new MethodGen(
          Constants.ACC_PUBLIC, Type.INT,
          new Type[] {Type.getType("[I")},
          new String[] {"args"},
          "evaluate", classgen.getClassName(),
          il, cp);
    
    
        method.setMaxStack();
        method.setMaxLocals();
    
    
        classgen.addMethod(method.getMethod());
      }
    }
    
      
     
    

    All Rights Reserved
    Copyright ©  2004 SYS-CON Media, Inc.
      E-mail: [email protected]

    Java and Java-based marks are trademarks or registered trademarks of Sun Microsystems, Inc. in the United States and other countries. SYS-CON Publications, Inc. is independent of Sun Microsystems, Inc.