This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
Re: Improve the performance of std::uniform_int_distribution (fewer divisions) [Potential patch]
- From: "Stephen M. Webb" <stephen dot webb at bregmasoft dot ca>
- To: libstdc++ at gcc dot gnu dot org
- Date: Mon, 2 Sep 2019 18:51:38 -0400
- Subject: Re: Improve the performance of std::uniform_int_distribution (fewer divisions) [Potential patch]
- References: <CAJ0XVj2Z4syCRPq=mdD1gkO=SHcehoAOA8gecpD8PgB=AZDH-w@mail.gmail.com>
- Reply-to: stephen dot webb at bregmasoft dot ca
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>