RFR: 8282365: Consolidate and improve division by constant idealizations [v30]

[Quan Anh Mai]

On Fri, 27 Oct 2023 10:51:25 GMT, Raffaello Giulietti <rgiulietti at openjdk.org> wrote:

>> @vnkozlov Can you verify if the error has been resolved? I have added 2 cases when the dividends are provably bounded, and here is the result of the latest patch on my AMD Ryzen 7 7700.
>> 
>>                                                                                       Before              After
>>     Benchmark                                        (BUFFER_SIZE)  Mode  Cnt     Score     Error     Score    Error  Units   Change
>>     IntegerDivMod.testDivideConstant                          1024  avgt    5   102.296 ±   0.509    89.752 ±  0.934  ns/op  -12.26%
>>     IntegerDivMod.testDivideConstantBounded                   1024  avgt    5   119.249 ±   1.479    49.908 ±  0.363  ns/op  -58.15%
>>     IntegerDivMod.testDivideUnsignedConstant                  1024  avgt    5  1158.261 ±   3.751    92.269 ±  0.980  ns/op  -92.03%
>>     IntegerDivMod.testDivideUnsignedConstantBounded           1024  avgt    5  1160.531 ±   6.941    28.073 ±  0.144  ns/op  -97.58%
>>     IntegerDivMod.testRemainderUnsignedConstant               1024  avgt    5  1180.825 ±  35.549   127.642 ±  1.561  ns/op  -89.19%
>>     LongDivMod.testDivideConstantBounded                      1024  avgt    5   591.165 ±  22.569   104.507 ±  0.606  ns/op  -82.32%
>>     LongDivMod.testDivideUnsignedConstant                     1024  avgt    5  1768.345 ±  15.068   532.097 ±  9.144  ns/op  -69.91%
>>     LongDivMod.testDivideUnsignedConstantBounded              1024  avgt    5  1354.547 ±  11.357    83.710 ±  0.780  ns/op  -93.82%
>>     LongDivMod.testRemainderUnsignedConstant                  1024  avgt    5  1742.673 ±  29.557   736.080 ± 22.306  ns/op  -57.76%
>
> @merykitty I'm not sure I understand the goal and restrictions of this PR. The title is about unsigned values, but the discussion also has x < 0.
> Let me summarize my understanding, but let me know if I'm wrong:
> 
> Let W = 32, let ^ denote exponentiation (as in LaTeX).
> Given integer d ∈ (0, 2^W), find integers c, m ≥ 0 such that for each x ∈ [0, 2^W) we have floor(x / d) = floor(x c / 2^m).
> 
> Is c ≥ 2^W acceptable? In other words, is it allowed for c to be a 64 bit integer?

@rgiulietti You are right, I have renamed the JBS issue and the PR title. Regarding the mathematical theory, everything is done in the ring of integers, which means that `c` and `m` can be arbitrary large numbers.

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

PR Comment: https://git.openjdk.org/jdk/pull/9947#issuecomment-1782766300