Batched random for the CSPRNG (and System.Random)

[bartonjs]

Background and motivation

When generating many small random numbers, it is more efficient to generate them in one bulk operation. The most obvious example would be 8 coin-flips can be generated from just one random byte.

Several algorithms exist for extracting multiple bounded integers from a pull of an RNG, without sacrificing a loss of entropy. For example, if one needs two integers in the range [0, 6), they independently compose to a single integer in the range [0, 12). These algorithms can significantly speed up throughput on systems with a slow random number generator.

API Proposal

namespace System.Security.Cryptography
{
    // Batched random
    public partial class RandomNumberGenerator
    {
        // Fill a homogeneous set of bounded integers.
        // Target: RNG.GetItems, dice roll simulations.
        public static void FillInt32(int toExclusive, Span<int> destination);
        public static void FillInt32(int fromInclusive, int toExclusive, Span<int> destination);
        public static void FillUInt32(uint toExclusive, Span<uint> destination);
        
        // Fill a heterogeneous set of bounded integers.
        // Target: Fisher-Yates Shuffle
        public static void FillUInt32(ReadOnlySpan<uint> toExclusives, Span<uint> destination);

        // Fully squaring off the feature:
        // T: Int32, UInt32, Int64, UInt64
        // public static void FillT(T toExclusive, Span<T> destination);
        // public static void FillT(T fromInclusive, T toExclusive, Span<T> destination);
        // public static void FillT(ReadOnlySpan<T> toExclusives, Span<T> destination);
        // public static void FillT(ReadOnlySpan<T> fromInclusives, ReadOnlySpan<T> toExclusives, Span<T> destination);

        public static void FillUInt32(uint fromInclusive, uint toExclusive, Span<uint> destination);
        public static void FillInt64(long toExclusive, Span<long> destination);
        public static void FillInt64(long fromInclusive, long toExclusive, Span<long> destination);
        public static void FillUInt64(ulong toExclusive, Span<ulong> destination);
        public static void FillUInt64(ulong fromInclusive, ulong toExclusive, Span<ulong> destination);
        public static void FillUInt32(ReadOnlySpan<uint> fromInclusives, ReadOnlySpan<uint> toExclusives, Span<uint> destination);
        public static void FillInt32(ReadOnlySpan<int> toExclusives, Span<int> destination);
        public static void FillInt32(ReadOnlySpan<int> fromInclusives, ReadOnlySpan<int> toExclusives, Span<uint> destination);
        public static void FillInt64(ReadOnlySpan<long> toExclusives, Span<long> destination);
        public static void FillInt64(ReadOnlySpan<long> fromInclusives, ReadOnlySpan<long> toExclusives, Span<long> destination);
        public static void FillUInt64(ReadOnlySpan<ulong> toExclusives, Span<ulong> destination);
        public static void FillUInt64(ReadOnlySpan<ulong> fromInclusives, ReadOnlySpan<ulong> toExclusives, Span<ulong> destination);
    }
    
    // Helper routines that would have made investigating this space easier
    public partial class RandomNumberGenerator
    {
        public static ulong GetUInt64();
        public static ulong GetUInt64(uint toExclusive);
    
        // The rest of these are "squaring the circle"
    
        public static int GetInt32();
    
        public static uint GetUInt32();
        public static uint GetUInt32(uint toExclusive);
        public static uint GetUInt32(uint fromInclusive, uint toExclusive);
    
        public static long GetInt64();
        public static long GetInt64(long toExclusive);
        public static long GetInt64(long fromInclusive, long toExclusive);
    
        public static ulong GetUInt64(uint fromInclusive, uint toExclusive);
    }
}

namespace System
{
    public partial class Random
    {
        // Only one exception case: toExclusive == 0
        public virtual void NextBatchUInt32(uint toExclusive, Span<uint> destination);
        // Only one exception case: toExclusives.Any(x => x == 0);
        public virtual void NextBatchUInt32(ReadOnlySpan<uint> toExclusives, Span<uint> destination);

        // Non-virtual, implemented in terms of NextBatchUInt32
        public void NextBatch(int toExclusive, Span<int> destination);
        public void NextBatch(int fromInclusive, int toExclusive, Span<int> destination);

        // squaring off
        public void NextBatchUInt32(uint fromInclusive, uint toExclusive, Span<uint> destination);
        public void NextBatchUInt32(ReadOnlySpan<uint> fromInclusives, ReadOnlySpan<uint> toExclusives, Span<uint> destination);
        public void NextBatchInt32(ReadOnlySpan<int> toExclusives, Span<int> destination);
        public void NextBatchInt32(ReadOnlySpan<int> fromInclusives, ReadOnlySpan<int> toExclusives, Span<int> destination);
        public void NextBatchInt64(long toExclusive, Span<long> destination);
        public void NextBatchInt64(long fromInclusive, long toExclusive, Span<long> destination);
        public void NextBatchInt64(ReadOnlySpan<long> toExclusives, Span<long> destination);
        public void NextBatchInt64(ReadOnlySpan<long> fromInclusives, ReadOnlySpan<long> toExclusives, Span<long> destination);
        public virtual void NextBatchUInt64(ulong toExclusive, Span<ulong> destination);
        public void NextBatchUInt64(ulong fromInclusive, ulong toExclusive, Span<ulong> destination);
        public virtual void NextBatchUInt64(ReadOnlySpan<ulong> toExclusives, Span<ulong> destination);
        public void NextBatchUInt64(ReadOnlySpan<ulong> fromInclusives, ReadOnlySpan<ulong> toExclusives, Span<ulong> destination);
    }
}

