Mandelbrot RS, the quick version, part 1

In the Mandelbrot Map application, I run the fractal computation straight with the Dalvik VM. The code is written in the Java language and the Dalvik VM runs it using its JIT. The core of the fractal computation is quite simple yet expensive to run, so this is the area where one would typically invest time and effort to speed things. There are two ways to make it all go faster.

The first and obvious way to speed this is to use the Android's Native Development Kit, which would allow us to rewrite this core computation in C or C++, build it as a lib and embed it into the Android application and call it from Dalvik.
The immediate pros is that the code is compiled directly to the CPU architecture of the target device (e.g. ARM for most current phones and tablets, ATOM/x86 soon for probably next year's hardware.)
The cons is that since the code is compiled against an architecture, you need one per target architecture, so next year you'll likely need 2 (ARM + x86). Debugging is tedious, and the JNI calls to communicate between the C and the dalvik parts can be a tad tricky and there isn't a lot of literature on the subject. The setup is also a tiny bit more involved that just adding a plugin to Eclipse, especially on Windows, but it's not that hard and is something you'd do only once.

Since Honeycomb however, we have another choice: RenderScript. This uses a "script" which looks like C (in fact it conforms to the C99 spec), but instead of being converted to machine code, it is compiled to LLVM bytecode. The bytecode is then converted once at runtime on the target device.
One of the immediate benefits of RenderScript is that the target can be either the CPU or the GPU. This will depend on the script and the capabilities of the target, based on some static analysis of the code involved. That means the programmer doesn't have anything to do, the engine takes care of selecting the most capable target.

Now RenderScript has 2 sides: it can be used to perform 3D rendering using some kind of scene graph and in this case it would typically replace your typical OpenGL calls with shader language. GL calls are pretty verbose and repetitive and it's something I always found a bit wasteful to do from the dalvik side. I haven't tried it, but it seems like RenderScript could help a lot here.
The other side is the so called "compute" script: pure number crunching, no GL or 3D involved.

So the question is: what would it take to use RenderScript to run my Mandelbrot core loop, and what speed benefit would I get?
The short answer is that it's trivial. I did the conversion in about 1 hour, including looking at samples and reading docs around, and the net result was a 2x speed improvement when running on a Xoom.

So here's the original from JavaMandel.java:

static void mandelbrot2_java(
    double x_start, double x_step,
    double y_start, double y_step,
    int sx, int sy,
    int max_iter,
    int size, int[] result) {
  if (max_iter <= 0) return;
  double x_begin = x_start;
  for(int j = 0, k = 0; j < sy; ++j, y_start += y_step) {
    x_start = x_begin;
    for(int i = 0; i < sx; ++i, ++k, x_start += x_step) {
      // the "naive" mandelbrot computation. nothing fancy.
      double x = x_start;
      double y = y_start;
      double x2 = x * x;
      double y2 = y * y;
      int iter = 0;
      while (x2 + y2 < 4 && iter < max_iter) {
        double xt = x2 - y2 + x_start;
        y = 2 * x * y + y_start;
        x = xt;
        x2 = xt * xt;
        y2 = y * y;
        ++iter;
      }

      result[k] = iter;
    } // i
  } // j
}

First we need to convert that to the C99 syntax for the RenderScript file. Luckily it's mostly copy and paste as we can see in src/com/alfray/mandelbrot2/mandel.rs:

#pragma version(1)
#pragma rs java_package_name(com.alfray.mandelbrot2)

int *result;

void mandel2(
  double x_start, double x_step,
  double y_start, double y_step,
  int sx, int sy,
  int max_iter) {

  int *ptr = result;

  // the "naive" mandelbrot computation. nothing fancy.
  double x_begin = x_start;
  int i, j, k;
  for(j = 0, k = 0; j < sy; ++j, y_start += y_step) {
    x_start = x_begin;
    for(i = 0; i < sx; ++i, ++k, x_start += x_step) {
      double x = x_start;
      double y = y_start;
      double x2 = x * x;
      double y2 = y * y;
      int iter = 0;
      while (x2 + y2 < 4 && iter < max_iter) {
        double xtemp = x2 - y2 + x_start;
        y = 2 * x * y + y_start;
        x = xtemp;
        x2 = x * x;
        y2 = y * y;
        ++iter;
      }

      *(ptr++) = iter;
    } // i
  } // j
}

The only question is how to give the parameters to the method and get the result back.
First: as soon as you save a RenderScript file in Eclipse, ADT will run the compiler on it[*]. This produces 2 things:

• A ".bc" file in the res/raw folder that has the same name as the .rs being compiled.
• A Java wrapper in the gen folder that wraps the script into a convenient Java helper.

You can find the details of the wrapper in the SDK's RenderScript section and don't forget to look at the samples for API 11.

[*] Note: there's a bug in ADT 10.0 and it will fail to compile an empty .rs file and keep trying and trying ad nauseam. In this case make sure to write the 2 magic #pragma lines before saving the first time.

So how do we use that RenderScript now? I have a little Java wrapper that performs the following steps.

First you need to instantiate the script:

RenderScript mRs = RenderScript.create(activity_context);
ScriptC_mandel mScript = new ScriptC_mandel(mRs,
                    activity_context.getResources(),
                    R.raw.mandel);

where R.raw.mandel is the id matching the res/raw/mandel.bc generated by the compiler.

Next we need to allocate the destination buffer. All allocations are done on the dalvik side. In the script we just defined a "global" *result without defining how it was set. So we'll do that now in the Java wrapper, creating an array of "size" number of integers and binding it with the "result" variable:

mAlloc = Allocation.createSized(mRs, Element.I32(mRs), size);
mScript.bind_result(mAlloc);

and we can now invoke the computation, still from the Java wrapper:

int[] javaResult = new int[size];
mScript.invoke_mandel2(x_start, x_step, y_start, y_step, sx, sy, max_iter);
mAlloc.copyTo(javaResult);

And that's it, we just got a 2x speed improvement in this case for a trivial amount of work -- 2x is when comparing the rendering time on a Xoom between the dalvik JIT and the RenderScript version. It is important to realize that both the dalvik code and the RenderScript one are single threaded and are not taking advantage of the dual core in the Xoom.

It's important to realize that in the little Java wrapper I caught all exceptions when trying to create the RenderScript instance. Not all devices are going to support RenderScript, starting with anything below API 11, which is currently 99.8% of the market, including the emulator. However we should soon see a plethora of tablets supporting it and these devices will have larger screens, meaning more pixels and thus more computations to run.

Some lessons learned:

• The HelloCompute RenderScript uses a rsForEach() helper method, but it wasn't clear at all how to use it. I will elaborate on this in a future article, as it's important to extract the most from RenderScript.
• It's as hard to debug RenderScript as it is with the NDK, due to the lack of proper debugger. There's an rsDebug() method that can be used to basically do printf-debugging. In my case it wasn't an issue since I already had the java code, yet I still managed a typo in the call parameters.
• As of Honeycomb, RenderScript doesn't run on the emulator yet. You will need a real device that can support it, which at the time of this writing only the Xoom can provide.

NDK and Cygwin 1.5

The latest Android NDK r5b does not support Cygwin 1.5 -- if you try to use it, it will detect it and abort.
One of my development boxes uses Cygwin 1.5 because I don't have a choice -- I use some software that doesn't build on 1.7 and it's complicated to try to run them side-by-side.

But fear not, there are ways.
First comment out the abort in line 170 of android-ndk-r5b/build/core/init.mk, and next run it with the NDK_USE_CYGPATH variable.

$ NDK_USE_CYGPATH=1 ~/android-ndk-r5b/ndk-build

The variable is necessary to help the ndk pass the right sources paths to gcc.
This makes the ndk build a tad slower, but as my project has only one source, it doesn't matter.

DIY Dependency Injection

Most Java people will tell you "you've got to use Dependency Injection". One valid argument I've seen lately is to replace global static singletons, which make apps easier to unit-test.

Now in my Android projects, I don't like to drag in huge libraries. So sure we have Guice, but really I don't want to include that just to inject a class somewhere. A singleton is finally pretty cheap. But then I realize I don't need that kind of heavyweight library. The core of an injection mechanism is pretty obvious with a bit of reflection.

Let's say I have an annotation:

@Retention(RetentionPolicy.RUNTIME)
@Target(ElementType.FIELD)
public @interface Inject {
}

and somewhere else I have something to inject into some field. It becomes trivial to explore a class instance, retrieve the fields that have our annotation and replace them by that something if it has the right type:

public class MainActivity extends Activity { 
    private static final String TAG = MainActivity.class.getSimpleName();

  @Inject
  private IProvider mProvider; // never initialized directly

  @Override
  public void onCreate(Bundle savedInstanceState) {
    super.onCreate(savedInstanceState);
    setContentView(R.layout.main);
    performInjection(this, new Provider());
    TextView text = (TextView) findViewById(R.id.the_text);
    text.setText(mProvider.getValue());
  }

  private void performInjection(Object target, Object...injected) { 
    for (Field f : target.getClass().getDeclaredFields()) { 
      try { 
        if (f.get(target) == null && f.getAnnotation(Inject.class) != null) { 
          Class<?> t = f.getType(); 
          for (Object in : injected) { 
          boolean inject = t.equals(in.getClass()); 
          if (!inject) { 
            for (Class<?> i : in.getClass().getInterfaces()) { 
              if (t.equals(i)) { 
                inject = true; 
                break; 
              } 
            } 
          } 
          if (inject) { 
            // Inject stuff 
            f.set(target, in);
            break; 
          } 
        } 
      } catch (IllegalArgumentException e) { 
        Log.w(TAG, e); 
      } catch (IllegalAccessException e) { 
        Log.w(TAG, e); 
      } 
    }
  }
} 

And... we're done. That was it. In this case I have a field mProvider of type IProvider. The performInjection() method takes a target, look for all fields that have our @Inject annotation, and if they are null tries to find an argument matching the interface and apply the value.

Typically an Android application or activity instance can configure a few fields like this, which can then be picked up later in the same context. Obviously you could have done the same thing in this case with some getter or setter... In a more complex example, the idea is that you can simplify a bit of code by not having to keep passing some parameter around just to pass it to a method 15 levels down. Instead, isn't much better to have this field auto-magically set, loosely coupled, impossible to make sure who allocated it, with no hard guarantee it's actually set when necessary?

Of course you could just pass a context structure around, like activities do in Android. That's just so simple, efficient and clear, who would want that?

ActionBar before Honeycomb

The Android Honeycomb UI now prominently features an "action bar" -- a bar at the top of the screen where an application can put its icon, application name and menus, either in the form of icon or as text or as a popup.

If you have no idea what I'm talking about, I recommend you start by having a look at Reto's excellent article on the subject: Android App Surgery: Earthquake Redux (Honeycomb Tablet Edition).

That article however doesn't say much about 2 things: how complicated is it to use the new action bar, and how to maintain compatibility with 99.8% of pre-Honeycomb platforms.

I won't kill you with suspense: the answer to the first question is that it's fairly trivial. As an Android developer, your first reaction should always be to run the ApiDemos sample matching the latest platform of the SDK.

In this case you'll find 4 examples that best explain what you can do here:

• You can activate the action bar using a window feature or a theme (preferred).
• You can select what the bar displays: icon, text, custom view, search field, menu items, popup menu.

For testing, I decided to update my Mandelbrot Map application for Android. Here's what it looks like on a phone running Gingerbread and below on a Xoom running Honeycomb, with no modification whatsoever.

In this application, I remove the title bar since it doesn't add much value and instead I replace it by a text view with the zoom parameters, number of iterations and coordinates in the Mandelbrot set. Note that the application doesn't hide the status bar -- this is not a "total immersion" game, instead it's the kind of modest utility one my run whilst waiting for an appointment or something to happen, so we want to keep notifications and time visible.

Even on the Xoom, out of the box it looks pretty good. The only drawback is the "old style" menu at the bottom, which isn't very pretty. But it's still very functional and that was an amazing zero amount of work so far -- the application already correctly declared it supported large screen sizes in its manifest.

So the first action is to get rid of the "old style" menu. To do this, all you have to do set android:targetSdkVersion to 11 in your manifest -- this tells the system you know your application can deal with API 11, so you'll get the new theme:

<manifest ...>
<uses-sdk
    android:targetSdkVersion="11"
    android:minSdkVersion="4" />
...

This will remove the "old" menu icon in the bottom bar. However rhe application will then suddenly offer no way for users to access the menu! How did that happen?!

That's because in this application I was overriding the default theme to use a theme with no title bar.

What we need is to change it for Honeycomb, yet we want to keep it as it was for previous versions. We can easily do that by defining the activity theme in a resource file and customizing it for version 11.

First set a theme on your activity -- this is a much better way than setting the theme or the window features programmatically as it helps the system initialize the screen to look right from the very start:

<activity
  android:name=".tiles.TileActivity"
  android:theme="@style/ThemeMandelWindow" />

Now we'll define the theme twice, once in res/values and once in res/values-v11:

In res/values/styles.xml:

<resources>
  <style name="ThemeMandelWindow" parent="android:Theme.NoTitleBar">
  </style>
</resources>

In res/values-v11/styles.xml:

<resources>
  <style name="ThemeMandelWindow" parent="android:Theme">
  <item name="android:windowActionBar">true</item>
  </style>
  </resources>

Where does that "windowActionBar=true" come from? It's all explained in ApiDemos in the app/ActionBarMechanics.java source. I use a resource style because the behavior is static. Had I wanted a dynamic behavior (e.g. depending on an intent or in response to a user action), I could have used this in the Activity.onCreate():

getWindow().requestFeature(Window.FEATURE_ACTION_BAR);

For most applications, you can stop here. You'd have an action bar with the default theme color, an icon and a label, and a menu drop-down if you have menu items in your activity.

For the Mandelbrot application however, I have this text view at top that displays some information. As an exercise, I'm going to display it in the action bar as a custom view. I also want to change the action bar background color.

First, the layout. I want that text view in all versions with API 10 or lower, and no text view in the version for API 11 or higher.  I will however want that text view as a custom widget for API 11 and in this case it's just simpler to define it once using a custom XML, then include it in the main layout for API 10.

First we'll need an XML just for the custom text view, in res/layout/infoview.xml:

<TextView xmlns:android="http://schemas.android.com/apk/res/android"
  android:id="@+id/text"
  android:layout_width="fill_parent"
  android:layout_height="wrap_content"
  android:lines="1"
  android:text="Mandelbrot Map"
  android:textAppearance="@style/TextCaption"
  android:gravity="center"
  android:background="@color/dark_blue"/>

Now in res/layout/tiles.xml we include this; this is for APIs 10 and lower:

<RelativeLayout
  android:layout_width="fill_parent"
  android:layout_height="fill_parent" >
  <include layout="@layout/infotext"
  android:layout_alignParentTop="true"
  android:layout_alignParentRight="true"
  android:layout_alignParentLeft="true" />
  <com.alfray.mandelbrot2.tiles.TileView
    android:id="@+id/tile_view" ... />
</RelativeLayout>

And we can have a version for API 11 without the include in res/layout-v11/tiles.xml:

<RelativeLayout
  android:layout_width="fill_parent"
  android:layout_height="fill_parent" >
  <com.alfray.mandelbrot2.tiles.TileView
    android:id="@+id/tile_view" ... />
</RelativeLayout>

Finally in the activity we just need to change the action bar to insert the custom view:

// Grab the text view. This will be null in API 11 and higher.
TextView textView = (TextView) findViewById(R.id.text);
if (Build.VERSION.SDK_INT >= 11) {
  // Instantiate a new custom view based on the infotext layout file
  textView = (TextView) getLayoutInflater().inflate(R.layout.infotext, null);

  // Get the action bar
  ActionBar bar = getActionBar();
  android.app.ActionBar.LayoutParams lp =
  new ActionBar.LayoutParams(LayoutParams.WRAP_CONTENT, LayoutParams.WRAP_CONTENT);
  lp.gravity = Gravity.CENTER;
  // Set the custom view and tell the action var to display it.
  bar.setCustomView(textView, lp);
  bar.setDisplayOptions(ActionBar.DISPLAY_SHOW_CUSTOM, ActionBar.DISPLAY_SHOW_CUSTOM);
  // Set the background of the action bar
  Resources r = getResources();
  bar.setBackgroundDrawable(new ColorDrawable(r.getColor(R.color.dark_blue)));
}
textView.setText("initial values");

Now here's the end result:

That was quite trivial and the application is one step towards having a UI more consistent with the rest of an Honeycomb tablet. Now the next step would be to create some actions that are displayed directly in the action bar and take them off the options menu, but that's left as exercise to the reader.