LibJ Math

$Build Status$

Introduction

LibJ Math is an extension to the java.math Java API. The classes in LibJ Math can be split in two categories:

Higher-performance alternatives to functionalities present in java.math.
Supplementary functionalities missing in java.math.

Higher-performance alternatives

`BigInt`

Introduction

An arbitrary-precision integer replacement for java.math.BigInteger, with the following differences:

Mutable: BigInt is mutable, allowing for reuse of allocated magnitude arrays.
Little-endian: BigInt's magnitude array is in little-endian order, allowing for faster operations concerning changes to a number's scale.
Faster arithmetic: The arithmetic algorithms in BigInt are implemented with the optimization of memory (heap allocation) and runtime performance in mind.
Faster multiplication of large numbers: Support parallel multiplication algorithm for large numbers.
In-place multiplication algorithms: Employs optimized algorithms that perform calculations in place, rather than instantiating transient magnitude arrays to defer to the GC to free later.
Support for int and long parameters and return types: BigInt does not require its parameters or return types to be BigInt, avoiding unnecessary instantiation of transient BigInt objects and int[] arrays.
Support for "object-less" operation: All methods in BigInt are available in static form, allowing bare int[] value-encoded number arrays to be used without a BigInt instance, leading to further reduction in heap memory allocation.
Significantly reduced heap allocation: BigInt was designed to reduce the number of instances allocated purely for the purpose of transient calculation, and significantly outperforms BigInteger with regard to memory and GC load.
No preemptive exception checking: BigInt does not preemptively check for exceptions. If a programmer divides by zero he has only himself to blame. And, it is ok to have undefined behavior.
Native bindings: BigInt provides select algorithms in 3 forms:
1. JNI: Critical Native JNI integration for fastest performance, with minimal function overhead.^* ^**
2. JNI: Java Native JNI integration for faster performance, with regular function overhead.^*
3. JIT: Java Bytecode implementation designed to be optimized by JIT compilation.

^{* Native Bindings are present in the built JAR for MacOS (x64 and Arm64), Linux (x64), and Windows (x64), and are loaded by default on system startup.}
^{** To use Critical Native JNI bindings, the JVM must be launched with -Xcomp.}

Bare `int[]` value-encoded number arrays

The BigInt architecture exposes the underlying int[] array, and provides static function equivalents for all of its instance methods. This is possible because the standalone int[] array contains all information regarding the magnitude of an arbitrary precision integer. The int[] has the following encoding:

Signed length: The sign and number of base-2³² digits (limbs) in the magnitude.
val[0] ∈ [-1 << 26, .., -1, 0, 1, .., 1 << 26]
Absolute length: The absolute number of base-2³² digits (limbs) in the magnitude.
Math.abs(val[0])
Sign: The sign of the magnitude (-1 for negative, and 1 for positive).
Math.signum(val[0])
Zero: Magnitude is zero.
val[0] == 0
Magnitude digits: The base-2³² digits (limbs).
val[2,val[0]-1] ∈ [Integer.MIN_VALUE, Integer.MAX_VALUE]
The base 2³² digits (limbs) of the number are in little-endian order.

The bare int[] array can therefore be used as a feature-equivalent replacement for BigInt, with one notable difference: no BigInt instance is required.

Getting Started

BigInt is bundled with this module, which is available in the Maven Central Repository. The BigInt implementation provides JNI bindings for MacOS (x64 and Arm64), Linux and Windows platforms (x64), which can improve performance significantly. The JNI bindings are activated automatically, unless -Dorg.libj.math.BigInt.noNative is specified as a system property. The JNI bindings were built with Intel compilers, and are as statically linked as can be. The bindings also rely on the following shared libraries:

Prerequisites

Linux: libcilkrts5
MacOS: None
Windows: None

Function Matrix

The following matrix provides a comparison of functions offered by BigInteger vs BigInt and bare int[] array. The values in the matrix have the following rules:

