Code Monkey home page Code Monkey logo

rand's Introduction

rand PkgGoDev CI

Fast, high quality alternative to math/rand and golang.org/x/exp/rand.

Compared to these packages, pgregory.net/rand:

  • is API-compatible with all *rand.Rand methods and all top-level functions except Seed(),
  • is significantly faster, while improving the generator quality,
  • has simpler generator initialization:
    • rand.New() instead of rand.New(rand.NewSource(time.Now().UnixNano()))
    • rand.New(1) instead of rand.New(rand.NewSource(1))
  • is deliberately not providing top-level Seed() and the Source interface.

Benchmarks

All benchmarks were run on Intel(R) Xeon(R) CPU E5-2680 v3 @ 2.50GHz, linux/amd64.

Compared to math/rand:

name                     old time/op    new time/op    delta
Float64-48                  180ns ± 8%       1ns ±12%   -99.66%  (p=0.000 n=10+9)
Intn-48                     186ns ± 2%       1ns ±11%   -99.63%  (p=0.000 n=10+10)
Intn_Big-48                 200ns ± 1%       1ns ±19%   -99.28%  (p=0.000 n=8+10)
Uint64-48                   193ns ± 5%       1ns ± 3%   -99.72%  (p=0.000 n=9+9)
Rand_New                   12.7µs ± 4%     0.1µs ± 6%   -99.38%  (p=0.000 n=10+10)
Rand_ExpFloat64            9.66ns ± 3%    5.90ns ± 3%   -38.97%  (p=0.000 n=10+10)
Rand_Float32               8.90ns ± 5%    2.04ns ± 4%   -77.05%  (p=0.000 n=10+10)
Rand_Float64               7.62ns ± 4%    2.93ns ± 3%   -61.50%  (p=0.000 n=10+10)
Rand_Int                   7.74ns ± 3%    2.92ns ± 2%   -62.30%  (p=0.000 n=10+10)
Rand_Int31                 7.81ns ± 3%    1.92ns ±14%   -75.39%  (p=0.000 n=10+10)
Rand_Int31n                12.7ns ± 3%     3.0ns ± 3%   -76.66%  (p=0.000 n=9+10)
Rand_Int31n_Big            12.6ns ± 4%     3.4ns ±10%   -73.39%  (p=0.000 n=10+10)
Rand_Int63                 7.78ns ± 4%    2.96ns ± 6%   -61.97%  (p=0.000 n=10+9)
Rand_Int63n                26.4ns ± 1%     3.6ns ± 3%   -86.56%  (p=0.000 n=10+10)
Rand_Int63n_Big            26.2ns ± 7%     6.2ns ± 4%   -76.53%  (p=0.000 n=10+10)
Rand_Intn                  14.4ns ± 5%     3.5ns ± 3%   -75.72%  (p=0.000 n=10+10)
Rand_Intn_Big              28.8ns ± 2%     6.0ns ± 6%   -79.03%  (p=0.000 n=10+10)
Rand_NormFloat64           10.7ns ± 6%     6.0ns ± 3%   -44.28%  (p=0.000 n=10+10)
Rand_Perm                  1.34µs ± 1%    0.39µs ± 3%   -70.86%  (p=0.000 n=9+10)
Rand_Read                   289ns ± 5%     104ns ± 5%   -64.00%  (p=0.000 n=10+10)
Rand_Seed                  10.9µs ± 4%     0.0µs ± 6%   -99.69%  (p=0.000 n=10+10)
Rand_Shuffle                790ns ± 4%     374ns ± 5%   -52.63%  (p=0.000 n=10+10)
Rand_ShuffleOverhead        522ns ± 3%     204ns ± 4%   -60.83%  (p=0.000 n=10+10)
Rand_Uint32                7.82ns ± 3%    1.72ns ± 3%   -77.98%  (p=0.000 n=10+9)
Rand_Uint64                9.59ns ± 3%    2.83ns ± 2%   -70.47%  (p=0.000 n=10+9)

name                     old alloc/op   new alloc/op   delta
Rand_New                   5.42kB ± 0%    0.05kB ± 0%   -99.12%  (p=0.000 n=10+10)
Rand_Perm                    416B ± 0%      416B ± 0%      ~     (all equal)

name                     old allocs/op  new allocs/op  delta
Rand_New                     2.00 ± 0%      1.00 ± 0%   -50.00%  (p=0.000 n=10+10)
Rand_Perm                    1.00 ± 0%      1.00 ± 0%      ~     (all equal)