API Usage

int[] dice = new int[5];
RandomNumberGenerator.FillInt32(6, dice);

for (int i = 0; i < 6; i++)
{
   if (dice.All(die => die == i))
   {
       return "Yahtzee!";
   }
}

Alternative Designs

• FillInt32 and friends can be int returning instead of void, to indicate how many items they processed in a single batch.
  • For the virtuals on System.Random we might want to encapsulate that with the template method pattern to ensure they don't return negative, or zero.

[dotnet-policy-service]

Tagging subscribers to this area: @dotnet/area-system-security, @bartonjs, @vcsjones
See info in area-owners.md if you want to be subscribed.

[vcsjones]

"squaring the circle"

Having Fill{Int32,UInt32} without a Int64 fills feels "missing". I know they can't be batched given some previous discussions, but we could just do a naive thing like:

public static void FillInt64(long toExclusive, Span<long> destination) {
    for (int i = 0; i < destination.Length; i++) {
        destination[i] = GetInt64(toExclusive);
    }
}

That's a squarer circle it seems. If we ever have a compelling reason to batch it, we can, if we can.

[bartonjs]

It's not that Int64 can't be batched, it's just that isn't guaranteed to be.

For batched UInt32, if the bound is uint.MaxValue, a pair of them fits in one UInt64. Is it worth it at that extreme? This batch succeeds in one GetUInt64() call in all but 2/(2^64) values, so it's 1 RNG call, 8 bytes (1 in 2^63 yields 2 calls, 16 bytes). A single call to GetUInt32(uint.MaxValue) has a 1/(2^32) chance of needing another random call, and because of probability combination rules that makes two result in 2 RNG calls for 8 total bytes in all but ~1 in 2^31 (1 in 2147483648.25), and 3 or more calls for 12 (or more) total bytes in the remainder. Depending on which way the wind is blowing, how much overhead we have today for a P/Invoke, how much overhead the RNG has when called, etc... it might be better, or might be worse 😄. (For Xoshiro, I assume it's worse to batch these, because the RNG overheads are low)

For the homogeneous call, if toExclusive is less than or equal to uint.MaxValue then batching would work fine... but might require some trickery to get an efficient algorithm from it (where "trickery" might mean making a local span, dispatching to FillUInt32, then do a widening-copy). Once it hits uint.MaxValue + 1, though, the batching wouldn't work without dipping into Int128 (which may, or may not, be better), so might drop to the suggested loop.

If we also did a heterogeneous version of FillUInt64, it has the drawback that it might only get one value per batch (consider inputs of [2, ulong.MaxValue, 2], it'll be done in 3 inefficient batches of one each).

My proposal above does leave some corners cut, e.g.

• FillUInt32(uint fromInclusive, uint toExclusive, destination) was not proposed, but could be.
  • For the Int32 one "that" overload is needed to support a range in excess of 2**31
  • Mainly I just can't imagine a scenario 😄
• Heterogeneous was proposed without fromInclusives
  • Because it's ugly. I can't think of a good way to do it without a temporary buffer (e.g. stackalloc uint 64)
  • Instead of toExclusives.IndexOf(0) >= 0 as the failure case, it has to do pairwise subtraction. Does it do that on-demand (late exception), or early (and then have to do it again when using the temporary buffer for calling the [0, bound) version)?
• Heterogeneous was only proposed for UInt32
  • Without fromInclusives the Int32 version has to throw for any non-positive toExclusive.
  • And with fromInclusives it has to do the subtraction with the same problems as before.

"So why did you cut the corners there, but square them off for Get-Int variants?" (asked no one yet)

Largely from "ok... assume none of these extras ever get called, how much work was wasted?". But I'm not fundamentally opposed to them.

How much squaring would you like to see?

[vcsjones]

How much squaring would you like to see?

Mostly just an observation. I think if we are going to add GetInt64, GetUInt64 etc. then I think symmetry between 64-bit types and 32-bit types is what is throwing me off. e.g. if it exists for UInt32 it should exist for UInt64, same for signed types.

To someone not familiar with the batching and such, it seems odd that we added a bunch of 64-bit things to square but "forgot" the fill variants.

[jeffhandley]

@bartonjs I know you submitted this yourself, but I'm assigning it to you for triage into a milestone.