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?

Advertisement

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.

ORMDroid 0.20 now available

ORMDroid 0.20, the first packaged release of the ORM framework for android, is now available from the project downloads page on Google Code. This first release packages up the Android library ADT project, adds some documentation (which you can view online here), and makes it easy to grab and go if you don’t like to/want to work with the Subversion repository.

In case you missed it, you can read more about ORMDroid here, here and here.

New toy has arrived!

My Raspberry Pi

The Royal Mail kindly delivered my new toy this morning – a shiny new Raspberry Pi. I’ve been wanting to get my hands on one of these for quite a while, but what with work and other commitments I’ve not actually gotten around to ordering one – until now.

Considering the lead times on the Pi have been long to say the least, I was very impressed to receive mine within three days. I knew they were getting out much more quickly than they did to begin with (demand at the start far exceeded expectations) but still, I didn’t expect to get it in less than a week or two. Ordered from Farnell on Tuesday, shipped on Wednesday, and at my door Friday morning. Sweet!

I love working with these embedded computers (in a previous job, I was the operating system guy on a team that designed a high-def video processing engine based on an Ambarella SoC, which is when I got hooked) so it’s actually strange that I’ve not gotten a Pi before now. I’m planning to make up for that with some heavy-duty hacking over the coming weeks.

In terms of plans, I’ve got a few. I’d really like to get Android running on it, and maybe use it as an Android-based media and entertainment box. There’s already an effort going on to port ICS to the Pi (the current major issue seems to be lack of GPU and AudioFlinger support) so I’ll take a look into that. In the meantime, there are already Gingerbread ports available.

For now though, I’m going to install stock Raspbian, fire this thing up, and have a poke around to see what it’s got. I may be some time….. 😉

DEXing Deelang – On a real device!

Further to my previous post, I’ve been working this week on the new native compiler for Deelang on Android. This is a drop-in replacement for the standard custom bytecode compiler and VM that compiles Deelang scripts directly to Dalvik Executable  (DEX) bytecode for use on the Dalvik VM used in Android.

Development has moved fairly quickly, and there is now support for some of the basic features of the language. Not everything is supported at present (there’s no field access, no method blocks, and no arithmetic support) but the basics of function/method calls are implemented, along with local variable assignment and access, and a lot of behind the scenes support that make implementing the missing features a lot easier.

The compiler is being written largely test-first, so there’s good test coverage of new features as they go in (using Dex2Jar to generate readable dumps of the generated code, which is then compared against the expected code), but this doesn’t prove a crucial fact – that we can load the code into a running device, and execute it. To this end, there’s a small sample app that lets us write code on a device, compile it and run it against a simple binding we provide.

The screenshot shows this simple (and, if I’m honest, ugly) app running on an HTC One X. Compiling the code is quick enough given the early stage of development, but it’s actually running it where the native compiler shines – because the code is a standard Java class (it’s implemented as a subclass of the com.roscopeco.deelang.runtime.CompiledScript class, which is also a java.lang.Runnable) there’s no discernible difference between running a script and calling any other Java method.

We’re not benchmarking this in any serious way at this early stage in the project, but it’s nice to get a feel for how things are going from a performance perspective.

If you’re interested in taking a look at the work so far, you can get the sample app from SVN at the following repository URL:

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

The sample includes a snapshot Deelang jar, so you don’t need the actual project to try it out. Of course, if you want to play around with the code you can grab it from:

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

Updating the snapshot is as simple as running ‘ant jar‘ in the deelang directory, and then copying out the new snapshot over to the DeeSample libs/ directory.

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).

Spritesheets with Gimp – An adventure in Scheme

One of the coolest Android projects I’m involved with at the moment is a new strategy game, and one of the coolest things about it is it’s retro-look 8-bit style graphics. Growing up in the 80’s I obviously got a lot of exposure to the unique look of games in the 8-bit era, and I have fond memories of hacking away on the C64 and Spectrum, trying to represent real objects in a tiny number of pixels. So I’m really loving the resurgence of these techniques on current mobile devices.

