Joseph D. Darcy's Sun Weblog

Thursday February 08, 2007

Boxing and Caches: Integer.valueOf(int) and friends

Recently, various folks have been discussing some code I wrote for the wrapper classes, java.lang.Integer and friends, back around March 2004 as part of JDK 5 beta 2:

private static class IntegerCache {
    private IntegerCache(){}

    static final Integer cache[] = new Integer[-(-128) + 127 + 1];

    static {
        for(int i = 0; i < cache.length; i++)
            cache[i] = new Integer(i - 128);
    }
}

public static Integer valueOf(int i) {
    final int offset = 128;
    if (i >= -128 && i <= 127) { // must cache 
        return IntegerCache.cache[i + offset];
    }
    return new Integer(i);
}

As correctly inferred, this caching code was added to support the object identity semantics of autoboxing for values between -128 and 127 (inclusive), as required by the language specification. Since the same object must be returned for integral values in this range, once the autoboxed value for, say, 0 is created, it must be retained until the virtual machine exits. That leaves the issue of whether or not the values in question are created eagerly or lazily and whether or not any container for those values is created eagerly or lazily.

The code above lazily creates the container object, but eagerly populates the object when it is created. This avoids having to use any synchronization when the elements are accessed. Of the three practical potential lazy-eager combinations, initially I planned to use the dual approach, eagerly creating an AtomicReferenceArray<Integer> container and then lazily populating this using compare and set. As I recall, Neal was first to suggest I use the initialize-on-demand holder class idiom to get lazy creation of the container object without synchronization. Further feedback from Josh and Doug Lea led to lazily allocating the plain array of Integer to be populated eagerly.

One reason I used the literal values "-128" and "127" in the code above is that those are the numbers given the specification and it is clear what they mean when used in the comparisons. Another code reviewer offered

if ((byte)i == i) {...} 

paired with IntegerCache.cache[((byte)x) & 0xff] to index into the array (using a different order) as an alternative to

if (i >= -128 && i <= 127) {...}

and IntegerCache.cache[i + offset]. The former approach does merit points for conciseness and cleverness, but it is more obscure and didn't run any faster in some quick micro-benchmarking so the more straightforward code remained.

Benchmarking this kind of caching code is difficult because what combination of lazy and eager allocation works best will be very dependent on the imposed workload. Therefore, something that always performs reasonably well is in some sense more robust than an algorithm that is really fast is some circumstances but much slower in others. In any case, I second the recommendation to use Integer.valueOf(foo) instead of new Integer(foo) since Integer.valueOf(foo) has the potential to use yet-to-be-developed fancy caching strategies while the constructor must always return a new object and object identity is rarely important for wrapper objects. Following Item 1 in Effective Java, if the wrapper classes could be redesigned, I would be inclined to remove the public constructors altogether and only provide factory methods.