Sunday, 27 February 2011

Clojure for Android source published

Over the next few weeks, I will be publishing the source code for the Clojure REPL for Android in a few different instalments:

  1. Clojure for Android, a modified version of Clojure adapted to run on the Dalvik virtual machine;
  2. Clojure Android Toolkit, a library of utilities for Clojure developers working on Android; and
  3. Clojure REPL, the source code of the application itself.

I have now published the modifications to my source code in a repository available on GitHub. My work is based on the 1.2.x branch of the Clojure source code and is available in the android-1.2.x branch.

This post will document my goals for Clojure on Android, give an overview of the changes I have made, describe the current implementation of dynamic compilation, and present areas for future work.

Goals

The three primary goals of the Clojure for Android release are as follows:

  1. Create a version of Clojure that works for both the Java and Dalvik virtual machines in the hope that the changes can eventually be included in Clojure itself,
  2. Create a development version of Clojure that supports dynamic compilation to enable more rapid development of applications, and
  3. Create a lean Clojure runtime that will deliver acceptable performance on Android devices.

Overview of changes

There really are not many changes in this initial release of Clojure for Android. They fall into three categories: the addition of a Dalvik-specific dynamic class loader, some minor runtime changes, and an update to the build configuration to support Android.

New DynamicClassLoader hierarchy

The most significant change is to DynamicClassLoader. In the original implementation, this class manages a constant pool, maintains a cache of class definitions, provides (deprecated) class path alteration capability, and is in charge of turning compiled class byte codes into classes available within the virtual machine.

In my implementation, it retains all of those abilities save for the last one. It is now an abstract class that delegates class realisation to its subclasses, of which there are two:

  1. JvmDynamicClassLoader relies on Java's standard ClassLoader.defineClass method.
  2. DalvikDynamicClassLoader uses a tortuous method, described later.
Runtime changes