0: Represents the baseline.
+###%: Prepresents "percent better^* compared to the baseline".
* "Better" means: 'faster' for runtime performance, and 'less instances' for heap memory allocation.

It is also important to note the following:

These numbers are derived from the detailed benchmark tests that are linked on each row. Please refer to Benchmarks for further information.
These numbers have an error margin, and should be considered as estimates. It is possible to achieve better precision in the results, but would require significant time running these tests in order to increase the sample size.
For functions that are not inherently available in the particular subject (i.e. in BigInteger), external utility functions were used to bridge the gap.

Benchmarks

The BigInt implementation is accompanied by a custom test framework that provides:

Assert correctness of function results
The results of each test are asserted to be equal amongst all test subjects.
Compare runtime performance
The custom test framework provides a mechanism for the isolation of a specific method to be tested. The actual tests are thus written to compare the feature-equivalent contextually appropriate function that is intended to be benchmarked.
Compare heap memory allocation
The custom test framework detects how many instances of a particular type are created during the execution of a test. This is accomplished with bytecode instrumentation via the Byteman and ByteBuddy instrumentation agents. The instrumentation enables a callback to be invoked after the instantiation of the types: BigInteger, BigInt, and int[].

The custom test framework achieves (2) and (3) with a "phased execution" approach, whereby the runtime performance is evaluated first, afterwhich the runtime is instrumented for the evaluation of the heap memory allocations in a repeated execution. It is necessary to evaluate the runtime performance before instrumentation, because instrumentation adds significant overhead to the runtime.

The following section provides benchmarks that compare the performance of BigInteger, BigInt, and bare int[] value-encoded number arrays.

The benchmark results provide runtime and memory heap allocation performance comparisons in the following kinds of tables and charts:

Summary of runtime performance

This table shows the relative performance of each function tested in the relevant test class (BigIntAdditionTest, BigIntMultiplicationTest, etc.). The values in this table represent the "percent less time spent in the function being tested", as compared to the baseline, which is the test subject (BigInteger, BigInt, or int[]) containing the 0 value (i.e. that test subject spends 0% less time than the baseline (itself) for the test).

Summary of heap memory allocation

This table shows the relative heap allocation performance of each function tested in the relevant test class (BigIntAdditionTest, BigIntMultiplicationTest, etc.). The values in this table represent the "percent less number of instances allocated on the heap during the execution of the function being tested", as compared to the baseline, which is the test subject (BigInteger, BigInt, or int[]) containing the 0 value (i.e. that test subject allocates 0% less instances than the baseline (itself) for the test). The columns for heap allocation results provide 2 values: T and int[]. Here, T represents the type of the test subject (BigInteger, BigInt, or int[]), and int[] represents the int[] type itself, as both BigInteger and BigInt use int[] as the underlying representation of the number's magnitude. Therefore, for bare int[] value-encoded number arrays, T and int[] refer to the same thing.

Detailed runtime performance

This table provides a detailed view of the runtime performance test results as delineated by the precision of the input(s) being tested. This table shows 3 meta-columns:

    a. Length: The length of the underlying int[] (i.e. int[].length).
    b. Precision: The precision (number of digits) of the number -- positive precision is for positive values, and negative precision is for negative values.
    c. Count: Number of tests that were run.

The values in the columns of the test subject (BigInteger, BigInt, or int[]) represent the mean time spent (nanoseconds) in the test method. If the test method being tested applies to one input (like BigInteger.abs(), where the one input is this), then the table will provide a single mean time spent value. If the test method being tested applies to two inputs (like BigInteger.add(BigInteger), where the first input is this and the second is some other BigInteger instance), then the table will provide two mean time spent values -- one for each input. This feature of the test framework allows one to more easily identify performance discrepancies between "when a particular value of a particular precision is the first argument vs if it's the second argument".

