Balisage Paper: The Effects of Bytecode Generation in XSLT and XQuery

Introduction

Many modern compilers generate code in an intermediate representation which is then interpreted by a virtual machine. One of the best known examples is Java: its intermediate code (known simply as bytecode) has proved flexible enough to be used as a target by many other high-level languages, allowing these languages to be mixed in the same Java Virtual Machine (JVM). XSLT and XQuery are no different from other languages in this respect, and a number of processors for these languages have used code generation to boost performance. There are few reports, however, that enable the effectiveness of this technique to be assessed, largely because of the difficulty in attributing performance differences to one particular optimization technique. This paper attempts to evaluate the impact of introducing code generation into the Saxon processor, enabling such a comparison to be made.

One well-known XSLT processor that compiles queries to Java bytecode is XSLTC [XSLTC]. [XSLTC] at a superficial level works by parsing the XSLT into an Abstract Syntax Tree (AST) which then goes through a type-checking phase before being compiled into Java bytecode. The output is a so-called translet class which can be used for transformations or saved to disk for re-use later. For XSLTC (which is distributed as part of the Apache Xalan-J package), the aim is not only to deliver enhanced performance in the runtime execution of queries, but also to produce a compact executable (the translet) which can be readily shipped around the network and executed anywhere.

Code generation is also believed to be used in a number of proprietary XSLT processors, such as the Datapower processor [DataPower] and Microsoft's .NET processor. However, no technical details of these products have been published in the literature.

Saxon first introduced Java code generation as long ago as version 4.2 [Kay1999] (some six months before XSLT 1.0 was published in 1999). However, this proved to be something of a blind alley, since it became clear that much greater performance gains could be realized through other optimization techniques, and that the existence of a code generator actually made these techniques more difficult to introduce. The architecture of Saxon at this time was to interpret the DOM of the source stylesheet directly instead of building an expression tree. This design made it impossible to do any extensive optimisation rewrites, as it is done now. One of the present authors [Kay2006a] argued that high-level optimizations are more important, and that compiling expressions to bytecode might reduce the scope for high-level optimizations, if only by making them more complex to implement and debug.As a result, the code generation was "shelved" while the architecture was changed to introduce tree rewriting.

Eventually code generation re-emerged in version 8.9 (Feb 2007), supporting XQuery only. It still took the form of Java source code generation, rather than bytecode generation. But it cannot be counted a great success: we are aware of very little usage. This is for several reasons:

This paper describes a new approach in which we hope to eliminate these problems. In particular, we believe that a 25% speed-up is not enough to encourage users to go to a great deal of effort in the way they execute their stylesheets and queries, but it will be much appreciated if it comes with no effort. There is a commercial factor which motivates this: Saxon is distributed in two versions, a free open-source product and a commercial paid-for version. While the commercial Enterprise Edition already has many features that users value, including features that can be used to deliver improved performance, users are sometimes disappointed to find it does not always run faster "out of the box". Code generation is an obvious way to remedy this, and ensure that users who pay their dues get some immediate benefit, with no need to change a single line of code.

Our objectives in adding code generation to Saxon are rather different from those for XSLTC, and this affects the approach we have adopted. In particular, we are not primarily interested in producing an executable that can be saved to disk or sent around the network. Rather, we want to integrate code generation and interpretation closely, so that we only generate code where there is a performance benefit to be gained, and continue to interpret otherwise. This should ensure that there are no language restrictions or differences when using code generation; it allows development effort to be focused where the potential gains are largest; and it limits the extent to which the existence of a code generation phase working off the expression tree limits our freedom to evolve the design of the expression tree itself when implementing new rewrite optimizations.

The remainder of this paper is organized as follows. Firstly, we discuss the high-level optimization of Saxon. Secondly, we discuss the bytecode generation feature of Saxon. Then we give an experimental evalaution of the running time performance of bytecode generation compared to Saxon interpreted mode. We base our experiments on the XMark benchmark queries, and conclude our findings.

High-level Optimization

The Saxon XSLT/XQuery processor includes a number of internal processes to compile, simplify and execute queries or stylesheets efficiently. In our discussion we will only make reference to XQuery, however in the Saxon internals very similar processes apply to XSLT.

Queries are parsed by a XSLT/XQuery compiler into a Abstract Syntax Tree (AST), which is a in-memory expression tree structure representing the logical structure of the query. In the case of XSLT, this tree combines the two sublanguages, XSLT and XPath, into a single integrated structure. References to variables and functions are largely resolved during parsing, an operation that is only slightly complicated by the fact that forwards references are permitted. Saxon then perfoms three optimization steps to produce the final AST that is interpreted at runtime. The first step is the normalisation of the AST, the second step is the type checking of the sub-expressions, and the third is expression rewriting. Detail of these are provided in the literature [Kay2008], [Kay2006b] and [Kay2005]. We summarize these steps below.

