RFR: JDK-8323186: A faster algorithm for MutablebigInteger.divWord(long, int)

[fabioromano1]

On Mon, 8 Jan 2024 18:20:09 GMT, Brian Burkhalter <bpb at openjdk.org> wrote:

> Do you have any benchmark results demonstrating the increased throughput?

I just uploaded a class for random tests. But during the execution, I've found a non banal problem concerning the old implementation's running time.
The problem is this: the running time of the old implementation depends strongly by the difference between the initial approximation and the exact value of the quotient. So, I tried to construct of a possible worst case, attempting to maximizing this distance. To do so, I maximized the dividend `n = -2` (treated as unsigned) and minimized the divisor `d = 3`. The result is this:
The computed initial approximation is `q0 = (n >>> 1) / (d >>> 1)`, so `q0 == 9223372036854775807L`, while the exact quotient is `q = 6148914691236517204L`. This implies that the number of iterations is  `|q - q0| == 3074457345618258603L` in the worst case. This means that the running time of the old implementation can be EXPONENTIAL in the bit length of |q - q0|.
Experimentally, you can notice this by the fact that if you try to do an increasingly number of divisions, the running time quickly becomes unreasonably long, this happens just over the `2^18 == 262144` divisions.

Anyway, these are my results of the tests' running.

New algorithm:

Time to do 1 divisions: PT0.002411989S
Average time for division: PT0.002411989S

Time to do 2 divisions: PT0.000003997S
Average time for division: PT0.000001998S

Time to do 4 divisions: PT0.000006194S
Average time for division: PT0.000001548S

Time to do 8 divisions: PT0.000013294S
Average time for division: PT0.000001661S

Time to do 16 divisions: PT0.000021008S
Average time for division: PT0.000001313S

Time to do 32 divisions: PT0.000042878S
Average time for division: PT0.000001339S

Time to do 64 divisions: PT0.000131778S
Average time for division: PT0.000002059S

Time to do 128 divisions: PT0.000163048S
Average time for division: PT0.000001273S

Time to do 256 divisions: PT0.000383142S
Average time for division: PT0.000001496S

Time to do 512 divisions: PT0.000319871S
Average time for division: PT0.000000624S

Time to do 1024 divisions: PT0.000413291S
Average time for division: PT0.000000403S

Time to do 2048 divisions: PT0.000591616S
Average time for division: PT0.000000288S

Time to do 4096 divisions: PT0.00135185S
Average time for division: PT0.00000033S

Time to do 8192 divisions: PT0.013735457S
Average time for division: PT0.000001676S

Time to do 16384 divisions: PT0.008213712S
Average time for division: PT0.000000501S

Time to do 32768 divisions: PT0.020442676S
Average time for division: PT0.000000623S

Time to do 65536 divisions: PT0.011344406S
Average time for division: PT0.000000173S

Time to do 131072 divisions: PT0.018728826S
Average time for division: PT0.000000142S

Time to do 262144 divisions: PT0.043171006S
Average time for division: PT0.000000164S

Time to do 524288 divisions: PT0.073636145S
Average time for division: PT0.00000014S

Time to do 1048576 divisions: PT0.120018251S
Average time for division: PT0.000000114S

Time to do 2097152 divisions: PT0.157581276S
Average time for division: PT0.000000075S

Time to do 4194304 divisions: PT0.348321185S
Average time for division: PT0.000000083S

Time to do 8388608 divisions: PT0.642987771S
Average time for division: PT0.000000076S

Time to do 16777216 divisions: PT1.104336979S
Average time for division: PT0.000000065S

Time to do 33554432 divisions: PT2.229299703S
Average time for division: PT0.000000066S

Time to do 67108864 divisions: PT4.386180114S
Average time for division: PT0.000000065S

Time to do 134217728 divisions: PT8.833464454S
Average time for division: PT0.000000065S

Time to do 268435456 divisions: PT17.504803158S
Average time for division: PT0.000000065S

Old algorithm:
Time to do 1 divisions: PT0.00590102S
Average time for division: PT0.00590102S

Time to do 2 divisions: PT0.000002469S
Average time for division: PT0.000001234S

Time to do 4 divisions: PT0.000014707S
Average time for division: PT0.000003676S

Time to do 8 divisions: PT0.00000855S
Average time for division: PT0.000001068S

Time to do 16 divisions: PT0.000027515S
Average time for division: PT0.000001719S

Time to do 32 divisions: PT0.000073262S
Average time for division: PT0.000002289S

Time to do 64 divisions: PT0.000340843S
Average time for division: PT0.000005325S

Time to do 128 divisions: PT0.00016714S
Average time for division: PT0.000001305S

Time to do 256 divisions: PT0.001197161S
Average time for division: PT0.000004676S

Time to do 512 divisions: PT0.000273558S
Average time for division: PT0.000000534S

Time to do 1024 divisions: PT0.000617932S
Average time for division: PT0.000000603S

Time to do 2048 divisions: PT0.000892402S
Average time for division: PT0.000000435S

Time to do 4096 divisions: PT0.001367862S
Average time for division: PT0.000000333S

Time to do 8192 divisions: PT1.319736346S
Average time for division: PT0.0001611S

Time to do 16384 divisions: PT8.109278716S
Average time for division: PT0.000494951S

Time to do 32768 divisions: PT0.038191561S
Average time for division: PT0.000001165S

Time to do 65536 divisions: PT3.249995508S
Average time for division: PT0.00004959S

Time to do 131072 divisions: PT0.203684211S
Average time for division: PT0.000001553S

Time to do 262144 divisions: PT9.767934912S
Average time for division: PT0.000037261S

-------------

PR Comment: https://git.openjdk.org/jdk/pull/17291#issuecomment-1883610685