The table provides 2 additional rows at the bottom:
    a. Sum: The sum of the mean time spent in all precision sections.
    a. +%: The relative improvement in performance, as represented by the "percent less time spent in the function being tested" by evaluating the sum mean time spent in all precision sections. Like in the table for the Summary of runtime performance, this percentage is compared to the baseline, which is the test subject (BigInteger, BigInt, or int[]) containing the 0 value (i.e. that test subject spends 0% less time than the baseline (itself) for the test).

Runtime performance chart

This chart provides a visual representation of the Detailed runtime performance table. Note that the y values are inverted, whereby the higher y values in the graph are better than lower.

Detailed heap memory alloction

This table provides a detailed view of the heap memory alloction test results as delineated by the precision of the input(s) being tested. This table shows 3 meta-columns:

    a. Length: The length of the underlying int[] (i.e. int[].length).
    b. Precision: The precision (number of digits) of the number -- positive precision is for positive values, and negative precision is for negative values.
    c. Count: Number of tests that were run.

The values in the columns of the test subject (BigInteger, BigInt, or int[]) represent the total number of instances allocated during the execution of the tested function. Like in the table for the Summary of heap memory allocation, the columns for heap allocation results provide 2 values: T and int[]. Here, T represents the type of the test subject (BigInteger, BigInt, or int[]), and int[] represents the int[] type itself, as both BigInteger and BigInt use int[] as the underlying representation of the number's magnitude. Therefore, for bare int[] value-encoded number arrays, T and int[] refer to the same thing.

The table provides 2 additional rows at the bottom:
    a. Sum: The sum of the total number of instances in all precision sections.
    a. +%: The relative improvement in performance, as represented by the "percent less number of instances allocated on the heap during the execution of the function being tested" by evaluating the sum total number of instances in all precision sections. Like in the table for the Summary of heap memory allocation, this percentage is compared to the baseline, which is the test subject (BigInteger, BigInt, or int[]) containing the 0 value (i.e. that test subject allocates 0% less instances than the baseline (itself) for the test). Similarly, the columns for heap allocation results provide 2 values: T and int[]. Here, T represents the type of the test subject (BigInteger, BigInt, or int[]), and int[] represents the int[] type itself, as both BigInteger and BigInt use int[] as the underlying representation of the number's magnitude. Therefore, for bare int[] value-encoded number arrays, T and int[] refer to the same thing.

Benchmark Results

All tests were run with Java 1.8.0_231 on Mac OS 10.15.6.
All tests were run with -Xcomp argument, for precompilation of JIT optimizations.
All tests were run with Critical Native bindings loaded, which automatically happens when -Xcomp is present on the JVM argument list.

Benchmark tests are organized in 8 test classes, each responsible for its context of functions:

Link to results	Link to test code
Addition and subtraction	`BigIntAdditionTest`
Multiplication	`BigIntMultiplicationTest`
Division	`BigIntDivisionTest`
Remainder and modulus	`BigIntRemainderTest`
Binary operations	`BigIntBinaryTest`
Bitwise operations	`BigIntBitwiseTest`
Predicate functions	`BigIntPredicateTest`
Constructors	`BigIntConstructorTest`

FAQ

Is BigInt error free?

With respect to the correctness of its algorithms, BigInt has a custom test framework specifically designed to test the full breadth and adjustable depth of inputs into its algorithms. The test framework separates test inputs into "special" and "random". Special inputs are those that involve numbers representing special edges insofar as the number's int encoding, or the result of operations leading to propagating carrys. Random inputs are generated on a "breadth first" basis with respect to the input's decimal precision, allowing the depth (testing of more random values for a single precision) to be adjustable for the purposes of development vs comprehensive analysis.

With respect to exception checking, the BigInt does not preemptively check for exceptions. If a programmer divides by zero he has only himself to blame. And, it is ok to have undefined behavior.
What is BigInt's biggest advantage?

