Pilot Error and Java Autoboxing
Engineers are frequently rediscovering conceptual errors in their coding as they suffer to correct their code. I wanted to capture a mistake I recently made. I once again had a “pilot error” experience in that Java appeared to not work as expected. Just so you can enjoy my surprise, that one can still make a bone-head error after coding Java for 23 years, just follow along with the detective story. There are some short in-line code snippets to review, but no links to follow. As a hint in this detective story, my programming background was in C++ prior to Java.
The Detective Story
Recently, in the context of an interview question, I proposed sorting a collection of 32-bit unsigned integers (“bit strings”) to improve later searches. Sorting required creating a comparator to achieve unsigned Java Integer comparison because Java does not support unsigned numerical types. Java array and List instances store Integer values that are passed into the sorting comparator as parameters, and the comparator results are used to sort the list.
My Java Comparator seemed to oddly fail around testing the equality of some Integer instances, but succeed for other Integer instances, and succeeded for all other non-equality comparisons. Here is one such failure (the first example in my TDD approach.) We have set it up in a debugging example:
As you can see, the particular value (Integer.MIN_VALUE) did not correctly compare equal when referencing objects but did correctly compare when viewed as a primitive. To add to the mystery, the other comparison operators worked as expected. Here is an example of GREATER-THAN success (e.g. (x > y)):
Seeing that only equality testing was the problem, I expanded the list of test cases for equality beyond the single test value shown above, and found that EQUAL would consistently fail on all of these additional test values:
Again, we can see that both primitive equality comparison and comparison of extracted int values succeed, but object equality of Integer values fails. The next step was to do some research on object comparison.
I discovered a historic but not widely perceived behavior in the Java “autoboxing” mechanism when converting between the primitive int type and the object Integer wrapper. The autoboxing behavior should be more widely known because of the many potential situations in which it occurs. There were four Google references to autoboxing dating between 2011 and 2018, which I found using the search phrase “Java autoboxing errors”.
None of these references fully explained the behavior I saw, and some pointed to the use of the Integer.valueOf() method in autoboxing causing comparison issues. StackOverflow had additional discussions on the interaction between Integer instances and the Java “Constant Pool”. Still, I found no direct explanation for this specific problem. For illustration, here is an example of the interaction between the valueOf method and the Constant Pool and equality testing:
For Integer instance 127, equality compares correctly; but for Integer instance 128, it fails! So, the plot thickens. Autoboxing can cause unexpected differences in equality testing.
This comparison conundrum is also present in Java 9. I am working in Java 8 (for AWS), but there is an online version of Java 9 with JShell available for short tests. You may run the Java 9 JShell from https://tryjshell.org.) The results of this test are shown below:
Problem Summary
Here is what we have so far:
The Culprit Revealed
Do you think you have the solution? Remembering back to my early days learning Java, we learned that the “==” operator tests for instance identity and the object equals method tests for content equality. This differed from the C++ approach where the “==” operator was overridden to provide content equality.
For some integer constants, specifically in the range -127 <= x <= 127, Java caches them in the Constant Pool using the Integer.valueOf method. That means that for a small set of Integer instances, object content and object identity testing get the same results. All other comparison operators extract the value of the integer instance and then perform the comparison. Ah, so that explains it!
Luckily, Java has added an unsigned comparison method to Integer, I think beginning in Java 7, so writing a Comparator for unsigned is now easy. You just delegate to that method. It looks like "return Integer.compareUnsigned(lhs, rhs)". I will post a link to the Comparator in my GitHub repo.
Right . . . except Integer is final, so extension is not possible. One could create such a class and contain an Integer to provide part of the implementation. Unfortunately, the UnsignedInteger class would not be recognized by Autoboxing. So instead of writing: Integer x = y + z, where y and z are Integer, you would have to write something like: UnsignedInteger x = y.add(z).
Why wouldn't you implement a super class called UnsignedInteger that extends Integer?