|
To address performance problems in the JDK 1.1 BigInteger class, Lou implemented mInts-his own "monster" integer library. The main difference between Lou's mInts and BigInteger is that BigInteger offers arbitrary precision, while Lou's library provides signed integers fixed at 256 bits.
November 01, 1997
URL:http://www.drdobbs.com/jvm/extended-precision-native-integers-for-j/184410316
Lou is the author of Zen of Windows 95 Programming (Coriolis Group, 1996). He can be contacted at [email protected].
To address performance problems in the JDK 1.1's BigInteger class, I implemented mInt, my own "monster" integer library. The main difference between Sun's implementation and mine is that BigInteger offers arbitrary precision, meaning the representation of a number is adjusted as needed. For example, if the result of adding two numbers won't fit in an integer the same size as that of the operands, the result is created with additional precision, and no overflow or underflow errors are possible. My library, however, provides signed integers fixed at 256 bits. Even though this is "only" four times the number of bits in the Java primitive type long, it still yields 77 decimal digits -- more than enough for most applications.
A subtler difference between the implementations is that Sun represents the number as a series of bytes that are logically combined to form one huge binary integer. My library represents each mInt as an array of 4-byte integers, which are also treated as parts of a single integer. This approach simplifies some parts of the implementation and lets the code operate on 32 (instead of 8) bits at a time.
The mInt library is a 32-bit Windows DLL built from a single source file, MINT.C (available electronically; see "Availability," page 3). MINT.DLL supports the four basic arithmetic functions, conversions from binary to ASCII (both decimal and hex) and decimal string to binary, and some bit-wise operations, including shifting left and right. From a Java point of view, the native methods are nontraditional in two respects -- immutability and use of exceptions.
Immutability is a trait that drives Java novices crazy. Trained by years of passing variables by reference to subroutines, many programmers inevitably want to modify a String or Integer object passed to a method, and find that they can't. These classes, like others in the standard Java libraries, are immutable, meaning there's no way to change an instance of them. Once the object is created, you have to replace it wholesale with a new instance with the desired value. This is done largely to provide safety in multithreaded environments. mInt is not immutable; when you add mInt Y to mInt X with the statement X.Add(Y), the result is stored in X, replacing its original value. I did this for performance reasons, since making a numeric class immutable can lead to many object instantiations and place a burden on the garbage collector when performing complex, iterative calculations. Also, I reasoned that mInts will be "specialty classes" used heavily in one area of a program for a calculation that can't be performed with Java's primitive types, and can be easily isolated from threading issues. If you require immutable mInts, it's a straightforward code conversion. I've implemented the Add() method several ways to demonstrate different techniques, including one variation (test2Add()) that shows how to make a native method immutable friendly. (Of course, you'll also have to remove the methods that modify the value of an existing mInt, such as SetFromInt32().)
I didn't use exceptions, preferring instead to use a Windows API-like convention. mInt methods return a Boolean True for success and False for failure, with a specific error code available that contains the last nonzero error code set. The last error code is a static variable, meaning one instance is global to the entire class. Also note that it is not reset by a successful operation. Methods are provided to get, set, get and set, and get and clear the last error value. This design decision is less defensible than the immutability one, and is largely a matter of personal taste. But again, my code can easily be made exceptional, so to speak, and I've provided the test3Add() method in mInt.java (see Listing One) that shows how to do this by wrapping the pedestrian Add() method. You can use this technique to provide both forms of methods in the same class with little performance impact and without code duplication.
Most of the mInt library uses a split implementation, with the real work being done on unsigned versions of mInts in separate subroutines. I find this organization easier to manage because it separates the Java-to-C interface details from the code that does the actual work.
The Add(), Subtract(), conversion, and bitwise operations are straightforward, even though some are implemented in C, and some in Java. (I left the logical operations in Java for the sake of variety; if you need higher-performing versions, they can be ported to C, using the Add() implementation as an example.) Multiplication is also straightforward -- the algorithm merely does a binary version of the manual multiplication method we all learned in grade school, shifting the cumulative result and adding one input to it as needed.
Division is more complicated, requiring you to preshift the denominator until it is as large as possible without making it exceed the value of the numerator. You then build the quotient by setting its low-order bit when the numerator is greater than the denominator, subtracting the denominator from the numerator, then always shifting the denominator right and quotient left. (Describing his algorithm is like trying to describe a spiral staircase without using your hands. Examine the loop in the UDivide() function in MINT.C, and it should make sense.) Because of Java's inability to return more than one output from a function (and because people rarely use both the quotient and remainder from an integer division), I decided to make Divide() and Remainder() separate methods. This could be changed by creating a new class with two mInt members, quotient and remainder, and have a new Divide() method return an instance of this class.
There's almost no detection and handling of special cases in the library. Once you speed up addition, subtraction, and shifting left multiple bits, there's little reason to implement the usual strength-reduction optimizations. For example, an early version of the library did things like detect division by a power of two, then shift one argument to the right the proper number of bits. It turned out that the performance gain for this type of optimization was minimal, and it added overhead to all ordinary operations. (For more on optimization, particularly as related to JNI, see the accompanying text box entitled "Sheng's Optimization Trick.")
If you want to expand or change the mInt library, it's easily rebuilt. First, if you make any changes to the portions of mInt.java that define native methods, you must compile that file with javac, then regenerate the C header, MINT.H (available electronically), with the command javah -jni mint.
Next, make the necessary changes to the C code, rebuild the DLL, and you're done. Obviously, if your changes are local to the C file, such as implementing a new algorithm for an existing method or function, then you can simply rebuild the DLL without changing the .java file or regenerating the header.
// mInt library copyright (c) 1997 Lou Grinzo
import java.lang.System;
class mIntError extends Exception
{
private int last_error;
mIntError(int le) { last_error = le; };
int GetLastError() { return last_error; }
}
class mInt
{
private static final int num_components = 8;
private int the_int[] = new int[num_components];
private static int last_error = 0;
public static final int mInt_OK = 0;
public static final int mInt_overflow = 1;
public static final int mInt_underflow = 2;
public static final int mInt_divide_by_zero = 3;
public static final int mInt_invalid_char = 4;
// Load the native methods and cache fieldIDs for last_error and the_int
static
{
System.loadLibrary("mInt");
cacheFID();
}
static private native void cacheFID();
// Constructors of various flavors //////////////////////
// See the called Set* methods for more details
mInt(int x0, int x1, int x2, int x3, int x4, int x5,
int x6, int x7)
{ Set(x0,x1,x2,x3,x4,x5,x6,x7); }
mInt(int x)
{ SetFromInt32(x); }
mInt(mInt x)
{ SetFrommInt(x); }
mInt(String s)
{ SetFromString(s); }
// Accessors and converters /////////////////////////////
public int[] GetInts()
{
int[] x = new int[num_components];
System.arraycopy(the_int,0,x,0,num_components);
return x;
}
// Treat the ints as hex components of a huge signed integer
public void Set(int x0, int x1, int x2, int x3, int x4,
int x5, int x6, int x7)
{
the_int[0] = x0; the_int[1] = x1;
the_int[2] = x2; the_int[3] = x3;
the_int[4] = x4; the_int[5] = x5;
the_int[6] = x6; the_int[7] = x7;
}
// Set the low-order int32 and sign-extend
public void SetFromInt32(int x)
{
the_int[num_components - 1] = x;
int temp = 0;
if(x < 0)
temp = -1;
for(int i = 0; i < num_components - 1; i++)
the_int[i] = temp;
}
// Simply copy the entire the_int array
public void SetFrommInt(mInt x)
{
System.arraycopy(x.the_int,0,the_int,0,num_components);
}
public native int SetFromString(String s);
public native String HexString();
public native String toString();
// Math methods /////////////////////////////////////////
public void Abs()
{
if(the_int[0] < 0)
Negate();
}
public native boolean Add(mInt y);
public boolean AddInt32(int x)
{ return Add(new mInt(x)); }
// Demos non-cached field access
public native boolean testAdd(mInt y);
// Demos object creation
public native mInt test2Add(mInt y);
// Wrap the primitive Add() to use exception
public void test3Add(mInt y) throws mIntError
{
if(!Add(y))
throw new mIntError(GetAndClearLastError());
}
public native boolean Subtract(mInt y);
public boolean SubtractInt32(int x)
{ return Subtract(new mInt(x)); }
public native boolean Multiply(mInt y);
public boolean MultiplyInt32(int x)
{ return Multiply(new mInt(x)); }
public native boolean Divide(mInt y);
public boolean DivideInt32(int x)
{ return Divide(new mInt(x)); }
public native boolean Remainder(mInt y);
public boolean RemainderInt32(int x)
{ return Remainder(new mInt(x)); }
// Compare two mInts, returning -1, 0, or 1 if
// this is <, ==, or > x, like common C usage
public native int Comp(mInt x);
public mInt Max(mInt x, mInt y)
{
if(x.Comp(y) >= 0)
return new mInt(x);
else
return new mInt(y);
}
public mInt Min(mInt x, mInt y)
{
if(x.Comp(y) <= 0)
return new mInt(x);
else
return new mInt(y);
}
// Bit twiddlers ////////////////////////////////////////
public native void Negate();
public native boolean ShiftLeft();
public native void ShiftRight();
public void AND(mInt x)
{
for(int i = 0; i < num_components; i++)
the_int[i] &= x.the_int[i];
}
public void OR(mInt x)
{
for(int i = 0; i < num_components; i++)
the_int[i] |= x.the_int[i];
}
public void NOT()
{
for(int i = 0; i < num_components; i++)
the_int[i] = ~the_int[i];
}
public void XOR(mInt x)
{
for(int i = 0; i < num_components; i++)
the_int[i] ^= x.the_int[i];
}
// Error detection methods //////////////////////////////
int GetLastError()
{ return last_error; }
int GetAndClearLastError()
{
int temp = last_error;
last_error = mInt_OK;
return temp;
}
int GetAndSetLastError(int x)
{
int temp = last_error;
last_error = x;
return temp;
}
void SetLastError(int new_last_error)
{ last_error = new_last_error; }
}
DDJ
Dr. Dobb's Journal November 1997
Accessing an object's field via the JNI typically requires a sequence of four API calls. In my first attempt to access the array of integers that hold the value of a mInt, the last call, GetIntArrayElements(), failed. After some debugging, I knew the first three calls were succeeding, so why was GetIntArrayElements() failing with a "JNI scalar array element type mismatch" error? Sun's Sheng Liang answered the question, showing me an error in the third call after all. That call, GetObjectField(), requires the object's handle as its second parameter, and I was accidentally passing a class handle. Instead of detecting that an incorrect type of handle was being passed, the JVM used it and returned a wildly wrong value, which I used as input to the fourth call, making it fail.
While JNI is an improvement over NMI, it still has some problems: It doesn't typecheck handles on JNI calls, so the JVM is prone to the same kind of API errors that plagued Windows programs in the past.
The performance trick Sheng showed me is simple: You can do the first two calls of this infamous four-call sequence once (when the native library is loaded), and cache the output of the second call, which is the fieldID of the field in question (see the cacheFID() call in Listing One). Then, perform calls three and four of the sequence in each method. (You really only need one call in cacheFID(): A static code member gets the class's handle as a parameter, so you don't need an explicit call to retrieve it.) You can safely cache and reuse this value because the fieldID for a given class and field never changes for any instance of that class. The second call in the sequence, GetFieldID(), is expensive, so caching it more than doubles the performance of the Add() method from 25,000 to 55,555 operations per second on a 133-MHz Pentium under Windows 95 using the JVM from Sun's JDK 1.1.1. If you want to run your own tests, you can run AddTime.java (also available electronically), which compares calling the methods Add() and testAdd(). testAdd() is simply a noncached version of Add().
-- L.G.
Terms of Service | Privacy Statement | Copyright © 2024 UBM Tech, All rights reserved.