On Mon, 8 Jan 2024 18:20:09 GMT, Brian Burkhalter <b...@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
