On Fri, Jun 4, 2010 at 3:04 AM, John Cowan <[email protected]> wrote:
> I actually tested Integers (with autoboxing) against BigIntegers on a
> 32-bit system (I don't have a 64-bit system at present), and I made
> sure that the arithmetic operations I was performing never overflowed
> 32 bits. The additional cost of using BigIntegers was between 2x and
> 3x, which I assume is the joint cost of:
>
> 1) overflow tests that fail;
>
> 2) the additional indirection: an Integer contains an int, whereas a
> BigInteger contains an array with one int.
>
> That seems to me small compared to having to handle two integer
> representations, with special provisions for mixed mode and so on.
Well dealing with the two isn't that big a deal; if the overflow check
fails, we just construct the BigInteger version and do the math again.
That's essentially the same logic you'd have to do with any
split-brain arbitrary-precision integer implementation. Of course
you're talking about whether just using BigInteger to begin with would
be faster.
Looking at size, if we're talking about Long it's object + long field.
We can ignore the object since that's the same for BigInteger, and
then the additional size is just 8 bytes. For BigInteger, it's object
+ int + int[] + (the remaining all deprecated, but *still there) four
more ints = 24-28 bytes, and can only represent up to 32-bit values
before adding the array, which is something like 8-12 bytes for the
header and then 4 bytes for each entry. So in terms of allocation
alone, BigInteger is several times larger than Long.
The overflow check is nontrivial. Here's the opto assembly for it (no
inlining, full method body, so some of this would disappear when
inlined):
000 B1: # B4 B2 <- BLOCK HEAD IS JUNK Freq: 1
000 PUSHL EBP
SUB ESP,8 # Create frame
007 MOV ECX,[ESP + #24]
MOV EBX,[ESP + #28]
00f XOR ECX.lo,[ESP + #16]
XOR ECX.hi,[ESP + #16]+4
017 MOV EBP,[ESP + #32]
MOV EDI,[ESP + #36]
01f XOR EBP.lo,[ESP + #16]
XOR EBP.hi,[ESP + #16]+4
027 AND ECX.lo,EBP.lo
AND ECX.hi,EBP.hi
02b AND ECX.lo,#-9223372036854775808.lo
AND ECX.hi,#-9223372036854775808.hi
034 MOV EDI,ECX.lo
OR EDI,ECX.hi ! Long is EQ/NE 0?
038 Jne,s B4 P=0.000000 C=19097.000000
038
03a B2: # B3 <- B1 Freq: 1
03a XOR EAX,EAX
03c
03c B3: # N1 <- B2 B4 Freq: 1
03c ADD ESP,8 # Destroy frame
POPL EBP
TEST PollPage,EAX ! Poll Safepoint
046 RET
046
047 B4: # B3 <- B1 Freq: 4.76837e-07
047 MOV EAX,#1
04c JMP,s B3
04c
This from the following code:
private static boolean subtractionOverflowed(long original, long
other, long result) {
return (~(original ^ ~other) & (original ^ result) & SIGN_BIT) != 0;
}
So I guess the question comes down to whether this overflow check plus
the associated branching logic is less costly than always using
BigInteger and paying the allocation costs (not to mention whatever
internal costs it has versus doing "long op long", even if you have to
unbox and box on the way in and out.
In JRuby, RubyFixnum has that long field plus an int flags field and a
reference to metaclass, for an additional 8-12 bytes. Narrows the gap
a bit.
I wasn't able to get +PrintAssembly to work (see my other email) so I
wasn't able to see how 32 and 64-bit Hotspot eventually assembles the
above opto assembly. It may be even tighter.
- Charlie
--
You received this message because you are subscribed to the Google Groups "JVM
Languages" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/jvm-languages?hl=en.
