sixlegs.com / blog / java / cglib-stringswitch.html

Root Beer Logo Root Beer

Chris Nokleberg's Fizzy Weblog

June 2003
Su M Tu W Th F Sa
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 19 20 21
22 23 24 25 26 27
29 30
Previous  |  Next  |  More...
#  Switching on Strings

Inspired in part by Cameron's stringswitch blogs from awhile ago, I've implemented something similar as a virtual opcode in CGLIB.

It transforms this imaginary code:

switch (arg) {
case "at":  /* a */
case "bar": /* b */
case "baz": /* c */
}

Into the following:

switch (arg.length()) {
case 2:
  switch (arg.charAt(0)) {
  case 'a':
    switch (arg.charAt(1)) {
    case 't':
      /* a */
    }
  }
case 3:
  switch (arg.charAt(0)) {
  case 'b':
    switch (arg.charAt(1)) {
    case 'a':
      switch (arg.charAt(2)) {
      case 'r':
        /* b */
      case 'z':
        /* c */
      }
    }
  }
}

This is basically a "trie" hard-coded into bytecode, where each branch of the tree is embodied by a switch statement on the next letter of the argument. Because the entire length of the string is traversed this way, it is never necessary to call equals.

In the JVM a switch is implemented using one of two opcodes, tableswitch and lookupswitch. The latter is best for sparse switch values, but is slower (binary search instead of an array lookup). I believe javac chooses which one to use based on which would generate less bytecode. In CGLIB I've made it choose tableswitch whenever the range of switches (max - min) is at least half full. This should be faster, but wastes a bit more space.

The first switch on the length of the argument is so that we do not have to catch out-of-bounds exceptions when getting a character past the end of the string. The disadvantage of this is if you were switching on two strings of different length, but with a common prefix (e.g. "foo" and "fool"), you cannot share the common branches, and the size of the generated method grows.

I plan to implement a similar switch for Yooster, an API around UTF-8 encoded byte arrays. I expect it to be faster for these reasons:

  • Transparent access to the actual bytes, i.e. no need to call charAt for each branch.
  • The case values will be bytes instead of characters, which makes it feasible to use tableswitch more often, without blowing out the code size.
  • The byte array is null-terminated, which means the initial switch on string length can go away, and the trees for strings of different lengths can be merged.

"So what is this good for?" It's not an unreasonable question, since most people want string switching as a language-level construct, and this is all being done at the bytecode level. The first use I've made of it is to implement a BeanMap, which presents any JavaBean as a java.util.Map. This is functionally similar to the Jakarta Commons Collections version. The difference is that the Jakarta one uses the argument key to lookup a java.lang.reflect.Method object from a hash table, and then uses reflection to get/set the bean property. The CGLIB version switches on the set of property names (known at compile time), and hard-codes the method invocations within the branches of the switch.

Here is a comparison of the running times between net.sf.cglib.BeanMap (in CVS) and org.apache.commons.collections.BeanMap. 500,000 iterations each, all times in milliseconds. The "primitive" times are slower because a Map only takes Objects, so an int needs to be converted to and from an Integer.

 Jakarta   CGLIB 
Get object 322 46
Get primitive 404 70
Set object 1272 44
Set primitive 20612 74

[Powered By FreeMarker]  [Valid Atom 1.0]  [Weblog Commenting by HaloScan.com]