David Walend's Blog

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.

Comments

• I suspect you'll be disappointed
  Obviously, I haven't seen the spec, either, but I suspect you'll be disappointed if you expect the same performance level as straight primitives.

  Autoboxing is merely going to convert between a primitive (e.g., int) and object (e.g., Integer) for you. That much we know is true; that's the definition of autoboxing. Beyond that, we can speculate, but I'd bet my first edition Duke Beanie-Baby* that this is the way it'll work: The compiler will insert the appropriate new Integer() and intValue() calls (or the appropriate calls for long, float, double, etc.) automatically, saving you only the trouble of writing that code yourself. This is reasonable speculation, both when you consider how this could be implemented, and Sun's stated goal of addressing the ease of coding and readability. Nowhere in the public information is performancea stated goal.

  "I hope...that developers will use the same care they show with Strings"

  That's precisely my worry, and a perfect analogy for how this has the potential to create performance problems that slip under the radar, because it makes the object creation so hidden. Consider String concatenation; many developers won't realize all the temporary StringBuffer and String objects being created and garbage collected.

  * I have no Duke Beanie-Baby, first edition or otherwise. But if I did, I'd be willing to put him on the line.

  Posted by: jimothy on September 18, 2003 at 07:29 AM

• Boxing slow and wasteful???
  Combine Autoboxing with type inferencing that HotSpot uses and I think you'll be suprised. For years people said that Lisp and Smalltalk were slow in numeric operations, but many times they were shown to be wrong, b/c the compilier could inference the optimal type and useage and then optimize the code.

  It is my belief that these same things will be or can be applied to the new Autoboxing features of Java.

  It's funny, Java being byte-coded, etc. and in many, many situations, that type information doesn't give the solutions any more speed than Smalltalk programmers get with no types being specified at all.

  Posted by: staypufd on September 18, 2003 at 01:21 PM

• Not what you want
  You are not going to get what you are looking for.

  The JSR-014 generics do not "generate a subclass of the parent class with the correct types". There is only one implementation of each generic class, and that implementation serves for all generic instances by using ordinary polymorphism. Furthermore, when using a generic class, the actual type of the generic parameter cannot be a primitive, so it cannot be an int or a double.

  Java genericity is a compile-time feature that provides additional type-safety and coding convenience. It does NOT provide any additional run-time abilities.

  Similarly, I do not see that autoboxing will buy you anything. Like jimothy said, it's just saving you the effort of writing "new Integer(x)". It's nice for making the source code cleaner and easier to read (especially for method arguments), but again, it does not give you any new abilities.

  Posted by: dougpardee on September 18, 2003 at 02:40 PM

• Shortcut to ...
  I think the autoboxing feature comes only to implement the new 'printf' feature (almost-C-like variable parameter list):

  C's printf (String s, ...) == J's printf (String s, Object[] params)

  then:

  int age = 20;
  printf ("%s is %d years old", { "Jack", 20 } ); //new shortcut syntax to new Object[]

  instead of

  printf ("%s is %d years old", { "Jack", new Integer(20) } );

  Autoboxing sux, and brings even more danger of hidding performance bottlenecks than Strings.

  Moreover, only autoboxing will be supported, not autounboxing, causing the code to handle the same value in different ways. Imagine:

  int a = 2;
  ArrayList list = new ArrayList();
  list.add(a); //add as int
  a = list.get(0); //error
  a = (int) list.get(0); //error
  a = (Integer) list.get(0); //error
  a = ((Integer) list.get(0)).intValue(); //get as Integer, cast and get int value

  or, with generics,
  int a = 2;
  ArrayList list = new ArrayList();
  list.add(a);
  a = list.get(0); //error
  a = list.get(0).intValue(); //get as Integer, and then get int value

  This is the only code to change:
  list.add(a); -> list.add(new Integer(a));
  

  Posted by: ronaldtm on September 19, 2003 at 08:53 AM

• I suspect you'll be disappointed
  Profiler. Profiler. Profiler. Performance only matters in small areas of the system and only after you know that you have a problem. If I can make my code more understandable and less cluttered in 90% of the application for a 20% increase in performance debug time, I will do it in a nanosecond.

  It brings back the original debate on Java versus compiled languages. ?It is slower?, went the chant of compiled people. It only matters if the user noticed and it is impossible to fix easily. Outside of the UI, that has not been the case for Java, nor will it be the case for autoboxing.
  

  Posted by: gjhicks12 on September 21, 2003 at 03:04 PM

• I suspect you'll be disappointed
  You're absolutely right that diligent use of a profile will help spot performance problems, and that there is a trade off in performance versus readability.

  However, you can, with some degree of reliability, predict performance hotspots. David may know in advanced that his path-finding algorithm will be frequently called, so performance is vital. Granted, a profile can and should be used to verify any assumptions.

  More importantly, things can be broken while performance tuning, and tuning itself takes development time. There are good habits that developers can learn, such as using StringBuffer in a loop, so they can write effecient code from the beginning, lessening the need to go back and optimize. I suspect we'll add a few points regarding autoboxing to that set of habits.

  Posted by: jimothy on September 22, 2003 at 09:46 AM

• Autoboxing + Generics
  Autoboxing is IMHO utter crap. It won't be efficient and will cause more problems. The only improvement will be on code appearance, since it is "cool" to write code like:

  int i = 1;
  list.add(i);

  Generics, again IMHO, is a no-good feature. Why would you need generics when you have good-old polymorphism?

  Besides, my guess is generics support for Java will merely be automatically generating the necessary type casts...

  Vagelis.

  Posted by: vgiannadakis on September 24, 2003 at 03:45 AM

• Will report when the jsdk 1.5 betas are out
  I've thought a while about how to respond to the talk back on this article. I'd like to say I think most of the talk back is too pessimistic. But I don't know yet.

  I think the best answer I can come up with is this: When Sun starts shipping the betas for JSDK 1.5, I'll try out using autoboxing and generics in the JDigraph's Floyd-Warshall implementation, see how far I can take the language, and do a performance study. It's open source, so you'll all be able to see what I'm doing in the study. I'll report my results in a blog entry so we can have answers instead of speculation.

  Dave

  Posted by: dwalend on September 26, 2003 at 08:53 AM

This work is licensed under a Creative Commons License.