Tries, JSNI and GWT

It's been a long time since the last post. I have been busy developing a web app based on GWT recently. While it's not exactly cutting edge technology, there are still some interesting aspects.

For example, there is the SuggestBox implementation that comes with GWT. You can use it to implement predictive text or auto-suggestions for a text input.

The suggest box uses a so called SuggestOracle to calculate the suggestions for a given string entered by the user. The default implementation that comes with GWT is the MultiWordSuggestOracle, which itself uses a combination of hash tables and a prefix tree to do its job.

A Trie is a Tree

A prefix tree or trie (as in retrieval) is a search tree where the nodes do not contain the keys themselves. Instead, the key for a particular node is determined by its position in the tree. More specifically, the key for a particular node is the concatenation of all the prefixes on the edges above it.

     X(he)        > prefix:""
      \
       X(ll)      > prefix: "he"
        \
         X(o)     > prefix: "hell"

If you look a my attempt at visualising a prefix tree for the word "Hello" above, you will notice that the root node is special in that its prefix is the empty string. The other thing to notice is that my example tree uses a prefix size of two characters. This has certain consequences for lookup time and data storage as we will see shortly. (Note: I put the values on the nodes to make it easier to read.)

What happens if you want to store more than one word in your prefix tree? Let's say we want to add the word "hell" to our trie.

     X(he)                 X(h)       
      \                     \
   (ll)X(ll)      OR         X(e)
        \                     \
      (o)X                     X(l)
                                \
                                 O(l)
                                  \
                                   O(o)

First of all the word "hell" was already in the tree as it is a substring of "hello". But the tree did not "know" about it. The tree on the left is the same tree I introduced before but on the first child node the additional "ll" string has been added. This is how the prefix tree that comes with GWT works. When adding new words, in this case "hell", we walk down the tree and we check on every node whether the remaining string length is equal or less than the prefix size (2). If so, we store the value directly on the node. If not, we look for a matching prefix tree below or create one. The prefix size increases by a power of 2 for each layer. (To keep it simpler I left that bit out in the illustration.)

If we compare this to a prefix tree with a prefix length of one (illustrated above on the right), there are two observations to make. First, you need a way of marking nodes of interest that are not leaf nodes. In our case we want to make clear that the string "hell" is a meaningful value and not just a substring of "hello". The GWT trie uses a separate storage location to hold "ll". This means that when looking up all values starting with "he", you have to look at those values stored on the nodes below "he" directly ("ll") and all values on child nodes ("llo"). In the case of the single character prefix you need some way of marking nodes that contain suffixes (i.e. that are the end of a meaningful word). I highlighted those nodes in the graphic by using an "O".

Oh, performance!

The second observation is that using a prefix size greater than one reduces the depth of the tree considerably. But, of course, there is a trade-off. If you choose your prefix too long, you lose the property that made the trie the right choice for the task: efficient lookup. The time complexity for a lookup in a prefix tree is determined by the length of the query string n and not the size of the tree, it is therefore O(n).