BigInt was created for one specific purpose: to lower the heap memory allocations for regular arithmetic operations. BigInteger liberally creates transient instances for the purpose of calculations, which results in a significant memory load and subsequent runtime performance load when the GC turns on. This situation is particularly relevant in applications that work with very many instances of arbitrary precision numbers. An example of such an application is an Asset Trading Systems (Level 3) that consumes live streams of order data. Arbitrary precision arithmetic is necessary for Asset Trading Systems in lieu of the need for fixed point arithmetic.

See Decimal.
What is BigInt's biggest disadvantage?

Though BigInt outperforms BigInteger in most operations, there are a few in which it is lacking. One particular operation that is important to note is mul(T) (i.e. multiplication of an arbitrary precision number by another arbitrary precision number). BigInt's mul(T) cannot match the performance of BigInteger's multiply(T) for "medium-sized numbers", because BigInteger's multiply(T) is implemented as an intrinsic function. BigInt comes close to this performance with its Critical Native implementation of its multiplication algorithms, but it is still not as fast. Nonetheless, where BigInt loses in isolated runtime performance, it gains back with its superior ability in reducing unnecessary heap memory allocation for transient calculations.

Please refer to Multiplication for benchmark statistics.
What is Critical Native JNI?

Calling a JNI method from Java is rather expensive compared to a simple C function call. Specifically when dealing with arrays, the JNI architecture necessitates expensive operations to convert Java arrays into "critical" native arrays and back. By converting a Java array to a "critical" native array, the JVM is notified to disallow the GC from freeing the respective memory. This overhead is significant, and all but disqualifies JNI as an optimization for algorithms that work with arrays.

The JDK has a private API called Critical Native to reduce the overhead function calls that do not require much JNI functionality. This feature was designed for internal use in the JDK. There is no public specification, and the only documentation you may find is in the comments to JDK-7013347.

For BigInt, the use of Critical Native JNI results in ~25% faster performance invoking JNI functions.

For further information about Critical Native JNI, please refer to this StackOverflow post.

`Decimal`

Introduction

A 64-bit precision decimal alternative to java.math.BigDecimal, with the following differences:

Avoids Heap Allocation: The Decimal represents a fixed-point number inside a long primitive, thus limiting the precision of a Decimal-encoded number to 64 bits, and eliminating the cost of heap allocation entirely. Please refer to Long Encoding for further details on Decimal's 64-bit Precision.
Support for "object-less" operation: All methods in Decimal are available in static form, allowing applications to work solely with long-encoded decimals.
Mutable: Decimal objects are mutable, allowing for reuse of allocated references.
Faster arithmetic: In lieu of Decimal's 64-bit precision limit, many arithmetic operations are faster due to inherent termination thresholds. Similarly, however, Decimal's 64-bit precision limit also demands it to perform precision and scale optimization on each operation, thus resulting in some arithmetic operations to be more expensive. Please refer to Function Matrix for further details on Decimal's performance.
Significantly reduced heap allocation: Decimal was designed to reduce the number of instances allocated purely for the purpose of transient calculation, and significantly outperforms BigDecimal with regard to memory and GC load. When utilizing long-encoded decimals, memory and GC load is reduced to zero.
No preemptive exception checking: Decimal does not preemptively check for exceptions. If a programmer divides by zero he has only himself to blame. And, it is ok to have undefined behavior.

Function Matrix

The following matrix provides a comparison of functions offered by BigDecimal vs Decimal and long-encoded numbers. The values in the matrix have the following rules:

0: Represents the baseline.
+###%: Prepresents "percent better^* compared to the baseline".
* "Better" means: 'faster' for runtime performance, and 'less instances' for heap memory allocation.

It is also important to note the following:

These numbers are derived from the detailed benchmark tests that are linked on each row. Please refer to Benchmarks for further information.
These numbers have an error margin, and should be considered as estimates. It is possible to achieve better precision in the results, but would require significant time running these tests in order to increase the sample size.
For functions that are not inherently available in the particular subject (i.e. in BigDecimal), external utility functions were used to bridge the gap.

