David Walend's Blog

Performance Archives

Defending Autoboxing (or Save Us From the Preprocessor)

I want to solve a design problem using autoboxing and generics for JDigraph that I'll otherwise have to solve with a preprocessor, or Jython, or a compiler and ClassLoader hack that will basically repeat what the generics and autoboxing should do for me. I think autoboxing and generics will do the job, but won't know until I get a chance to read what the expert group has decided. I might even have to wait until the JSDK 1.5 betas are out to try it.

JDigraph's measured package has a collection of path optimization algorithms. Path optimization algorithms like Johnson's, Dijkstra's and Floyd-Warshall use a relax() procedure at their core. relax() compares the current cost to traverse between a "from" node and a "to" node to the cost of using a "through" node. The three indexes (fromIndex, throughIndex and toIndex) correspond with the nodes. safeLength() returns the lowest known cost to cross an edge between two nodes. Here's the the relax() method from AbstractShortestCEDistances.java.

    private int[][] distances;

    protected void relax(int fromIndex,int throughIndex,int toIndex) 
    {
        int fromThrough = safeLength(fromIndex,throughIndex); 
        if(fromThrough==Integer.MAX_VALUE)
        {
            return;
        }
        
        int throughTo = safeLength(throughIndex,toIndex); 
        if(throughTo==Integer.MAX_VALUE)
        {
            return;
        }
        
        int startLength = Integer.MAX_VALUE;
        
        int fromTo = safeLength(fromIndex,toIndex); 
        if(fromTo fromThrough+throughTo)
        {
            distances[fromIndex][toIndex]=fromThrough+throughTo;
        }
    }

Right now this code uses an int[][] for distances. I would like to use autoboxing and generics to easily switch this class from ints to doubles or other Number subclasses. A generic should generate a subclass of the parent class with the correct types, which would be very efficient. I'm hoping that autoboxing will let me keep the efficiency of primitive types while letting me access that flexibility. A profiling investigation showed that the algorithm spent most of its time assigning new distances in that last if block, so this method should be a good test of efficiency. It will be easy to measure once the JSDK 1.5 betas start to come out; I've got the timing study ready.

One alternative approach is to use a preprocessor to change the primitives. (And to rename the class so that the same ClassLoader context can use versions for different primitives). But to do that I'd have to guess what all the possible child classes of Number should be at build time. (Plus I'd need to do the same thing to my Heap for Dijkstra's algorithm. Plus all the interfaces involving path length would have to run through the same process to have the right APIs.)

A second alternative is to use string substitution, code generation, and a compiler at runtime to build the .class files I need at runtime. Defining the interfaces for these would be difficult; I'd still have to do some tricks at compile time. That work would repeat what the generics feature does already.

A third alternative is to write the code in Jython. But I expect this numeric-intensive code would be much slower. A disappointing implementation of autoboxing would run at Jython speed. (Like Erb says, "Wouldn't I be just as well off using Python?") However, it would work and I could speed it up when it's important.

I hope and expect that autoboxing will be efficient enough to let this work well, instead of just work.

SomnifugiJMS for User Interfaces and Simple-Enough APIs

I have trouble tracking all the issues in building a Swing interface: Swing's API has about a hundred top-level classes, each with a few dozen methods, plus nine subpackages, AWT, and Java2D to get things just right. Getting a group of people to all use MVC, JavaBeans and Threads the same way is hard. The model always has its own dynamics, and usually changes a few times a day. Add users unfamiliar with the new UI to make the project even harder.

The "Use Topics to communicate from the view to the controllers" pattern is a nice complement to the "Use SwingUtils.invokeLater() to communicate from the controllers to the view" pattern. Extending the pattern to place model handling in separate Threads is just a matter of adding extra Topics or Queues for the controller to consume. Plus if I need to make the application fit a client-server model, all I have to do is swap the model's Somnifugi JMS Topics for distributed JMS Topics.

I think the power in this pattern comes from breaking up the task into small, easy-to-grasp pieces.

Using a Topic to communicate from the view to the controller simplifies both by decoupling them. The view generates messages whenever any user action happens. The controller digests those messages. The JMS API is small and easy to learn and use. Using Topics simplifies performance decisions about handling Threads and shared Objects. The projects become more predictable, easier to decouple and test, and more pleasant to work on.

I think a lot of this gain is because a JMS Topic is easier to use than Java's threading support. The JMS specification is one of the best written specifications to come out of the JCP. The underlying ideas work without bending the universe to match. Each interface fills an outlined role and I don't have to do anything weird to my own code to use them. There's no requiring me to inheriting from someone else's superclass for example. (See Allen Holub's article, "The fragile base-class problem".) I needed a single afternoon to read the spec, and I understood without strain.

I spoke briefly with Joseph Fialli (one of the authors of the JMS spec) after he gave an invited talk (on JaxB) at a local user group. I described how I was using JMS behind Swing interfaces. He thought the pattern was pretty slick. He was the only person ever to compare it to InfoBus.* After the talk, I found my notes from reading the InfoBus spec in 1999. "InfoBus API looks more complex than just using the Thread API. We'd need to fill in most of the JavaBeans event spec. Not a good fit for our problem." Over the years, I've never seen a project that uses InfoBus, despite the hype it received in the late 90's. A JSR to update the InfoBus specification was started in 1998 but withdrawn in 1999. I think the InfoBus spec has been abandoned, but some ideas live on in the JavaBeans spec.

I think there's a strong correlation between simple APIs and how likely developers are to use those APIs. JMS survives and thrives because it meets a need that developers recognize with relatively little overhead. JMS exemplifies a "Simple-Enough Principle" for API design. Developers never adopted InfoBus in large numbers because we didn't think InfoBus was any better than what we had before.

Because all the code I write becomes library code, I try to keep this principle in mind when I define APIs. I want to create an API rich enough to do the job, but simple enough for another developer to be able to use without expanding the problem he's working on. Perhaps the advances in Aspect-Oriented code will reduce the typing overhead for JavaBeans to the point where developers can meet the specification. But that's a different blog.

* As I added mark up to this article, I got email from Ted Shab asking about Somnifugi JMS, "We are looking for InfoBus-like functionality, as well as some other related concepts."

This work is licensed under a Creative Commons License.