By increasing the prefix size, the deeper we descend into the tree, we give up that property. The longer your prefix, the more values will be stored on a particular node. The time complexity is now dominated by the size of the tree and the data structure used to store values on the nodes. Because you have to check every suffix on a particular node for a partial match, time complexity is now O(m), where m is the number of values stored on that node. So the worst case performance for this modified prefix tree with a start prefix length of p is O((log_p(n)m) on a degenerated tree with all values on one node.

I can only guess that the reason for this design decision was an assumption about typical usage patterns of the auto-suggest feature. If the user accepts a suggestion after typing only a couple of characters, the increasing prefix size makes the tree actually more efficient. The lookup is reasonably efficient for short queries, where the prefixes are still short and you do not have to descend into a very deep tree to find all suggestions.

This implementation also avoids deep trees consisting of many objects, because in a typical prefix tree you would find one (sub-)tree object per character. The creators seem to have traded lookup efficiency for easy retrieval, smaller memory footprint and a lower cost of object creation in JavaScript.

There is much more to be said about prefix trees, but what I want to try here is to go from the high level concepts down to the implementation details in Java and eventually to the resulting JavaScript all in one post. So let's look at the implementation now.

JSNI is the inline assembly of GWT

Well, sort of. JSNI allows you to include bits of "native" JavaScript in your Java code. By writing a "native" method in Java and including the JavaScript in a special comment block, you instruct the GWT compiler to include that bit of code with only minimal checking directly into the resulting JavaScript object.

In this example you can also see how the interaction with those parts of the PrefixTree class works that have not been implemented in JSNI but in Java. It's not exactly elegant or easy too read. Suddenly, the assembly comparison seems not so far off. Once you put JavaScript into a forced marriage with Java, it loses all elegance and succinctness. What you can see, though, is how all the members of the PrefixTree class are translated to JavaScript by referring to them in "mangled" syntax that uses fully-qualified names for everything.

If you try to find the method I just used as an example for the JSNI syntax in the output of the GWT compiler, you won't find it. At least not where you expect it. The compiler has inlined the "clear" method into the constructor of the prefix tree. The generated code is very readable compared to its JSNI counterpart.

If you turn on the emulated stack trace feature of GWT, the compiler keeps track of the original source on every call by storing the current location in a global variable. All the readability is gone. But it shows again how the code has been inlined. You can now see the line numbers from the original Java source file:

All non trivial methods of the PrefixTree class are implemented using JSNI in GWT.

What does it buy you?

First, there is a cost attached: you lose almost all tool support in your IDE. There is no refactoring tool that will pick up usages inside a JSNI block. It is easy to get your JavaScript wrong, introduce a memory leak and so forth.

What you're promised in return is performance. To test that I reimplemented the PrefixTree in pure Java, compiled it with GWT and compared the two implementations in a recent version of Firefox. I saw that the optimised method to calculate the possible suffixes for a given prefix was about four to six times faster than my reimplementation.

My simple test setup was to implement both versions using a small subset of about 2000 geographic names in the USA, run the same queries on both of the inputs and profile them using the build-in Firefox profiler.

The version without JSNI shown above spends about 20% of the overall runtime looking up suggestions in the trie. It also noteworthy that about 80% of the time is spent outside the prefix tree code.

Looking at the optimised version, the speed-up is striking but, at the same time, the ratio of tree lookup / time spent on things not related to the lookup is even more off-balance. The reason is to be found in the way the MultiWordSuggestOracle is implemented. As it is a multi-word suggest-box, it needs to map partial matches across word boundaries back to the original input strings (e.g. a query for "Mou" would match "Aquarius Mountains" etc.) It therefore keeps a separate copy of all "real" suggestions in a hash map. It then splits up the originals at the word boundaries and inserts them as a normalised, "fragmented" version of each suggestion into the tree. Looking up the original suggestions and sorting the final results takes about 50% of the time; the actual tree lookup amounts to only 4.5%.

Conclusion

I find it very rewarding to look at a piece of technology and to try to dig up layer after layer to understand its inner workings and the design decisions behind it. What I found in this case supports my general opinion about GWT in that there is a whole lot of cleverness and well thought-out solutions to be found under the hood: the right data structure with some well advised optimisations yields a convincing solution. But it has showed me again the ambiguity that comes with most optimisations. While the 5x performance gain justifies the use of JSNI, the component itself is only one small part in the greater context of the auto-suggest feature. In this bigger context the gain is much smaller and limited to the stock implementation that comes with GWT. While the PrefixTree and its optimisations are well isolated from other code by making the class package private, it also means you cannot reuse any of it easily in your auto-suggest implementation.

Logging Key Events on Mac OS X with JNA

In the previous post I introduced the APIs available in Mac OS X to get access to key events. The task was to write a small Eclipse plugin to log all keystrokes including hot-keys issued by the user while using the IDE. To my knowledge, this is not possible just using Java. The basic idea was to use JNA in order to call the native Objective-C APIs to log the key events.

Road Blocks

The first thing I tried was to write a simple call to Cocoa's NSEvent API (as outlined last time) via JNA. As a reminder, the goal was to implement this one-liner in JNA:

    [NSEvent addLocalMonitorForEventsMatchingMask:NSKeyDownMask 
                                          handler:
      ^NSEvent *(NSEvent * event) {
       /**
        * Here goes your logging...
        */
        return event;
    } ];

Easy, right?

Not quite so easy, as I had to find out. First it's Objective-C: You can't do it in JNA out of the box. As you may know, a message in Objective-C is sent to a class ( javaish: a static method is called ) like this:

   [classname messagename:argument]

The compiler translates this into something that could also be expressed as:

   Class cls = objc_getclass(classname);
   SEL selector = sel_registerName(messagename);
   objc_msgSend(cls, selector, argument);

It starts by looking up the class in the Objective-C runtime (l.1: objc_getclass). Then (l.2), sel_registerName registers a message name with the runtime. In our case, the message has already been registered (remember we are trying to call an existing API), so this function just returns the so called selector identifying the message. The last call actually tries to send the message to the class as the receiver.

This API exposes quite clearly the dynamic nature of Objective-C, which is based on message passing to receivers determined at runtime instead of just calling methods on entities defined at compile time.

You might wonder why these low-level functions are exposed in the Objective-C runtime at all. The reason is that they allow you to write all sorts of bridging layers between Objective-C and other languages. As a matter of fact, there used to be an Apple-provided Java-Objective-C bridge.

Well, not any more. Java on the desktop seems to be considered legacy technology by Apple. So we have to build all this by hand in JNA. Still no big deal, as we just need the three methods just mentioned out of the runtime API.

import com.sun.jna.Library;
import com.sun.jna.Native;

public interface ObjC extends Library {
 
 public static final ObjC INSTANCE = (ObjC) Native.loadLibrary("objc", ObjC.class);
 
 public void objc_msgSend(Object id, SEL theSelector, Object...objects);
 
 public Class objc_getClass(String name);
 
 public SEL sel_registerName(String str);

}

All there is left to do now is to call [NSEvent addLocalMonitorForEventsMatchingMask: handler:] from Java using the methods now available via JNA.

  ObjC objc = ObjC.INSTANCE;
  Class cls = objc.objc_getClass("NSEvent");
  objc.objc_msgSend(cls, objc.sel_registerName("addLocalMonitorForEventsMatchingMask:handler:"), mask.getMask(), block);  

Brilliant. Except it does not work. Why? Well, if you scroll to the very right in the code snippet—ignoring the mask.getMask() statement to define the event mask—you will notice that the last argument of the method is something I clumsily named block, because it's an Objective-C block acting as the callback when a key event is received. So surely this must work just like a function pointer, I thought. Not quite. Time to look at blocks in more detail.

Objective-C Blocks and JNA

Blocks are a C-level language feature built into the compilers that ship with Mac OS X since 10.6. They are closures capturing the enclosing lexical scope. So calling from Java you cannot just use com.sun.jna.Callback instead and pray that it works.

One of the reasons why this won't work is that you would pass in a function pointer where actually a pointer to a block literal would be expected.

A block literal is a C struct of the following form:

struct Block_literal_1 {
    void *isa; 
    int flags;
    int reserved; 
    void (*invoke)(void *, ...); //function pointer
    struct __block_descriptor_1 *descriptor;//omitted for brevity
    // imported variables go here
};

The important part for now is that it contains a pointer to a function with the logic you put into your block. You will find that this function pointer is located at offset 16 (assuming x86_64). The struct contains an isa pointer (8 bytes, so it's structurally also an Objective-C object!) and two integer fields (4 bytes each) followed by the function pointer.

If we then look at how the call of the block looks like in assembly we find another difference from a regular function pointer. We assume that a pointer to the block literal is stored in %rax and a pointer to the argument for the block (in our case an instance of NSEvent) is held on the stack at -32(%rbp). An invocation of the block could look like this:

0x100001452:  movq   %rax, %rdx //copy the block literal pointer to %rdx
0x100001455:  movq   -32(%rbp), %rsi //copy the argument to %rsi
0x100001459:  movq   %rdx, %rdi // copy the block literal pointer to %rdi
0x10000145c:  callq  *16(%rax) //call the function contained in the block literal (offset 16 remember)

The block function is thus invoked with the block literal as the implicit first argument and all other explicit arguments follow shifted by one place. In our case it's just the pointer to the NSEvent instance that comes in %rsi instead of %rdi as you would expect for a regular function call.

Even if you managed to get your function pointer in there, it would never be executed. The calling code expects the actual function pointer at *16(%rax) and it uses a different calling convention with the added block literal argument in the first position.

So in order to make this work from JNA, you would need to fabricate a structure isomorphic to the ones created by the compiler for Objective-C blocks and pass that instead. This would require a change to JNA itself.

Two Solutions

If you are free to choose your dependencies, you could just give up on JNA and use either JNI or give BridJ a try. BridJ seems relatively immature compared to JNA but it implements support for Objective-C blocks. It is actually done by creating an empty block as a template and then manipulating the function pointer inside the struct.

But I did not want to introduce another dependency just for the Mac OS version of the plugin or resort to JNI, consequently my solution was to implement a Quartz event tap using JNA. As explained in the last post, this is a low level C-API intended for the implementation of assistive devices and such. It works with JNA because it does not use blocks. If you are interested in the code it can be found here.

The Cost of Apache Commons HashCode

I had a discussion at work today about the cost of object creation in Java. It was about the way you are supposed to use Apache Commons HashCodeBuilder and EqualsBuilder creating a new object on every single call to hashcode() or equals():

@Override
public int hashCode(){
    return new HashCodeBuilder()
        .append(name)
        .append(length)
        .append(children)
        .toHashCode();
}

While I was pretty sure that the cost of creating these short lived objects on a modern JVM was pretty negligible in most use cases, I had no numbers to prove it.

Time for a biased benchmark of the simplest kind like the following:

package org.blogspot.pbrc.benchmarks;

import java.util.HashSet;
import java.util.Random;
import java.util.Set;

public class Runner {

 private static final int NUM_ELEMS = 100000;
 private static final int NUM_RUNS = 100;

 public static void main(String[] args) {
  String[] keys = createKeys();
  Integer[] numerics = createNumericValues();

  // priming the jvm
  for (int i = 0; i < 5; i++) {
   manualEqualsTest(i, keys, numerics);
   autoEqualsTest(i, keys, numerics);
  }

  long time = 0l;
  for (int i = 0; i < NUM_RUNS; i++) {
   time += manualEqualsTest(i, keys, numerics);
  }
  System.out.format("%s %.4fsecs\n", "Manual avg:",
    (time / Double.valueOf(NUM_RUNS)) / 1000000000.0);

  long autotime = 0l;
  for (int i = 0; i < NUM_RUNS; i++) {
   autotime += autoEqualsTest(i, keys, numerics);
  }
  System.out.format("%s %.4fsecs\n", "Apache commons avg:",
    (autotime / Double.valueOf(NUM_RUNS)) / 1000000000.0);

 }

 private static long autoEqualsTest(int runNumber, String[] keys,
   Integer[] numerics) {
  Set<CommonsEqualsAndHashcode> autoObjs = new HashSet<CommonsEqualsAndHashcode>(
    NUM_ELEMS);

  long start = System.nanoTime();
  for (int i = 0; i < NUM_ELEMS; i++) {
   autoObjs.add(new CommonsEqualsAndHashcode(keys[i], numerics[i]));
  }

  return System.nanoTime() - start;
 }

 private static long manualEqualsTest(int runNumber, String[] keys,
   Integer[] numerics) {
  Set<ManualEqualsAndHashCode> valueObjs = new HashSet<ManualEqualsAndHashCode>(
    NUM_ELEMS);
  long start = System.nanoTime();

  for (int i = 0; i < NUM_ELEMS; i++) {
   valueObjs.add(new ManualEqualsAndHashCode(keys[i], numerics[i]));
  }

  return System.nanoTime() - start;
 }

 private static Integer[] createNumericValues() {
  Integer[] result = new Integer[NUM_ELEMS];
  Random rand = new Random();
  for (int i = 0; i < NUM_ELEMS; i++) {
   result[i] = rand.nextInt();
  }
  return result;
 }

 private static String[] createKeys() {
  String[] result = new String[NUM_ELEMS];
  RandomString rand = new RandomString(32);
  for (int i = 0; i < NUM_ELEMS; i++) {
   result[i] = rand.nextString();
  }
  return result;
 }

}

I used two—otherwise identical—immutable value types: one with hand-crafted equals() and hashcode(), the other using Apache Commons HashCodeBuilder and EqualsBuilder.

package org.blogspot.pbrc.benchmarks;
public class ManualEqualsAndHashCode {

 public final String val;
 public final Integer numeric;

 public ManualEqualsAndHashCode(String val, Integer numeric) {
  this.val = val;
  this.numeric = numeric;

 }

 @Override
 public boolean equals(Object obj) {
  if (obj == this) {
   return true;
  }
  if (!(obj instanceof ManualEqualsAndHashCode)) {
   return false;
  }
  ManualEqualsAndHashCode other = (ManualEqualsAndHashCode) obj;
  return other.val.equals(this.val) && other.numeric.equals(this.numeric);
 }

 @Override
 public int hashCode() {
  int result = 17;
  result = 31 * result + val.hashCode();
  result = 31 * result + numeric;
  return result;
 }

}

I got the following results on a 2 GHz Intel Core 2 Duo with 4 GB 1067 MHz DDR3 running OS X 10.8.1 (12B19) with Java 1.7.06

Manual avg: 0.4052secs
Apache commons avg: 0.4508secs

In this particular scenario the overhead—when using the Apache Commons classes—amounts to about ten percent. Depending on where you're coming from, this might be a price worth paying. But, of course, this test scenario of just putting items into a collection is highly synthetic so your mileage may vary.

Now go and find more flaws in the benchmark!