name                     old speed      new speed      delta
Rand_Read                 887MB/s ± 4%  2464MB/s ± 4%  +177.83%  (p=0.000 n=10+10)
Rand_Uint32               511MB/s ± 3%  2306MB/s ± 7%  +350.86%  (p=0.000 n=10+10)
Rand_Uint64               834MB/s ± 3%  2811MB/s ± 4%  +236.85%  (p=0.000 n=10+10)
Compared to golang.org/x/exp/rand:
name                     old time/op    new time/op    delta
Float64-48                  175ns ± 8%       1ns ±12%   -99.65%  (p=0.000 n=10+9)
Intn-48                     176ns ±10%       1ns ±11%   -99.61%  (p=0.000 n=10+10)
Intn_Big-48                 174ns ± 1%       1ns ±19%   -99.18%  (p=0.000 n=9+10)
Uint64-48                   157ns ± 5%       1ns ± 3%   -99.66%  (p=0.000 n=10+9)
Rand_New                   78.8ns ± 6%    78.3ns ± 6%      ~     (p=0.853 n=10+10)
Rand_ExpFloat64            8.94ns ± 6%    5.90ns ± 3%   -34.00%  (p=0.000 n=10+10)
Rand_Float32               9.67ns ± 5%    2.04ns ± 4%   -78.89%  (p=0.000 n=10+10)
Rand_Float64               8.56ns ± 5%    2.93ns ± 3%   -65.74%  (p=0.000 n=10+10)
Rand_Int                   5.75ns ± 3%    2.92ns ± 2%   -49.25%  (p=0.000 n=9+10)
Rand_Int31                 5.72ns ± 5%    1.92ns ±14%   -66.37%  (p=0.000 n=10+10)
Rand_Int31n                17.4ns ± 7%     3.0ns ± 3%   -82.87%  (p=0.000 n=10+10)
Rand_Int31n_Big            17.3ns ± 4%     3.4ns ±10%   -80.57%  (p=0.000 n=10+10)
Rand_Int63                 5.77ns ± 4%    2.96ns ± 6%   -48.73%  (p=0.000 n=10+9)
Rand_Int63n                17.0ns ± 2%     3.6ns ± 3%   -79.13%  (p=0.000 n=9+10)
Rand_Int63n_Big            26.5ns ± 2%     6.2ns ± 4%   -76.81%  (p=0.000 n=10+10)
Rand_Intn                  17.5ns ± 5%     3.5ns ± 3%   -79.94%  (p=0.000 n=10+10)
Rand_Intn_Big              27.5ns ± 3%     6.0ns ± 6%   -78.09%  (p=0.000 n=10+10)
Rand_NormFloat64           10.0ns ± 3%     6.0ns ± 3%   -40.45%  (p=0.000 n=10+10)
Rand_Perm                  1.31µs ± 1%    0.39µs ± 3%   -70.04%  (p=0.000 n=10+10)
Rand_Read                   334ns ± 1%     104ns ± 5%   -68.88%  (p=0.000 n=8+10)
Rand_Seed                  5.36ns ± 2%   33.73ns ± 6%  +528.91%  (p=0.000 n=10+10)
Rand_Shuffle               1.22µs ± 2%    0.37µs ± 5%   -69.36%  (p=0.000 n=10+10)
Rand_ShuffleOverhead        907ns ± 2%     204ns ± 4%   -77.45%  (p=0.000 n=10+10)
Rand_Uint32                5.20ns ± 5%    1.72ns ± 3%   -66.84%  (p=0.000 n=10+9)
Rand_Uint64                5.14ns ± 5%    2.83ns ± 2%   -44.85%  (p=0.000 n=10+9)
Rand_Uint64n               17.6ns ± 3%     3.5ns ± 2%   -80.32%  (p=0.000 n=10+10)
Rand_Uint64n_Big           27.3ns ± 2%     6.0ns ± 7%   -77.97%  (p=0.000 n=10+10)
Rand_MarshalBinary         30.5ns ± 1%     3.8ns ± 4%   -87.70%  (p=0.000 n=8+10)
Rand_UnmarshalBinary       3.22ns ± 4%    3.71ns ± 3%   +15.16%  (p=0.000 n=10+10)

name                     old alloc/op   new alloc/op   delta
Rand_New                    48.0B ± 0%     48.0B ± 0%      ~     (all equal)
Rand_Perm                    416B ± 0%      416B ± 0%      ~     (all equal)
Rand_MarshalBinary          16.0B ± 0%      0.0B       -100.00%  (p=0.000 n=10+10)
Rand_UnmarshalBinary        0.00B          0.00B           ~     (all equal)

name                     old allocs/op  new allocs/op  delta
Rand_New                     2.00 ± 0%      1.00 ± 0%   -50.00%  (p=0.000 n=10+10)
Rand_Perm                    1.00 ± 0%      1.00 ± 0%      ~     (all equal)
Rand_MarshalBinary           1.00 ± 0%      0.00       -100.00%  (p=0.000 n=10+10)
Rand_UnmarshalBinary         0.00           0.00           ~     (all equal)