The optimizations require several depth-first traversals of the tree. In Saxon a visitor object provides a depth-first navigation of the expression tree. This class supports the various optimization steps involved in the processing of an expression tree, as it requires a recursive walk visiting each node in turn. A stack is also maintained as each node is visited, which holds the current ancestor nodes. The expression tree consists of many kinds of expression nodes, each of which implement the Expression interface. (This is the classic Interpreter design pattern.) The Expression class contains three important methods: simplify, typeCheck and optimize.

Each of these phases adds information to the tree. The most obvious information is the inferred static type of each expression, but there are many other properties that play an equally important role: for example the dependencies of an expression on variables or on the dynamic context, and properties of node-sets such as whether they are known to be sorted and whether they can contain duplicates.

Bytecode Generation

We now discuss a new Java bytecode generation feature in Saxon, which we consider as a fourth step in the optimization processes discussed in Section 2. It directly replaces the java source code generation feature provided in Saxon up to version 9.3. Here we are now generating the Java bytecode directly when compiling a query after it has been optimized. Our approach is different to that in XSLTC because we are generating bytecode selectively for expressions that are considered to have potential performance improvements, so that interpreted code and compiled code interact freely. The fact that compiled code exists only transiently in memory means that it can refer to data structures on the expression tree, rather than regenerating them at initialization time. In the longer term, this architecture also leaves the door open to just-in-time compilation (or hotspot compilation) based on observed execution patterns at run-time.

There are a number of Java class manipulation tools available (see Bruneton2002). One of the most widely used of these tools is BCEL [Dahm1999, Bruneton2002]. In this tool the class modification is achieved in a three part process: The bytecode representing the class is deserialized into a constructed class structure in memory, with a object created for each node, right down to the bytecode instructions. This structure is then manipulated in the second phase. The third phase is to serialize the modified object structure into a new byte array.

We chose instead to use the ASM [Bruneton2002] framework library tool to generate bytecode for queries. ASM [Bruneton2002] claims to be smaller and to give better performance than other tools. Where BCEL builds a DOM-like tree representation of the code, ASM works using a series of SAX-like streaming passes over it. There are other Java class manipulation tools which we only mention here such as SERP, JIOE: these are described in [Bruneton2002]. We have not done any experimental anaylsis of the Java class manipulation tools nor is there scope in this paper to provide an anaysis of these tools. Nevertheless, we have chosen the ASM library based upon [Bruneton2002], due to the simplicity of the tool and our requirement which only relied upon a small part of the library to dynamically generate bytecode in the runtime of queries.

The bytecode generation process has as input an AST, optimized to a greater or lesser extent in earlier phases depending on the Saxon product that is used. The top-level expression in each function or XSLT template is compiled into an equivalent Java bytecode class. We call this a CompiledExpression: it is constructed as we traverse the AST and can be evaluated at runtime. If the expression cannot be compiled, perhaps because it uses unusual language constructs, it is simply interpreted instead: but its subexpressions can still be compiled. The structure of the CompiledExpression is as follows: Firstly we generate static variables which have been initialised. As mentioned above, we are generating transient bytecode that works interchangably with interpreted code. The static variables in the generated code contain references to data on the expression tree: either whole expressions, or helper classes such as node tests, comparators, converters, and the like. For example, the NodeTest object, which provides XSLT pattern matching, acts as a predicate in axis steps, and also acts as an item type for type matching, is stored as a static variable available for use in the bytecode generated.

As discussed in [Kay2009] and [Kay2010], Saxon can execute internally in both pull and push mode. In pull mode, an expression iterates over the data supplied by its child expressions; child expressions therefore implement an iterate() method which delivers results incrementally to the caller. In push mode, an expression writes SAX-like events to an output destination (a Receiver). Choosing between pull and push mode can make a substantial difference to performance: during development, when we have observed situations where compiled code was outperformed by interpreted code, it was generally because the interpreter was making better decisions on when to pull and when to push. The compiled code therefore needs to work in both modes, so each CompiledExpression has two methods: an iterate method to deliver results to its caller, and a process method to write events to a Receiver. A third method, evaluateItem(), is provided for single-shot evaluation of expressions that always return a singleton result. Of course in many cases these methods will share common logic.

compileToItem    - Generate bytecode to evaluate the expression as an Item
compileToIterator - Generate bytecode to evaluate the expression as an Iterator.
compileToBoolean  - Generate bytecode to evaluate the expression as a boolean.
compileToPush     - Generate bytecode to evaluate the expression in push mode.
compileToLoop     - Generate bytecode to evaluate the expression in such a way that
                the supplied loop body argument is executed once for each Item. 
