🗺️ Overview

Exactly 3 years ago, @MattStephanson's #3012 implemented @lemire's algorithm "Fast Random Integer Generation in an Interval" for TR1 uniform_int and Standard uniform_int_distribution, shipped in VS 2022 17.5.

This PR extends the use of the algorithm to sample(), shuffle(), ranges::sample, and ranges::shuffle. It's a behavioral change (the results of sampling and shuffling will be different), but the significant speedup is worth it.

We have to fix some warnings in _Rng_from_urng_v2 because it was never previously exposed to signed difference types.

My #5712 very recently split TR1 uniform_int from Standard uniform_int_distribution. The former still switches between my old _Rng_from_urng and the new Lemire-powered _Rng_from_urng_v2 depending on whether it senses the presence of static constexpr min() and max() from the engine, as Lemire's algorithm greatly benefits from having them as compile-time constants. After #5712, the Standard distribution now assumes it's being used with Standard engines (as it would be highly inconsistent for a program to be mixing the Standard distribution with a TR1 engine; both spellings should be updated simultaneously).

As shuffle() was C++11 and sample() was C++17, it is slightly more conceivable for those algorithms to be used with old TR1 engines. For the moment, to preserve source compatibility, I am using the same "switch between v1 and v2" logic that TR1 uniform_int uses (and that Standard uniform_int_distribution indirectly used between #3012 and #5712).

In the near future, I plan to purge TR1 entirely, making use of v2 unconditional, but I want to land this improvement separately.

⚙️ Commits

• Add benchmarks for sample() and shuffle().
  • I didn't observe interesting length dependence, so to reduce output verbosity, I selected a single length.
• Move _Rng_from_urng_v2 up to <algorithm>, no other changes.
• Move _Has_static_min_max up to <algorithm>, no other changes.
• Extract _Rng_from_urng_v1_or_v2.
• Cleanup _Rng_from_urng_v2: static constexpr => constexpr for a local constant.
• Fix URBG usage: min() and max() must be constexpr.
• Fix URBG usage: Must provide result_type, must be unsigned integer.
  • Thanks @MattStephanson for bring this squirrelly type to my attention. 🐿️
• Behavioral change: Use _Rng_from_urng_v1_or_v2 to optimize sample(), shuffle(), ranges::sample, ranges::shuffle.
• Fix warning C4018: '<': signed/unsigned mismatch
  • This was comparing _Rem < _Index, where _Rem is _Udiff & _Udiff (almost always _Udiff) while we have potentially signed _Diff _Index.
• Fix warning C4365: 'initializing': conversion from 'int' to 'unsigned __int64', signed/unsigned mismatch
  • _Urng::result_type must be unsigned, but result_type - result_type performs the usual arithmetic conversions, promoting tiny types to int. Therefore, we need to static_cast<_Udiff>.
• Fix error C2397: conversion from 'const int' to 'unsigned __int64' requires a narrowing conversion
  • Except for iterators with exotic difference types:
  • For x64 algorithms, _Diff is naturally 64-bit, so is_same_v<_Udiff, uint64_t> is naturally taken.
  • But for x86 algorithms, _Diff is naturally 32-bit. If the URBG is 32-bit (or smaller), then _Udiff will be uint32_t, and the else branch will be taken.
  • In that case, the error correctly complains that we're using braces to convert from signed _Diff _Index to unsigned _Uprod, which is narrowing. We should directly static_cast instead.
• Fix warning C4018: '<': signed/unsigned mismatch
  • Again, (_Urng::max) () - (_Urng::min) () is result_type - result_type, subject to the usual arithmetic conversions. When compared against _Udiff _Bmask_local, this can emit signed/unsigned mismatch warnings.
  • (This repro is x86-specific because MSVC emits warning C4018 at level 3 for int < unsigned int. int < unsigned long long emits an off-by-default warning C4388 "signed/unsigned mismatch". So even though the warning behavior is architecture-neutral, the varying size of _Udiff causes the warning to be x86-specific.)
  • I'm avoiding extracting the max - min as a constant to avoid VSO-2580691 "/analyze emits bogus warning C6295 (Loop executes infinitely) for a loop that immediately finishes".

⏱️ Benchmark results

On my 5950X: