Improve the performance of std::uniform_int_distribution (fewer divisions) [Potential patch]

[Stephen M. Webb]

On 2019-09-02 17:11, Daniel Lemire wrote:
> Even on recent processors, integer division is relatively expensive.
> The current implementation of  std::uniform_int_distribution typically
> requires two divisions by invocation:
> 
>         // downscaling
>         const __uctype __uerange = __urange + 1; // __urange can be zero
>         const __uctype __scaling = __urngrange / __uerange;
>         const __uctype __past = __uerange * __scaling;
>         do
>           __ret = __uctype(__urng()) - __urngmin;
>         while (__ret >= __past);
>         __ret /= __scaling;
> 
> We can achieve the same algorithmic result with at most one division, and
> typically
> no division at all without requiring more calls to the random number
> generator.
> This was recently added to Swift (https://github.com/apple/swift/pull/25286)

It would be good to see some perforamce numbers for both Intel64 and Aarch64, and also with and without SIMD enabled.


-- 
Stephen M. Webb  <stephen.webb@bregmasoft.ca>