There are a few relatively minor runtime changes:

  • The addition of a new var, clojure.core/*vm-type*, which will be set to either :dalvik-vm or :java-vm at runtime.
  • Choosing the correct DynamicClassLoader implementation depending on *vm-type*
  • A workaround for a bug fixed in ‘FroYo’ where the context class loader is set to a system class loader instead of the application’s class loader
  • The pre-emptive loading of clojure.set, clojure.xml, and clojure.zip is disabled on Dalvik.

That’s it.

Build system update

The build system has received somewhat more extensive changes. There are two basic scenarios:

  1. Building Clojure without Android support: This should work just fine. Just run ant as usual.
  2. Building Clojure with Android support: You will need to create a local.properties file with pointers to the Android SDK directory and SDK version you want to use. More documentation is available in readme.txt.

When building with Android support, the build file will create a stripped down version of the dx.jar file from the Android SDK. By default, this will do a simplistic removal of purely test classes. However, if you have ProGuard, it can do a more exhaustive shrinking. This is enabled by setting the proguard.jar property.

When Android is enabled, the build will create two additional JAR files:

  1. clojure-nosrc.jar, the opposite of clojure-slim.jar, a compiled-only version of Clojure. This JAR also contains the dx tool classes that are needed at runtime.
  2. clojure-dex.jar, a version of clojure-nosrc.jar where all of the classes have been compiled into a Dalvik executable. This file is suitable for loading by one of Android’s class loading mechanisms.

Dynamic compilation

To illustrate how I implemented dynamic compilation in Clojure, I will first present the traditional path from compiled Java class to instantiated Dalvik class. Next, I will show how the modified version of Clojure takes dynamically generated classes through the same process. Finally, I will present the trade-offs involved in the current implementation and what you should keep in mind when using the dynamic compilation.

Traditional work flow

The following is a brief description of the path of a compiled class file from build to execution:

  1. At build time:
    1. Java files are compiled into Java classes made up of JVM byte codes.
    2. All of the classes are prepared into a Dalvik Executable (DEX file) by the dx tool. This file is called classes.dex.
    3. The DEX file is placed into the Android package.
  2. At install time:
    1. The installer reads the DEX file from the package.
    2. The DEX file is verified to remove illegal instructions and performs some computations to aid in garbage collection.
    3. The verified DEX data is then optimized, creating a hardware- and platform-specific version of the code. Some optimizations include replacing virtual method call resolution with indices in a vtable, inlining method calls, pruning empty methods, etc.
    4. The resulting optimised DEX file (ODEX file), is written to a special cache directory.
  3. At run time:
    1. The ODEX file is checked to make sure it is still valid. If not, then the original DEX file is again verified and optimised.
    2. The application loads its classes from the ODEX file.
Dynamic Clojure work flow
  1. The Clojure evaluator compiles a form into a class using the embedded ASM bytecode engineering library.
  2. The DalvikDynamicClassLoader processes the compiled byte code as follows:
    1. It uses the embedded dx tool to translate the JVM class into an in-memory DEX file.
    2. It writes the DEX file into a temporary JAR file in *compile-path*.
    3. It uses Android’s dalvik.system.DexFile to load the JAR file. In doing so, Android will create an ODEX file in *compile-path*.
    4. Loads the class from the DexFile object and returns it.
Trade-offs

The main disadvantage to this form of dynamic compilation is that it is slow. It requires using the disk, as well as performing all sorts of computations at runtime. Anyone who has used the Clojure REPL for Android can attest to its sluggishness.

Unfortunately, to the best of my knowledge, there are no other accessible APIs available for doing this better. Most of the work is done in native code, making it difficult to bundle it into Clojure. There is some hope that this may change in the future. From the Dalvik documentation:

Some languages and frameworks rely on the ability to generate bytecode and execute it. The rather heavy dexopt verification and optimization model doesn't work well with that.

We intend to support this in a future release, but the exact method is to be determined. We may allow individual classes to be added or whole DEX files; may allow Java bytecode or Dalvik bytecode in instructions; may perform the usual set of optimizations, or use a separate interpreter that performs on-first-use optimizations directly on the bytecode

Until such an API is released, it is necessary to either take the slow but simple route, or to create a Clojure compiler for the Dalvik VM from scratch.

I think that dynamic compilation is of interest primarily to developers. Most applications will have no need for dynamic compilation as they can be AOT-compiled. As such, the slowness may well be acceptable. After all, waiting seconds for a function to recompile in your running application is much more tolerable than needing to go through a full compile-deploy cycle that may be measured in minutes.

Caveats

There are two things to be aware of when using dynamic compilation:

  1. You will need to be sure to point *compile-path* to some place where your application has write access.
  2. Some forms may blow the stack during compilation, such as (for [x (range 5) y (range 5)] [x y]). This is a limitation of the runtime.

Future work

There is still much to be done. As the source is now released, I look forward to seeing what sorts of feedback and improvements will come from others. Given the three goals I stated above, I think much of the work is as follows:

Integration with upstream

Get feedback on how to best integrate these changes into the language from other Clojure developers in general and, I hope, the Clojure/core team itself. Of course, it will most likely take some time before these changes make it into a Clojure release.

Clojure for Android development

While not perfect, I think the current solution largely satisfies this goal. Writing a new compilation back-end may make things better, but I am not sure that it will provide as good a return as working on the third goal.

I think that any new development should follow the master branch of Clojure going forward. The patches to the code itself should be simple enough to manage. Porting the build system changes to Maven will be more cumbersome.

Lean Clojure runtime

This is the place where the most work needs to be done. There have already been some good ideas presented on how to improve this, such as:

  • Eliminating metadata from compiled code to reduce memory footprint,
  • Finding ways to cut down on the immense amount of object churn during bootstrap, and
  • Generally finding ways to cut down on the amount of work done during the bootstrapping process.

My current idea is to find ways to modularise clojure/core.clj somewhat to be able to either completely eliminate some functionality (such as those for dynamic compilation) or at least delay loading it. Not every program makes use of every feature of the language. Some programs may never use one or more of: agents, futures, primitive vectors and arrays, etc. If there were some way to make some of these things load-on-demand, if only in an Android environment, that could significantly improve bootstrap times.

I look forward to the feedback from others and welcome any help in trying to get these things working. I think that it is quite possible to make Clojure a first-class development language for the Android platform.

TrackBacks

Comments