compileToPrimitive - Generate bytecode to evaluate the expression as a plain Java value 
                     (e.g. int, double, String). This method must only be called if the 
                     target type of the expression is known  statically.

 public process(Lnet/sf/saxon/expr/XPathContext;)V
   L0
    // Get the Receiver to which output will be sent
    ALOAD 1    // the XPathContext object
    INVOKEINTERFACE net/sf/saxon/expr/XPathContext.getReceiver ()Lnet/sf/saxon/event/SequenceReceiver;
    ASTORE 2   // local variable holding the current Receiver
    ALOAD 2
   L1
   L2
    // Get the context item (evaluate ".")
    ALOAD 1    // the XPathContext object
    INVOKEINTERFACE net/sf/saxon/expr/XPathContext.getContextItem ()Lnet/sf/saxon/om/Item;
    DUP
    // Generate an error if no context item is defined
    IFNONNULL L3
    NEW net/sf/saxon/trans/XPathException
    DUP
    LDC "Context item for '.' is undefined"
    LDC "XPDY0002"
    INVOKESPECIAL net/sf/saxon/trans/XPathException.<init> (Ljava/lang/String;Ljava/lang/String;)V
    DUP
    GETSTATIC CE_main_671511612.nContextItemExpression0 : Lnet/sf/saxon/expr/ContextItemExpression;
    INVOKEVIRTUAL javax/xml/transform/TransformerException.setLocator (Ljavax/xml/transform/SourceLocator;)V
    ATHROW
    // Load "true" (1) or "false" (0) depending on whether the value is null
   L3
    IFNULL L4_returnFalse
    ICONST_1    //Load true (1)
    GOTO L5
   L4_returnFalse
    ICONST_0    //Load false (0)
   L5_endExists
    // Convert the result to a Saxon BooleanValue object and send it to the Receiver
    INVOKESTATIC net/sf/saxon/value/BooleanValue.get (Z)Lnet/sf/saxon/value/BooleanValue;
    INVOKEVIRTUAL net/sf/saxon/event/SequenceReceiver.append (Lnet/sf/saxon/om/Item;)V
    RETURN
}

public void process(final XPathContext context) throws XPathException {
    SequenceReceiver out = context.getReceiver();
    if (context.getContextItem() == null) {
        dynamicError("The context item is undefined", "XPDY0002", context);
    }
    final boolean b0 = (context.getContextItem() != null);
    out.append(BooleanValue.get(b0), 0, NodeInfo.ALL_NAMESPACES);
}

Experimental Evaluation

In this section we draw comparisons of the running time performance between interpreted code and generated bytecode. An important aim is to compare the impact of code generation with the impact of high-level rewrite optimizations: to this end we run with four configurations, both features being switched on or off. (In the released product, neither feature will be available in the open source Saxon-HE, and by default both will be enabled in Saxon-EE).

Setup

We used Saxon 9.3.0.4 as the baseline. The test machine was a Intel Core i5 processor 430M laptop with 4GB memory, 2.26Ghz CPU and 3MB L3 cache, running Ubuntu 10.04LTS Linux. The compiler was Sun/Oracle Java 1.6.0.2. The experiments are based on the XMark benchmark [XMark]. We use the XMark XQuery queries numbered q1 to q20, and synthetically generate several XML data files from [XMark], these being of sizes in the range 1MB to 64MB.

Running Times

The 20 XMark queries are run repeatedly up to 1000 times or until 30 seconds have elapsed, and we record the average time spent to complete the runs, using the system clock in Java. [Appendix B] shows the complete running times. We show these for Saxon-HE, Saxon-Bytecode, Saxon-EE and Saxon-EE-Bytecode (that is, with weak optimization and no code generation; with weak optimization plus code generation, with strong optimization and no code generation, and with strong optimization followed by code generation). We compare the running times of the Saxon-EE product for the interpreted code and bytecode. We found on average over all files that bytecode generation gave between 14% and 27% improvement.

Figure 1: Scalability test. Running time performance for different file sizes on query 10

Scalability test: For Saxon-HE, Saxon-EE and Saxon-EE-Bytecode the timing results of running the XMark benchmark query 10 on XMark generated data files of sizes 2MB, 4MB, 8MB, 16MB, 32MB and 64MB. For Saxon-HE the running time for the 64MB data file is omitted as it goes off the graph.

In Figure 1, we show a graph of the scalability of running the query 10 on the XMark data files of sizes ranging from 2MB to 64MB with Saxon-HE, Saxon-EE and Saxon-EE-Bytecode. In Saxon-EE and Saxon-EE-bytecode the timing results show a linear growth as files become larger in size. For Saxon-HE we observe a quadratic growth: this shows up the absence of join optimization in the Saxon-HE product.

