Switch to OpenJDK 8 java/math
The main goal here is performance by avoiding JNI and especially
NativeAllocationRegistry overhead. We gain a factor of 10 or so
on small BigInteger arithmetic. For large computations, we gain
substantially in a few cases where OpenJDK seems to use better
algorithms. AFAIK, with this version we never lose by integral
factors relative to what we had before.
A secondary goal is to clean out open BigInteger bugs.
The base version is 8u252, which for this part of the tree is
identical to June 15 2020 ToT.
Note that this means we included the java.math part of
https://hg.openjdk.java.net/jdk8u/jdk8u/jdk/rev/a5f5d7fd9be6 (29 Oct 2019)
That appears to be a separable fix that makes no interface changes.
I re-added @NonNull annotations. We also removed some code to write
certain backwards-compatibility fields during serialization, since we
never had those.
This also adds a the <X>ValueExact Java 8 BigInteger methods that had
not been previously supported.
This removes a Harmony test for compatibility with the RI implementation
that the RI implementation itself apparently fails. And, IMO, the
observed behavior is better than what we previously tested for.
Fixed a bunch of comment spelling errors. All of these have now
been fixed in upstream ToT.
Benchmarking showed that a straight move to the RI version slowed down
large multiplications, divisions, and modular exponentiation enough to
make it problematic. Thus I reintroduced NativeBN to allow those to fall
back to boringssl, at least for sufficiently large inputs. It was moved
to a hopefully more appropriate location. The fallback is tuned for
64 bits; for 32 bits it's probably much less useful; much of the
boringssl performance advantage comes from 64-bit "digits".
The boringssl fallbacks are not completely free, since we need extra
conversions on each operation. But since we only do this for large
asymptotically expensive computations, we see at mosts tens of percents
regressions, which probably qualifies as "in the noise" here. If we
find additional performance issues, we can add more boringssl fallbacks;
the required code is now fairly straightforward.
Unlike the old version, this no longer uses NativeAllocationRegistry or
similar mechanisms at all. Native memory is only used on a short-term
basis, with explicit deallocation. We no longer use boringssl for
simple linear-time operations like addition.
Microbenchmark results for the newly added benchmark, and for a
close-to-final BigInteger version, listed as "combined":
Msecs/iteration
Digits: 5/10 50/100 500/1000 5000/10000
Inner product, 1000 terms, factors of larger indicated size:
current 2.1 2.5 6.4 168
RI 0.11 0.66 11.0 486
combined 0.12 0.67 9.1 189
Harmonic series, uses smaller indicated size
current 3.7 3.2 4.3 17.6
RI 0.16 0.34 1.4 14.3
combined 0.17 0.34 1.23 14.2
(1+1/100000)^100000, larger size
current 0.07 0.073 0.33 15.8
RI 0.011 0.049 1.553 63.6
combined 0.011 0.049 0.48 13.6
Single modPow() call, smaller size
current 0.005 0.011 1.1 583
RI 0.006 0.038 7.2 5580
combined 0.011 0.012 1.1 541
Single modInverse call, larger size
current 0.003 0.014 0.375 27.8
RI 0.003 0.003 0.026 1.6
combined 0.002 0.002 0.008 0.4
Bug: 160641142
Bug: 136887041
Bug: 119491938
Bug: 28214673
Bug: 28251030
Bug: 2950143
Test: AOSP Boots. Ran some manual Calculator tests on Cuttlefish.
Change-Id: Id577d99328013b1e3c389973dcb0195fa7f52b0b
31 files changed