Java int math blows...
A recent post by Google software developer Josh Bloch explains how a bug in the jdk went undetected for 9 years even after the perfectly good code was copied from John Bentley programming pearls.
mid = (low + high) / 2;
which for large values of low/high (as in huge collections) it would overflow and fail. Since we finally have huge machines and huges indexes, this gives Java math an opportunity to fail all over the place.
Turns out the Smalltalk binary search in my image has nearly identical code (gee, makes you think, did some Java programmer derive their class libraries from Smalltalk ? but I digress)... but I'll have you know that the Smalltalk version does not have the bug. It's simple, Smalltalk math works. Java math blows.
Lucy wanted some 'splaining ... so ...
If you have a language where a < b and (a+b)/2 is not greater or equal to a and less than b, then you're screwed by this kind of bug. The overflow is not caught and you are at the mercy of twos compliement math on ints. Boo hoo for you - you chose Java or C or many others... but if you chose Smalltalk ... smile and be happy - math works in Smalltalk. yes... I said works. It doesn't work in Java or C... (ok it works just not well).
Some sample code ...
package test;
public class BrokenMath {
public static void main(String[] args) {
testIntMath(1,100);
testIntMath(Integer.MAX_VALUE - 10, Integer.MAX_VALUE);
}
private static void testIntMath(int low, int high) {
int mid;
mid = (low+high)/2;
System.out.println ();
System.out.println ("Testing Low " + low + " high " + high);
System.out.println ("Is low < high ? " + (low < high));
System.out.println ("what is mid ? " + (mid));
System.out.println ("Is mid >= low ? " +(mid >= low));
System.out.println ("Is mid < high ? " +(mid < high));
if (!(mid >= low)) System.out.println ("Java int math blows");
if (!(mid < high)) System.out.println ("Java int math blows");
}
}
and you get something like this.
Testing Low 1 high 100
Is low < high ? true
what is mid ? 50
Is mid >= low ? true
Is mid < high ? true
Testing Low 2147483637 high 2147483647
Is low < high ? true
what is mid ? -6
Is mid >= low ? false
Is mid < high ? true
Java int math blows
in Smalltalk the equivalent ...
testLow: low high: high
| mid |
mid := (low + high) // 2.
Transcript cr.
Transcript cr; show: 'Testing Low ' , low printString , ' high ' , high printString.
Transcript cr; show: 'Is low < high ? ' , (low < high) printString.
Transcript cr; show: 'what is mid ? ' , mid printString.
Transcript cr; show: 'Is mid >= low ? ' ,(mid >= low) printString.
Transcript cr; show: 'Is mid < high ? ' ,(mid < high) printString.
(mid >= low) ifFalse: [ Transcript cr; show: 'Smalltalk int math blows'].
(mid < high) ifFalse: [ Transcript cr; show: 'Smalltalk int math blows']
"
self testLow: 1 high: 100.
self testLow: SmallInteger largest - 10 high: SmallInteger largest
"
Testing Low 1 high 100
Is low < high ? true
what is mid ? 50
Is mid >= low ? true
Is mid < high ? true
Testing Low 1073741813 high 1073741823
Is low < high ? true
what is mid ? 1073741818
Is mid >= low ? true
Is mid < high ? true
You see ! Smalltalk math works, Java math does not. Java blows at math.
And yeah, if you could catch the overflow (thank you C#) then you could detect this case but don't look for Java for help there either. It blows.
mid = (low + high) / 2;
which for large values of low/high (as in huge collections) it would overflow and fail. Since we finally have huge machines and huges indexes, this gives Java math an opportunity to fail all over the place.
Turns out the Smalltalk binary search in my image has nearly identical code (gee, makes you think, did some Java programmer derive their class libraries from Smalltalk ? but I digress)... but I'll have you know that the Smalltalk version does not have the bug. It's simple, Smalltalk math works. Java math blows.
Lucy wanted some 'splaining ... so ...
If you have a language where a < b and (a+b)/2 is not greater or equal to a and less than b, then you're screwed by this kind of bug. The overflow is not caught and you are at the mercy of twos compliement math on ints. Boo hoo for you - you chose Java or C or many others... but if you chose Smalltalk ... smile and be happy - math works in Smalltalk. yes... I said works. It doesn't work in Java or C... (ok it works just not well).
Some sample code ...
package test;
public class BrokenMath {
public static void main(String[] args) {
testIntMath(1,100);
testIntMath(Integer.MAX_VALUE - 10, Integer.MAX_VALUE);
}
private static void testIntMath(int low, int high) {
int mid;
mid = (low+high)/2;
System.out.println ();
System.out.println ("Testing Low " + low + " high " + high);
System.out.println ("Is low < high ? " + (low < high));
System.out.println ("what is mid ? " + (mid));
System.out.println ("Is mid >= low ? " +(mid >= low));
System.out.println ("Is mid < high ? " +(mid < high));
if (!(mid >= low)) System.out.println ("Java int math blows");
if (!(mid < high)) System.out.println ("Java int math blows");
}
}
and you get something like this.
Testing Low 1 high 100
Is low < high ? true
what is mid ? 50
Is mid >= low ? true
Is mid < high ? true
Testing Low 2147483637 high 2147483647
Is low < high ? true
what is mid ? -6
Is mid >= low ? false
Is mid < high ? true
Java int math blows
in Smalltalk the equivalent ...
testLow: low high: high
| mid |
mid := (low + high) // 2.
Transcript cr.
Transcript cr; show: 'Testing Low ' , low printString , ' high ' , high printString.
Transcript cr; show: 'Is low < high ? ' , (low < high) printString.
Transcript cr; show: 'what is mid ? ' , mid printString.
Transcript cr; show: 'Is mid >= low ? ' ,(mid >= low) printString.
Transcript cr; show: 'Is mid < high ? ' ,(mid < high) printString.
(mid >= low) ifFalse: [ Transcript cr; show: 'Smalltalk int math blows'].
(mid < high) ifFalse: [ Transcript cr; show: 'Smalltalk int math blows']
"
self testLow: 1 high: 100.
self testLow: SmallInteger largest - 10 high: SmallInteger largest
"
Testing Low 1 high 100
Is low < high ? true
what is mid ? 50
Is mid >= low ? true
Is mid < high ? true
Testing Low 1073741813 high 1073741823
Is low < high ? true
what is mid ? 1073741818
Is mid >= low ? true
Is mid < high ? true
You see ! Smalltalk math works, Java math does not. Java blows at math.
And yeah, if you could catch the overflow (thank you C#) then you could detect this case but don't look for Java for help there either. It blows.
posted by John Duimovich at 7:08 PM
3 Comments:
couldn't you just cast (a+b) to a type with enough precision to store the result?
java and c math don't blow, you just don't seem to like to work in the problem domain that java and c work well for, or you don't know how to express what you want with java or c, or both. both of which are valid complaints, mind, but there not the same as saying java int math blows.
Yes, you could cast but then you would be using 64 bit integers and performance would suffer (on some hardware). There are simpler solutions which work around this one specific issue and Josh's blog showed some of them.
Your comment "you just don't seem to like to work in the problem domain that java and c work well for" ... hmmmm ...
the specific use case which demonstrated the problem is not my code in *my* domain, it is code found in the Java class libraries themselves so apparently Java itself doesn't work well in it's own domain.
Of course, there are other things wrong with Java ints, including lack of unsigned which forces you to do unholy things if you need that extra bit for positive numbers that don't really need 64 bits and as I mentioned in the original blog entry, the lack of ability to detect overflow and act on it.
so, if it doesn't blow perhaps the opposite ?
what i'm saying is that i'm sure smalltalk, in the example, is just smart enough to cast to the larger type, and does so behind your back. if you want intermediate values constrained to the width of the operands you supply, for whatever reason, smalltalk would continue to do the "smart" thing behind your back.
so smalltalk is a slightly higher level language in this example. that doesn't make java math blow.
"so apparently Java itself doesn't work well in it's own domain."
:) not too well, no.
"Of course, there are other things wrong with Java ints, including lack of unsigned which forces you to do unholy things if you need that extra bit for positive numbers that don't really need 64 bits and as I mentioned in the original blog entry, the lack of ability to detect overflow and act on it."
no unsigned is silly, i agree.
but detecting overflow and acting on it, well the programmer can do that herself if she feels it necessary. to do it behind her back would just be pushing the language higher level, and making it more appropriate for a different set of problems.
which is all i was saying.
java int math doesn't blow, java just blows, for reasons far beyond a few supposed inconsistencies in its handling of integers. i'm sure everyone can agree with that.
Post a Comment
<< Home