In Figure 2 and in Table III in Appendix B we observe that for certain queries the performance of bytecode generation is well above average. Queries 8, 10, 11 and 12 gave improvements between 35% and 50%. We compare the Saxon-EE products with the feature of Java code generation (Saxon-EE-JavaGen, featured in Saxon 9.3), the interpreted code and bytecode. Again we see an overall improvement over the intepreted code, but we observe similar results for Java code generation and bytecode generation, the difference being approximately 10% on average over all queries.

Effect of Optimization Rewrites

Comparison of the timings for different data sizes shows that with weak optimization, queries 8, 9, 10, 11 and 12 have performance that is quadratic in the data size; with strong optimization, only query 11 is quadratic. This is because queries 8, 9, 10 and 12 are equijoins, whereas query 11 is a non-equijoin which the Saxon optimizer cannot handle well.

Figure 2: XQuery Queries Running Times (10MB data file)

For Saxon-EE-JavaGen (Java Generation in Saxon 9.3), Saxon-EE and Saxon-EE-Bytecode the timing results of running XMark benchmark query 7, 8, 9, 10, 11 and 12 on a 10MB XMark generated data file.

Using Hand-written Code as a Benchmark

In the previous sections we've concentrated on comparing the performance of compiled queries and stylesheets with the same queries and stylesheets run under the interpreter. But there's another technique we have found useful, which is to compare the performance of a compiled query with hand-written Java code performing the same task. The performance of the hand-written code sets a target to aim for, and provides a measure of how much room for improvement is available.

The results show great variation between different queries, which is useful information in itself. Here we'll consider two simple queries.

The first computes the average income of buyers recorded in the XMark dataset: we're running the query

avg(//profile/@income)

The Saxon interpreter runs this in an average of 792ms. Currently, when compiling to bytecode, the improvement is quite modest: average time is 768ms.

The same query coded in Java looks like this:

NodeInfo root = doc.getUnderlyingNode();
AxisIterator descendants = root.iterateAxis
                      (net.sf.saxon.om.Axis.DESCENDANT, 
                       new NameTest(Type.ELEMENT, profileNC, pool));
NodeInfo profile;
double total = 0;
int count = 0;
while ((profile = descendants.next()) != null) {
    String income = Navigator.getAttributeValue(profile, "", "income");
    if (income != null) {
        total += Double.valueOf(income);
        count++;
    }
}

The execution time for this code is 690ms. So we see that the interpreter is already almost as fast as the hand-written Java code. On the assumption that generated bytecode will rarely be better than hand-written Java code, there is little headroom available for the code generator to make a significant impact. It's easy to see why this should be the case: the query is spending nearly all its time (a) searching the descendant axis for <profile> elements, and (b) converting attribute values from strings to numbers. These two operations are done by library routines that execute exactly the same code whether it is run under the XQuery interpreter, the XQuery code generator, or the hand-written Java code. Both routines have been carefully tuned over the years and there is little scope for improvement; neither is doing any work that doesn't absolutely need to be done.

Our second query is rather different. This one doesn't in fact process any XML, so one could argue that it is atypical; but as a fragment within a larger query it is code that one might well encounter:

sum(for $i in 1 to $p return xs:double($i)*xs:double($i))

double j = 0;
for (int i=1; i<=100000; i++) {
    j += (double)i * (double)i;
}

The lessons from this exercise are firstly, that there are some execution paths where it is very hard to improve performance because it is already very close to optimal; but that there are other operations that still leave much room for improvement, and one good way to identify this is to compare the system-generated code with hand-written Java code that performs the same task.

Conclusion

The purpose of this paper was to study the performance benefits that can be achieved by adding a code-generation phase to an XSLT or XQuery processor. To do so, we examined these side-by-side with the benefits achieved by high level optimization rewrites. The two techniques are orthogonal to each other, in that one can do either or both, but it is interesting to analyze which delivers better improvements in relation to the cost.

In the best case (or the worst case, depending on how you look at it), optimization rewrites can turn a query with quadratic performance into one with linear performance. This is something code generation can never aspire to. This therefore vindicates the approach that has been taken in Saxon of putting aside work on code generation until the high-level optimizer had achieved a sufficient level of maturity.

The conclusion of our study is that compiled code can be expected to run about 25% faster than code executed under an optimal interpreter, but the improvements can be greater (up to 50% in our case) when the interpreter is less than optimal or when the individual expressions on the expression tree are performing tasks such as arithmetic operations or numeric comparisons whose execution time is small in comparison to the overhead of the control logic for invoking them.

For Saxon, the extra 25% is well worth achieving, since there are many users with demanding workloads, and since the business model for the product relies on the development being funded by revenue from the small number of users with the most demanding requirements. For other products, the trade-off might be different: in particular the message from this study is that code-generation is something you should do only when all other opportunities for performance improvement have been exhausted.