Rewriting Vs. Rewriting

As previously mentioned, I planned to spend yesterday rewriting Deelang‘s parser with the aim of fixing some long-term issues and revisiting some design decisions that get in the way of the DEX compiler. As it turned out, I didn’t have as much time as I wanted to spend on this (as usual!) but I did get some time to play with it, and it turned out that my decision to rewrite much of the parser was, well, somewhat premature.

The main aim of the rewrite was to change the way the AST is generated, to remove the imaginary CHAIN nodes that proliferate the current AST. CHAIN nodes are used as the LHS in field accesses and method calls, as well as one or two other places, and denote that the receiver is the result of the previous operation. They work great when compiling for a stack machine (such as the JVM or the original Dee VM) – they translate simply as “pop the top object from the stack” – but are less intuitive when compiling for a register architecture, such as Dalvik.

Continue reading

Advertisements

Deelang 0.20 released!

After about a month of coding (on and off), The Deelang DEX compiler is now feature complete, and what better way to celebrate than by releasing the code? It’s always been available in Subversion of course, but now you can download all the new stuff from the downloads page as either a source package or ready-made Jar, without all that messing around with Subversion, finding the right branch, or any of that. It’s right there, on the downloads page, just waiting for you to grab and go!

I’ve blogged a bit about the new features in this version (for example, here, here and here), and if you missed all that and are now wondering what on Earth I’m on about, I’ve also blogged generally about Deelang (e.g. here). The short version is that Deelang is a compiled script language designed for embedded devices (especially Android) that allows developers to give their users a simple way to extend their apps by writing small scripts.

Now that there’s a file release available, we’re hoping to get some bug reports and open a discussion about where Deelang could/should go. Other than the DEX compiler (which has been about a month of solid effort in OSS terms) development is a bit haphazard – it works for us, so we leave it. If we need something new, we implement it, then we leave it at that. I really want to get a community going around this thing, to make it more generally useful for everyone…

So why not grab the code, play around with it, file issues if you find any bugs, and come over and join the mailing list?

Dex vs Dee VM – A microbenchmark

During a recent discussion, I had the need to show some numbers demonstrating why Deelang needs the new DEX compiler. As I said in that thread, it’s all about removing reflection from the compiled classes.

We all know that “reflection is slow” (for some value of slow) and especially on Android, that it isn’t generally a good solution for general use in method invocation. Looking up methods by reflection is slow, as is performing the actual invoke. But how slow? Could I quantify the difference?

Since the Deelang DEX compiler is still being actively developed, I’ve never paid much attention to performance before, and have certainly never benchmarked it. We knew that the Dee VM wasn’t fast enough for some of the things we were using it for, and I knew from experience that it would be faster without reflection, and we left it at that. This discussion got me thinking though, and I decided it would be nice to have some idea of the actual difference between the Dee VM and scripts compiled to DEX.

Despite the fact that microbenchmarks are often a bad idea, and are a bit of a minefield at the best of times, I wrote one in this instance. After all, I only want some idea of the comparative performance for the sake of discussion – I won’t actually be basing any design or implementation decisions on these results.

I expected a decent performance boost in the DEX compiled scripts, but I honestly wasn’t quite prepared for how much of a boost:

09-27 10:45:27.525: I/BENCHMARK(15853): Rehearsal
09-27 10:45:37.665: I/BENCHMARK(15853): DeeVM completed : 10000 runs : 10107ms (10.107 seconds)
09-27 10:45:37.725: I/BENCHMARK(15853): Dex completed   : 10000 runs : 31ms (0.031 seconds)
09-27 10:45:37.725: I/BENCHMARK(15853): Real
09-27 10:45:46.695: I/BENCHMARK(15853): DeeVM completed : 10000 runs : 8938ms (8.938 seconds)
09-27 10:45:46.745: I/BENCHMARK(15853): Dex completed   : 10000 runs : 25ms (0.025 seconds)

(This is logcat from the benchmark running on-device on a HTC One X)

That’s right – almost 9 seconds for the reflection-based Dee VM, compared to 0.025 seconds for the DEX compiled version. The difference is so marked that I at first didn’t believe the results. I changed the script to actually produce some output to logcat, to make sure that it was actually running each implementation properly, and it was. It turns out that, in this case, reflection has a much bigger impact that I expected.

In case you’re interested, you can see the benchmark code at the this page on the project wiki on Google Code.

DEXing Deelang – First steps in SVN

If you’re one of the few who’ve already taken a look at Deelang, you’ll know that it’s a simple scripting language that compiles to a custom bytecode format, which then runs in a simple virtual machine. It can run anywhere, but is targeted mostly for embedded devices, and especially for Android.