Although there are a few “pixel art” graphics tools out there, we’re actually using the gimp to create our art (it’s what we know and love) and the game itself is using a layered sprite system to allow us to keep raw data to a minimum and also to make it easy for us to use different permutations of layers to create different sprites. For example, all the characters in the game are built from a small set of sprite layers which we just overlay in different combinations.

Perhaps an example is in order. Consider the rather snazzy (and somewhat surprised) looking individual on the left. He’s actually composed of a number of different layers in gimp, which are grouped and arranged in such an order that when one layer from each group is visible, they combine to create a character (in this case a mildly-shocked purple-haired gentleman in a blue sweater).

There are a number of these files, some covering people (as in this example), some with vehicles, some with background objects, and so on. And in each one, there are many layers each with a different sprite image. Not all are overlaid in this way, but they all use gimp’s layer features. Continuing the example, the image on the right shows you the gimp layers palette with the various layers that comprise the purple-haired dude.

If you look carefully you’ll see that our chap comprises a number of layers, with helpful names such as “skin_med” and “hair_02_purple”. All this works great while we’re actually drawing stuff, but once we come to actually put it into the game, we’re obviously not importing layered XCF  files – instead we break up the layers into a sprite sheet which flattens all the layers out and arranges them side-by-side in a single image (traditional sprite-sheets actually use multiple rows and columns, usually to give a fixed width and height as required by the hardware – we’re not doing this at the moment, although we do support it in the graphics engine). Turns out that this is not especially well supported in gimp.

Originally, we were using the built-in filmstrip plugin to accomplish this, but this was always a stop-gap solution – filmstrip is designed for use with photos, as a visual effect. As such, it actually adds virtual sprocket holes, frame numbers, and other assorted things. All nice if you’re making a montage of your week in Barbados, but no so great if you’re trying to get an exact-sized image you can then index into by pixel from your code. It is possible to stop these effects by tweaking the settings, but they don’t get saved across sessions, and in any event it doesn’t support transparent backgrounds so there’s always an extra select by colour/delete step once the sheet is made.

Luckily, Gimp supports scripting (via it’s Script-Fu interface to the Scheme language), so it was a fairly simple matter to knock up a script to take care of the conversion from layered image to flattened spritesheet. Gimp also supports Python scripts, but given the choice between a whitespace-sensitive language and a Lisp-like dialect, I’ll take the latter every time. It’s been a while since I last wrote Scheme, making it an ideal time to brush up some skills. A definite win-win situation!

After a little hacking around the API (Script-Fu has changed a bit since I last used it, but not so much that it’s unrecognisable) I had a basic working script, which I could call at any time through a menu item (on a new ‘Sprite’ menu I added, in anticipation of further scripts and plug-ins the guys have already asked me for). Going back to our example, the script creates a spritesheet in a new image, which for the guy above looks like:

Obviously, this example is so contrived as to be pointless. The real files have many more sprite tiles than this – I don’t think I’d be too popular if I started dumping all our graphic artifacts on here – but you get the idea.

And just in case you’re doing something similar and might find this useful, here’s the code. Call it a Saturday present from me, to you.

; Script to convert image layers to a sprite sheet.
; Copyright (c) 2012 Ross Bamford.
; http://www.apache.org/licenses/LICENSE-2.0.html
(define (script-fu-spritesheet img)
  (let* (
      (layer-count (car  (gimp-image-get-layers img)))
      (layer-ids   (cadr (gimp-image-get-layers img)))
      (sprite-width(car  (gimp-image-width img)))
      (spritesheet-width (* sprite-width layer-count))

      ; Create new image with appropriate size
      (spritesheet-image (car (gimp-image-new 
                                      spritesheet-width
                                      (car (gimp-image-height img)) 
                                      RGB)
                          )
      )
    )

    ; Copy and move each source layer appropriately
    (let (
        (i (- layer-count 1))
      )

      (while (> i -1)
        (let (
            (new-layer (car(gimp-layer-new-from-drawable 
                                      (aref layer-ids i) 
                                      spritesheet-image)
                        )
            )                     
          )

          (gimp-image-insert-layer spritesheet-image new-layer 0 -1)        
          (gimp-layer-translate new-layer (- spritesheet-width (* sprite-width (+ i 1))) 0)
          (gimp-item-set-visible new-layer TRUE)
        )

        (set! i (- i 1))
      )
    )

    ; Merge layers and rename
    (gimp-image-merge-visible-layers spritesheet-image CLIP-TO-IMAGE)
    (gimp-item-set-name (aref (cadr (gimp-image-get-layers spritesheet-image)) 0) "spritesheet")

    ; Create view for new image
    (gimp-display-new spritesheet-image)
  )
)

