Compiling the Knight's Tour

By Michael Kay on September 24, 2006 at 02:18p.m.

A progress report on query compilation: I've now got to the point where I can compile the knight's tour query (tour.xq in the Saxon samples distribution) into Java code, and execute it with correct results. It's running in 39.3ms, compared with 45.9ms for the interpreted code, which isn't wildly exciting, but there's enormous scope for tuning the generated code and it shouldn't be hard to improve on this figure very significantly.

The 292 lines of XQuery translate into 1362 lines of Java, which will come down as the code generation gets more efficient.

This is of course a very untypical query, as it has no input and generates fairly minimal output: it spends most of its time doing recursive function calls. But it's always been something of a torture test, so it's pleasing to have got it working (without any really hard bugs to solve en route, I might add). I've also got most of the XMark benchmark queries working, with speed factors varying from about 110% (compiled-to-interpreted throughput ratio) to 400%.

There's still an enormous amount of work ahead though. Compiling 30% of the language is enough to run 90% of queries, but it's not enough for a release.