RFR: 8284493: Improve computeNextExponential tail performance and accuracy [v19]

[GuySteele]

On Thu, 6 Apr 2023 18:07:29 GMT, Chris Hennick <duke at openjdk.org> wrote:

>> This PR improves both the worst-case performance of `nextExponential` and `nextGaussian` and the distribution of output at the tails. It fixes the following imperfections:
>> 
>> * Repeatedly adding DoubleZigguratTables.exponentialX0 to extra causes a rounding error to accumulate at the tail of the distribution (probably starting around `2*exponentialX0 == 0x1.e46eff20739afp3 ~ 15.1`); this PR fixes that by tracking the multiple of exponentialX0 as a long. (This distortion is worst when `x > 0x1.0p56` since in that case, a rounding error means `extra + x == extra`.
>> * Reduces several equations using `Math.fma`. (This will almost certainly improve performance, and may or may not improve output distribution.)
>> * Uses the newly-extracted `computeWinsorizedNextExponential` function to prevent `nextGaussian` from going into the `nextExponential` tail twice.
>
> Chris Hennick has updated the pull request with a new target base due to a merge or a rebase. The pull request now contains 17 commits:
> 
>  - Merge branch 'master' of https://git.openjdk.org/jdk into patch-1
>  - Merge branch 'master' of https://git.openjdk.org/jdk into patch-1
>  - Merge branch 'master' into patch-1
>  - Update copyright date in RandomNext.java
>  - Update copyright date in RandomGeneratorNext.java
>  - Update copyright date in RandomGeneratorExponentialGaussian.java
>  - Update copyright date in RandomSupport.java
>  - Add parameter to enable/disable fixed PRNG seed
>  - Rewrite Javadoc
>  - Simplify Javadoc description
>  - ... and 7 more: https://git.openjdk.org/jdk/compare/08fbb7bb...2470c00a

I have now reviewed all the changes in file .../jdk/internal/util/random/RandomSupport.java . It appears that the method formerly called computeWinsorizedNextExponential has been renamed to computeNextExponentialSoftCapped, and that is a good change. All the changes to the executable code appear to be sound (and, yes, I believe I still remember how all this code is supposed to work—even while admitting that I wrote it some years ago and that a couple of embarrassing mistakes were later discovered and repaired, thank goodness). I looked especially carefully at the change of representation for the variable "extra" from double to long and the new uses of fma. I went back and looked at email exchanges I had with Joe Darcy on May 10, 2022, and I see that many of the concerns I expressed at that time have been addressed. 

I do suggest that for extra clarity, the declaration and computation of maxExtraMinus1 at lines 1206--1212 be moved down below to after line 1222, just below the comment that begins "We didn't use the upper part of U1 after all". It may be that good optimizing Java compilers perform this code motion anyway (the code in lines 1213–1221 does not refer to maxExtraMinus1), but it would help a human reader to understand that this code is not part of and does not need to be part of the fast path through the code. Moreover, though a compiler cannot tell that it's okay to move the comparison of maxValue to 0.0 (and the possible forced return of 0.0) off the fast path, I argue that it is indeed okay to do so, because it is always permitted to return a value larger than maxValue, and the fast path does always return a nonnegative value. So I actually argue to move three more lines (in all, lines 1203–1212) to after line 1222.

In all other respects, I recommend that this set of changes be adopted exactly as is.

If making the one change I suggested above might cause adoption to slip from JDK21 to JDK22 (perhaps because of a need for retesting), then I would suggest adopting the code exactly as is and then scheduling the suggested change for JDK22, because the suggested change improves clarity and code speed but should not change the advertised functionality at all.

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

PR Comment: https://git.openjdk.org/jdk/pull/8131#issuecomment-1546202844