name                     old speed      new speed      delta
Rand_Read                 764MB/s ± 3%  2464MB/s ± 4%  +222.68%  (p=0.000 n=9+10)
Rand_Uint32               770MB/s ± 5%  2306MB/s ± 7%  +199.35%  (p=0.000 n=10+10)
Rand_Uint64              1.56GB/s ± 5%  2.81GB/s ± 4%   +80.32%  (p=0.000 n=10+10)
Compared to github.com/valyala/fastrand:

Note that fastrand does not generate good random numbers.

name       old time/op  new time/op  delta
Uint64-48  3.20ns ±35%  0.53ns ± 3%  -83.29%  (p=0.000 n=10+9)
Intn-48    1.83ns ±21%  0.69ns ±11%  -62.35%  (p=0.000 n=10+10)

FAQ

Why did you write this?

math/rand is both slow and not up to standards in terms of quality (but can not be changed because of Go 1 compatibility promise). golang.org/x/exp/rand fixes some (but not all) quality issues, without improving the speed, and it seems that there is no active development happening there.

How does this thing work?

This package builds on 4 primitives: raw 64-bit generation using sfc64 or goroutine-local runtime.fastrand64(), floating-point generation using floating-point multiplication, and integer generation in range using 32.64 or 64.128 fixed-point multiplication.

Why is it fast?

The primitives selected are (as far as I am aware) about as fast as you can go without sacrificing quality. On top of that, it is mainly making sure the compiler is able to inline code, and a couple of micro-optimizations.

Why no Source?

In Go (but not in C++ or Rust) it is a costly abstraction that provides no real value. How often do you use a non-default Source with math/rand?

Why no top-level Seed()?

Top-level Seed() would require sharing global mutex-protected state between all top-level functions, which (unlike the goroutine-local state used) does not scale when the parallelism increases.

Why sfc64?

I like it. It has withstood the test of time, with no known flaws or weaknesses despite a lot of effort and CPU-hours spent on finding them. Also, it provides guarantees about period length and distance between generators seeded with different seeds. And it is fast.

Why not...

...pcg?

A bit slow. Otherwise, pcg64dxsm is probably a fine choice.

...xoshiro/xoroshiro?

Quite a bit of controversy and people finding weaknesses in variants of this design. Did you know that xoshiro256**, which author describes as an "all-purpose, rock-solid generator" that "passes all tests we are aware of", fails them in seconds if you multiply the output by 57?

...splitmix?

With 64-bit state and 64-bit output, splitmix64 outputs every 64-bit number exactly once over its 2^64 period — in other words, the probability of generating the same number is 0. A birthday test will quickly find this problem.

...wyrand?

An excellent generator if you are OK with slightly lower quality. Because its output function (unlike splitmix) is not a bijection, some outputs are more likely to appear than others. You can easily observe this non-uniformity with a birthday test. On most modern platforms, top-level functions in this package use goroutine-local wyrand generators provided by the runtime as the best compromise between quality and speed of concurrent execution.

...romu?

Very fast, but relatively new and untested. Also, no guarantees about the period length.

Status

pgregory.net/rand is stable. In addition to API stability, deterministic pseudo-random generation produces the same results on 32-bit and 64-bit architectures, both little-endian and big-endian. Any observable change to these results would only occur together with a major version bump.

License

pgregory.net/rand is licensed under the Mozilla Public License Version 2.0.

rand's People

Contributors

flyingmutant avatar

Stargazers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

Watchers

 avatar  avatar  avatar  avatar  avatar

rand's Issues

Find a good design for Sample

Sample was added in ce7c277, however there are several problematic things:

  • as of go1.18, compiler can't allocate the result on the stack, even when Sample was inline and the k is constant (!); see:
  • the map is not reused between different calls
    • however, placing it into Rand increases its size, and introduces a pointer in a previously pointer-free struct
  • Floyd's sampling algorithm does not guarantee random order, so people are required to read the docs and don't forget to Shuffle if required
  • potential PartialShuffle is much faster and guarantees random order (although it requires mutable slice of size n)
  • having all 4 of Perm, Sample, PartialShuffle and Shuffle is maybe too much

On the other hand, Sample runs in O(k) for both time and memory. Also, algorithm is simple but non-obvious (a bit like Shuffle), as is the linear-search-instead-of-map optimization.

Also, with #1, Sample may be not required at all.

rand64() can not generate zero

In "global_go119.go", maphash.Bytes(maphash.MakeSeed(), nil) can not generate zero, because rthash(nil, 0, state) returns state directly and state must not be 0.

Think about adding Pick2

#2 is about a general purpose Sample, but a relatively common case is func Pick2(n int) (i int, j int). Is it worth adding as a separate function, given that it will only be marginally better than a straightforward loop-based implementation?

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.