On 05/28/2010 03:24 AM, Kresten Krab Thorup wrote:
On May 27, 1:17 am, Per Bothner<[email protected]> wrote:
This is another example of where structs would be helpful. That would
allow:
struct Integer {
int ivalue;
int[] iwords;
}
....
Kawa basically does this using a regular class gnu.math.Integer,
and "small" Integers pre-allocated. That is one reason Kawa's
arbitrary-precision handling is (mostly) noticeably faster than BigInteger.
(Some of that could be achieved by further tweaking BigInteger.)
1: I'm intrigued. How much does this give you?
I don't have numbers convenient, but even with the current JVM (i.e.
no "struct" support) the big advantage is that in most cases you
don't allocate a "data" array, as long as the integer fits in 32 bits.
That same you a lot of memory and gc time. It means you have to explicitly
check for the immediate vs array modes (i.e. words==null or not), but
once determined you have a 32-bit number the actual work is quick,
and requires fewer memory accesses (and hence cache misses).
BigInteger could (and perhaps should) do the same optimization.
But BigInteger has a some further overheads, including some
seldomly-used fields.
I can see that you avoid a virtual call for all math operators where
you can determine the integer-ness of operands; so it does not have to
choose between SmallInt and BigInt objects. But it comes at the
overhead of an extra word per integer.
Right, but that is modest compared to the space used by BigInteger.
Integer arithmetic (most notably X+1, X-1, and X==<constant>) used in
loops is currently a noticeable performance issue in Erjang (when
comparing to the normal erlang implementation using tags). In many
such cases, I could avoid a virtual call and that does sound
appealing.
2: What is the motivation in Kawa to make your own bignum
implementation. Why not just have
class KawaInteger {
int ival;
BigInteger bval;
...
}
i.e., fall back on the standard bignum implementation?
That was not an option at the time: gnu.math.IntNum was implemented
before java.math.BigInteger was available. If I started from scratch
that would probably have made sense to do what you're suggesting. But
since the current implementation is faster and more space efficient
than using BigInteger I don't see much point in ripping it out.
You're free to use gnu.math.IntNum (and gnu.math in general); it has
no dependencies on the rest of Kawa.
--
--Per Bothner
[email protected] http://per.bothner.com/
--
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.