A few other points:

Decimal's 64-bit precision limit demands it to perform precision and scale optimization on each operation, thus resulting in some arithmetic operations to be slower than with BigDecimal. This effectively means that for each arithmetic operation, Decimal is also performing a reduced setScale(scale) adjustment to ensure its number can fit in a long-encoded number.
Operations on long-encoded numbers are systematically slower than their Decimal equivalents. This is due to the need for the value and scale to be first decoded from a long-encoded number prior to the arithmetic operation. Similarly, the value and scale of the result of the operation need to be then re-encoded into long-encoded number. Though these overhead operations are miniscule, they still do reduce the overall runtime perform of algorithms on long-encoded decimals.
The use of the ∞ symbol in Heap Allocation stats is due to zero heap allocation for algorithms on long-encoded decimals.

Note: The benchmark results in the following table show arithmetic algorithms specified with a value in parentheses that ranges from 0 (or 3) to 16. This value represents the number of bits reserved for the scale in the long-encoded number representation. Please refer to Long Encoding for further details.

Long Encoding

The representation of a decimal value in Decimal encoding is achieved with the following model:

To represent a value such as 1234567.89, a Decimal-encoded long has two numbers inside it:

value
This is a variable range value (maximum of long) representing the full unscaled precision (all significant digits), i.e.:
```
123456789
```
scale
This is a variable range value (maximum of short) representing the position of the decimal point in the unscaled value, i.e.:
```
2
```

A decimal represented with Decimal encoding can be reconstituted with value and scale by multiplying the value by ten to the power of the negation of the scale (value ✕ 10⁻ˢᶜᵃˡᵉ), i.e.:

123456789 ✕ 10⁻² = 1234567.89

To maximize precision, the Decimal encoding implements a variable range for the scale. The variable range is defined by a scaleBits variable representing the number of bits inside the 64-bit long that are reserved for the signed representation of the scale. This effectively means that the variable range of value is 64 - bits.

Since both value and scale are signed, one bit is reserved for the sign in each. The following table provides sample value and scale ranges for various scale bits values:

For example, consider the following table with scale scaleBits as the variable:

`scaleBits` ^{[0, 16]}	Scale range ^{[-2ᵇⁱᵗˢ⁻¹, 2ᵇⁱᵗˢ⁻¹ - 1]}	`valueBits` ^64-bits	Value range ^{[-2⁶³⁻ᵇⁱᵗˢ, 2⁶³⁻ᵇⁱᵗˢ - 1]}	Example
⁰	^{[0, 0]}	⁶⁴	^{[-2⁶³, 2⁶³ - 1]}	^{Long.MAX_VALUE}
¹	^{[0, 0]}	⁶³	^{[-2⁶², 2⁶² - 1]}	^{4611686018427387904}
²	^{[-1, 0]}	⁶²	^{[-2⁶¹, 2⁶¹ - 1]}	^{2305843009213693952E1}
³	^{[-2, 1]}	⁶¹	^{[-2⁶⁰, 2⁶⁰ - 1]}	^{11529215046068469.76}
⁴	^{[-8, 7]}	⁶⁰	^{[-2⁵⁹, 2⁵⁹ - 1]}	^{57646075230.3423488}
⁸	^{[-128, 127]}	⁵⁶	^{[-2⁵⁵, 2⁵⁵ - 1]}	^{3.6028797018963968E111}
¹⁶	^{[-32768, 32767]}	⁴⁸	^{[-2⁴⁷, 2⁴⁷ - 1]}	^{1.40737488355328E−32768}

Technically, scaleBits below 3 are not very useful. Therefore, Decimal officially supports scaleBits values between 3 and 16 with its unit tests. Some unit tests also test for scaleBits values of 0, 1 and 2, but this is supplementary.

The following illustrates the way Decimal encodes the value and scale inside a long primitive:

        scale sign bit (for scaleBits > 0)
       /
      1
