Batched random for the CSPRNG (and System.Random) #111211
Description
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
intreturning instead ofvoid, 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.