All this is fine, and for the most part it doesn’t perform too badly. Unfortunately though it does mean that it’s most common operation (calling out to Java methods) is relatively slow, because under the hood reflection is used everywhere. This has the potential to be a problem since in Dee, everything is a method – you can’t define your own classes, methods or functions in scripts, but instead rely on a (Java-side) API provided by whoever embedded the language in their application. Even arithmetic and conditionals are done with methods. Reflection (especially on Android) is just too slow for this kind of usage.

To address this, I’ve been thinking for some time about a implementing a native (i.e. Dex) compiler for Deelang on Android, and over the past few days I’ve finally made a start. The architecture is pretty well mapped out in a first-cut kind of way (well, in my mind at least) but the implementation is only just taking it’s first baby steps. Hardly anything is supported right now – in fact, the only thing it’s possible to actually compile is literals and simple, direct function calls (what the Dee VM calls SELFCALLs). But it’s a start, and it’s in Subversion on Googlecode now if you feel like taking a look. All the work is being done in a branch, which you can browse or check-out at:

http://deelang.googlecode.com/svn/branches/DEXCOMPILER/deelang

What can it do?

As mentioned above, it’s very limited at the moment. In fact, about the most exciting thing it can do is take code such as:

foo(1,2)

and compile it to native Dex bytecode like:

//class:0000  access:0x0001
public class DexCompiledScript531a8036-8e20-4965-8148-e87dfb51283f extends com.roscopeco.deelang.runtime.CompiledScript

//method:0000  access:0x0001
//LDexCompiledScript531a8036-8e20-4965-8148-e87dfb51283f;.run(Ldee/lang/DeelangObject;Lcom/roscopeco/deelang/runtime/Binding;)V
public V run(dee.lang.DeelangObject,com.roscopeco.deelang.runtime.Binding)
                this:v3   //DexCompiledScript531a8036-8e20-4965-8148-e87dfb51283f
                    :v4   //dee.lang.DeelangObject
                    :v5   //com.roscopeco.deelang.runtime.Binding
CONST               |     |v1=0x00000001  // int:1   float:0.000000
NEW_INSTANCE        |     |v0=NEW Ldee/lang/DeelangInteger;
INVOKE_DIRECT       |     |v0.(v5,v1)  //Ldee/lang/DeelangInteger;.(Lcom/roscopeco/deelang/runtime/Binding;I)V
CONST               |     |v1=0x00000002  // int:2   float:0.000000
NEW_INSTANCE        |     |v2=NEW Ldee/lang/DeelangInteger;
INVOKE_DIRECT       |     |v2.(v5,v1)  //Ldee/lang/DeelangInteger;.(Lcom/roscopeco/deelang/runtime/Binding;I)V
INVOKE_VIRTUAL      |     |v4.foo(v0,v2)  //Lcom/roscopeco/deelang/compiler/dex/CompilerFuncTestBase$Foo;.foo(Ldee/lang/DeelangInteger;Ldee/lang/DeelangInteger;)V
RETURN_VOID         |     |return

Development is moving quite quickly though, so over the next few days expect some support for most of the current (VM-based) capabilities.

Why go native?

As mentioned, the current VM architecture makes heavy use of reflection, which in some cases just doesn’t have the performance we need. Compiling ‘natively’ to Dex bytecode will eliminate all reflection in the generated code and core runtime, and will make compiled scripts fully-fledged members of your application. There won’t be any need to carry around the VM and it’s runtime, and instead you’ll only need a lightweight core runtime package that provides the standard implementations of the arithmetic operators, the if and or operators, and so on.

The trade off is flexibility. In the VM, all binding is done at runtime, with the ability to swap out any bound object (including the self reference) at any time. In the compiler, binding has to be static, so some of that flexibility is lost. But in 90% of cases (at least in our code) this doesn’t matter, as scripts are run against a fixed binding anyway (that’s what provides the ‘API’ for users to script against).

In any event, this isn’t about replacing the current VM setup – the new compiler is actually just a new back-end for the existing com.roscopeco.deelang.compiler.Compiler class. To compile the script above, you use the standard compiler with the new backend, like so:

Compiler c = new Compiler();
byte[] dex = c.compile(new DexCompilationUnit(c, "<no file>", Foo.class),
                 Parser.staticParse("foo(1,2)")).getCode();

You can still use the old (now called DVM) compiler and VM runtime as before (although there have been some slightly incompatible API changes during implementation of the new architecture, notably the moving of the deelang.* namespace to dee.vm.lang.*, so you’ll need to tweak your code a bit) if you feel it fits your needs better. There are currently no plans to drop the VM (although it may stop being the default at some point).