.---+---+---- // --------+------------------------------ // -------------------------------.
|   |   '                |                                                                 |
|   |   '   scale        |                             value                               |
|   |   '                |                                                                 |
'---+---+---- // --------+----------------------------- // --------------------------------'
  0      [1, scaleBits+1]                  [scaleBits+1, 63-scaleBits]
   \
    value sign bit

Benchmark Results

All tests were run with Java 1.8.0_231 on Mac OS 10.15.6.
All tests were run with -Xcomp argument, for precompilation of JIT optimizations.

Benchmark tests are organized in 8 test classes, each responsible for its context of functions:

Link to results	Link to test code
Addition and subtraction	`DecimalAdditionTest`
Multiplication	`DecimalMultiplicationTest`
Division	`DecimalDivisionTest`
Predicate functions	`DecimalPredicateTest`

FAQ

Is Decimal error free?

The development of Decimal utilized the same test framework as that of BigInt. The test framework is specifically designed to test the full breadth and adjustable depth of inputs into Decimal's algorithms. The test framework separates test inputs into "special" and "random". Special inputs are those that involve numbers representing special edges insofar as the number's long encoding, or the result of operations leading to propagating carrys of remainders. Random inputs are generated on a "breadth first" basis with respect to the input's decimal precision, allowing the depth (testing of more random values for a single precision) to be adjustable for the purposes of development vs comprehensive analysis.
What is Decimal's biggest advantage?

Decimal was created for one specific purpose: to lower the heap memory allocations for regular arithmetic operations. It achieves this with its single object allocation count in case of Decimal instances, or zero object allocation count in case of long-encoded numbers. In comparison, BigDecimal utilized BigInteger algorithms that liberally creates transient instances for the purpose of calculations, which results in a significant memory load and subsequent runtime performance load when the GC turns on. This situation is particularly relevant in applications that work with very many fixed-point numbers. An example of such an application is an Asset Trading Systems (Level 3) that consumes live streams of order data. Arbitrary precision arithmetic is necessary for Asset Trading Systems in lieu of the need for fixed point arithmetic.
What is Decimal's biggest disadvantage?

Though Decimal outperforms BigDecimal in many operations, there are a those in which it is lacking. One particular operation that is important to note is mul(T). Decimal utilizes BigInt's mul(T), which cannot match the performance of BigInteger's multiply(T) for "medium-sized numbers", because BigInteger's multiply(T) is implemented as an intrinsic function. BigInt comes close to this performance with its Critical Native implementation of its multiplication algorithms, but it is still not as fast. Nonetheless, where BigInt loses in isolated runtime performance, it gains back with its superior ability in reducing unnecessary heap memory allocation for transient calculations.

Please refer to BigInt's Multiplication for benchmark statistics.

Contributing

Pull requests are welcome. For major changes, please open an issue first to discuss what you would like to change.

Please make sure to update tests as appropriate.

License

This project is licensed under the MIT License - see the LICENSE.txt file for details.

Name		Name	Last commit message	Last commit date
Latest commit History 337 Commits
.github/workflows		.github/workflows
src		src
.gitignore		.gitignore
CHANGELOG.md		CHANGELOG.md
LICENSE.txt		LICENSE.txt
Makefile		Makefile
README.md		README.md
pom.xml		pom.xml
settings.xml		settings.xml

License

libj/math

Folders and files

Latest commit

History

Repository files navigation

LibJ Math

Introduction

Higher-performance alternatives

BigInt

Introduction

Bare int[] value-encoded number arrays

Getting Started

Prerequisites

Function Matrix

Benchmarks

Benchmark Results

FAQ

Decimal

Introduction

Function Matrix

Long Encoding

Benchmark Results

FAQ

Contributing

License

About

Topics

Resources

License

Stars

Watchers

Forks

Languages

`BigInt`

Bare `int[]` value-encoded number arrays

`Decimal`