README
¶
fastrand
⚠ API is not stable yet.
Some fast, non-cryptographic PRNG sources, in three variants:
- Plain - the basic implementation. Fastest, but can not be used concurrently without external synchronization.
- Atomic - implementation using atomic operations. Non-locking, can be used concurrently, but a bit slower (especially at high concurrency).
- Sharded - implementation using per-thread (P) sharding. Non-locking, can be used concurrently, fast (even at high concurrency), but does not support explicit seeding.
PRNGs currently implemented:
| Name | State (bits) | Output (bits) | Period | Variants |
|---|---|---|---|---|
| SplitMix64 | 64 | 64 | 264 | Plain, Atomic, Sharded |
| PCG-XSH-RR | 64 | 32 | 264 | Plain, Atomic, Sharded |
| Xoshiro256** | 256 | 64 | 2256-1 | Plain, Sharded |
Planned additions include:
| Name | State (bits) | Output (bits) | Period | Variants |
|---|---|---|---|---|
| PCG-XSL-RR | 128 | 64 | 2128 | Plain, Atomic3, Sharded |
| xorshift128+ | 128 | 64 | 2128-1 | Plain, Atomic3, Sharded |
Performance
Tests run on a Intel(R) Core(TM) i9-8950HK CPU @ 2.90GHz with Turbo Boost disabled. Lower is better.
GOMAXPROCS=1
| PRNG | Plain | Atomic | Sharded |
|---|---|---|---|
| SplitMix64 | 2.02ns | 8.72ns | 7.33ns |
| PCG-XSH-RR | 3.17ns | 11.90ns | 7.33ns |
| Xoshiro256** | 4.57ns | -1 | 12.40ns |
| math/rand | 7.06ns | 24.20ns2 | - |
GOMAXPROCS=8
| PRNG | Plain | Atomic | Sharded |
|---|---|---|---|
| SplitMix64 | 0.29ns | 26.20ns | 1.33ns |
| PCG-XSH-RR | 0.41ns | 13.20ns | 1.34ns |
| Xoshiro256** | 0.81ns | -1 | 2.12ns |
| math/rand | 1.19ns | 72.40ns2 | - |
Usage notes
Atomic variants
The atomic variant currently relies on unsafe to improve the performance of its CAS loops. It does so by calling the unexported procyield function in package runtime. This dependency will be removed in a future release. Usage of unsafe can be disabled by setting the fastrand_nounsafe build tag, at the cost of lower performance.
The state of the atomic variants is not padded/aligned to fill the cacheline: if needed users should pad the structure to avoid false sharing of the cacheline.
Sharded variants
Sharded variants rely on unsafe to implement sharding. They do so by calling the unexported procPin and procUnpin functions in package runtime. These functions are used by other packages (e.g. sync) for the same purpose, so they are unlikely to disappear/change. Usage of unsafe can be disabled by setting the fastrand_nounsafe build tag, at the cost of lower performance.
Sharded variants detect the value of GOMAXPROCS when they are instantiated (with NewShardedXxx). If GOMAXPROCS is increased after a sharded PRNG is instantiated it will yield suboptimal performance, as it may dynamically fallback to the corresponding atomic variant.
Sharded variants use more memory for the state than the other variants: in general they use at least GOMAXPROCS * 64 bytes. This is done to avoid false sharing of cachelines between shards.
Sharded variants do not allow explicit seeding since there is no easy way for a user to obtain a deterministic sequence from these variants (because, in general, goroutines can migrate between threads at any time).
License
1 there is no atomic variant for Xoshiro256** because its large state is not amenable to a performant atomic implementation.
2 the math/rand atomic variant is not a pure non-locking implementation, since it is implemented by guarding a rand.Rand using a sync.Mutex.
3 only for platforms where 128 bit CAS primitives are supported.
Documentation
¶
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
Types ¶
type AtomicPCG ¶
type AtomicPCG struct {
PCG
}
AtomicPCG implements the PCG-XSH-RR generator with atomic state updates.
This generator is safe for concurrent use by multiple goroutines. The zero value is a valid state: Seed() can be called to set a custom seed.
type AtomicSplitMix64 ¶
type AtomicSplitMix64 struct {
SplitMix64
}
AtomicSplitMix64 implements the Java 8 SplittableRandom generator with atomic state updates.
This generator is safe for concurrent use by multiple goroutines. The zero value is a valid state: Seed() can be called to set a custom seed.
func (*AtomicSplitMix64) Seed ¶
func (r *AtomicSplitMix64) Seed(s uint64)
Seed initializes the state with the provided seed.
This function is safe for concurrent use by multiple goroutines.
func (*AtomicSplitMix64) Uint64 ¶
func (r *AtomicSplitMix64) Uint64() uint64
Uint64 returns a random uint64.
This function is safe for concurrent use by multiple goroutines.
type PCG ¶
type PCG struct {
// contains filtered or unexported fields
}
PCG implements the PCG-XSH-RR generator. This generator is not safe for concurrent use by multiple goroutines. The zero value is a valid state: Seed() can be called to set a custom seed.
type ShardedPCG ¶
type ShardedPCG struct {
// contains filtered or unexported fields
}
ShardedPCG implements the PCG-XSH-RR generator with per-thread (per-P) states.
This generator is safe for concurrent use by multiple goroutines. The zero value is a valid state, but it uses a static, all zero seed: use NewShardedPCG to instantiate a ShardedPCG with a random seed.
func NewShardedPCG ¶
func NewShardedPCG() *ShardedPCG
NewShardedPCG creates a valid ShardedPCG instance seeded using crypto/rand.
Increasing the value of GOMAXPROCS after instantiation will likely yield sub-optimal performance.
func (*ShardedPCG) Uint32 ¶
func (p *ShardedPCG) Uint32() uint32
Uint32 returns a random uint32.
This function is safe for concurrent use by multiple goroutines.
type ShardedSplitMix64 ¶
type ShardedSplitMix64 struct {
// contains filtered or unexported fields
}
ShardedSplitMix64 implements the Java 8 SplittableRandom generator with per-thread (per-P) states.
This generator is safe for concurrent use by multiple goroutines. The zero value is a valid state, but it uses a static, all zero seed: use NewShardedSplitMix64 to instantiate a ShardedSplitMix64 with a random seed.
func NewShardedSplitMix64 ¶
func NewShardedSplitMix64() *ShardedSplitMix64
NewShardedSplitMix64 creates a valid ShardedSplitMix64 instance seeded using crypto/rand.
Increasing the value of GOMAXPROCS after instantiation will likely yield sub-optimal performance.
func (*ShardedSplitMix64) Uint64 ¶
func (r *ShardedSplitMix64) Uint64() uint64
Uint64 returns a random uint64.
This function is safe for concurrent use by multiple goroutines.
type ShardedXoshiro256StarStar ¶
type ShardedXoshiro256StarStar struct {
// contains filtered or unexported fields
}
ShardedXoshiro256StarStar implements the Xoshiro256** PRNG with per-thread (per-P) states.
This generator is safe for concurrent use by multiple goroutines. The zero value is not a valid state: use NewShardedXoshiro256StarStar to construct a valid instance. Increasing the value of GOMAXPROCS after instantiation will likely yield sub-optimal performance.
func NewShardedXoshiro256StarStar ¶
func NewShardedXoshiro256StarStar() *ShardedXoshiro256StarStar
NewShardedXoshiro256StarStar creates a valid ShardedXoshiro256StarStar instance seeded using crypto/rand.
Increasing the value of GOMAXPROCS after instantiation will likely yield sub-optimal performance.
func (*ShardedXoshiro256StarStar) Uint64 ¶
func (r *ShardedXoshiro256StarStar) Uint64() uint64
Uint64 returns a random uint64.
This function is safe for concurrent use by multiple goroutines.
type SplitMix64 ¶
type SplitMix64 struct {
// contains filtered or unexported fields
}
SplitMix64 implements the Java 8 SplittableRandom generator. This generator is not safe for concurrent use by multiple goroutines. The zero value is a valid state: Seed() can be called to set a custom seed.
func (*SplitMix64) Seed ¶
func (r *SplitMix64) Seed(s uint64)
Seed initializes the state with the provided seed.
This function is not safe for concurrent use by multiple goroutines.
func (*SplitMix64) Uint64 ¶
func (r *SplitMix64) Uint64() uint64
Uint64 returns a random uint64.
This function is not safe for concurrent use by multiple goroutines.
type Xoshiro256StarStar ¶
type Xoshiro256StarStar struct {
// contains filtered or unexported fields
}
Xoshiro256StarStar implements the Xoshiro256** PRNG.
This generator is not safe for concurrent use by multiple goroutines. The zero value is not a valid state: Seed() must be called before generating random numbers.
func (*Xoshiro256StarStar) Seed ¶
func (r *Xoshiro256StarStar) Seed(s0, s1, s2, s3 uint64)
Seed sets the seed for the generator.
The seed should not be all zeros (i.e. at least one of the four uint64 should be non-zero). This function is not safe for concurrent use by multiple goroutines.
func (*Xoshiro256StarStar) Uint64 ¶
func (r *Xoshiro256StarStar) Uint64() uint64
Uint64 returns a random uint64.
This function is not safe for concurrent use by multiple goroutines.
Source Files