SortedList, now faster

Externally, Glazed Lists is all lists. No other ADTs - no heaps, trees or graphs - just lists. But internally, much is implemented using trees. For example, FilterList remembers which elements are filtered out using a custom AVL-tree called Barcode. SortedList maps indices using two instances of our custom IndexedTree class. And since version 1.6, ListEvents keep track of change blocks using yet another custom tree called BC2. Since each tree has different requirements we need different implementations:
  • FilterList's Barcode simply stores boolean 'filtered' or 'unfiltered' state and provides methods to convert between filtered and unfiltered indices.
  • SortedList's IndexedTree allows nodes to be inserted either by index or in sorted order using a comparator. Individual nodes in an otherwise sorted tree can be made unsorted in order to preserve the location of edited values.
  • ListEvent's BC2 Tree stores nodes in one of four states - inserted, updated, deleted and unchanged. In addition, it needs to offset between the 'before' tree and the 'after' tree. In the future we plan to store deleted elements in the nodes.

It's quite unpleasant to have 3 implementations of the same basic concept, especially since each is particularly complex. Plus, the different trees haven't been uniformly tested, optimized or even documented.

This problem has prompted me to spend the last week or so to unify our internal tree classes. The first step has been removing IndexedTree from SortedList, replacing it with an improved BC2 Tree. BC2 is our best and fastest tree but it needed sorting support to be used in SortedList. I added the required fields and logic and after some effort I had it working with SortedList.

But BC2 maintains state that SortedList doesn't need, which makes it slower than IndexedTree.

Since I'm sure Glazed Lists users wouldn't like to see a performance regression, I had a problem. Options:
  1. give up, go back to IndexedTree
  2. accept the performance regression
  3. cut and paste the class and strip out the unneeded fields

Yikes. I decided to go with a modified version of option 3. If I were to create a one-time copy of BC2, each time I fixed a bug or optimized something in BC2, I'd need to do it twice. Yuck. Instead, I annotated the source of BC2 using M4 macros to designate which fields and methods are not needed by IndexedTree. Then I can run a quick ant script and generate the 'light' version of whenever necessary*.

The result of all my hackery? SortedList is 5-10% faster than before.

* Why do the dynamic stuff at build time with hacks like M4 macros rather than runtime with elegant abstractions like interfaces? Interfaces are great but in this rare, performance-critical situation, the runtime cost of dynamic method invocation is a dealbreaker. I ran tests with Japex comparing both approaches, and even with Hotspot magic, the M4 solution is 20% faster.

Wanna download iTunes shared tracks? Get Git!

Get it TogetherIf you use iTunes streaming, you'll know how annoying it is that you can't download other user's tracks. Get It Together is a pretty simple Java app that solves this problem. If you've got two computers and you need to move music around, it's a great tool in a pinch. It works through Bonjour and DAAP, so there's absolutely no setup. It'll even work on Linux!

And the best part? Glazed Lists is inside.

Using m4 as a macro processor for Java, the nice way