(script-fu-register "script-fu-spritesheet"
                    "Create spritesheet"
                    "Create a spritesheet from current image layers"
                    "Ross Bamford"
                    "Copyright (c)2012 Ross Bamford"
                    "2012"
                    "*"
                    SF-IMAGE    "Image"         0)
(script-fu-menu-register "script-fu-spritesheet"
                         "<Image>/Sprites")

(Caveat: I’m not primarily a scheme programmer. If you are, and you find my style abhorrent, well, tough :D)

(Postscript: Turns out that WordPress.com doesn’t support Scheme in it’s sourcecode tags! Thanks to the guys over at tohtml.com for their highlighter, even though I had to pretend this was lisp to get it highlighted anything like properly.)

Android NDK + Eclipse + Windows = Headache!

Whew! Just spent an “interesting” hour or two trying to get some native android code working under Eclipse on Windows… Although this isn’t the first time I’ve used the NDK, it’s the first time I’ve tried to get it working with Eclipse on the Windows (+Cygwin) platform. To borrow an unrelated phrase from elsewhere, it’s been emotional – I’m guessing the problems I’ve had are a combination of my lack of knowledge of Windows, and Windows lack of knowledge of, well, anything really.

No flames necessary, by the way. My position on Windows as a development platform are well known around these parts, and I don’t think there’s really any need to go into all that again. But Windows is what I have to hand at the moment, so it’s what I must work with.

The background is that I had an existing Android project that had some cross-compiled code (actually, the Quake III engine) that required a bit of work. The engine itself is a separate (non-Android) project, so I started by grabbing the source from subversion, and did the cross compile using the latest NDK (r8b). This went without a hitch once I’d updated a few things in the Makefile to adjust for the local setup.

Cool“, thought I. “Now to get going on the Android side of things, where I actually need to make changes”.

The way this project is set up is fairly convoluted, but it works. The android side of things has a bit of C that exposes the game engine to Java via JNI. The engine itself is (as mentioned above) cross-compiled separately, and there’s a simple Ant build that takes care of copying in the required shared libraries during the build.

To cut a long story short, it didn’t work. I checked the project out, and Eclipse couldn’t resolve the platform includes. I checked it out as a new (basic Android) project. Still no includes. I checked it out as a new C++ project, and manually added the appropriate nature and settings for an ADT project (Yes, I was getting desperate). Predictably enough, still no dice. I deleted the whole thing. I checked it out from a terminal and fiddled with various things. I shouted a bit. I went away and watched TV for a while (“A touch of cloth“, a new spoof detective show on Sky 1, by the way, is hilarious!). I googled incessantly. I checked paths, and re-checked them. Still, Eclipse couldn’t find the includes.

The maddening thing in all this was that the ndk-build command was working fine, and building the JNI glue without any problems. Even during the Eclipse build, it was fine. But I couldn’t actually deploy the app from within Eclipse because the IDE itself couldn’t see the includes, and so wouldn’t let me launch the app because it contained “errors”. Googling had turned up quite a few people with similar problems, but none of the proffered solutions worked for me. The include paths in the Eclipse C/C++ build properties were obviously correct, but still, no includes. I added more paths. I changed what I could. I created a brand-new project with a basic JNI test as a sanity check. And guess what? That’s right. No includes.

