README
¶
randshiro
See https://pkg.go.dev/github.com/silverisntgold/randshiro for documentation
Documentation
¶
Overview ¶
Package randshiro is a Go implementation of the Xoroshiro128++, Xoshiro256++, and Xoshiro512++ pseudo random number generators, a subset of PRNGs from the Xoroshiro/Xoshiro family, created by David Blackman and Sebastiano Vigna.
Useful links ¶
Their "PRNG shootout" can be found here: https://prng.di.unimi.it/
Their paper on this family of PRNGs can be found here: https://vigna.di.unimi.it/papers.php#BlVSLPNG
Explanation ¶
This implementation provides an API somewhat similar to that of the math/rand package, but it is not a drop-in replacement. This is largely a byproduct of how seeding/creation is handled: randshiro automatically seeds each *Gen on creation using crypto/rand, with the ability to fall back to a SplitMix64 implementation if that fails. The internally-used generators themselves are also not accessible by end-users. The user instead calls a factory function that returns a *Gen, which internally manages one of the backing generators. That being said, if you currently use math/rand and your code only calls Intn(), Float32(), and/or Float64(), the only change you'll need to make is replacing your math/rand instantiations with one of the randshiro factory functions.
Local initialization of a math/rand instance may look like:
var rng = rand.New(rand.NewSource(time.Now().UnixNano()))
But using randshiro:
var rngDefault = randshiro.New() var rng128pp = randshiro.New128pp() var rng256pp = randshiro.New256pp() var rng512pp = randshiro.New512pp()
New() is a convenience wrapper for New256pp().
Unlike math/rand, randshiro does not provide a global generator instance. The only reason I can think of for math/rand having this is the high cost of creating and maintaining instances. Since randshiro generators are very cheap to create and maintain it is entirely reasonable, and even recommended, to create a unique Gen instance for each function or goroutine that needs one.
If a *Gen needs to be manually seeded, there is a ManualSeed()
var rng = randshiro.New() var newSeed uint64 = 69420 rng.ManualSeed(newSeed)
Unpredictability can only be restored by re-initializing the generator with another call to a factory function. A dedicated Reseed() method is not provided, since I believe that would make manually seeding too accessible, and you shouldn't be manually seeding these generators unless you are absolutely certain that you need to. Since backing generator instances live behind an interface, it is not required that the factory function used to re-seed is the same that was originally used for that *Gen.
Methods belonging to Gen do no verification of the variables passed into them.
Performance ¶
The main driving factor behind this implementation was the relatively poor performance/memory utilization of math/rand.
At time of writing math/rand uses an additive lagged Fibonacci generator (https://en.wikipedia.org/wiki/Lagged_Fibonacci_generator) with a length of 607 and a tap of 273. This means that for each math/rand instance an array of 607 int64 values (4856 bytes) needs to be seeded and maintained. Xoroshiro128++, Xoshiro256++, and Xoshiro512++ only use 16, 32, and 64 bytes, respectively. Not only are they cheap to keep in memory, they are computationally cheap to properly seed.
The math/rand package also uses an old method for bounding integers/floats to maintain backwards compatible value streams. Replacing those methods is where most of the speed improvements come from. The method this package uses for bounding integers is Daniel Lemire's nearly divisionless method: https://arxiv.org/abs/1805.10941.
On my machine (AMD R7 2700 at 4.05 GHz with 3200MHz memory on Go 1.20.5):
Xoroshiro128++ New: ~225 ns Uint64: ~2.7 ns Intn/Uint64n: ~3.2 ns Float64/Float32: ~2.8 ns FastFloat32: ~3.1ns (~1.55 ns per float32) Xoshiro256++ (randshiro default) New: ~250 ns Uint64: ~3.1 ns Intn/Uint64n: ~3.8 ns Float64/Float32: ~3.1 ns FastFloat32: ~3.8ns (~1.9 ns per float32) IntnWorstCase: ~8.2 ns Normal: ~32 ns (~16 ns per float64) Exponential: ~15 ns Xoshiro512++ New: ~300 ns Uint64: ~4.2 ns Intn/Uint64n: ~5.3 ns Float64/Float32: ~4.2 ns FastFloat32: ~4.9ns (~2.45 ns per float32) math/rand New: ~8100 ns Uint64: ~4.2 ns Uint64Parallel: ~90ns Intn: ~9.6 ns Float64: ~4.3 ns Float32: ~4.9 ns Normal: ~6.6 ns Exponential: ~6 ns
All benchmarks for math/rand (with the exception of Uint64Parallel) are for local instances. Using the global instance in parallel goroutines will absolutely decimate performance. If you're currently doing so, moving to randshiro will likely result in orders of magnitude better performance.
Float64() and Float32() are both extremely fast due to being just a shift and multiplication, and both are capable of uniformly generating all unique real numbers their type can accurately represent in the interval [0.0, 1.0). That is, multiplying their output by 2^53 for float64 or 2^24 for float32 will restore the exact output of the generator before it was converted to a float. This is in contrast to the floating-point methods from math/rand, whose output values are known to be far denser towards 0. If you need to batch-generate float32s, FastFloat32() provides two float32s for a little more than the cost of one Float32() call. There is no speed difference when comparing Float64() vs. Float32(); if you need float64s use Float64() and if you need float32s use Float32()/FastFloat32(). Explanation of the method used can be found at: https://lemire.me/blog/2017/02/28/how-many-floating-point-numbers-are-in-the-interval-01/
IntnWorstCase calls it's Intn() with math.IntMax as the bound (and Intn() just wraps Uint64n()). Intn()/Uint64n() execution time should never exceed this time for *Gen instances backed by Xoshiro256++, but should be much closer to that of the 256ppIntn benchmark (bound of 1,000,000) for reasonable bounds. Generally speaking, Intn()/Uint64n() execution time increases the closer the bound is to math.IntMax. If you need a bound that happens to be a power of two prefer using Uint64bits().
Normal() is provided for generating normally distributed float64s. It uses the Marsaglia polar method (https://en.wikipedia.org/wiki/Marsaglia_polar_method) and returns pairs of independent float64s. NormalDist() can be used to adjust the mean and stddev of the returned float64s.
Exponential() is provided for generating exponentially distributed float64s. It uses inverse transform sampling to generate its output: https://en.wikipedia.org/wiki/Exponential_distribution#Random_variate_generation.
Other members of the Xoroshiro/Xoshiro PRNG family (+ and ** variants) were not included in this package because testing showed near zero performance benefit for doing so. In C/C++ they make more of a difference since a 0.14 ns jump is relatively big when your initial time is already low (0.75 ns -> 0.61 ns for 256++ -> 256+, from the PRNG shootout). But in this Go package much of the execution time is runtime overhead that can't be avoided, so the jump is less meaningful. The jump is also smaller: when testing the 256+ variant I was only seeing ~0.08 ns faster test results vs 256++ (~3.8 ns -> ~3.72 ns for Intn()). No Xoroshiro1024 variants were included because there is no use for them in this package.
Extra ¶
A Fisher-Yates shuffle is also provided as Shuffle(), but it is a function belonging to the randshiro package instead of a method belonging to *Gen. This is done to work around the inability to use generics in methods.
Index ¶
- func Shuffle[T any](rng *Gen, slice []T)
- type Gen
- func (rng *Gen) Bool() bool
- func (rng *Gen) Exponential() float64
- func (rng *Gen) FastFloat32() (float32, float32)
- func (rng *Gen) Float32() float32
- func (rng *Gen) Float64() float64
- func (rng *Gen) IntRange(lowerBound, upperBound int) int
- func (rng *Gen) Intn(bound int) int
- func (rng *Gen) ManualSeed(seed uint64)
- func (rng *Gen) Normal() (float64, float64)
- func (rng *Gen) NormalDist(mean, stddev float64) (float64, float64)
- func (rng *Gen) Perm(n int) []int
- func (rng *Gen) Shuffle()
- func (rng *Gen) Uint64() uint64
- func (rng *Gen) Uint64bits(bitcount uint) uint64
- func (rng *Gen) Uint64n(bound uint64) uint64
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
Types ¶
type Gen ¶
type Gen struct {
// contains filtered or unexported fields
}
Instances are not threadsafe
It is recommended that each goroutine needing a source of random values should create and own a unique Gen instance
func New ¶
func New() *Gen
Creates and cryptographically seeds a *Gen with backing Xoshiro256++ instance
Equivalent to calling New256pp()
func New128pp ¶
func New128pp() *Gen
Creates and cryptographically seeds a *Gen with backing Xoroshiro128++ instance
Original C implementation: https://prng.di.unimi.it/xoroshiro128plusplus.c
func New256pp ¶
func New256pp() *Gen
Creates and cryptographically seeds a *Gen with backing Xoshiro256++ instance
Original C implementation: https://prng.di.unimi.it/xoshiro256plusplus.c
func New512pp ¶
func New512pp() *Gen
Creates and cryptographically seeds a *Gen with backing Xoshiro512++ instance
Original C implementation: https://prng.di.unimi.it/xoshiro512plusplus.c
func (*Gen) Exponential ¶
Returns an exponentially distributed float64 with a rate constant (lambda) of 1
Lambda can be adjusted with: Exponential() / lambda
func (*Gen) FastFloat32 ¶ added in v1.2.0
Returns two independent and uniformly distributed float32s in the interval [0.0, 1.0)
Don't cast the float32s produced by this function to float64: use Float64()
func (*Gen) Float32 ¶
Returns a uniformly distributed float32 in the interval [0.0, 1.0)
Don't cast the float32s produced by this function to float64: use Float64()
func (*Gen) Float64 ¶
Returns a uniformly distributed float64 in the interval [0.0, 1.0)
Don't cast the float64s produced by this function to float32: use Float32() or FastFloat32()
func (*Gen) IntRange ¶
Returns an int in the interval [lowerBound, upperBound)
Makes no range checks on lowerBound/upperBound
func (*Gen) ManualSeed ¶
Manually seeds the backing generator of the calling Gen instance
Unless you are absolutely certain that you need to use this, you don't
func (*Gen) Normal ¶
Returns two independent and normally distributed float64s with mean = 0.0 and stddev = 1.0
Use NormalDist() if you need to adjust mean/stddev
func (*Gen) NormalDist ¶
Returns two independent and normally distributed float64s with user-defined mean and stddev
Makes no range checks on mean/stddev
func (*Gen) Shuffle ¶
func (rng *Gen) Shuffle()
This method only exists to tell you that the real Shuffle() is a function belonging to the randshiro package
func (*Gen) Uint64bits ¶
Returns a uint64 in the interval [0, 2^bitcount)
Makes no range checks on bitcount
Source Files