For reasons I won't disclose, I've come to need a macro processor to generate a bunch of .java files. Somebody at work is using m4 for a similar task, so I decided to try it. Unfortunately, using macro processors with Java brings a huge problem - you typically cannot use an IDE like IntelliJ to edit the raw files. For example, this trivial macro program cannot be parsed by IntelliJ:
public class HelloNTimes {
public static void main(String[] args) {
forloop(`i', 1, HELLO_COUNT, `System.out.println("Hello i");

After running it through m4 (first adding the standard m4 forloop), the output is compilable:
public class HelloNTimes {
public static void main(String[] args) {
System.out.println("Hello 1");
System.out.println("Hello 2");
System.out.println("Hello 3");
System.out.println("Hello 4");

But I'd like to have my cake and eat it too. I'd like to be able to edit a .java file that is both well-formed and contains macros! To make this possible, I need alternate code for every piece of macro code that I write. This alternate code serves many purposes:
  • it allows me to reference symbols defined only by macros
  • it gives me something to verify the generated code against

    Including the alternate code, here's what the HelloNTimes app looks like:
    public class HelloNTimes {
    public static void main(String[] args) {
    forloop(`i', 1, HELLO_COUNT, `System.out.println("Hello i");
    END_M4_MACRO */

    System.out.println("Hello 1");
    System.out.println("Hello 2");

    As you can see, the 'alternate' section tells you what the macro could generate. Of course, if the parameters passed to the macro change (in this case HELLO_COUNT), the alternate will not equal what's generated. Due to the careful use of commenting, /* and */, this code will compile fine! That means I can edit this file just fine in my IDE.

    Then I add m4 definitions, to remove my markers when the file is processed:
    define(`END_M4_MACRO', `/'`* END M4 MACRO GENERATED CODE ')
    /'`* ')

    Finally I can see what the whole works generates. Note that it keeps the alternate code inside a comment, so I can verify that it's generating what I expect:
    public class HelloNTimes {
    public static void main(String[] args) {
    System.out.println("Hello 1");
    System.out.println("Hello 2");
    System.out.println("Hello 3");
    System.out.println("Hello 4");

    System.out.println("Hello 1");
    System.out.println("Hello 2");


    Note that the generated code has 4 hellos, wheras the alternate has only 2. This is because I'm running m4 with a parameter, -DHELLO_COUNT=4.

    Preprocessor code is inconvenient, but when I can edit in my IDE, it loses a lot of its pain! If you're interested, please look at the example HelloNTimes.jh source file, or my real-world usage in NodeN.
  • Fine grained events: for performance

    One critical difference between Glazed Lists' EventList and Swing's ListModel is that Glazed Lists uses fine-grained events and ListModel doesn't. What's the difference? First, lets compare the APIs:

    Method count313
    Granularity1 rangeUnlimited ranges
    Sample Event5-13 updated5-7 updated, 10-12 deleted, 13 inserted

    So fine-grained events are more detailed, but more complex as a consequence. What's the benefit?

    Suppose you're writing a World Cup app and have a List with 32 elements. To apply the score of a recent game, you simultaneously update Czech Republic (element 5) and USA (element 22). With fine grained events, the event object says just that: "5 updated, 22 updated". Without fine-grained events, a minimal spanning range is created, in this case "5 through 22 updated".
    Fine-grained events describe only what actually changed.

    When JTable receives the "5-22 updated" event, it must repaint the two changed rows plus the 16 rows in between, which are falsely reported as "updated". With the other event, it only needs to repaint two rows.
    Fine-grained events save repaints.

    Add sorting to the mix. So we'll need to re-sort the 18 'updated' elements. And although 5-22 was the minimum range before sorting, the sorter must fire a single event with that may span even more indices, perhaps '3-30 updated'. With fine-grained events, only the two impacted indices need to be re-sorted, so the sorter fires a concise event.
    Fine-grained events save sorts. Fine-grained events don't expand when indices are reordered..

    Now on to filtering. It's not hard to imagine that the change to the 'USA' element caused it to be filtered out of the user's view. To users of the filtered view, the change will look like Czech element was updated and the USA element was deleted. Unfortunately, loosely grained events cannot have a change containing both an update and a delete. What happens? Badness! TableModelEvent has a special state to cover these 'drastic' cases: "All rows changed". Among other things, this causes the entire table to be repainted.
    Fine-grained events can handle mixed-type events which occur naturally wherever filtering is used.

    So fine-grained events offer big performance benefits. This is particularly important with large datasets (think thousands) because the performance is perceptible to the user.

    JSR 295: the future of observable lists?

    JSR 295 will create a spec to bind plain old Java Objects to Swing components. Its a great idea which will increase productivity for Swing developers.

    Ultimately the spec will include bindings from java.util.List to components like JTable and JList. This tiny subproblem is what I've spent the last 3 years working on with Glazed Lists, and if done right it will make Glazed Lists mostly irrelevant.

    What I fear is that should JSR 295 be done wrong, it may still make Glazed Lists irrelevant! Therefore I think my best option is to embrace JSR 295, and hope that someday Glazed Lists will complement it rather than competing with it. This is the same approach as Hibernate+EJB 3.0 or util.concurrent+java.util.concurrent, albeit not nearly as high profile.

    Therefore over the next few months I plan to blog about Glazed Lists' design, with hopes of influencing development of the JSR. I'm going to get into low level API and implementation details, discussing both the strengths and weaknesses of our approach. Finally, note that I have offered to donate all or any of Glazed Lists source code to the project.

    Why there's no String.getCharset()

    With Java's String class, there's a 2 arg constructor that takes bytes and charsetName:
    byte[] characters = { 83, 87, 65, 78, 75, 46, 67, 65 };
    String myString = new String(characters, "ISO 8859-1");

    Symmetrically, you might expect this:
    byte[] theBytes = myString.getBytes();
    String theCharset = myString.getCharsetName()

    The second line doesn't compile because there's no getCharsetName() method on String.

    Why? Internally, Strings are always UTF-16, regardless of what charset was used to create them. The String(byte[],charset) constructor converts the bytes into UTF-16 characters using the charset as a guide.

    This turns out to be very handy:
  • Since all Strings use the same charset, there's no need to convert charsets when doing compareTo(), indexOf() or equals().
  • Once you have a String, you don't need to think about its character set! Charsets and encodings only matter when you're converting between byte[]s and Strings.

    Unfortunately, some code in an otherwise awesome project that misunderstands this concept has caused me some grief! Hopefully everything will be resolved soon.

    One cause of this problem is that Java developers have been trained to expect that constructor arguments will be used to initialize an object's properties. Perhaps instead of a constructor, Java's designers could have used a simple factory method to make the decoding action more explicit:
    public static String decodeBytes(byte[], charset)

    For a great overview of why character sets are the way they are, check out Joel Spolsky's article.
  • Tuning Java Performance? Think Japex

    Unit testing has spawned a new type of development, test driven development. In TDD, test coverage leads the way in development, and it's a great way to develop new functionality.

    Unfortunately performance tuning hasn't kept up with unit testing in terms of tools support and ubiquity. Usually when Java developers do performance tuning, it seems the strategy is generally ad-hoc and untargetted. I am certainly guilty of using this approach, and the code I've written suffers as a consequence. My ad-hoc approach is lame:
  • Write a main() method that exercises the code of interest
  • Sprinkle System.currentTimeMillis() calls throughout
  • Add extra code to warm-up HotSpot
  • Run the application, watching execution time getting printed to System.out
  • Cut and paste the execution time to a spreadsheet
  • Tweak the code of interest, randomly poking at things that look slow
  • Repeat the tests. If my change turns out to be slower, I check out the original implementation from CVS and redo the executions to confirm the data in the spreadsheet. Finally, I rollback the change.

    Japex GraphsBut there hasn't really been alternatives to this ad-hoc approach. Although tools like Netbeans Profiler and JProbe can analyze the performance of a single component, they're not good at comparing different implementations of the same component because they only work with one implementation at a time.

    Enter Japex. This fantastic tool is to performance testing what JUnit is to unit testing. Here's my new strategy, which is a much more efficient:
  • Create a Japex driver that exercises the code of interest
  • Refactor the API for the code of interest so I have one interface and N implementations. Each implementation uses a different strategy to accomplish the task
  • Edit a simple XML file to point to the driver and each of the implementations
  • Run Japex, a report with pretty bar charts is automatically saved (no spreadsheets!)
  • Tweak any implementation (or edit a copy) and re-execute Japex

    My code-compile-test cycle is now much faster. I'm able to try more things so I get a better understanding of the performance impact of each change. Just like how unit tests give me confidence to refactor, Japex gives me confidence to performance tune. Be sure to check it out, it's a worthy tool for your Java developer toolbox.
  • Canonical path of a file in Bash

    In Java, it's pretty straightfoward to take any abstract pathname (such as ~/Desktop/regina.jpg) and convert it to it's canonical pathname, /Users/jessewilson/Desktop/regina.jpg. Sometimes I find myself needing this function when writing simple shell scripts in Bash, and Google Groups showed me how.

    Save the following text to a file called canonicalize, add it to your $PATH, and chmod it so it's executable:
    cd -P -- "$(dirname -- "$1")" &&
    printf '%s\n' "$(pwd -P)/$(basename -- "$1")"

    Then you can use the location of a partial filename, even if you change directories:
    chixdiglinux:jessewilson$ canonicalize ./bash_profile
    chixdiglinux:jessewilson$ export JESSES_PROFILE=`canonicalize ./bash_profile`
    chixdiglinux:jessewilson$ cd ~kevinmaltby
    chixdiglinux:kevinmaltby$ diff $JESSES_PROFILE ./bash_profile