Eventually, I decided that there must be some kind of problem with the Android tool chain provided by the ADT. In every case so far I’d gone the “right-click -> Android Tools -> Add native support” route, so I decided to get back to basics and do things manually. For anyone else who encounters similar problems, these are the steps I took:

  • I closed the project in eclipse, and deleted .cproject from a terminal.
  • I re-opened the project in the C/C++ perspective.
  • I went to File->New->Convert to a C/C++ project (Adds C/C++ Nature).
  • I selected “Makefile project“, and “–Other toolchain–” (obviously I tried the “Android GCC” option but ended up with the same problems).
  • I then fired up the Project Properties, and went into the Builders page. Here, I unchecked “Use default build command” and entered the following instead: bash -c 'c:/opt/android-ndk-r8b/ndk-build':Eclipse Builders Properties
  • I then switched to the “Behaviour” tab in this same dialog, and removed the ‘all’ argument to the incremental build command, and completely disabled the “clean” behaviour since I didn’t need it when using ndk-build manually:Eclipse Builders "Behaviour" dialog
  • Finally, I manually entered the include path into the “C/C++ General/Paths and Symbols” settings. In my case, the path I added was “NDK_HOME\platforms\android-14\arch-arm\usr\include“. I made sure that both the “Add to all configurations” and “Add to all languages” checkboxes were checked (I’m on Eclipse Juno, these checkboxes may not show up in earlier versions). So that the include paths ended up looking like:Eclipse include paths dialog
  • I applied these settings, and okayed the dialog.
  • Finally, for good measure, I closed the project, re-opened it, and ran a clean followed by a build, and all was good!

So that was it. The includes were all showing up (I actually had to prove this to myself by Ctrl+Clicking on an #include <jni.h> line!), and I could happily deploy and run the project from Eclipse. ndk-build was running (as it always had) but there were no more complaints from Eclipse. Needless to say, I’m happy. I can now get on with the actual work I set out to do in the first place.

I’m still not convinced this is a bug, so I haven’t filed any reports anywhere. But when I get chance to run down exactly what’s going on here in more depth I will either realise where I went wrong in the first place, or I’ll file bugs appropriately.

Final note: If you’re having similar problems, and decide to follow the steps I took, keep in mind that depending on your project you may need additional include paths, to ensure Eclipse can see the platform-specific headers from the NDK. In my case this wasn’t necessary, but if it is for you then just take a look at the standard paths in an NDK project, and copy them across as necessary.

Deelang – First file release available to download

After a few months in Subversion, with a few folks playing with the code and seeing what use they can make of it, the first file release of Deelang is now available from the project’s downloads page. This release is still a very early public release (as denoted by the 0.18 version number) but is already mostly functional (with the notable exception of first-class regular expressions, which may never make it in anyway) and ready for testing.

Like most of our Android stuff, Deelang started life as internal code for a (closed source) third-party app, that ended up being deemed “possibly generally-useful enough” for open-source. So, at the moment, it mostly does the things we needed it to do when it was written. And, as with ORMDroid, the intention here isn’t to just dump the code into Google Code and forget about it – I intent to keep developing these things. What I really need is for folks to pick up the code, start using it, and either come back to me and tell me what cool new things they want to see it do, or (even better!) send over a patch with the aforementioned cool new things.

In case you’ve read this far in the hope of finding out what the heck Deelang is, the project page summary puts it thus:

Deelang is a lightweight, embeddable, dynamically-typed scripting language for Java that is intended for use in user-scriptable applications in limited resource environments, and especially for Android devices.

Basically it’s a very simple scripting environment that allows you to provide some manner of customization to your users, or to others deploying your apps. You define an API (it comes with almost none, beyond a basic object hierarchy for ‘primitives’) for code to run against, and Deelang provides a compiler, and a virtual machine in which to run scripts against this API. To quote (again) from the project site on google, it allows you/your users/someone else to write scripts like:

pic = Camera.take_picture()
pic.save_to_media()

Facebook.share(pic) {
caption = "I just took this picture!"
  album = "Random pics I took"
} or {
  post_status("took a pic but couldn't upload it :(")
}

(Obviously, assuming you provide the appropriate Camera and Facebook implementations). These scripts can then be compiled and run on the fly, or compiled and cached for later, perhaps to run in response to some broadcast intent or whatever.

So anyway, if you have a minute, grab the code and take a look, have a look at the (sparse) wiki, see if Deelang might be useful in your own projects, and if you think of a killer feature that you could really, really use, get in touch via the comments and we’ll talk…

PJ5 TTL CPU

Blog about the TTL based CPU design we're making

Don Charisma

because anything is possible with Charisma

Tech Filled Fantasy

One stop shop for all your tech-filled pleasures!