math/rand/v2: revised API for math/rand #61716

rsc · 2023-08-02T16:54:16Z

Based on earlier discussions in #60751, #26263, and #21835, as well as discussions with @robpike, I propose adding a new version of math/rand, imported as math/rand/v2, to the standard library. The full text is below but is nearly identical to what we discussed in #60751.

The most direct motivation for this proposal is to clean up math/rand and fix these many lingering problems, especially the use of an outdated generator, slow algorithms, and the unfortunate collision with crypto/rand.Read.

A more indirect but equally important motivation is to set an example for other v2 packages in the standard library. Creating math/rand/v2 will let us work out tooling issues (support for v2 packages in gopls, goimports, and so on) in a relatively rarely used package with fairly low stakes attached before moving on to more commonly used, higher-stakes packages like sync/v2 or encoding/json/v2.

This proposal establishes the pattern for v2 packages in the standard library, namely that they are subdirectories of the original package and that the starting point for the API is the original package, with each deviation clearly justified. In particular, v2 packages are not an opportunity to redesign something from scratch "just because". The existing APIs work well, and deviations should be carefully considered. A from-scratch new API is just as likely (probably more likely) to introduce new problems as it is to fix existing ones.

Once math/rand/v2 has shipped, we would tag and delete x/exp/rand. This would keep programs that already use x/exp/rand working (by reference to the tagged version or older versions of x/exp) but allow us to delete the code from the main branch of x/exp, making clear that development on it has ended.

A prototype of these math/rand/v2 changes can be found at https://go.dev/cl/502506 and the CLs below it in the stack.

Proposal

The math/rand/v2 API would use math/rand as a starting point and then make the following backwards incompatible changes:

Remove Rand.Read and top-level Read. It is almost always a mistake to pretend that a pseudo-random generator is a good source of arbitrarily long byte sequences. The kinds of simulations and non-deterministic algorithms for which math/rand is a good choice almost never need byte sequences. Read is the only common piece of API between math/rand and crypto/rand, and code should essentially always use crypto/rand.Read instead. (math/rand.Read and crypto/rand.Read are problematic because they have the the same signature; math/rand.Int and crypto/rand.Int also both exist, but with different signatures, meaning code never accidentally mistakes one for the other.)
Remove Source.Seed, Rand.Seed, and top-level Seed. Top-level Seed is deprecated as of Go 1.20. Source.Seed and Rand.Seed assume that the underlying source can be seeded by a single int64, which is only true of a limited number of sources. Specific source implementations can provide Seed methods with appropriate signatures, or none at all for generators that cannot be reseeded; the details of seeding do not belong in the general interface.

Note that removing top-level Seed means that the top-level functions like Int will always be randomly seeded rather than deterministically seeded. math/rand/v2 will not pay attention to the randautoseed GODEBUG setting that math/rand does; auto-seeding for top-level functions is the only mode. This means in turn that the specific PRNG algorithm used by the top-level functions is unspecified and can change from release to release without breaking any existing code.
Change the Source interface to have a single Uint64() uint64 method, replacing Int63() int64. The latter was overfitting to the original Mitchell & Reeds LFSR generator. Modern generators can provide uint64s, and uint64s have fewer special cases at call sites.
Remove Source64, which is unnecessary now that Source provides the Uint64 method.
Use a more straightforward implementation in Float32 and Float64. Taking Float64 as an example, it originally used float64(r.Int63()) / (1<<63), but this has the problem of occasionally rounding up to 1.0, which Float64 must not. We tried changing it to float64(r.Int63n(1<<53) / (1<<53), which avoids the rounding problem, but we decided it was a backwards compatibile change to break the value streams that rand.Rand generators, and instead added a retry loop for the rare 1.0 case. Now we can make the breaking change, which is simpler and faster.

Note that some people have observed that the simple division does not make use of all the possible float64 values in the range [0, 1). For example values like 1/(1<<54), 1/(1<<55), 3/(1<<55), and so on are not generated at all, both in today's math/rand and in this simpler algorithm. Only the values 0 and 1/(1<<53) are, not the ones in between. It is possible to introduce even more complex algorithms to spread out the low values more while preserving something that can be deemed a uniform distribution, but these algorithms seem like overkill. The simple division should continue to suffice.
(New since #60751.) Correct bias problems in ExpFloat64 and NormFloat64. @flyingmutant reports that these have detectable bias, perhaps due to a mistake in porting the Ziggurat algorithms from float32 to float64. We can take this opportunity to correct those.
Implement Rand.Perm in terms of Rand.Shuffle. Shuffle is a bit more efficient, and then we have only one implementation. It has been suggested elsewhere to remove Rand.Perm instead, but keeping it costs little (especially if implemented in terms of Shuffle) and avoids unnecessary churn for users.
Rename Intn, Int31, Int31n, Int63, Int64n to IntN, Int32, Int32N, Int64, Int64N. The 31 and 63 in the names are unnecessarily pedantic and confusing, and the capitalized N is more idiomatic for a second "word" in the name in Go. Note: The capital N's in the names are a change from #60751.
Add Uint32, Uint32N, Uint64, Uint64N, Uint, UintN, both as top-level functions and methods on Rand. At the least, we need Uint64 to provide access to the widest values that the Source can provide. But we may as well complete the set while we are here. Note: The capital N's in the names are a change from #60751.
(New since #60751) Add a generic top-level function N that is like Int64N or Uint64N but works for any integer type. In particular this allows using rand.N(1*time.Minute) to get a random duration in the range [0, 1*time.Minute).
Use Lemire's algorithm in N, IntN, UintN, and so on. Preliminary benchmarks show a 40% savings compared to v1 Int31n and a 75% savings compared to v1 Int63n. (Like with Float64, since this changes the values returned, it is a breaking change that can only be applied in math/rand/v2.)
Add a new Source implementation, PCG-DXSM, with this API:
```
func NewPCG(seed1, seed2 uint64) *PCG
type PCG struct { ... }
func (p *PCG) Uint64() uint64
func (p *PCG) Seed(seed1, seed2 uint64)
func (p *PCG) MarshalBinary() ([]byte, error)
func (p *PCG) UnmarshalBinary(data []byte) error
```
PCG is a simple, efficient algorithm with good statistical randomness properties. The DXSM variant was introduced by the author specifically to correct a rare, obscure shortcoming in the original (PCG-XSLRR) and is now the default generator in Numpy.

PCG is provided for people who are writing simulations and need a seeded, deterministic source of randomness suitable for most purposes. Note that PCG is not assumed in any code. In particular the top-level functions need not use PCG (and in the current prototype do not). If in the future we add another algorithm, it will sit alongside PCG as a true peer.

Note: MarshalBinary and UnmarshalBinary are new since #60751.
Remove the Mitchell & Reeds LFSR generator and NewSource. An alternative to removing it would be to give it a name like NewLFSR or NewMitchellReeds, but that would serve no purpose. The obvious purpose would be to provide the original math/rand source so that code that needs to reproduce the exact math/rand outputs can do so. But the other changes to Rand, in routines like Intn and Float64, change the derived values from Rand's methods for a given Source input stream. Since preserving the math/rand Source stream would not suffice to preserve the math/rand Rand stream, preserving the math/rand Source is not worthwhile. Programs that need exactly the math/rand value streams can continue to use that package; it will not be removed.
(New since #60751 and the original proposal in this issue) Add a new Source implementation, ChaCha8, with this API:
```
func NewChaCha8(seed [32]byte) *ChaCha8
type ChaCha8 struct { ... }
func (c *ChaCha8) Uint64() uint64
func (c *ChaCha8) Seed(seed [32]byte)
func (c *ChaCha8) MarshalBinary() ([]byte, error)
func (c *ChaCha8) UnmarshalBinary(data []byte) error
```
ChaCha8 is a cryptographically-strong random number generator derived from the ChaCha8 stream cipher. It provides security equivalent to ChaCha8 encryption.
(New since #60751 and the original proposal in this issue) Use a per-OS-thread ChaCha8 for the global random generator, both in math/rand/v2 and in math/rand (when unseeded). The current implementation uses a per-OS-thread wyrand, which was fine compared to the Mitchell/Reeds/Thompson generator but is not really great compared to PCG or ChaCha8. In particular, it is strange for the top-level randomness to be less studied and less robust than the two concrete implementations provided. Using ChaCha8 also gives the default top-level randomness real cryptographic strength, turning accidental use of math/rand where crypto/rand would be more appropriate into less of a security problem. Using ChaCha8 runs slower than using wyrand, but it is about as fast as the current sync.Mutex-locked generator in math/rand (~6ns per value on my 2019 Intel MacBook Pro).

Differences since previous discussion

The differences between this proposal and what we discussed in #60751 are:

Renamed Intn, Int64n, etc to IntN, Int64N, etc, capitalizing the N.
Added top-level generic rand.N function, which is like tbe current rand.Int64n or rand.Uint64n but works for any integer type.
Added MarshalBinary and UnmarshalBinary methods to the new PCG type.
Adjust the ExpFloat64 and NormFloat64 algorithms to remove bias. (Thanks to @zephyrtronium.)
Add ChaCha8 alongside PCG.
Use ChaCha8 for global generator.

These differences are also marked above.

Discussion Summary

Summarizing the discussion on #60751:

There was a suggestion to parameterize the top-level Intn, Uintn, Int64n, Uint64n etc functions. The single N function does that instead.
There was a suggestion to make PCG implement BinaryMarshaler and BinaryUnmarshaler, which has been accepted.
There was a suggestion to use more efficient algorithms for ExpFloat64 and NormFloat64, which has been accepted.
There was a suggestion to use more efficient but subtly biased fixed-point multiplication-based algorithms for Int64N and related functions. Careful benchmarks do not seem to bear out the benefits of these, so I've left them using a variant of Lemire's algorithm that is less efficient only in the rare cases where it is correcting the subtle bias.
There was a suggestion to use a more complex implementation of Float64 that spreads some of the probability of very small values around to even smaller values that would otherwise never be generated. Specifically, values betwen 0 and 1/2⁵³ are never generated, so the suggestion is to generate 0 and 1/2⁵³ with probability less than the current 1-in-2⁵³ and reuse some of that probability for values in between. This does not seem worth the cost for two reasons. First, the simple division algorithm produces numbers that have uniform gaps between them. That is, the gaps near 1 are the same size as the gaps near zero. That specific uniformity is lost if you get clever about creating smaller gaps near zero. Second, many times the result of Float32 or Float64 is scaled or translated or both (Float64()*X + Y). The +Y undoes all the work to create those gaps, and the *X scales the gaps so that in the new range it's still not true that every possible floating point value in the range will be generated. (This basic rationale is in the proposal text below as well, since it was included in the text used to begin the discussion at #60751.)
There was a suggestion to remove the indirection of the Source abstraction, but that abstraction is important for being able to substitute a different pseudo-random algorithm, especially in simulations that care about the algorithm. The suggestion was motivated by performance reasons, but I am confident any performance problems can be handled by devirtualization in the compiler.
There was a suggestion to use v2/math/rand instead, but generally the v2 seems like a "lower order bit" than the package path, and so it should come after the package path. That form would also break 'go test math...' or at least not include math/rand. Another, related problem with v2/math/rand is that at some point we may want to break the standard library into separate modules. For example a crypto module could provide crypto/.... If some crypto packages are v2, like crypto/tls/v2, then there is no problem with the module named crypto providing both crypto/tls and crypto/tls/v2. However, the module named crypto cannot provide v2/crypto/tls, because strings.HasPrefix(v2/crypto/tls, crypto/) == false. I don't know whether it's a good idea to break the standard library up this way or not, but I think we want to at least leave that door accessible in case we want to walk through it. v2/crypto/tls or v2/math/rand would block that door. It is worth noting that the standard library is not special in being allowed to introduce v2 subdirectories for specific packages. Any module can do this, and in particular v1 modules can do this.
There was a suggestion to leave the top-level Read removed but add back rand.Rand.Read. The need for this is unclear, so it seems worth leaving out for now.
There was a suggestion to provide access to a goroutine-safe implementation of Source. That is not a common need, and it can be implemented trivially as a wrapper around rand.Uint64.
There was a suggestion to rename the package from math/rand to math/pseudorand, to try to draw more of a distinction between math/rand and crypto/rand. I have not done this, for a few reasons. First, even crypto/rand can be pseudo-random, just in a cryptographically stronger way. Second, the names are long and not Go-like. Third, there is already an established name for this package, and it is math/rand. If you notice there are packages named math/rand and math/rand/v2, the relationship is clear. If you notice packages named math/rand and math/pseudorand, the relationship is much less clear. Just as we are conservative about changing established API from v1 to v2, we should be conservative about changing established names.
There was a hyperbolic suggestion that Go "would do a great service to its users by making it as hard as possible to use any RNG other than crypto/rand." We are not going to take that approach, but we've added ChaCha8 as a source you can construct explicitly, and we've also changed the top-level functions to use ChaCha8 underneath, although this is not a documented guarantee.

The text was updated successfully, but these errors were encountered:

rsc · 2023-08-02T18:03:21Z

This proposal has been added to the active column of the proposals project
and will now be reviewed at the weekly proposal review meetings.
— rsc for the proposal review group

zephyrtronium · 2023-08-02T19:00:32Z

Adjust the ExpFloat64 and NormFloat64 algorithms to remove bias. (Not implemented yet.)

I have an example implementation of this in https://github.com/zephyrtronium/pgregory_rand/tree/master/misc/practrand which I used to verify that it does resolve the bias detected by practrand. My approach uses recalculated 1024-step ziggurats specifically built for 64-bit PRNGs to improve the rejection procedure efficiency, which gives about -6% ns/op versus the 128-step normal ziggurat and +4% ns/op versus the 256-step exponential one (possibly due to bounds checking? I can't investigate at the moment), at the cost of the tables being a collective 48 kB instead of 4.5 kB.

goos: linux
goarch: amd64
pkg: math/rand
cpu: 12th Gen Intel(R) Core(TM) i5-1235U
               │ /home/branden/old.bench │      /home/branden/new.bench       │
               │         sec/op          │   sec/op     vs base               │
NormFloat64-12               3.961n ± 2%   3.709n ± 0%  -6.35% (p=0.000 n=20)
ExpFloat64-12                3.801n ± 1%   3.974n ± 0%  +4.56% (p=0.000 n=20)
geomean                      3.880n        3.840n       -1.04%

An alternative implementation is to use the same tables but adjusting the input to avoid reusing random bits between the step selection and the final output, which would leave tables unchanged and should result in the same performance but still resolve the bias.

This is out of band for the proposal per se, but would it be appropriate for me to send in a CL based on 502506 implementing the new ziggurats? I don't know whether or how I can do that.

rsc · 2023-08-02T20:01:32Z

@zephyrtronium If you can send a CL with the new code that'd be great. We will not be able to submit it as is, but I can lift it from there and add it to the v2 stack. 48kB of table is a lot more than 4.5kB, so your alternative leaving the tables unchanged sounds like the right approach. Thanks!

joeshaw · 2023-08-02T20:08:18Z

Creating math/rand/v2 will let us work out tooling issues (support for v2 packages in gopls, goimports, and so on)

Typically packages are identified in code by the last portion of their import path. This would be undesirable for packages versioned this way, so is the subtext here that tools like goimports would recognize math/rand/v2 and write import statements with renamed identifiers (import rand "math/rand/v2")?

rsc · 2023-08-02T20:18:05Z

@joeshaw Tools like goimports already recognize math/rand/v2 and understand that it is 'rand' even without a renamed import. Such paths are common already for the root package of a module that is >=v2.

See: golang/go#61716 https://go-review.googlesource.com/c/go/+/502502/3

gopherbot · 2023-08-04T22:01:30Z

Change https://go.dev/cl/516275 mentions this issue: math/rand: don't reuse bits in ziggurat variates

gopherbot · 2023-08-08T02:51:23Z

Change https://go.dev/cl/502500 mentions this issue: math/rand/v2: add, optimize N, UintN, Uint32N, Uint64N

gopherbot · 2023-08-08T02:51:24Z

Change https://go.dev/cl/502506 mentions this issue: math/rand/v2: delete Mitchell/Reeds source

gopherbot · 2023-08-08T02:51:25Z

Change https://go.dev/cl/516859 mentions this issue: math/rand/v2: add ChaCha8

gopherbot · 2023-08-08T02:51:25Z

Change https://go.dev/cl/516857 mentions this issue: math/rand/v2: rename various functions

gopherbot · 2023-08-08T02:51:26Z

Change https://go.dev/cl/502504 mentions this issue: math/rand/v2: simplify Perm

gopherbot · 2023-08-08T02:51:27Z

Change https://go.dev/cl/502496 mentions this issue: math/rand/v2: update benchmarks

gopherbot · 2023-08-08T02:51:28Z

Change https://go.dev/cl/502497 mentions this issue: math/rand/v2: remove Read

gopherbot · 2023-08-08T02:51:29Z

Change https://go.dev/cl/516858 mentions this issue: math/rand/v2: clean up regression test

gopherbot · 2023-08-08T02:51:30Z

Change https://go.dev/cl/502499 mentions this issue: math/rand/v2: change Source to use uint64

gopherbot · 2023-08-08T02:51:30Z

Change https://go.dev/cl/516860 mentions this issue: math/rand, math/rand/v2: use ChaCha8 for global rand

gopherbot · 2023-08-08T02:51:32Z

Change https://go.dev/cl/502503 mentions this issue: math/rand/v2: optimize Float32, Float64

gopherbot · 2023-08-08T02:51:32Z

Change https://go.dev/cl/502505 mentions this issue: math/rand/v2: add PCG-DXSM

gopherbot · 2023-08-08T02:51:33Z

Change https://go.dev/cl/502495 mentions this issue: math/rand/v2: start of new API

gopherbot · 2023-08-08T02:51:34Z

Change https://go.dev/cl/502498 mentions this issue: math/rand/v2: remove Rand.Seed

rsc · 2023-08-08T03:24:45Z

People seem overall happy with this proposal, since we already hashed almost everything out in the previous discussion. I've updated the CL stack with recent adjustments and updated benchmarks. Thanks to @zephyrtronium for contributing fixes for ExpFloat64 and NormFloat64, now included in the stack.

After discussion with @FiloSottile, I've added a ChaCha8 source alongside the PCG source, so that people who want cryptographically strong randomness can have it.

rsc · 2023-08-08T03:27:04Z

Also based on discussion with @FiloSottile, I've changed the implementation of the top-level random functions to use an unexported per-OS-thread ChaCha8 source. (Anyone who wants this in Source form can build a trivial Source out of rand.Uint64, as noted before.)

The top-level per-thread ChaCha8 source is slower than the per-thread wyrand source I had been using in the stack, but it's about the same speed as the top-level locked source in math/rand. We eliminate the lock but use the cost savings to pay for cryptographic randomness by default instead. This seems like a reasonable trade. In particular, wyrand is less well understood than either PCG or ChaCha8, so it seems strange to have a package that exports PCG and ChaCha8 and then uses something less robust implicitly in the top-level functions.

I've timed using each of them, and ChaCha8 is a little faster than PCG on 32-bit, a little slower on 64-bit, but overall quite similar. Both are slower than wyrand, but wyrand is fairly trivial. Given the choice between PCG and ChaCha8 for the top-level randomness, ChaCha8 has a similar cost but provides cryptographic strength. That makes accidental use of math/rand/v2 instead of crypto/rand much less of a problem.

ChaCha8 requires maintaining 304 bytes of extra state in the per-OS-thread m structure in the runtime.

[This is a separate comment so people can thumbs-up or thumbs-down the idea of using ChaCha8 as the global generator separate from the other update.]

rsc · 2023-08-08T03:31:29Z

If we do keep ChaCha8 as the global generator and commit to having some cryptographic global generator like ChaCha8 in the future, we could potentially bring back both the top-level Read function and the Rand.Read method.

In the earlier discussion, some people asked what to do about getting short byte sequences from the PRNG. We essentially sacrificed the convenience of Read for the security of forcing people over to crypto/rand. But if we make the top-level Read backed by a cryptographic generator, we could bring Read back and have both convenience and security.

Not entirely sure whether this is worth doing, but it seems worth discussing.

[This is a separate comment so people can thumbs-up or thumbs-down the idea of bringing Read back separate from the other updates.]

Merovius · 2023-08-08T04:31:40Z

@rsc

ChaCha8 requires maintaining 304 bytes of extra state in the per-OS-thread m structure in the runtime.

If I checked correctly, an m is currently 408 bytes, so this seems like a lot? Is it possible this might slow down unrelated code by the extra size?

If we do keep ChaCha8 as the global generator and commit to having some cryptographic global generator like ChaCha8 in the future, we could potentially bring back both the top-level Read function and the Rand.Read method.

ISTM that crypto/rand.Read is still more secure, is it not? AIUI it uses facilities by the kernel to get data, which I would tend to trust more than the Go runtime to do this correctly (no offense - common OS kernels just have more eyes on them).

robpike · 2023-08-08T07:29:57Z

I feel that 304 bytes is too much for the default source. Making chacha8 easy to use is great, but let's keep the default one as PCG because it is very small. 19 times smaller in fact.

rsc · 2023-08-08T15:03:36Z

The m struct tends to be noise compared to the per-thread stack allocated by the operating system.
On my MacBook Pro, for example, an m's stack is 512 kB. Another 304 bytes is noise.
Even on the systems where C is not involved and Go allocates the stacks, we allocate 8 kB.

@aclements points out that the state should be per-P, in which case there are even fewer:
on a 16-core machine the cost would be under 5kB total for the process.
(As a relative fraction compared to OS stacks it remains noise.)

gopherbot · 2023-10-05T02:16:48Z

Change https://go.dev/cl/532756 mentions this issue: math/rand/v2: add ChaCha8 doc comments and binary methods

This is the beginning of the math/rand/v2 package from proposal #61716. Start by copying old API. This CL copies math/rand/* to math/rand/v2 and updates references to math/rand to add v2 throughout. Later CLs will make the v2 changes. For #61716. Change-Id: I1624ccffae3dfa442d4ba2461942decbd076e11b Reviewed-on: https://go-review.googlesource.com/c/go/+/502495 Reviewed-by: Dmitri Shuralyov <dmitshur@google.com> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com> Auto-Submit: Russ Cox <rsc@golang.org> Reviewed-by: Rob Pike <r@golang.org>

Int31 -> Int32 Int31n -> Int32N Int63 -> Int64 Int63n -> Int64N Intn -> IntN The 31 and 63 are pedantic and confusing: the functions should be named for the type they return, same as all the others. The lower-case n is inconsistent with Go's usual CamelCase and especially problematic because we plan to add 'func N'. Capitalize the n. For #61716. Change-Id: Idb1a005a82f353677450d47fb612ade7a41fde69 Reviewed-on: https://go-review.googlesource.com/c/go/+/516857 Auto-Submit: Russ Cox <rsc@golang.org> Reviewed-by: Robert Griesemer <gri@google.com> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>

In math/rand, Read is deprecated. Remove in v2. People should use crypto/rand if they need long strings. For #61716. Change-Id: Ib254b7e1844616e96db60a3a7abb572b0dcb1583 Reviewed-on: https://go-review.googlesource.com/c/go/+/502497 Reviewed-by: Rob Pike <r@golang.org> Reviewed-by: Dmitri Shuralyov <dmitshur@google.com> Auto-Submit: Russ Cox <rsc@golang.org> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>

Add more test cases. Replace -printgolden with -update, which rewrites the files for us. For #61716. Change-Id: I7c4c900ee896042429135a21971a56ebe16b6a66 Reviewed-on: https://go-review.googlesource.com/c/go/+/516858 Reviewed-by: Rob Pike <r@golang.org> Reviewed-by: David Chase <drchase@google.com> Auto-Submit: Russ Cox <rsc@golang.org> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>

Removing Rand.Seed lets us remove lockedSource as well, along with the ambiguity in globalRand about which source to use. For #61716. Change-Id: Ibe150520dd1e7dd87165eacaebe9f0c2daeaedfd Reviewed-on: https://go-review.googlesource.com/c/go/+/502498 Reviewed-by: Dmitri Shuralyov <dmitshur@google.com> Reviewed-by: Rob Pike <r@golang.org> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com> Auto-Submit: Russ Cox <rsc@golang.org>

Change the benchmarks to use the result of the calls, as I found that in certain cases inlining resulted in discarding part of the computation in the benchmark loop. Add various benchmarks that will be relevant in future CLs. goos: linux goarch: amd64 pkg: math/rand/v2 cpu: AMD Ryzen 9 7950X 16-Core Processor │ 220860f76f.amd64 │ │ sec/op │ SourceUint64-32 1.555n ± 1% GlobalInt64-32 2.071n ± 1% GlobalInt63Parallel-32 0.1023n ± 1% GlobalUint64-32 5.193n ± 1% GlobalUint64Parallel-32 0.2341n ± 0% Int64-32 2.056n ± 2% Uint64-32 2.077n ± 2% GlobalIntN1000-32 4.077n ± 2% IntN1000-32 3.476n ± 2% Int64N1000-32 3.059n ± 1% Int64N1e8-32 2.942n ± 1% Int64N1e9-32 2.932n ± 1% Int64N2e9-32 2.925n ± 1% Int64N1e18-32 3.116n ± 1% Int64N2e18-32 4.067n ± 1% Int64N4e18-32 4.054n ± 1% Int32N1000-32 2.951n ± 1% Int32N1e8-32 3.102n ± 1% Int32N1e9-32 3.535n ± 1% Int32N2e9-32 3.514n ± 1% Float32-32 2.760n ± 1% Float64-32 2.284n ± 1% ExpFloat64-32 3.757n ± 1% NormFloat64-32 3.837n ± 1% Perm3-32 35.23n ± 2% Perm30-32 208.8n ± 1% Perm30ViaShuffle-32 111.7n ± 1% ShuffleOverhead-32 101.1n ± 1% Concurrent-32 2.108n ± 7% goos: darwin goarch: arm64 pkg: math/rand/v2 cpu: Apple M1 │ 220860f76f.arm64 │ │ sec/op │ SourceUint64-8 2.316n ± 1% GlobalInt64-8 2.183n ± 1% GlobalInt63Parallel-8 0.4331n ± 0% GlobalUint64-8 4.377n ± 2% GlobalUint64Parallel-8 0.9237n ± 0% Int64-8 2.538n ± 1% Uint64-8 2.604n ± 1% GlobalIntN1000-8 3.857n ± 2% IntN1000-8 3.822n ± 2% Int64N1000-8 3.318n ± 0% Int64N1e8-8 3.349n ± 1% Int64N1e9-8 3.317n ± 2% Int64N2e9-8 3.317n ± 2% Int64N1e18-8 3.542n ± 1% Int64N2e18-8 5.087n ± 0% Int64N4e18-8 5.084n ± 0% Int32N1000-8 3.208n ± 2% Int32N1e8-8 3.610n ± 1% Int32N1e9-8 4.235n ± 0% Int32N2e9-8 4.229n ± 1% Float32-8 3.468n ± 0% Float64-8 3.447n ± 0% ExpFloat64-8 4.567n ± 0% NormFloat64-8 4.821n ± 0% Perm3-8 28.89n ± 0% Perm30-8 175.7n ± 0% Perm30ViaShuffle-8 153.5n ± 0% ShuffleOverhead-8 119.8n ± 1% Concurrent-8 2.433n ± 3% goos: linux goarch: 386 pkg: math/rand/v2 cpu: AMD Ryzen 9 7950X 16-Core Processor │ 220860f76f.386 │ │ sec/op │ SourceUint64-32 2.370n ± 1% GlobalInt64-32 3.569n ± 1% GlobalInt63Parallel-32 0.3221n ± 1% GlobalUint64-32 8.797n ± 10% GlobalUint64Parallel-32 0.6351n ± 0% Int64-32 2.612n ± 2% Uint64-32 3.350n ± 1% GlobalIntN1000-32 5.892n ± 1% IntN1000-32 4.546n ± 1% Int64N1000-32 14.59n ± 1% Int64N1e8-32 14.76n ± 2% Int64N1e9-32 16.57n ± 1% Int64N2e9-32 14.54n ± 1% Int64N1e18-32 16.14n ± 1% Int64N2e18-32 18.10n ± 1% Int64N4e18-32 18.65n ± 1% Int32N1000-32 3.560n ± 1% Int32N1e8-32 3.770n ± 2% Int32N1e9-32 4.098n ± 0% Int32N2e9-32 4.179n ± 1% Float32-32 21.18n ± 4% Float64-32 20.60n ± 2% ExpFloat64-32 13.07n ± 0% NormFloat64-32 7.738n ± 2% Perm3-32 36.73n ± 1% Perm30-32 211.9n ± 1% Perm30ViaShuffle-32 165.2n ± 1% ShuffleOverhead-32 133.9n ± 1% Concurrent-32 3.287n ± 2% For #61716. Change-Id: I2f0938eae4b7bf736a8cd899a99783e731bf2179 Reviewed-on: https://go-review.googlesource.com/c/go/+/502496 Auto-Submit: Russ Cox <rsc@golang.org> Reviewed-by: Dmitri Shuralyov <dmitshur@google.com> Reviewed-by: Rob Pike <r@golang.org> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>

This should make Uint64-using functions faster and leave other things alone. It is a mystery why so much got faster. A good cautionary tale not to read too much into minor jitter in the benchmarks. goos: linux goarch: amd64 pkg: math/rand/v2 cpu: AMD Ryzen 9 7950X 16-Core Processor │ 220860f76f.amd64 │ 11ad9fdddc.amd64 │ │ sec/op │ sec/op vs base │ SourceUint64-32 1.555n ± 1% 1.335n ± 1% -14.15% (p=0.000 n=20) GlobalInt64-32 2.071n ± 1% 2.046n ± 1% ~ (p=0.016 n=20) GlobalInt63Parallel-32 0.1023n ± 1% 0.1037n ± 1% +1.37% (p=0.002 n=20) GlobalUint64-32 5.193n ± 1% 2.075n ± 0% -60.06% (p=0.000 n=20) GlobalUint64Parallel-32 0.2341n ± 0% 0.1013n ± 1% -56.74% (p=0.000 n=20) Int64-32 2.056n ± 2% 1.726n ± 2% -16.10% (p=0.000 n=20) Uint64-32 2.077n ± 2% 1.673n ± 1% -19.46% (p=0.000 n=20) GlobalIntN1000-32 4.077n ± 2% 3.895n ± 2% -4.45% (p=0.000 n=20) IntN1000-32 3.476n ± 2% 3.403n ± 1% -2.10% (p=0.000 n=20) Int64N1000-32 3.059n ± 1% 3.053n ± 2% ~ (p=0.131 n=20) Int64N1e8-32 2.942n ± 1% 2.718n ± 1% -7.60% (p=0.000 n=20) Int64N1e9-32 2.932n ± 1% 2.712n ± 1% -7.50% (p=0.000 n=20) Int64N2e9-32 2.925n ± 1% 2.690n ± 1% -8.03% (p=0.000 n=20) Int64N1e18-32 3.116n ± 1% 3.084n ± 2% ~ (p=0.425 n=20) Int64N2e18-32 4.067n ± 1% 4.026n ± 1% -1.02% (p=0.007 n=20) Int64N4e18-32 4.054n ± 1% 4.049n ± 2% ~ (p=0.204 n=20) Int32N1000-32 2.951n ± 1% 2.730n ± 0% -7.49% (p=0.000 n=20) Int32N1e8-32 3.102n ± 1% 2.916n ± 2% -6.03% (p=0.000 n=20) Int32N1e9-32 3.535n ± 1% 3.375n ± 1% -4.54% (p=0.000 n=20) Int32N2e9-32 3.514n ± 1% 3.292n ± 1% -6.30% (p=0.000 n=20) Float32-32 2.760n ± 1% 2.673n ± 1% -3.13% (p=0.000 n=20) Float64-32 2.284n ± 1% 2.485n ± 1% +8.80% (p=0.000 n=20) ExpFloat64-32 3.757n ± 1% 3.577n ± 2% -4.78% (p=0.000 n=20) NormFloat64-32 3.837n ± 1% 3.797n ± 2% ~ (p=0.204 n=20) Perm3-32 35.23n ± 2% 35.79n ± 2% ~ (p=0.298 n=20) Perm30-32 208.8n ± 1% 205.1n ± 1% -1.82% (p=0.000 n=20) Perm30ViaShuffle-32 111.7n ± 1% 111.2n ± 2% ~ (p=0.273 n=20) ShuffleOverhead-32 101.1n ± 1% 100.5n ± 2% ~ (p=0.878 n=20) Concurrent-32 2.108n ± 7% 2.188n ± 5% ~ (p=0.417 n=20) goos: darwin goarch: arm64 pkg: math/rand/v2 │ 220860f76f.arm64 │ 11ad9fdddc.arm64 │ │ sec/op │ sec/op vs base │ SourceUint64-8 2.316n ± 1% 2.272n ± 1% -1.86% (p=0.000 n=20) GlobalInt64-8 2.183n ± 1% 2.155n ± 1% ~ (p=0.122 n=20) GlobalInt63Parallel-8 0.4331n ± 0% 0.4352n ± 0% +0.48% (p=0.000 n=20) GlobalUint64-8 4.377n ± 2% 2.173n ± 1% -50.35% (p=0.000 n=20) GlobalUint64Parallel-8 0.9237n ± 0% 0.4340n ± 0% -53.02% (p=0.000 n=20) Int64-8 2.538n ± 1% 2.544n ± 1% ~ (p=0.189 n=20) Uint64-8 2.604n ± 1% 2.552n ± 1% -1.98% (p=0.000 n=20) GlobalIntN1000-8 3.857n ± 2% 3.856n ± 0% ~ (p=0.051 n=20) IntN1000-8 3.822n ± 2% 3.820n ± 0% -0.05% (p=0.001 n=20) Int64N1000-8 3.318n ± 0% 3.219n ± 2% -2.98% (p=0.000 n=20) Int64N1e8-8 3.349n ± 1% 3.221n ± 2% -3.79% (p=0.000 n=20) Int64N1e9-8 3.317n ± 2% 3.276n ± 2% -1.24% (p=0.001 n=20) Int64N2e9-8 3.317n ± 2% 3.217n ± 0% -3.01% (p=0.000 n=20) Int64N1e18-8 3.542n ± 1% 3.502n ± 2% -1.16% (p=0.001 n=20) Int64N2e18-8 5.087n ± 0% 4.968n ± 1% -2.33% (p=0.000 n=20) Int64N4e18-8 5.084n ± 0% 4.963n ± 0% -2.39% (p=0.000 n=20) Int32N1000-8 3.208n ± 2% 3.189n ± 1% -0.58% (p=0.001 n=20) Int32N1e8-8 3.610n ± 1% 3.514n ± 1% -2.67% (p=0.000 n=20) Int32N1e9-8 4.235n ± 0% 4.133n ± 0% -2.40% (p=0.000 n=20) Int32N2e9-8 4.229n ± 1% 4.137n ± 0% -2.19% (p=0.000 n=20) Float32-8 3.468n ± 0% 3.468n ± 1% ~ (p=0.350 n=20) Float64-8 3.447n ± 0% 3.478n ± 0% +0.90% (p=0.000 n=20) ExpFloat64-8 4.567n ± 0% 4.563n ± 0% -0.10% (p=0.002 n=20) NormFloat64-8 4.821n ± 0% 4.768n ± 0% -1.09% (p=0.000 n=20) Perm3-8 28.89n ± 0% 28.94n ± 0% +0.17% (p=0.000 n=20) Perm30-8 175.7n ± 0% 175.9n ± 0% +0.14% (p=0.000 n=20) Perm30ViaShuffle-8 153.5n ± 0% 152.6n ± 1% ~ (p=0.010 n=20) ShuffleOverhead-8 119.8n ± 1% 119.6n ± 1% ~ (p=0.147 n=20) Concurrent-8 2.433n ± 3% 2.452n ± 3% ~ (p=0.616 n=20) goos: linux goarch: 386 pkg: math/rand/v2 cpu: AMD Ryzen 9 7950X 16-Core Processor │ 220860f76f.386 │ 11ad9fdddc.386 │ │ sec/op │ sec/op vs base │ SourceUint64-32 2.370n ± 1% 2.091n ± 1% -11.75% (p=0.000 n=20) GlobalInt64-32 3.569n ± 1% 3.514n ± 2% -1.56% (p=0.000 n=20) GlobalInt63Parallel-32 0.3221n ± 1% 0.3197n ± 0% -0.76% (p=0.000 n=20) GlobalUint64-32 8.797n ± 10% 3.542n ± 1% -59.74% (p=0.000 n=20) GlobalUint64Parallel-32 0.6351n ± 0% 0.3218n ± 0% -49.33% (p=0.000 n=20) Int64-32 2.612n ± 2% 2.552n ± 2% -2.30% (p=0.000 n=20) Uint64-32 3.350n ± 1% 2.566n ± 1% -23.42% (p=0.000 n=20) GlobalIntN1000-32 5.892n ± 1% 5.965n ± 2% ~ (p=0.082 n=20) IntN1000-32 4.546n ± 1% 4.652n ± 1% +2.33% (p=0.000 n=20) Int64N1000-32 14.59n ± 1% 14.48n ± 1% ~ (p=0.652 n=20) Int64N1e8-32 14.76n ± 2% 14.67n ± 1% ~ (p=0.836 n=20) Int64N1e9-32 16.57n ± 1% 16.80n ± 2% ~ (p=0.016 n=20) Int64N2e9-32 14.54n ± 1% 14.52n ± 1% ~ (p=0.533 n=20) Int64N1e18-32 16.14n ± 1% 16.16n ± 1% ~ (p=0.606 n=20) Int64N2e18-32 18.10n ± 1% 17.95n ± 2% ~ (p=0.062 n=20) Int64N4e18-32 18.65n ± 1% 18.35n ± 2% -1.61% (p=0.010 n=20) Int32N1000-32 3.560n ± 1% 3.608n ± 1% +1.33% (p=0.001 n=20) Int32N1e8-32 3.770n ± 2% 3.767n ± 1% ~ (p=0.155 n=20) Int32N1e9-32 4.098n ± 0% 4.130n ± 2% ~ (p=0.016 n=20) Int32N2e9-32 4.179n ± 1% 4.206n ± 1% ~ (p=0.011 n=20) Float32-32 21.18n ± 4% 22.18n ± 4% +4.70% (p=0.003 n=20) Float64-32 20.60n ± 2% 20.75n ± 4% +0.73% (p=0.000 n=20) ExpFloat64-32 13.07n ± 0% 12.58n ± 3% -3.82% (p=0.000 n=20) NormFloat64-32 7.738n ± 2% 7.920n ± 3% ~ (p=0.066 n=20) Perm3-32 36.73n ± 1% 40.27n ± 1% +9.65% (p=0.000 n=20) Perm30-32 211.9n ± 1% 213.2n ± 2% ~ (p=0.262 n=20) Perm30ViaShuffle-32 165.2n ± 1% 164.2n ± 2% ~ (p=0.029 n=20) ShuffleOverhead-32 133.9n ± 1% 134.7n ± 2% ~ (p=0.551 n=20) Concurrent-32 3.287n ± 2% 3.301n ± 2% ~ (p=0.330 n=20) For #61716. Change-Id: I8d2f73f87dd3603a0c2ff069988938e0957b6904 Reviewed-on: https://go-review.googlesource.com/c/go/+/502499 LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com> Auto-Submit: Russ Cox <rsc@golang.org> Reviewed-by: Dmitri Shuralyov <dmitshur@google.com> Reviewed-by: Rob Pike <r@golang.org>

Now that we can break the value stream, we can take advantage of better algorithms that have been suggested since the original code was written. Also optimizes IntN, Int32N, Int64N, Perm (indirectly). All the N variants (IntN, Int32N, Int64N, UintN, N, etc) now return the same values given a Source and parameter n, so that for example uint(r.IntN(10)) and r.UintN(10) and r.N(uint(10)) are completely interchangeable. Int64N4e18 gets slower but that is a near worst case for the algorithm and is extremely unlikely in practice. 32-bit Int32N variants got slower too, by 15-30%, in exchange for speeding up everything on 64-bit systems and consistency across the N functions. Also rename previously missed benchmark GlobalInt63Parallel to GlobalInt64Parallel. goos: linux goarch: amd64 pkg: math/rand/v2 cpu: AMD Ryzen 9 7950X 16-Core Processor │ 11ad9fdddc.amd64 │ 4d84a369d1.amd64 │ │ sec/op │ sec/op vs base │ SourceUint64-32 1.335n ± 1% 1.348n ± 2% ~ (p=0.335 n=20) GlobalInt64-32 2.046n ± 1% 2.082n ± 2% ~ (p=0.310 n=20) GlobalInt63Parallel-32 0.1037n ± 1% GlobalInt64Parallel-32 0.1036n ± 1% GlobalUint64-32 2.075n ± 0% 2.077n ± 2% ~ (p=0.228 n=20) GlobalUint64Parallel-32 0.1013n ± 1% 0.1012n ± 1% ~ (p=0.878 n=20) Int64-32 1.726n ± 2% 1.750n ± 0% +1.39% (p=0.000 n=20) Uint64-32 1.673n ± 1% 1.707n ± 2% +2.03% (p=0.002 n=20) GlobalIntN1000-32 3.895n ± 2% 3.192n ± 1% -18.05% (p=0.000 n=20) IntN1000-32 3.403n ± 1% 2.462n ± 2% -27.65% (p=0.000 n=20) Int64N1000-32 3.053n ± 2% 2.470n ± 1% -19.11% (p=0.000 n=20) Int64N1e8-32 2.718n ± 1% 2.503n ± 2% -7.91% (p=0.000 n=20) Int64N1e9-32 2.712n ± 1% 2.487n ± 1% -8.31% (p=0.000 n=20) Int64N2e9-32 2.690n ± 1% 2.487n ± 1% -7.57% (p=0.000 n=20) Int64N1e18-32 3.084n ± 2% 3.006n ± 2% -2.53% (p=0.000 n=20) Int64N2e18-32 4.026n ± 1% 3.368n ± 1% -16.33% (p=0.000 n=20) Int64N4e18-32 4.049n ± 2% 4.763n ± 1% +17.62% (p=0.000 n=20) Int32N1000-32 2.730n ± 0% 2.403n ± 1% -11.94% (p=0.000 n=20) Int32N1e8-32 2.916n ± 2% 2.405n ± 1% -17.53% (p=0.000 n=20) Int32N1e9-32 3.375n ± 1% 2.402n ± 2% -28.83% (p=0.000 n=20) Int32N2e9-32 3.292n ± 1% 2.384n ± 1% -27.58% (p=0.000 n=20) Float32-32 2.673n ± 1% 2.641n ± 2% ~ (p=0.147 n=20) Float64-32 2.485n ± 1% 2.483n ± 1% ~ (p=0.804 n=20) ExpFloat64-32 3.577n ± 2% 3.486n ± 2% -2.57% (p=0.000 n=20) NormFloat64-32 3.797n ± 2% 3.648n ± 1% -3.92% (p=0.000 n=20) Perm3-32 35.79n ± 2% 33.04n ± 1% -7.68% (p=0.000 n=20) Perm30-32 205.1n ± 1% 171.9n ± 1% -16.14% (p=0.000 n=20) Perm30ViaShuffle-32 111.2n ± 2% 100.3n ± 1% -9.76% (p=0.000 n=20) ShuffleOverhead-32 100.5n ± 2% 102.5n ± 1% +1.99% (p=0.007 n=20) Concurrent-32 2.188n ± 5% 2.101n ± 0% ~ (p=0.013 n=20) goos: darwin goarch: arm64 pkg: math/rand/v2 cpu: Apple M1 │ 11ad9fdddc.arm64 │ 4d84a369d1.arm64 │ │ sec/op │ sec/op vs base │ SourceUint64-8 2.272n ± 1% 2.261n ± 1% ~ (p=0.172 n=20) GlobalInt64-8 2.155n ± 1% 2.160n ± 1% ~ (p=0.482 n=20) GlobalInt63Parallel-8 0.4352n ± 0% GlobalInt64Parallel-8 0.4299n ± 0% GlobalUint64-8 2.173n ± 1% 2.169n ± 1% ~ (p=0.262 n=20) GlobalUint64Parallel-8 0.4340n ± 0% 0.4293n ± 1% -1.08% (p=0.000 n=20) Int64-8 2.544n ± 1% 2.473n ± 1% -2.83% (p=0.000 n=20) Uint64-8 2.552n ± 1% 2.453n ± 1% -3.90% (p=0.000 n=20) GlobalIntN1000-8 3.856n ± 0% 2.814n ± 2% -27.02% (p=0.000 n=20) IntN1000-8 3.820n ± 0% 2.933n ± 2% -23.22% (p=0.000 n=20) Int64N1000-8 3.219n ± 2% 2.934n ± 2% -8.85% (p=0.000 n=20) Int64N1e8-8 3.221n ± 2% 2.935n ± 2% -8.91% (p=0.000 n=20) Int64N1e9-8 3.276n ± 2% 2.934n ± 2% -10.44% (p=0.000 n=20) Int64N2e9-8 3.217n ± 0% 2.935n ± 2% -8.78% (p=0.000 n=20) Int64N1e18-8 3.502n ± 2% 3.778n ± 1% +7.91% (p=0.000 n=20) Int64N2e18-8 4.968n ± 1% 4.359n ± 1% -12.26% (p=0.000 n=20) Int64N4e18-8 4.963n ± 0% 6.546n ± 1% +31.92% (p=0.000 n=20) Int32N1000-8 3.189n ± 1% 2.940n ± 2% -7.81% (p=0.000 n=20) Int32N1e8-8 3.514n ± 1% 2.937n ± 2% -16.41% (p=0.000 n=20) Int32N1e9-8 4.133n ± 0% 2.938n ± 0% -28.91% (p=0.000 n=20) Int32N2e9-8 4.137n ± 0% 2.938n ± 2% -28.97% (p=0.000 n=20) Float32-8 3.468n ± 1% 3.486n ± 0% +0.52% (p=0.000 n=20) Float64-8 3.478n ± 0% 3.480n ± 0% ~ (p=0.063 n=20) ExpFloat64-8 4.563n ± 0% 4.533n ± 0% -0.67% (p=0.000 n=20) NormFloat64-8 4.768n ± 0% 4.764n ± 0% -0.07% (p=0.001 n=20) Perm3-8 28.94n ± 0% 26.66n ± 0% -7.88% (p=0.000 n=20) Perm30-8 175.9n ± 0% 143.4n ± 0% -18.50% (p=0.000 n=20) Perm30ViaShuffle-8 152.6n ± 1% 142.9n ± 0% -6.29% (p=0.000 n=20) ShuffleOverhead-8 119.6n ± 1% 120.7n ± 0% +0.96% (p=0.000 n=20) Concurrent-8 2.452n ± 3% 2.360n ± 2% -3.73% (p=0.007 n=20) goos: linux goarch: 386 pkg: math/rand/v2 cpu: AMD Ryzen 9 7950X 16-Core Processor │ 11ad9fdddc.386 │ 4d84a369d1.386 │ │ sec/op │ sec/op vs base │ SourceUint64-32 2.091n ± 1% 2.101n ± 2% ~ (p=0.672 n=20) GlobalInt64-32 3.514n ± 2% 3.518n ± 2% ~ (p=0.723 n=20) GlobalInt63Parallel-32 0.3197n ± 0% GlobalInt64Parallel-32 0.3206n ± 0% GlobalUint64-32 3.542n ± 1% 3.538n ± 1% ~ (p=0.304 n=20) GlobalUint64Parallel-32 0.3218n ± 0% 0.3231n ± 0% ~ (p=0.071 n=20) Int64-32 2.552n ± 2% 2.554n ± 2% ~ (p=0.693 n=20) Uint64-32 2.566n ± 1% 2.575n ± 2% ~ (p=0.606 n=20) GlobalIntN1000-32 5.965n ± 2% 6.292n ± 1% +5.46% (p=0.000 n=20) IntN1000-32 4.652n ± 1% 4.735n ± 1% +1.77% (p=0.000 n=20) Int64N1000-32 14.485n ± 1% 5.489n ± 2% -62.11% (p=0.000 n=20) Int64N1e8-32 14.675n ± 1% 5.528n ± 2% -62.33% (p=0.000 n=20) Int64N1e9-32 16.805n ± 2% 5.438n ± 2% -67.64% (p=0.000 n=20) Int64N2e9-32 14.515n ± 1% 5.474n ± 1% -62.28% (p=0.000 n=20) Int64N1e18-32 16.165n ± 1% 9.053n ± 1% -44.00% (p=0.000 n=20) Int64N2e18-32 17.945n ± 2% 9.685n ± 2% -46.03% (p=0.000 n=20) Int64N4e18-32 18.35n ± 2% 12.18n ± 1% -33.62% (p=0.000 n=20) Int32N1000-32 3.608n ± 1% 4.862n ± 1% +34.77% (p=0.000 n=20) Int32N1e8-32 3.767n ± 1% 4.758n ± 2% +26.31% (p=0.000 n=20) Int32N1e9-32 4.130n ± 2% 4.772n ± 1% +15.54% (p=0.000 n=20) Int32N2e9-32 4.206n ± 1% 4.847n ± 0% +15.24% (p=0.000 n=20) Float32-32 22.18n ± 4% 22.18n ± 4% ~ (p=0.195 n=20) Float64-32 20.75n ± 4% 21.21n ± 3% ~ (p=0.394 n=20) ExpFloat64-32 12.58n ± 3% 12.39n ± 2% ~ (p=0.032 n=20) NormFloat64-32 7.920n ± 3% 7.422n ± 1% -6.29% (p=0.000 n=20) Perm3-32 40.27n ± 1% 38.00n ± 2% -5.65% (p=0.000 n=20) Perm30-32 213.2n ± 2% 212.7n ± 1% ~ (p=0.995 n=20) Perm30ViaShuffle-32 164.2n ± 2% 187.5n ± 2% +14.22% (p=0.000 n=20) ShuffleOverhead-32 134.7n ± 2% 159.7n ± 1% +18.52% (p=0.000 n=20) Concurrent-32 3.301n ± 2% 3.470n ± 0% +5.10% (p=0.000 n=20) For #61716. Change-Id: Id1481b04202883cd0b23e21bb58d1bca4e482bd3 Reviewed-on: https://go-review.googlesource.com/c/go/+/502500 Reviewed-by: Rob Pike <r@golang.org> Auto-Submit: Russ Cox <rsc@golang.org> Reviewed-by: David Chase <drchase@google.com> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>

We realized too late after Go 1 that float64(r.Uint64())/(1<<64) is not a correct implementation: it occasionally rounds to 1. The correct implementation is float64(r.Uint64()&(1<<53-1))/(1<<53) but we couldn't change the implementation for compatibility, so we changed it to retry only in the "round to 1" cases. The change to v2 lets us update the algorithm to the simpler, faster one. Note that this implementation cannot generate 2⁻⁵⁴, nor 2⁻¹⁰⁰, nor any of the other numbers between 0 and 2⁻⁵³. A slower algorithm could shift some of the probability of generating these two boundary values over to the values in between, but that would be much slower and not necessarily be better. In particular, the current implementation has the property that there are uniform gaps between the possible returned floats, which might help stability. Also, the result is often scaled and shifted, like Float64()*X+Y. Multiplying by X>1 would open new gaps, and adding most Y would erase all the distinctions that were introduced. The only changes to benchmarks should be in Float32 and Float64. The other changes remain a cautionary tale. goos: linux goarch: amd64 pkg: math/rand/v2 cpu: AMD Ryzen 9 7950X 16-Core Processor │ 4d84a369d1.amd64 │ 2703446c2e.amd64 │ │ sec/op │ sec/op vs base │ SourceUint64-32 1.348n ± 2% 1.337n ± 1% ~ (p=0.662 n=20) GlobalInt64-32 2.082n ± 2% 2.225n ± 2% +6.87% (p=0.000 n=20) GlobalInt64Parallel-32 0.1036n ± 1% 0.1043n ± 2% ~ (p=0.171 n=20) GlobalUint64-32 2.077n ± 2% 2.058n ± 1% ~ (p=0.560 n=20) GlobalUint64Parallel-32 0.1012n ± 1% 0.1009n ± 1% ~ (p=0.995 n=20) Int64-32 1.750n ± 0% 1.719n ± 2% -1.74% (p=0.000 n=20) Uint64-32 1.707n ± 2% 1.669n ± 1% -2.20% (p=0.000 n=20) GlobalIntN1000-32 3.192n ± 1% 3.321n ± 2% +4.04% (p=0.000 n=20) IntN1000-32 2.462n ± 2% 2.479n ± 1% ~ (p=0.417 n=20) Int64N1000-32 2.470n ± 1% 2.477n ± 1% ~ (p=0.664 n=20) Int64N1e8-32 2.503n ± 2% 2.490n ± 1% ~ (p=0.245 n=20) Int64N1e9-32 2.487n ± 1% 2.458n ± 1% ~ (p=0.032 n=20) Int64N2e9-32 2.487n ± 1% 2.486n ± 2% ~ (p=0.507 n=20) Int64N1e18-32 3.006n ± 2% 3.215n ± 2% +6.94% (p=0.000 n=20) Int64N2e18-32 3.368n ± 1% 3.588n ± 2% +6.55% (p=0.000 n=20) Int64N4e18-32 4.763n ± 1% 4.938n ± 2% +3.69% (p=0.000 n=20) Int32N1000-32 2.403n ± 1% 2.673n ± 2% +11.19% (p=0.000 n=20) Int32N1e8-32 2.405n ± 1% 2.631n ± 2% +9.42% (p=0.000 n=20) Int32N1e9-32 2.402n ± 2% 2.628n ± 2% +9.41% (p=0.000 n=20) Int32N2e9-32 2.384n ± 1% 2.684n ± 2% +12.56% (p=0.000 n=20) Float32-32 2.641n ± 2% 2.240n ± 2% -15.18% (p=0.000 n=20) Float64-32 2.483n ± 1% 2.253n ± 1% -9.26% (p=0.000 n=20) ExpFloat64-32 3.486n ± 2% 3.677n ± 1% +5.49% (p=0.000 n=20) NormFloat64-32 3.648n ± 1% 3.761n ± 1% +3.11% (p=0.000 n=20) Perm3-32 33.04n ± 1% 33.55n ± 2% ~ (p=0.180 n=20) Perm30-32 171.9n ± 1% 173.2n ± 1% ~ (p=0.050 n=20) Perm30ViaShuffle-32 100.3n ± 1% 115.9n ± 1% +15.55% (p=0.000 n=20) ShuffleOverhead-32 102.5n ± 1% 101.9n ± 1% ~ (p=0.266 n=20) Concurrent-32 2.101n ± 0% 2.107n ± 6% ~ (p=0.212 n=20) goos: darwin goarch: arm64 pkg: math/rand/v2 cpu: Apple M1 │ 4d84a369d1.arm64 │ 2703446c2e.arm64 │ │ sec/op │ sec/op vs base │ SourceUint64-8 2.261n ± 1% 2.275n ± 0% ~ (p=0.082 n=20) GlobalInt64-8 2.160n ± 1% 2.154n ± 1% ~ (p=0.490 n=20) GlobalInt64Parallel-8 0.4299n ± 0% 0.4298n ± 0% ~ (p=0.663 n=20) GlobalUint64-8 2.169n ± 1% 2.160n ± 1% ~ (p=0.292 n=20) GlobalUint64Parallel-8 0.4293n ± 1% 0.4286n ± 0% ~ (p=0.155 n=20) Int64-8 2.473n ± 1% 2.491n ± 1% ~ (p=0.317 n=20) Uint64-8 2.453n ± 1% 2.458n ± 0% ~ (p=0.941 n=20) GlobalIntN1000-8 2.814n ± 2% 2.814n ± 2% ~ (p=0.972 n=20) IntN1000-8 2.933n ± 2% 2.933n ± 0% ~ (p=0.287 n=20) Int64N1000-8 2.934n ± 2% 2.962n ± 1% ~ (p=0.062 n=20) Int64N1e8-8 2.935n ± 2% 2.960n ± 1% ~ (p=0.183 n=20) Int64N1e9-8 2.934n ± 2% 2.935n ± 2% ~ (p=0.367 n=20) Int64N2e9-8 2.935n ± 2% 2.934n ± 0% ~ (p=0.455 n=20) Int64N1e18-8 3.778n ± 1% 3.777n ± 1% ~ (p=0.995 n=20) Int64N2e18-8 4.359n ± 1% 4.359n ± 1% ~ (p=0.122 n=20) Int64N4e18-8 6.546n ± 1% 6.536n ± 1% ~ (p=0.920 n=20) Int32N1000-8 2.940n ± 2% 2.937n ± 0% ~ (p=0.149 n=20) Int32N1e8-8 2.937n ± 2% 2.937n ± 1% ~ (p=0.620 n=20) Int32N1e9-8 2.938n ± 0% 2.936n ± 0% ~ (p=0.046 n=20) Int32N2e9-8 2.938n ± 2% 2.938n ± 2% ~ (p=0.455 n=20) Float32-8 3.486n ± 0% 3.441n ± 0% -1.28% (p=0.000 n=20) Float64-8 3.480n ± 0% 3.441n ± 0% -1.13% (p=0.000 n=20) ExpFloat64-8 4.533n ± 0% 4.486n ± 0% -1.03% (p=0.000 n=20) NormFloat64-8 4.764n ± 0% 4.721n ± 0% -0.90% (p=0.000 n=20) Perm3-8 26.66n ± 0% 26.65n ± 0% ~ (p=0.019 n=20) Perm30-8 143.4n ± 0% 143.2n ± 0% -0.17% (p=0.000 n=20) Perm30ViaShuffle-8 142.9n ± 0% 143.0n ± 0% ~ (p=0.522 n=20) ShuffleOverhead-8 120.7n ± 0% 120.6n ± 1% ~ (p=0.488 n=20) Concurrent-8 2.360n ± 2% 2.399n ± 5% ~ (p=0.062 n=20) goos: linux goarch: 386 pkg: math/rand/v2 cpu: AMD Ryzen 9 7950X 16-Core Processor │ 4d84a369d1.386 │ 2703446c2e.386 │ │ sec/op │ sec/op vs base │ SourceUint64-32 2.101n ± 2% 2.072n ± 2% ~ (p=0.273 n=20) GlobalInt64-32 3.518n ± 2% 3.546n ± 27% +0.78% (p=0.007 n=20) GlobalInt64Parallel-32 0.3206n ± 0% 0.3211n ± 0% ~ (p=0.386 n=20) GlobalUint64-32 3.538n ± 1% 3.522n ± 2% ~ (p=0.331 n=20) GlobalUint64Parallel-32 0.3231n ± 0% 0.3172n ± 0% -1.84% (p=0.000 n=20) Int64-32 2.554n ± 2% 2.520n ± 2% ~ (p=0.465 n=20) Uint64-32 2.575n ± 2% 2.581n ± 1% ~ (p=0.213 n=20) GlobalIntN1000-32 6.292n ± 1% 6.171n ± 1% ~ (p=0.015 n=20) IntN1000-32 4.735n ± 1% 4.752n ± 2% ~ (p=0.635 n=20) Int64N1000-32 5.489n ± 2% 5.429n ± 1% ~ (p=0.324 n=20) Int64N1e8-32 5.528n ± 2% 5.469n ± 2% ~ (p=0.013 n=20) Int64N1e9-32 5.438n ± 2% 5.489n ± 2% ~ (p=0.984 n=20) Int64N2e9-32 5.474n ± 1% 5.492n ± 2% ~ (p=0.616 n=20) Int64N1e18-32 9.053n ± 1% 8.927n ± 1% ~ (p=0.037 n=20) Int64N2e18-32 9.685n ± 2% 9.622n ± 1% ~ (p=0.449 n=20) Int64N4e18-32 12.18n ± 1% 12.03n ± 1% ~ (p=0.013 n=20) Int32N1000-32 4.862n ± 1% 4.817n ± 1% -0.94% (p=0.002 n=20) Int32N1e8-32 4.758n ± 2% 4.801n ± 1% ~ (p=0.597 n=20) Int32N1e9-32 4.772n ± 1% 4.798n ± 1% ~ (p=0.774 n=20) Int32N2e9-32 4.847n ± 0% 4.840n ± 1% ~ (p=0.867 n=20) Float32-32 22.18n ± 4% 10.51n ± 4% -52.61% (p=0.000 n=20) Float64-32 21.21n ± 3% 20.33n ± 3% -4.17% (p=0.000 n=20) ExpFloat64-32 12.39n ± 2% 12.59n ± 2% ~ (p=0.139 n=20) NormFloat64-32 7.422n ± 1% 7.350n ± 2% ~ (p=0.208 n=20) Perm3-32 38.00n ± 2% 39.29n ± 2% +3.38% (p=0.000 n=20) Perm30-32 212.7n ± 1% 219.1n ± 2% +3.03% (p=0.001 n=20) Perm30ViaShuffle-32 187.5n ± 2% 189.8n ± 2% ~ (p=0.457 n=20) ShuffleOverhead-32 159.7n ± 1% 158.9n ± 2% ~ (p=0.920 n=20) Concurrent-32 3.470n ± 0% 3.306n ± 3% -4.71% (p=0.000 n=20) For #61716. Change-Id: I1933f1f9efd7e6e832d83e7fa5d84398f67d41f5 Reviewed-on: https://go-review.googlesource.com/c/go/+/502503 Auto-Submit: Russ Cox <rsc@golang.org> Reviewed-by: Rob Pike <r@golang.org> Reviewed-by: Dmitri Shuralyov <dmitshur@google.com> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>

The original implementation of the ziggurat algorithm was designed for 32-bit random integer inputs. This necessitated reusing some low-order bits for the slice selection and the random coordinate, which introduces statistical bias. The result is that PractRand consistently fails the math/rand normal and exponential sequences (transformed to uniform) within 2 GB of variates. This change adjusts the ziggurat procedures to use 63-bit random inputs, so that there is no need to reuse bits between the slice and coordinate. This is sufficient for the normal sequence to survive to 256 GB of PractRand testing. An alternative technique is to recalculate the ziggurats to use 1024 rather than 128 or 256 slices to make full use of 64-bit inputs. This improves the survival of the normal sequence to far beyond 256 GB and additionally provides a 6% performance improvement due to the improved rejection procedure efficiency. However, doing so increases the total size of the ziggurat tables from 4.5 kB to 48 kB. goos: linux goarch: amd64 pkg: math/rand/v2 cpu: AMD Ryzen 9 7950X 16-Core Processor │ 2703446c2e.amd64 │ e1bbe739fb.amd64 │ │ sec/op │ sec/op vs base │ SourceUint64-32 1.337n ± 1% 1.316n ± 2% ~ (p=0.024 n=20) GlobalInt64-32 2.225n ± 2% 2.048n ± 1% -7.93% (p=0.000 n=20) GlobalInt64Parallel-32 0.1043n ± 2% 0.1037n ± 1% ~ (p=0.587 n=20) GlobalUint64-32 2.058n ± 1% 2.039n ± 2% ~ (p=0.030 n=20) GlobalUint64Parallel-32 0.1009n ± 1% 0.1013n ± 1% ~ (p=0.984 n=20) Int64-32 1.719n ± 2% 1.692n ± 2% ~ (p=0.085 n=20) Uint64-32 1.669n ± 1% 1.643n ± 2% ~ (p=0.049 n=20) GlobalIntN1000-32 3.321n ± 2% 3.287n ± 1% ~ (p=0.298 n=20) IntN1000-32 2.479n ± 1% 2.678n ± 2% +8.01% (p=0.000 n=20) Int64N1000-32 2.477n ± 1% 2.684n ± 2% +8.38% (p=0.000 n=20) Int64N1e8-32 2.490n ± 1% 2.663n ± 2% +6.99% (p=0.000 n=20) Int64N1e9-32 2.458n ± 1% 2.633n ± 1% +7.12% (p=0.000 n=20) Int64N2e9-32 2.486n ± 2% 2.657n ± 1% +6.90% (p=0.000 n=20) Int64N1e18-32 3.215n ± 2% 3.125n ± 2% -2.78% (p=0.000 n=20) Int64N2e18-32 3.588n ± 2% 3.476n ± 1% -3.15% (p=0.000 n=20) Int64N4e18-32 4.938n ± 2% 4.795n ± 1% -2.91% (p=0.000 n=20) Int32N1000-32 2.673n ± 2% 2.485n ± 2% -7.02% (p=0.000 n=20) Int32N1e8-32 2.631n ± 2% 2.457n ± 1% -6.63% (p=0.000 n=20) Int32N1e9-32 2.628n ± 2% 2.452n ± 1% -6.70% (p=0.000 n=20) Int32N2e9-32 2.684n ± 2% 2.453n ± 1% -8.61% (p=0.000 n=20) Float32-32 2.240n ± 2% 2.254n ± 1% ~ (p=0.878 n=20) Float64-32 2.253n ± 1% 2.262n ± 1% ~ (p=0.963 n=20) ExpFloat64-32 3.677n ± 1% 3.777n ± 2% +2.71% (p=0.004 n=20) NormFloat64-32 3.761n ± 1% 3.606n ± 1% -4.15% (p=0.000 n=20) Perm3-32 33.55n ± 2% 33.12n ± 2% ~ (p=0.402 n=20) Perm30-32 173.2n ± 1% 176.1n ± 1% +1.67% (p=0.000 n=20) Perm30ViaShuffle-32 115.9n ± 1% 109.3n ± 1% -5.69% (p=0.000 n=20) ShuffleOverhead-32 101.9n ± 1% 112.5n ± 1% +10.35% (p=0.000 n=20) Concurrent-32 2.107n ± 6% 2.099n ± 0% ~ (p=0.051 n=20) goos: darwin goarch: arm64 pkg: math/rand/v2 cpu: Apple M1 │ 2703446c2e.arm64 │ e1bbe739fb.arm64 │ │ sec/op │ sec/op vs base │ SourceUint64-8 2.275n ± 0% 2.290n ± 1% ~ (p=0.044 n=20) GlobalInt64-8 2.154n ± 1% 2.180n ± 1% ~ (p=0.068 n=20) GlobalInt64Parallel-8 0.4298n ± 0% 0.4294n ± 0% ~ (p=0.079 n=20) GlobalUint64-8 2.160n ± 1% 2.170n ± 1% ~ (p=0.129 n=20) GlobalUint64Parallel-8 0.4286n ± 0% 0.4283n ± 0% ~ (p=0.350 n=20) Int64-8 2.491n ± 1% 2.481n ± 1% ~ (p=0.330 n=20) Uint64-8 2.458n ± 0% 2.464n ± 1% ~ (p=0.351 n=20) GlobalIntN1000-8 2.814n ± 2% 2.814n ± 0% ~ (p=0.325 n=20) IntN1000-8 2.933n ± 0% 2.934n ± 2% ~ (p=0.079 n=20) Int64N1000-8 2.962n ± 1% 2.957n ± 1% ~ (p=0.259 n=20) Int64N1e8-8 2.960n ± 1% 2.935n ± 2% ~ (p=0.276 n=20) Int64N1e9-8 2.935n ± 2% 2.935n ± 2% ~ (p=0.984 n=20) Int64N2e9-8 2.934n ± 0% 2.933n ± 4% ~ (p=0.463 n=20) Int64N1e18-8 3.777n ± 1% 3.781n ± 1% ~ (p=0.516 n=20) Int64N2e18-8 4.359n ± 1% 4.362n ± 0% ~ (p=0.256 n=20) Int64N4e18-8 6.536n ± 1% 6.576n ± 1% ~ (p=0.224 n=20) Int32N1000-8 2.937n ± 0% 2.942n ± 2% ~ (p=0.312 n=20) Int32N1e8-8 2.937n ± 1% 2.941n ± 1% ~ (p=0.463 n=20) Int32N1e9-8 2.936n ± 0% 2.938n ± 2% ~ (p=0.044 n=20) Int32N2e9-8 2.938n ± 2% 2.982n ± 2% ~ (p=0.174 n=20) Float32-8 3.441n ± 0% 3.441n ± 0% ~ (p=0.064 n=20) Float64-8 3.441n ± 0% 3.441n ± 0% ~ (p=0.826 n=20) ExpFloat64-8 4.486n ± 0% 4.472n ± 0% -0.31% (p=0.000 n=20) NormFloat64-8 4.721n ± 0% 4.716n ± 0% ~ (p=0.051 n=20) Perm3-8 26.65n ± 0% 26.66n ± 0% ~ (p=0.080 n=20) Perm30-8 143.2n ± 0% 143.3n ± 0% +0.10% (p=0.000 n=20) Perm30ViaShuffle-8 143.0n ± 0% 142.9n ± 0% ~ (p=0.642 n=20) ShuffleOverhead-8 120.6n ± 1% 121.1n ± 1% +0.41% (p=0.010 n=20) Concurrent-8 2.399n ± 5% 2.379n ± 2% ~ (p=0.365 n=20) goos: linux goarch: 386 pkg: math/rand/v2 cpu: AMD Ryzen 9 7950X 16-Core Processor │ 2703446c2e.386 │ e1bbe739fb.386 │ │ sec/op │ sec/op vs base │ SourceUint64-32 2.072n ± 2% 2.087n ± 1% ~ (p=0.440 n=20) GlobalInt64-32 3.546n ± 27% 3.538n ± 2% ~ (p=0.101 n=20) GlobalInt64Parallel-32 0.3211n ± 0% 0.3207n ± 1% ~ (p=0.753 n=20) GlobalUint64-32 3.522n ± 2% 3.543n ± 1% ~ (p=0.071 n=20) GlobalUint64Parallel-32 0.3172n ± 0% 0.3170n ± 0% ~ (p=0.507 n=20) Int64-32 2.520n ± 2% 2.548n ± 1% ~ (p=0.267 n=20) Uint64-32 2.581n ± 1% 2.565n ± 2% ~ (p=0.143 n=20) GlobalIntN1000-32 6.171n ± 1% 6.300n ± 1% ~ (p=0.037 n=20) IntN1000-32 4.752n ± 2% 4.750n ± 0% ~ (p=0.984 n=20) Int64N1000-32 5.429n ± 1% 5.515n ± 2% ~ (p=0.292 n=20) Int64N1e8-32 5.469n ± 2% 5.527n ± 0% ~ (p=0.013 n=20) Int64N1e9-32 5.489n ± 2% 5.531n ± 2% ~ (p=0.256 n=20) Int64N2e9-32 5.492n ± 2% 5.514n ± 2% ~ (p=0.606 n=20) Int64N1e18-32 8.927n ± 1% 9.059n ± 1% ~ (p=0.229 n=20) Int64N2e18-32 9.622n ± 1% 9.594n ± 1% ~ (p=0.703 n=20) Int64N4e18-32 12.03n ± 1% 12.05n ± 2% ~ (p=0.733 n=20) Int32N1000-32 4.817n ± 1% 4.840n ± 2% ~ (p=0.941 n=20) Int32N1e8-32 4.801n ± 1% 4.832n ± 2% ~ (p=0.228 n=20) Int32N1e9-32 4.798n ± 1% 4.815n ± 2% ~ (p=0.560 n=20) Int32N2e9-32 4.840n ± 1% 4.813n ± 1% ~ (p=0.015 n=20) Float32-32 10.51n ± 4% 10.90n ± 2% +3.71% (p=0.007 n=20) Float64-32 20.33n ± 3% 20.32n ± 4% ~ (p=0.566 n=20) ExpFloat64-32 12.59n ± 2% 12.95n ± 3% +2.86% (p=0.002 n=20) NormFloat64-32 7.350n ± 2% 7.570n ± 1% +2.99% (p=0.007 n=20) Perm3-32 39.29n ± 2% 37.80n ± 2% -3.79% (p=0.000 n=20) Perm30-32 219.1n ± 2% 214.0n ± 1% -2.33% (p=0.002 n=20) Perm30ViaShuffle-32 189.8n ± 2% 188.7n ± 2% ~ (p=0.147 n=20) ShuffleOverhead-32 158.9n ± 2% 160.8n ± 1% ~ (p=0.176 n=20) Concurrent-32 3.306n ± 3% 3.288n ± 0% -0.54% (p=0.005 n=20) For #61716. Change-Id: I4c5fe710b310dc075ae21c97d1805bcc20db5050 Reviewed-on: https://go-review.googlesource.com/c/go/+/516275 Auto-Submit: Russ Cox <rsc@golang.org> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com> Reviewed-by: Dmitri Shuralyov <dmitshur@google.com> Reviewed-by: Rob Pike <r@golang.org>

The compiler says Perm is being inlined into BenchmarkPerm, and yet BenchmarkPerm30ViaShuffle, which you'd think is the same code, still runs significantly faster. The benchmarks are mystifying but this is clearly still a step in the right direction, since BenchmarkPerm30ViaShuffle is still the fastest and we avoid having two copies of that logic. goos: linux goarch: amd64 pkg: math/rand/v2 cpu: AMD Ryzen 9 7950X 16-Core Processor │ e1bbe739fb.amd64 │ 8993506f2f.amd64 │ │ sec/op │ sec/op vs base │ SourceUint64-32 1.316n ± 2% 1.325n ± 1% ~ (p=0.208 n=20) GlobalInt64-32 2.048n ± 1% 2.240n ± 1% +9.38% (p=0.000 n=20) GlobalInt64Parallel-32 0.1037n ± 1% 0.1041n ± 1% ~ (p=0.774 n=20) GlobalUint64-32 2.039n ± 2% 2.072n ± 3% ~ (p=0.115 n=20) GlobalUint64Parallel-32 0.1013n ± 1% 0.1008n ± 1% ~ (p=0.417 n=20) Int64-32 1.692n ± 2% 1.716n ± 1% ~ (p=0.122 n=20) Uint64-32 1.643n ± 2% 1.665n ± 1% ~ (p=0.062 n=20) GlobalIntN1000-32 3.287n ± 1% 3.335n ± 1% ~ (p=0.147 n=20) IntN1000-32 2.678n ± 2% 2.484n ± 1% -7.24% (p=0.000 n=20) Int64N1000-32 2.684n ± 2% 2.502n ± 2% -6.80% (p=0.000 n=20) Int64N1e8-32 2.663n ± 2% 2.484n ± 2% -6.76% (p=0.000 n=20) Int64N1e9-32 2.633n ± 1% 2.502n ± 0% -4.98% (p=0.000 n=20) Int64N2e9-32 2.657n ± 1% 2.502n ± 0% -5.87% (p=0.000 n=20) Int64N1e18-32 3.125n ± 2% 3.201n ± 1% +2.43% (p=0.000 n=20) Int64N2e18-32 3.476n ± 1% 3.504n ± 1% +0.83% (p=0.009 n=20) Int64N4e18-32 4.795n ± 1% 4.873n ± 1% ~ (p=0.106 n=20) Int32N1000-32 2.485n ± 2% 2.639n ± 1% +6.20% (p=0.000 n=20) Int32N1e8-32 2.457n ± 1% 2.686n ± 2% +9.34% (p=0.000 n=20) Int32N1e9-32 2.452n ± 1% 2.636n ± 1% +7.52% (p=0.000 n=20) Int32N2e9-32 2.453n ± 1% 2.660n ± 1% +8.44% (p=0.000 n=20) Float32-32 2.254n ± 1% 2.261n ± 1% ~ (p=0.888 n=20) Float64-32 2.262n ± 1% 2.280n ± 1% ~ (p=0.040 n=20) ExpFloat64-32 3.777n ± 2% 3.891n ± 1% +3.03% (p=0.000 n=20) NormFloat64-32 3.606n ± 1% 3.711n ± 1% +2.91% (p=0.000 n=20) Perm3-32 33.12n ± 2% 32.60n ± 2% ~ (p=0.045 n=20) Perm30-32 176.1n ± 1% 204.2n ± 0% +15.96% (p=0.000 n=20) Perm30ViaShuffle-32 109.3n ± 1% 121.7n ± 2% +11.30% (p=0.000 n=20) ShuffleOverhead-32 112.5n ± 1% 106.2n ± 2% -5.56% (p=0.000 n=20) Concurrent-32 2.099n ± 0% 2.190n ± 5% +4.36% (p=0.001 n=20) goos: darwin goarch: arm64 pkg: math/rand/v2 cpu: Apple M1 │ e1bbe739fb.arm64 │ 8993506f2f.arm64 │ │ sec/op │ sec/op vs base │ SourceUint64-8 2.290n ± 1% 2.271n ± 0% ~ (p=0.015 n=20) GlobalInt64-8 2.180n ± 1% 2.161n ± 1% ~ (p=0.180 n=20) GlobalInt64Parallel-8 0.4294n ± 0% 0.4303n ± 0% +0.19% (p=0.001 n=20) GlobalUint64-8 2.170n ± 1% 2.164n ± 1% ~ (p=0.673 n=20) GlobalUint64Parallel-8 0.4283n ± 0% 0.4287n ± 0% ~ (p=0.128 n=20) Int64-8 2.481n ± 1% 2.478n ± 1% ~ (p=0.867 n=20) Uint64-8 2.464n ± 1% 2.460n ± 1% ~ (p=0.763 n=20) GlobalIntN1000-8 2.814n ± 0% 2.814n ± 2% ~ (p=0.969 n=20) IntN1000-8 2.934n ± 2% 3.003n ± 2% +2.35% (p=0.000 n=20) Int64N1000-8 2.957n ± 1% 2.954n ± 0% ~ (p=0.285 n=20) Int64N1e8-8 2.935n ± 2% 2.956n ± 0% +0.73% (p=0.002 n=20) Int64N1e9-8 2.935n ± 2% 3.325n ± 0% +13.29% (p=0.000 n=20) Int64N2e9-8 2.933n ± 4% 2.956n ± 2% ~ (p=0.163 n=20) Int64N1e18-8 3.781n ± 1% 3.780n ± 1% ~ (p=0.805 n=20) Int64N2e18-8 4.362n ± 0% 4.385n ± 0% ~ (p=0.077 n=20) Int64N4e18-8 6.576n ± 1% 6.527n ± 0% ~ (p=0.024 n=20) Int32N1000-8 2.942n ± 2% 2.964n ± 1% ~ (p=0.073 n=20) Int32N1e8-8 2.941n ± 1% 2.964n ± 1% ~ (p=0.058 n=20) Int32N1e9-8 2.938n ± 2% 2.963n ± 2% +0.87% (p=0.003 n=20) Int32N2e9-8 2.982n ± 2% 2.961n ± 2% ~ (p=0.056 n=20) Float32-8 3.441n ± 0% 3.442n ± 0% ~ (p=0.030 n=20) Float64-8 3.441n ± 0% 3.442n ± 0% +0.03% (p=0.001 n=20) ExpFloat64-8 4.472n ± 0% 4.472n ± 0% ~ (p=0.877 n=20) NormFloat64-8 4.716n ± 0% 4.734n ± 0% +0.38% (p=0.000 n=20) Perm3-8 26.66n ± 0% 26.55n ± 0% -0.39% (p=0.000 n=20) Perm30-8 143.3n ± 0% 181.9n ± 0% +26.97% (p=0.000 n=20) Perm30ViaShuffle-8 142.9n ± 0% 143.1n ± 0% ~ (p=0.669 n=20) ShuffleOverhead-8 121.1n ± 1% 120.6n ± 1% -0.41% (p=0.004 n=20) Concurrent-8 2.379n ± 2% 2.357n ± 2% ~ (p=0.337 n=20) goos: linux goarch: 386 pkg: math/rand/v2 cpu: AMD Ryzen 9 7950X 16-Core Processor │ e1bbe739fb.386 │ 8993506f2f.386 │ │ sec/op │ sec/op vs base │ SourceUint64-32 2.087n ± 1% 2.102n ± 2% ~ (p=0.507 n=20) GlobalInt64-32 3.538n ± 2% 3.542n ± 2% ~ (p=0.425 n=20) GlobalInt64Parallel-32 0.3207n ± 1% 0.3202n ± 0% ~ (p=0.963 n=20) GlobalUint64-32 3.543n ± 1% 3.507n ± 1% ~ (p=0.034 n=20) GlobalUint64Parallel-32 0.3170n ± 0% 0.3170n ± 1% ~ (p=0.920 n=20) Int64-32 2.548n ± 1% 2.516n ± 1% ~ (p=0.139 n=20) Uint64-32 2.565n ± 2% 2.544n ± 1% ~ (p=0.394 n=20) GlobalIntN1000-32 6.300n ± 1% 6.237n ± 1% ~ (p=0.029 n=20) IntN1000-32 4.750n ± 0% 4.670n ± 2% ~ (p=0.034 n=20) Int64N1000-32 5.515n ± 2% 5.412n ± 1% -1.86% (p=0.009 n=20) Int64N1e8-32 5.527n ± 0% 5.414n ± 2% -2.05% (p=0.002 n=20) Int64N1e9-32 5.531n ± 2% 5.473n ± 1% ~ (p=0.047 n=20) Int64N2e9-32 5.514n ± 2% 5.487n ± 1% ~ (p=0.298 n=20) Int64N1e18-32 9.059n ± 1% 8.901n ± 2% ~ (p=0.037 n=20) Int64N2e18-32 9.594n ± 1% 9.521n ± 1% ~ (p=0.051 n=20) Int64N4e18-32 12.05n ± 2% 11.92n ± 1% ~ (p=0.357 n=20) Int32N1000-32 4.840n ± 2% 4.785n ± 1% ~ (p=0.189 n=20) Int32N1e8-32 4.832n ± 2% 4.748n ± 1% ~ (p=0.042 n=20) Int32N1e9-32 4.815n ± 2% 4.810n ± 1% ~ (p=0.878 n=20) Int32N2e9-32 4.813n ± 1% 4.812n ± 1% ~ (p=0.542 n=20) Float32-32 10.90n ± 2% 10.48n ± 4% -3.85% (p=0.007 n=20) Float64-32 20.32n ± 4% 19.79n ± 3% ~ (p=0.553 n=20) ExpFloat64-32 12.95n ± 3% 12.91n ± 3% ~ (p=0.909 n=20) NormFloat64-32 7.570n ± 1% 7.462n ± 1% -1.44% (p=0.004 n=20) Perm3-32 37.80n ± 2% 35.98n ± 2% -4.79% (p=0.000 n=20) Perm30-32 214.0n ± 1% 241.5n ± 1% +12.85% (p=0.000 n=20) Perm30ViaShuffle-32 188.7n ± 2% 187.3n ± 2% ~ (p=0.029 n=20) ShuffleOverhead-32 160.8n ± 1% 160.2n ± 1% ~ (p=0.180 n=20) Concurrent-32 3.288n ± 0% 3.308n ± 3% ~ (p=0.037 n=20) For #61716. Change-Id: I342b611456c3569520d3c91c849d29eba325d87e Reviewed-on: https://go-review.googlesource.com/c/go/+/502504 Reviewed-by: Dmitri Shuralyov <dmitshur@google.com> Auto-Submit: Russ Cox <rsc@golang.org> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com> Reviewed-by: Rob Pike <r@golang.org>

For the original math/rand, we ported Plan 9's random number generator, which was a refinement by Ken Thompson of an algorithm by Don Mitchell and Jim Reeds, which Mitchell in turn recalls as having been derived from an algorithm by Marsaglia. At its core, it is an additive lagged Fibonacci generator (ALFG). Whatever the details of the history, this generator is nowhere near the current state of the art for simple, pseudo-random generators. This CL adds an implementation of Melissa O'Neill's PCG, specifically the variant PCG-DXSM, which she defined after writing the PCG paper and which is now the default in Numpy. The update is slightly slower (a few multiplies and adds, instead of a few adds), but the state is dramatically smaller (2 words instead of 607). The statistical output properties are better too. A followup CL will delete the old generator. PCG is the only change here, so no benchmarks should be affected. Including them anyway as further evidence for caution. goos: linux goarch: amd64 pkg: math/rand/v2 cpu: AMD Ryzen 9 7950X 16-Core Processor │ 8993506f2f.amd64 │ 01ff938549.amd64 │ │ sec/op │ sec/op vs base │ SourceUint64-32 1.325n ± 1% 1.352n ± 1% +2.00% (p=0.000 n=20) GlobalInt64-32 2.240n ± 1% 2.083n ± 0% -7.03% (p=0.000 n=20) GlobalInt64Parallel-32 0.1041n ± 1% 0.1035n ± 1% ~ (p=0.064 n=20) GlobalUint64-32 2.072n ± 3% 2.038n ± 1% ~ (p=0.089 n=20) GlobalUint64Parallel-32 0.1008n ± 1% 0.1006n ± 1% ~ (p=0.804 n=20) Int64-32 1.716n ± 1% 1.687n ± 2% ~ (p=0.045 n=20) Uint64-32 1.665n ± 1% 1.674n ± 2% ~ (p=0.878 n=20) GlobalIntN1000-32 3.335n ± 1% 3.135n ± 1% -6.00% (p=0.000 n=20) IntN1000-32 2.484n ± 1% 2.478n ± 1% ~ (p=0.085 n=20) Int64N1000-32 2.502n ± 2% 2.455n ± 1% -1.88% (p=0.002 n=20) Int64N1e8-32 2.484n ± 2% 2.467n ± 2% ~ (p=0.048 n=20) Int64N1e9-32 2.502n ± 0% 2.454n ± 1% -1.92% (p=0.000 n=20) Int64N2e9-32 2.502n ± 0% 2.482n ± 1% -0.76% (p=0.000 n=20) Int64N1e18-32 3.201n ± 1% 3.349n ± 2% +4.62% (p=0.000 n=20) Int64N2e18-32 3.504n ± 1% 3.537n ± 1% ~ (p=0.185 n=20) Int64N4e18-32 4.873n ± 1% 4.917n ± 0% +0.90% (p=0.000 n=20) Int32N1000-32 2.639n ± 1% 2.386n ± 1% -9.57% (p=0.000 n=20) Int32N1e8-32 2.686n ± 2% 2.366n ± 1% -11.91% (p=0.000 n=20) Int32N1e9-32 2.636n ± 1% 2.355n ± 2% -10.70% (p=0.000 n=20) Int32N2e9-32 2.660n ± 1% 2.371n ± 1% -10.88% (p=0.000 n=20) Float32-32 2.261n ± 1% 2.245n ± 2% ~ (p=0.752 n=20) Float64-32 2.280n ± 1% 2.235n ± 1% -1.97% (p=0.007 n=20) ExpFloat64-32 3.891n ± 1% 3.813n ± 3% ~ (p=0.087 n=20) NormFloat64-32 3.711n ± 1% 3.652n ± 2% ~ (p=0.021 n=20) Perm3-32 32.60n ± 2% 33.12n ± 3% ~ (p=0.107 n=20) Perm30-32 204.2n ± 0% 205.1n ± 1% ~ (p=0.358 n=20) Perm30ViaShuffle-32 121.7n ± 2% 110.8n ± 1% -8.96% (p=0.000 n=20) ShuffleOverhead-32 106.2n ± 2% 113.0n ± 1% +6.36% (p=0.000 n=20) Concurrent-32 2.190n ± 5% 2.100n ± 0% -4.13% (p=0.001 n=20) PCG_DXSM-32 1.490n ± 0% goos: darwin goarch: arm64 pkg: math/rand/v2 cpu: Apple M1 │ 8993506f2f.arm64 │ 01ff938549.arm64 │ │ sec/op │ sec/op vs base │ SourceUint64-8 2.271n ± 0% 2.258n ± 1% ~ (p=0.167 n=20) GlobalInt64-8 2.161n ± 1% 2.167n ± 0% ~ (p=0.693 n=20) GlobalInt64Parallel-8 0.4303n ± 0% 0.4310n ± 0% ~ (p=0.051 n=20) GlobalUint64-8 2.164n ± 1% 2.182n ± 1% ~ (p=0.042 n=20) GlobalUint64Parallel-8 0.4287n ± 0% 0.4297n ± 0% ~ (p=0.082 n=20) Int64-8 2.478n ± 1% 2.472n ± 1% ~ (p=0.151 n=20) Uint64-8 2.460n ± 1% 2.449n ± 1% ~ (p=0.013 n=20) GlobalIntN1000-8 2.814n ± 2% 2.814n ± 2% ~ (p=0.821 n=20) IntN1000-8 3.003n ± 2% 2.998n ± 2% ~ (p=0.024 n=20) Int64N1000-8 2.954n ± 0% 2.949n ± 2% ~ (p=0.192 n=20) Int64N1e8-8 2.956n ± 0% 2.953n ± 2% ~ (p=0.109 n=20) Int64N1e9-8 3.325n ± 0% 2.950n ± 0% -11.26% (p=0.000 n=20) Int64N2e9-8 2.956n ± 2% 2.946n ± 2% ~ (p=0.027 n=20) Int64N1e18-8 3.780n ± 1% 3.779n ± 1% ~ (p=0.815 n=20) Int64N2e18-8 4.385n ± 0% 4.370n ± 1% ~ (p=0.402 n=20) Int64N4e18-8 6.527n ± 0% 6.544n ± 1% ~ (p=0.140 n=20) Int32N1000-8 2.964n ± 1% 2.950n ± 0% -0.47% (p=0.002 n=20) Int32N1e8-8 2.964n ± 1% 2.950n ± 2% ~ (p=0.013 n=20) Int32N1e9-8 2.963n ± 2% 2.951n ± 2% ~ (p=0.062 n=20) Int32N2e9-8 2.961n ± 2% 2.950n ± 2% -0.37% (p=0.002 n=20) Float32-8 3.442n ± 0% 3.441n ± 0% ~ (p=0.211 n=20) Float64-8 3.442n ± 0% 3.442n ± 0% ~ (p=0.067 n=20) ExpFloat64-8 4.472n ± 0% 4.481n ± 0% +0.20% (p=0.000 n=20) NormFloat64-8 4.734n ± 0% 4.725n ± 0% -0.19% (p=0.003 n=20) Perm3-8 26.55n ± 0% 26.55n ± 0% ~ (p=0.833 n=20) Perm30-8 181.9n ± 0% 181.9n ± 0% -0.03% (p=0.004 n=20) Perm30ViaShuffle-8 143.1n ± 0% 142.9n ± 0% ~ (p=0.204 n=20) ShuffleOverhead-8 120.6n ± 1% 120.8n ± 2% ~ (p=0.102 n=20) Concurrent-8 2.357n ± 2% 2.421n ± 6% ~ (p=0.016 n=20) PCG_DXSM-8 2.531n ± 0% goos: linux goarch: 386 pkg: math/rand/v2 cpu: AMD Ryzen 9 7950X 16-Core Processor │ 8993506f2f.386 │ 01ff938549.386 │ │ sec/op │ sec/op vs base │ SourceUint64-32 2.102n ± 2% 2.069n ± 0% ~ (p=0.021 n=20) GlobalInt64-32 3.542n ± 2% 3.456n ± 1% -2.44% (p=0.001 n=20) GlobalInt64Parallel-32 0.3202n ± 0% 0.3252n ± 0% +1.56% (p=0.000 n=20) GlobalUint64-32 3.507n ± 1% 3.573n ± 1% +1.87% (p=0.000 n=20) GlobalUint64Parallel-32 0.3170n ± 1% 0.3159n ± 0% ~ (p=0.167 n=20) Int64-32 2.516n ± 1% 2.562n ± 2% ~ (p=0.016 n=20) Uint64-32 2.544n ± 1% 2.592n ± 0% +1.85% (p=0.000 n=20) GlobalIntN1000-32 6.237n ± 1% 6.266n ± 2% ~ (p=0.268 n=20) IntN1000-32 4.670n ± 2% 4.724n ± 2% ~ (p=0.644 n=20) Int64N1000-32 5.412n ± 1% 5.490n ± 2% ~ (p=0.159 n=20) Int64N1e8-32 5.414n ± 2% 5.513n ± 2% ~ (p=0.129 n=20) Int64N1e9-32 5.473n ± 1% 5.476n ± 1% ~ (p=0.723 n=20) Int64N2e9-32 5.487n ± 1% 5.501n ± 2% ~ (p=0.481 n=20) Int64N1e18-32 8.901n ± 2% 9.043n ± 2% ~ (p=0.330 n=20) Int64N2e18-32 9.521n ± 1% 9.601n ± 2% ~ (p=0.703 n=20) Int64N4e18-32 11.92n ± 1% 12.00n ± 1% ~ (p=0.489 n=20) Int32N1000-32 4.785n ± 1% 4.829n ± 2% ~ (p=0.402 n=20) Int32N1e8-32 4.748n ± 1% 4.825n ± 2% ~ (p=0.218 n=20) Int32N1e9-32 4.810n ± 1% 4.830n ± 2% ~ (p=0.794 n=20) Int32N2e9-32 4.812n ± 1% 4.750n ± 2% ~ (p=0.057 n=20) Float32-32 10.48n ± 4% 10.89n ± 4% ~ (p=0.162 n=20) Float64-32 19.79n ± 3% 19.60n ± 4% ~ (p=0.668 n=20) ExpFloat64-32 12.91n ± 3% 12.96n ± 3% ~ (p=1.000 n=20) NormFloat64-32 7.462n ± 1% 7.516n ± 1% ~ (p=0.051 n=20) Perm3-32 35.98n ± 2% 36.78n ± 2% ~ (p=0.033 n=20) Perm30-32 241.5n ± 1% 238.9n ± 2% ~ (p=0.126 n=20) Perm30ViaShuffle-32 187.3n ± 2% 189.7n ± 2% ~ (p=0.387 n=20) ShuffleOverhead-32 160.2n ± 1% 159.8n ± 1% ~ (p=0.256 n=20) Concurrent-32 3.308n ± 3% 3.286n ± 1% ~ (p=0.038 n=20) PCG_DXSM-32 7.613n ± 1% For #61716. Change-Id: Icb274ca1f782504d658305a40159b4ae6a2f3f1d Reviewed-on: https://go-review.googlesource.com/c/go/+/502505 Auto-Submit: Russ Cox <rsc@golang.org> Reviewed-by: Dmitri Shuralyov <dmitshur@google.com> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com> Reviewed-by: Rob Pike <r@golang.org>

These slowdowns are because we are now using PCG instead of the Mitchell/Reeds LFSR for the benchmarks. PCG is in fact a bit slower (but generates statically far better random numbers). goos: linux goarch: amd64 pkg: math/rand/v2 cpu: AMD Ryzen 9 7950X 16-Core Processor │ 01ff938549.amd64 │ afa459a2f0.amd64 │ │ sec/op │ sec/op vs base │ PCG_DXSM-32 1.490n ± 0% 1.488n ± 2% ~ (p=0.408 n=20) SourceUint64-32 1.352n ± 1% 1.450n ± 3% +7.21% (p=0.000 n=20) GlobalInt64-32 2.083n ± 0% 2.067n ± 2% ~ (p=0.223 n=20) GlobalInt64Parallel-32 0.1035n ± 1% 0.1044n ± 2% ~ (p=0.010 n=20) GlobalUint64-32 2.038n ± 1% 2.085n ± 0% +2.28% (p=0.000 n=20) GlobalUint64Parallel-32 0.1006n ± 1% 0.1008n ± 1% ~ (p=0.733 n=20) Int64-32 1.687n ± 2% 1.779n ± 1% +5.48% (p=0.000 n=20) Uint64-32 1.674n ± 2% 1.854n ± 2% +10.69% (p=0.000 n=20) GlobalIntN1000-32 3.135n ± 1% 3.140n ± 3% ~ (p=0.794 n=20) IntN1000-32 2.478n ± 1% 2.496n ± 1% +0.73% (p=0.006 n=20) Int64N1000-32 2.455n ± 1% 2.510n ± 2% +2.22% (p=0.000 n=20) Int64N1e8-32 2.467n ± 2% 2.471n ± 2% ~ (p=0.050 n=20) Int64N1e9-32 2.454n ± 1% 2.488n ± 2% +1.39% (p=0.000 n=20) Int64N2e9-32 2.482n ± 1% 2.478n ± 2% ~ (p=0.066 n=20) Int64N1e18-32 3.349n ± 2% 3.088n ± 1% -7.81% (p=0.000 n=20) Int64N2e18-32 3.537n ± 1% 3.493n ± 1% -1.24% (p=0.002 n=20) Int64N4e18-32 4.917n ± 0% 5.060n ± 2% +2.91% (p=0.000 n=20) Int32N1000-32 2.386n ± 1% 2.620n ± 1% +9.76% (p=0.000 n=20) Int32N1e8-32 2.366n ± 1% 2.652n ± 0% +12.11% (p=0.000 n=20) Int32N1e9-32 2.355n ± 2% 2.644n ± 1% +12.32% (p=0.000 n=20) Int32N2e9-32 2.371n ± 1% 2.619n ± 2% +10.48% (p=0.000 n=20) Float32-32 2.245n ± 2% 2.261n ± 1% ~ (p=0.625 n=20) Float64-32 2.235n ± 1% 2.241n ± 2% ~ (p=0.393 n=20) ExpFloat64-32 3.813n ± 3% 3.716n ± 1% -2.53% (p=0.000 n=20) NormFloat64-32 3.652n ± 2% 3.718n ± 1% +1.79% (p=0.006 n=20) Perm3-32 33.12n ± 3% 34.11n ± 2% ~ (p=0.021 n=20) Perm30-32 205.1n ± 1% 200.6n ± 0% -2.17% (p=0.000 n=20) Perm30ViaShuffle-32 110.8n ± 1% 109.7n ± 1% -0.99% (p=0.002 n=20) ShuffleOverhead-32 113.0n ± 1% 107.2n ± 1% -5.09% (p=0.000 n=20) Concurrent-32 2.100n ± 0% 2.108n ± 6% ~ (p=0.103 n=20) goos: darwin goarch: arm64 pkg: math/rand/v2 │ 01ff938549.arm64 │ afa459a2f0.arm64 │ │ sec/op │ sec/op vs base │ PCG_DXSM-8 2.531n ± 0% 2.531n ± 0% ~ (p=0.763 n=20) SourceUint64-8 2.258n ± 1% 2.531n ± 0% +12.09% (p=0.000 n=20) GlobalInt64-8 2.167n ± 0% 2.177n ± 1% ~ (p=0.213 n=20) GlobalInt64Parallel-8 0.4310n ± 0% 0.4319n ± 0% ~ (p=0.027 n=20) GlobalUint64-8 2.182n ± 1% 2.185n ± 1% ~ (p=0.683 n=20) GlobalUint64Parallel-8 0.4297n ± 0% 0.4295n ± 1% ~ (p=0.941 n=20) Int64-8 2.472n ± 1% 4.104n ± 0% +66.00% (p=0.000 n=20) Uint64-8 2.449n ± 1% 4.080n ± 0% +66.60% (p=0.000 n=20) GlobalIntN1000-8 2.814n ± 2% 2.814n ± 1% ~ (p=0.972 n=20) IntN1000-8 2.998n ± 2% 4.140n ± 0% +38.09% (p=0.000 n=20) Int64N1000-8 2.949n ± 2% 4.139n ± 0% +40.35% (p=0.000 n=20) Int64N1e8-8 2.953n ± 2% 4.140n ± 0% +40.22% (p=0.000 n=20) Int64N1e9-8 2.950n ± 0% 4.139n ± 0% +40.32% (p=0.000 n=20) Int64N2e9-8 2.946n ± 2% 4.140n ± 0% +40.53% (p=0.000 n=20) Int64N1e18-8 3.779n ± 1% 5.273n ± 0% +39.52% (p=0.000 n=20) Int64N2e18-8 4.370n ± 1% 6.059n ± 0% +38.65% (p=0.000 n=20) Int64N4e18-8 6.544n ± 1% 8.803n ± 0% +34.52% (p=0.000 n=20) Int32N1000-8 2.950n ± 0% 4.131n ± 0% +40.06% (p=0.000 n=20) Int32N1e8-8 2.950n ± 2% 4.131n ± 0% +40.03% (p=0.000 n=20) Int32N1e9-8 2.951n ± 2% 4.131n ± 0% +39.99% (p=0.000 n=20) Int32N2e9-8 2.950n ± 2% 4.131n ± 0% +40.03% (p=0.000 n=20) Float32-8 3.441n ± 0% 4.110n ± 0% +19.44% (p=0.000 n=20) Float64-8 3.442n ± 0% 4.104n ± 0% +19.24% (p=0.000 n=20) ExpFloat64-8 4.481n ± 0% 5.338n ± 0% +19.11% (p=0.000 n=20) NormFloat64-8 4.725n ± 0% 5.731n ± 0% +21.28% (p=0.000 n=20) Perm3-8 26.55n ± 0% 26.62n ± 0% +0.28% (p=0.000 n=20) Perm30-8 181.9n ± 0% 194.6n ± 2% +6.98% (p=0.000 n=20) Perm30ViaShuffle-8 142.9n ± 0% 156.4n ± 0% +9.45% (p=0.000 n=20) ShuffleOverhead-8 120.8n ± 2% 125.8n ± 0% +4.10% (p=0.000 n=20) Concurrent-8 2.421n ± 6% 2.654n ± 6% +9.67% (p=0.002 n=20) goos: linux goarch: 386 pkg: math/rand/v2 cpu: AMD Ryzen 9 7950X 16-Core Processor │ 01ff938549.386 │ afa459a2f0.386 │ │ sec/op │ sec/op vs base │ PCG_DXSM-32 7.613n ± 1% 7.793n ± 2% +2.38% (p=0.000 n=20) SourceUint64-32 2.069n ± 0% 7.680n ± 1% +271.19% (p=0.000 n=20) GlobalInt64-32 3.456n ± 1% 3.474n ± 3% ~ (p=0.654 n=20) GlobalInt64Parallel-32 0.3252n ± 0% 0.3253n ± 0% ~ (p=0.952 n=20) GlobalUint64-32 3.573n ± 1% 3.433n ± 2% -3.92% (p=0.000 n=20) GlobalUint64Parallel-32 0.3159n ± 0% 0.3156n ± 0% ~ (p=0.223 n=20) Int64-32 2.562n ± 2% 7.707n ± 1% +200.74% (p=0.000 n=20) Uint64-32 2.592n ± 0% 7.714n ± 1% +197.65% (p=0.000 n=20) GlobalIntN1000-32 6.266n ± 2% 6.236n ± 1% ~ (p=0.039 n=20) IntN1000-32 4.724n ± 2% 10.410n ± 1% +120.39% (p=0.000 n=20) Int64N1000-32 5.490n ± 2% 10.975n ± 2% +99.89% (p=0.000 n=20) Int64N1e8-32 5.513n ± 2% 10.980n ± 1% +99.15% (p=0.000 n=20) Int64N1e9-32 5.476n ± 1% 10.950n ± 0% +99.96% (p=0.000 n=20) Int64N2e9-32 5.501n ± 2% 11.110n ± 1% +101.96% (p=0.000 n=20) Int64N1e18-32 9.043n ± 2% 15.180n ± 2% +67.86% (p=0.000 n=20) Int64N2e18-32 9.601n ± 2% 15.610n ± 1% +62.60% (p=0.000 n=20) Int64N4e18-32 12.00n ± 1% 19.23n ± 2% +60.14% (p=0.000 n=20) Int32N1000-32 4.829n ± 2% 10.345n ± 1% +114.25% (p=0.000 n=20) Int32N1e8-32 4.825n ± 2% 10.330n ± 1% +114.09% (p=0.000 n=20) Int32N1e9-32 4.830n ± 2% 10.350n ± 1% +114.26% (p=0.000 n=20) Int32N2e9-32 4.750n ± 2% 10.345n ± 1% +117.81% (p=0.000 n=20) Float32-32 10.89n ± 4% 13.57n ± 1% +24.61% (p=0.000 n=20) Float64-32 19.60n ± 4% 22.95n ± 4% +17.12% (p=0.000 n=20) ExpFloat64-32 12.96n ± 3% 15.23n ± 2% +17.47% (p=0.000 n=20) NormFloat64-32 7.516n ± 1% 13.780n ± 1% +83.34% (p=0.000 n=20) Perm3-32 36.78n ± 2% 46.62n ± 2% +26.72% (p=0.000 n=20) Perm30-32 238.9n ± 2% 400.7n ± 1% +67.73% (p=0.000 n=20) Perm30ViaShuffle-32 189.7n ± 2% 350.5n ± 1% +84.79% (p=0.000 n=20) ShuffleOverhead-32 159.8n ± 1% 326.0n ± 2% +104.01% (p=0.000 n=20) Concurrent-32 3.286n ± 1% 3.290n ± 0% ~ (p=0.743 n=20) On the other hand, compared to the original "update benchmarks" CL, the cleanups we've made more than compensate for PCG being a bit slower than LFSR, at least on 64-bit x86. ARM64 (Apple M1) is a bit slower: perhaps the 64x64→128 multiply is slower there for some reason. 386 is noticeably slower, but it's also a non-SSA backend. goos: linux goarch: amd64 pkg: math/rand/v2 cpu: AMD Ryzen 9 7950X 16-Core Processor │ 220860f76f.amd64 │ afa459a2f0.amd64 │ │ sec/op │ sec/op vs base │ SourceUint64-32 1.555n ± 1% 1.450n ± 3% -6.78% (p=0.000 n=20) GlobalInt64-32 2.071n ± 1% 2.067n ± 2% ~ (p=0.673 n=20) GlobalInt63Parallel-32 0.1023n ± 1% GlobalInt64Parallel-32 0.1044n ± 2% GlobalUint64-32 5.193n ± 1% 2.085n ± 0% -59.86% (p=0.000 n=20) GlobalUint64Parallel-32 0.2341n ± 0% 0.1008n ± 1% -56.93% (p=0.000 n=20) Int64-32 2.056n ± 2% 1.779n ± 1% -13.47% (p=0.000 n=20) Uint64-32 2.077n ± 2% 1.854n ± 2% -10.74% (p=0.000 n=20) GlobalIntN1000-32 4.077n ± 2% 3.140n ± 3% -22.98% (p=0.000 n=20) IntN1000-32 3.476n ± 2% 2.496n ± 1% -28.19% (p=0.000 n=20) Int64N1000-32 3.059n ± 1% 2.510n ± 2% -17.96% (p=0.000 n=20) Int64N1e8-32 2.942n ± 1% 2.471n ± 2% -15.98% (p=0.000 n=20) Int64N1e9-32 2.932n ± 1% 2.488n ± 2% -15.14% (p=0.000 n=20) Int64N2e9-32 2.925n ± 1% 2.478n ± 2% -15.30% (p=0.000 n=20) Int64N1e18-32 3.116n ± 1% 3.088n ± 1% ~ (p=0.013 n=20) Int64N2e18-32 4.067n ± 1% 3.493n ± 1% -14.11% (p=0.000 n=20) Int64N4e18-32 4.054n ± 1% 5.060n ± 2% +24.80% (p=0.000 n=20) Int32N1000-32 2.951n ± 1% 2.620n ± 1% -11.22% (p=0.000 n=20) Int32N1e8-32 3.102n ± 1% 2.652n ± 0% -14.50% (p=0.000 n=20) Int32N1e9-32 3.535n ± 1% 2.644n ± 1% -25.20% (p=0.000 n=20) Int32N2e9-32 3.514n ± 1% 2.619n ± 2% -25.47% (p=0.000 n=20) Float32-32 2.760n ± 1% 2.261n ± 1% -18.06% (p=0.000 n=20) Float64-32 2.284n ± 1% 2.241n ± 2% ~ (p=0.016 n=20) ExpFloat64-32 3.757n ± 1% 3.716n ± 1% ~ (p=0.034 n=20) NormFloat64-32 3.837n ± 1% 3.718n ± 1% -3.09% (p=0.000 n=20) Perm3-32 35.23n ± 2% 34.11n ± 2% -3.19% (p=0.000 n=20) Perm30-32 208.8n ± 1% 200.6n ± 0% -3.93% (p=0.000 n=20) Perm30ViaShuffle-32 111.7n ± 1% 109.7n ± 1% -1.84% (p=0.000 n=20) ShuffleOverhead-32 101.1n ± 1% 107.2n ± 1% +6.03% (p=0.000 n=20) Concurrent-32 2.108n ± 7% 2.108n ± 6% ~ (p=0.644 n=20) PCG_DXSM-32 1.488n ± 2% goos: darwin goarch: arm64 pkg: math/rand/v2 cpu: Apple M1 │ 220860f76f.arm64 │ afa459a2f0.arm64 │ │ sec/op │ sec/op vs base │ SourceUint64-8 2.316n ± 1% 2.531n ± 0% +9.33% (p=0.000 n=20) GlobalInt64-8 2.183n ± 1% 2.177n ± 1% ~ (p=0.533 n=20) GlobalInt63Parallel-8 0.4331n ± 0% GlobalInt64Parallel-8 0.4319n ± 0% GlobalUint64-8 4.377n ± 2% 2.185n ± 1% -50.07% (p=0.000 n=20) GlobalUint64Parallel-8 0.9237n ± 0% 0.4295n ± 1% -53.50% (p=0.000 n=20) Int64-8 2.538n ± 1% 4.104n ± 0% +61.68% (p=0.000 n=20) Uint64-8 2.604n ± 1% 4.080n ± 0% +56.68% (p=0.000 n=20) GlobalIntN1000-8 3.857n ± 2% 2.814n ± 1% -27.04% (p=0.000 n=20) IntN1000-8 3.822n ± 2% 4.140n ± 0% +8.32% (p=0.000 n=20) Int64N1000-8 3.318n ± 0% 4.139n ± 0% +24.74% (p=0.000 n=20) Int64N1e8-8 3.349n ± 1% 4.140n ± 0% +23.64% (p=0.000 n=20) Int64N1e9-8 3.317n ± 2% 4.139n ± 0% +24.80% (p=0.000 n=20) Int64N2e9-8 3.317n ± 2% 4.140n ± 0% +24.81% (p=0.000 n=20) Int64N1e18-8 3.542n ± 1% 5.273n ± 0% +48.85% (p=0.000 n=20) Int64N2e18-8 5.087n ± 0% 6.059n ± 0% +19.12% (p=0.000 n=20) Int64N4e18-8 5.084n ± 0% 8.803n ± 0% +73.16% (p=0.000 n=20) Int32N1000-8 3.208n ± 2% 4.131n ± 0% +28.79% (p=0.000 n=20) Int32N1e8-8 3.610n ± 1% 4.131n ± 0% +14.43% (p=0.000 n=20) Int32N1e9-8 4.235n ± 0% 4.131n ± 0% -2.44% (p=0.000 n=20) Int32N2e9-8 4.229n ± 1% 4.131n ± 0% -2.33% (p=0.000 n=20) Float32-8 3.468n ± 0% 4.110n ± 0% +18.50% (p=0.000 n=20) Float64-8 3.447n ± 0% 4.104n ± 0% +19.05% (p=0.000 n=20) ExpFloat64-8 4.567n ± 0% 5.338n ± 0% +16.86% (p=0.000 n=20) NormFloat64-8 4.821n ± 0% 5.731n ± 0% +18.89% (p=0.000 n=20) Perm3-8 28.89n ± 0% 26.62n ± 0% -7.84% (p=0.000 n=20) Perm30-8 175.7n ± 0% 194.6n ± 2% +10.76% (p=0.000 n=20) Perm30ViaShuffle-8 153.5n ± 0% 156.4n ± 0% +1.86% (p=0.000 n=20) ShuffleOverhead-8 119.8n ± 1% 125.8n ± 0% +4.97% (p=0.000 n=20) Concurrent-8 2.433n ± 3% 2.654n ± 6% +9.13% (p=0.001 n=20) PCG_DXSM-8 2.531n ± 0% goos: linux goarch: 386 pkg: math/rand/v2 cpu: AMD Ryzen 9 7950X 16-Core Processor │ 220860f76f.386 │ afa459a2f0.386 │ │ sec/op │ sec/op vs base │ SourceUint64-32 2.370n ± 1% 7.680n ± 1% +224.05% (p=0.000 n=20) GlobalInt64-32 3.569n ± 1% 3.474n ± 3% -2.66% (p=0.001 n=20) GlobalInt63Parallel-32 0.3221n ± 1% GlobalInt64Parallel-32 0.3253n ± 0% GlobalUint64-32 8.797n ± 10% 3.433n ± 2% -60.98% (p=0.000 n=20) GlobalUint64Parallel-32 0.6351n ± 0% 0.3156n ± 0% -50.31% (p=0.000 n=20) Int64-32 2.612n ± 2% 7.707n ± 1% +195.04% (p=0.000 n=20) Uint64-32 3.350n ± 1% 7.714n ± 1% +130.25% (p=0.000 n=20) GlobalIntN1000-32 5.892n ± 1% 6.236n ± 1% +5.82% (p=0.000 n=20) IntN1000-32 4.546n ± 1% 10.410n ± 1% +128.97% (p=0.000 n=20) Int64N1000-32 14.59n ± 1% 10.97n ± 2% -24.75% (p=0.000 n=20) Int64N1e8-32 14.76n ± 2% 10.98n ± 1% -25.58% (p=0.000 n=20) Int64N1e9-32 16.57n ± 1% 10.95n ± 0% -33.90% (p=0.000 n=20) Int64N2e9-32 14.54n ± 1% 11.11n ± 1% -23.62% (p=0.000 n=20) Int64N1e18-32 16.14n ± 1% 15.18n ± 2% -5.95% (p=0.000 n=20) Int64N2e18-32 18.10n ± 1% 15.61n ± 1% -13.73% (p=0.000 n=20) Int64N4e18-32 18.65n ± 1% 19.23n ± 2% +3.08% (p=0.000 n=20) Int32N1000-32 3.560n ± 1% 10.345n ± 1% +190.55% (p=0.000 n=20) Int32N1e8-32 3.770n ± 2% 10.330n ± 1% +174.01% (p=0.000 n=20) Int32N1e9-32 4.098n ± 0% 10.350n ± 1% +152.53% (p=0.000 n=20) Int32N2e9-32 4.179n ± 1% 10.345n ± 1% +147.52% (p=0.000 n=20) Float32-32 21.18n ± 4% 13.57n ± 1% -35.93% (p=0.000 n=20) Float64-32 20.60n ± 2% 22.95n ± 4% +11.41% (p=0.000 n=20) ExpFloat64-32 13.07n ± 0% 15.23n ± 2% +16.48% (p=0.000 n=20) NormFloat64-32 7.738n ± 2% 13.780n ± 1% +78.08% (p=0.000 n=20) Perm3-32 36.73n ± 1% 46.62n ± 2% +26.91% (p=0.000 n=20) Perm30-32 211.9n ± 1% 400.7n ± 1% +89.05% (p=0.000 n=20) Perm30ViaShuffle-32 165.2n ± 1% 350.5n ± 1% +112.20% (p=0.000 n=20) ShuffleOverhead-32 133.9n ± 1% 326.0n ± 2% +143.37% (p=0.000 n=20) Concurrent-32 3.287n ± 2% 3.290n ± 0% ~ (p=0.365 n=20) PCG_DXSM-32 7.793n ± 2% For #61716. Change-Id: I4e9c0525b5f84a2ac46f23da9e365495e2d05777 Reviewed-on: https://go-review.googlesource.com/c/go/+/502506 Reviewed-by: Rob Pike <r@golang.org> Reviewed-by: Dmitri Shuralyov <dmitshur@google.com> Auto-Submit: Russ Cox <rsc@golang.org> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>

ChaCha8 provides a cryptographically strong generator alongside PCG, so that people who want stronger randomness have access to that. On systems with 128-bit vector math assembly (amd64 and arm64), ChaCha8 runs at about the same speed as PCG (25% slower on amd64, 2% faster on arm64). Obviously all the claimed benchmark variation other than the new ChaCha8 benchmark is a lie. goos: linux goarch: amd64 pkg: math/rand/v2 cpu: AMD Ryzen 9 7950X 16-Core Processor │ afa459a2f0.amd64 │ bbb48afeb7.amd64 │ │ sec/op │ sec/op vs base │ PCG_DXSM-32 1.488n ± 2% 1.492n ± 2% ~ (p=0.309 n=20) ChaCha8-32 1.861n ± 2% SourceUint64-32 1.450n ± 3% 1.590n ± 2% +9.69% (p=0.000 n=20) GlobalInt64-32 2.067n ± 2% 2.061n ± 1% ~ (p=0.952 n=20) GlobalInt64Parallel-32 0.1044n ± 2% 0.1041n ± 1% ~ (p=0.498 n=20) GlobalUint64-32 2.085n ± 0% 2.256n ± 2% +8.23% (p=0.000 n=20) GlobalUint64Parallel-32 0.1008n ± 1% 0.1018n ± 1% ~ (p=0.041 n=20) Int64-32 1.779n ± 1% 1.779n ± 1% ~ (p=0.410 n=20) Uint64-32 1.854n ± 2% 1.882n ± 1% ~ (p=0.044 n=20) GlobalIntN1000-32 3.140n ± 3% 3.115n ± 3% ~ (p=0.673 n=20) IntN1000-32 2.496n ± 1% 2.509n ± 1% ~ (p=0.171 n=20) Int64N1000-32 2.510n ± 2% 2.493n ± 1% ~ (p=0.804 n=20) Int64N1e8-32 2.471n ± 2% 2.521n ± 1% +1.98% (p=0.003 n=20) Int64N1e9-32 2.488n ± 2% 2.506n ± 1% ~ (p=0.663 n=20) Int64N2e9-32 2.478n ± 2% 2.482n ± 2% ~ (p=0.533 n=20) Int64N1e18-32 3.088n ± 1% 3.216n ± 1% +4.15% (p=0.000 n=20) Int64N2e18-32 3.493n ± 1% 3.635n ± 2% +4.05% (p=0.000 n=20) Int64N4e18-32 5.060n ± 2% 5.122n ± 1% +1.22% (p=0.000 n=20) Int32N1000-32 2.620n ± 1% 2.672n ± 1% +2.00% (p=0.002 n=20) Int32N1e8-32 2.652n ± 0% 2.646n ± 1% ~ (p=0.743 n=20) Int32N1e9-32 2.644n ± 1% 2.660n ± 2% ~ (p=0.163 n=20) Int32N2e9-32 2.619n ± 2% 2.652n ± 1% ~ (p=0.132 n=20) Float32-32 2.261n ± 1% 2.267n ± 1% ~ (p=0.516 n=20) Float64-32 2.241n ± 2% 2.276n ± 1% ~ (p=0.080 n=20) ExpFloat64-32 3.716n ± 1% 3.779n ± 1% +1.68% (p=0.007 n=20) NormFloat64-32 3.718n ± 1% 3.747n ± 1% ~ (p=0.011 n=20) Perm3-32 34.11n ± 2% 34.23n ± 2% ~ (p=0.779 n=20) Perm30-32 200.6n ± 0% 202.3n ± 2% ~ (p=0.055 n=20) Perm30ViaShuffle-32 109.7n ± 1% 115.5n ± 2% +5.34% (p=0.000 n=20) ShuffleOverhead-32 107.2n ± 1% 113.3n ± 1% +5.74% (p=0.000 n=20) Concurrent-32 2.108n ± 6% 2.107n ± 1% ~ (p=0.448 n=20) goos: darwin goarch: arm64 pkg: math/rand/v2 cpu: Apple M1 │ afa459a2f0.arm64 │ bbb48afeb7.arm64 │ │ sec/op │ sec/op vs base │ PCG_DXSM-8 2.531n ± 0% 2.529n ± 0% ~ (p=0.586 n=20) ChaCha8-8 2.480n ± 0% SourceUint64-8 2.531n ± 0% 2.534n ± 0% ~ (p=0.227 n=20) GlobalInt64-8 2.177n ± 1% 2.173n ± 1% ~ (p=0.733 n=20) GlobalInt64Parallel-8 0.4319n ± 0% 0.4304n ± 0% -0.32% (p=0.003 n=20) GlobalUint64-8 2.185n ± 1% 2.185n ± 0% ~ (p=0.541 n=20) GlobalUint64Parallel-8 0.4295n ± 1% 0.4294n ± 0% ~ (p=0.203 n=20) Int64-8 4.104n ± 0% 4.107n ± 0% ~ (p=0.193 n=20) Uint64-8 4.080n ± 0% 4.081n ± 0% ~ (p=0.053 n=20) GlobalIntN1000-8 2.814n ± 1% 2.814n ± 0% ~ (p=0.879 n=20) IntN1000-8 4.140n ± 0% 4.141n ± 0% ~ (p=0.428 n=20) Int64N1000-8 4.139n ± 0% 4.140n ± 0% ~ (p=0.114 n=20) Int64N1e8-8 4.140n ± 0% 4.140n ± 0% ~ (p=0.898 n=20) Int64N1e9-8 4.139n ± 0% 4.140n ± 0% ~ (p=0.593 n=20) Int64N2e9-8 4.140n ± 0% 4.139n ± 0% ~ (p=0.158 n=20) Int64N1e18-8 5.273n ± 0% 5.274n ± 0% ~ (p=0.308 n=20) Int64N2e18-8 6.059n ± 0% 6.058n ± 0% ~ (p=0.053 n=20) Int64N4e18-8 8.803n ± 0% 8.800n ± 0% ~ (p=0.673 n=20) Int32N1000-8 4.131n ± 0% 4.131n ± 0% ~ (p=0.342 n=20) Int32N1e8-8 4.131n ± 0% 4.131n ± 0% ~ (p=0.091 n=20) Int32N1e9-8 4.131n ± 0% 4.131n ± 0% ~ (p=0.273 n=20) Int32N2e9-8 4.131n ± 0% 4.131n ± 0% ~ (p=0.425 n=20) Float32-8 4.110n ± 0% 4.112n ± 0% ~ (p=0.203 n=20) Float64-8 4.104n ± 0% 4.106n ± 0% ~ (p=0.409 n=20) ExpFloat64-8 5.338n ± 0% 5.339n ± 0% ~ (p=0.037 n=20) NormFloat64-8 5.731n ± 0% 5.733n ± 0% ~ (p=0.692 n=20) Perm3-8 26.62n ± 0% 26.65n ± 0% +0.09% (p=0.000 n=20) Perm30-8 194.6n ± 2% 194.9n ± 0% ~ (p=0.141 n=20) Perm30ViaShuffle-8 156.4n ± 0% 156.5n ± 0% +0.06% (p=0.000 n=20) ShuffleOverhead-8 125.8n ± 0% 125.0n ± 0% -0.64% (p=0.000 n=20) Concurrent-8 2.654n ± 6% 2.441n ± 6% -8.06% (p=0.009 n=20) goos: linux goarch: 386 pkg: math/rand/v2 cpu: AMD Ryzen 9 7950X 16-Core Processor │ afa459a2f0.386 │ bbb48afeb7.386 │ │ sec/op │ sec/op vs base │ PCG_DXSM-32 7.793n ± 2% 7.647n ± 1% ~ (p=0.021 n=20) ChaCha8-32 11.48n ± 2% SourceUint64-32 7.680n ± 1% 7.714n ± 1% ~ (p=0.713 n=20) GlobalInt64-32 3.474n ± 3% 3.491n ± 28% ~ (p=0.337 n=20) GlobalInt64Parallel-32 0.3253n ± 0% 0.3194n ± 0% -1.81% (p=0.000 n=20) GlobalUint64-32 3.433n ± 2% 3.610n ± 2% +5.14% (p=0.000 n=20) GlobalUint64Parallel-32 0.3156n ± 0% 0.3164n ± 0% ~ (p=0.073 n=20) Int64-32 7.707n ± 1% 7.824n ± 0% +1.52% (p=0.005 n=20) Uint64-32 7.714n ± 1% 7.732n ± 2% ~ (p=0.441 n=20) GlobalIntN1000-32 6.236n ± 1% 6.176n ± 2% ~ (p=0.499 n=20) IntN1000-32 10.41n ± 1% 10.31n ± 2% ~ (p=0.782 n=20) Int64N1000-32 10.97n ± 2% 11.22n ± 2% +2.19% (p=0.002 n=20) Int64N1e8-32 10.98n ± 1% 11.07n ± 1% ~ (p=0.056 n=20) Int64N1e9-32 10.95n ± 0% 11.15n ± 2% ~ (p=0.016 n=20) Int64N2e9-32 11.11n ± 1% 11.00n ± 1% ~ (p=0.654 n=20) Int64N1e18-32 15.18n ± 2% 14.97n ± 2% ~ (p=0.387 n=20) Int64N2e18-32 15.61n ± 1% 15.91n ± 1% +1.92% (p=0.003 n=20) Int64N4e18-32 19.23n ± 2% 18.98n ± 1% ~ (p=1.000 n=20) Int32N1000-32 10.35n ± 1% 10.31n ± 2% ~ (p=0.081 n=20) Int32N1e8-32 10.33n ± 1% 10.38n ± 1% ~ (p=0.335 n=20) Int32N1e9-32 10.35n ± 1% 10.37n ± 1% ~ (p=0.497 n=20) Int32N2e9-32 10.35n ± 1% 10.41n ± 1% ~ (p=0.605 n=20) Float32-32 13.57n ± 1% 13.78n ± 2% ~ (p=0.047 n=20) Float64-32 22.95n ± 4% 23.43n ± 3% ~ (p=0.218 n=20) ExpFloat64-32 15.23n ± 2% 15.46n ± 1% ~ (p=0.095 n=20) NormFloat64-32 13.78n ± 1% 13.73n ± 2% ~ (p=0.031 n=20) Perm3-32 46.62n ± 2% 47.46n ± 2% +1.82% (p=0.004 n=20) Perm30-32 400.7n ± 1% 403.5n ± 1% ~ (p=0.098 n=20) Perm30ViaShuffle-32 350.5n ± 1% 348.1n ± 2% ~ (p=0.703 n=20) ShuffleOverhead-32 326.0n ± 2% 326.2n ± 2% ~ (p=0.440 n=20) Concurrent-32 3.290n ± 0% 3.297n ± 4% ~ (p=0.189 n=20) For #61716. Change-Id: Id2a7e1c1db0beb81f563faaefba65fe292497269 Reviewed-on: https://go-review.googlesource.com/c/go/+/516859 LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com> Reviewed-by: Filippo Valsorda <filippo@golang.org> Reviewed-by: Heschi Kreinick <heschi@google.com>

seebs · 2023-11-23T07:39:13Z

Was recently running some tests that used some random data. They genuinely didn't care what the data was, just wanted it to be anything at all not just zeros. The switch from math/rand.Read to crypto/rand.Read made that go from <1% of CPU time to, I think, around 10% of CPU time used by the entire test run.

I think my intuition here is that the arguments against using a PRNG as a random data source are much weaker when talking about test cases than they are when talking about production usage. But also, I think it's important to note that at least on some systems (I was hitting this on a Mac), the performance penalty for using the crypto reader is pretty devastating.

It really feels like "I genuinely don't care if the data's any good, I just want a few KB of bits that aren't completely obviously patterned" is a real use case. On the other hand, it's probably easy enough to synthesize it from Uint64(), and that's probably equivalent to what's happening internally anyway.

I just want to stress, though, that the performance penalty is not uniformly trivial on at least some current platforms.

Move ChaCha8 code into internal/chacha8rand and use it to implement runtime.rand, which is used for the unseeded global source for both math/rand and math/rand/v2. This also affects the calculation of the start point for iteration over very very large maps (when the 32-bit fastrand is not big enough). The benefit is that misuse of the global random number generators in math/rand and math/rand/v2 in contexts where non-predictable randomness is important for security reasons is no longer a security problem, removing a common mistake among programmers who are unaware of the different kinds of randomness. The cost is an extra 304 bytes per thread stored in the m struct plus 2-3ns more per random uint64 due to the more sophisticated algorithm. Using PCG looks like it would cost about the same, although I haven't benchmarked that. Before this, the math/rand and math/rand/v2 global generator was wyrand (https://github.com/wangyi-fudan/wyhash). For math/rand, using wyrand instead of the Mitchell/Reeds/Thompson ALFG was justifiable, since the latter was not any better. But for math/rand/v2, the global generator really should be at least as good as one of the well-studied, specific algorithms provided directly by the package, and it's not. (Wyrand is still reasonable for scheduling and cache decisions.) Good randomness does have a cost: about twice wyrand. Also rationalize the various runtime rand references. goos: linux goarch: amd64 pkg: math/rand/v2 cpu: AMD Ryzen 9 7950X 16-Core Processor │ bbb48afeb7.amd64 │ 5cf807d1ea.amd64 │ │ sec/op │ sec/op vs base │ ChaCha8-32 1.862n ± 2% 1.861n ± 2% ~ (p=0.825 n=20) PCG_DXSM-32 1.471n ± 1% 1.460n ± 2% ~ (p=0.153 n=20) SourceUint64-32 1.636n ± 2% 1.582n ± 1% -3.30% (p=0.000 n=20) GlobalInt64-32 2.087n ± 1% 3.663n ± 1% +75.54% (p=0.000 n=20) GlobalInt64Parallel-32 0.1042n ± 1% 0.2026n ± 1% +94.48% (p=0.000 n=20) GlobalUint64-32 2.263n ± 2% 3.724n ± 1% +64.57% (p=0.000 n=20) GlobalUint64Parallel-32 0.1019n ± 1% 0.1973n ± 1% +93.67% (p=0.000 n=20) Int64-32 1.771n ± 1% 1.774n ± 1% ~ (p=0.449 n=20) Uint64-32 1.863n ± 2% 1.866n ± 1% ~ (p=0.364 n=20) GlobalIntN1000-32 3.134n ± 3% 4.730n ± 2% +50.95% (p=0.000 n=20) IntN1000-32 2.489n ± 1% 2.489n ± 1% ~ (p=0.683 n=20) Int64N1000-32 2.521n ± 1% 2.516n ± 1% ~ (p=0.394 n=20) Int64N1e8-32 2.479n ± 1% 2.478n ± 2% ~ (p=0.743 n=20) Int64N1e9-32 2.530n ± 2% 2.514n ± 2% ~ (p=0.193 n=20) Int64N2e9-32 2.501n ± 1% 2.494n ± 1% ~ (p=0.616 n=20) Int64N1e18-32 3.227n ± 1% 3.205n ± 1% ~ (p=0.101 n=20) Int64N2e18-32 3.647n ± 1% 3.599n ± 1% ~ (p=0.019 n=20) Int64N4e18-32 5.135n ± 1% 5.069n ± 2% ~ (p=0.034 n=20) Int32N1000-32 2.657n ± 1% 2.637n ± 1% ~ (p=0.180 n=20) Int32N1e8-32 2.636n ± 1% 2.636n ± 1% ~ (p=0.763 n=20) Int32N1e9-32 2.660n ± 2% 2.638n ± 1% ~ (p=0.358 n=20) Int32N2e9-32 2.662n ± 2% 2.618n ± 2% ~ (p=0.064 n=20) Float32-32 2.272n ± 2% 2.239n ± 2% ~ (p=0.194 n=20) Float64-32 2.272n ± 1% 2.286n ± 2% ~ (p=0.763 n=20) ExpFloat64-32 3.762n ± 1% 3.744n ± 1% ~ (p=0.171 n=20) NormFloat64-32 3.706n ± 1% 3.655n ± 2% ~ (p=0.066 n=20) Perm3-32 32.93n ± 3% 34.62n ± 1% +5.13% (p=0.000 n=20) Perm30-32 202.9n ± 1% 204.0n ± 1% ~ (p=0.482 n=20) Perm30ViaShuffle-32 115.0n ± 1% 114.9n ± 1% ~ (p=0.358 n=20) ShuffleOverhead-32 112.8n ± 1% 112.7n ± 1% ~ (p=0.692 n=20) Concurrent-32 2.107n ± 0% 3.725n ± 1% +76.75% (p=0.000 n=20) goos: darwin goarch: arm64 pkg: math/rand/v2 │ bbb48afeb7.arm64 │ 5cf807d1ea.arm64 │ │ sec/op │ sec/op vs base │ ChaCha8-8 2.480n ± 0% 2.429n ± 0% -2.04% (p=0.000 n=20) PCG_DXSM-8 2.531n ± 0% 2.530n ± 0% ~ (p=0.877 n=20) SourceUint64-8 2.534n ± 0% 2.533n ± 0% ~ (p=0.732 n=20) GlobalInt64-8 2.172n ± 1% 4.794n ± 0% +120.67% (p=0.000 n=20) GlobalInt64Parallel-8 0.4320n ± 0% 0.9605n ± 0% +122.32% (p=0.000 n=20) GlobalUint64-8 2.182n ± 0% 4.770n ± 0% +118.58% (p=0.000 n=20) GlobalUint64Parallel-8 0.4307n ± 0% 0.9583n ± 0% +122.51% (p=0.000 n=20) Int64-8 4.107n ± 0% 4.104n ± 0% ~ (p=0.416 n=20) Uint64-8 4.080n ± 0% 4.080n ± 0% ~ (p=0.052 n=20) GlobalIntN1000-8 2.814n ± 2% 5.643n ± 0% +100.50% (p=0.000 n=20) IntN1000-8 4.141n ± 0% 4.139n ± 0% ~ (p=0.140 n=20) Int64N1000-8 4.140n ± 0% 4.140n ± 0% ~ (p=0.313 n=20) Int64N1e8-8 4.140n ± 0% 4.139n ± 0% ~ (p=0.103 n=20) Int64N1e9-8 4.139n ± 0% 4.140n ± 0% ~ (p=0.761 n=20) Int64N2e9-8 4.140n ± 0% 4.140n ± 0% ~ (p=0.636 n=20) Int64N1e18-8 5.266n ± 0% 5.326n ± 1% +1.14% (p=0.001 n=20) Int64N2e18-8 6.052n ± 0% 6.167n ± 0% +1.90% (p=0.000 n=20) Int64N4e18-8 8.826n ± 0% 9.051n ± 0% +2.55% (p=0.000 n=20) Int32N1000-8 4.127n ± 0% 4.132n ± 0% +0.12% (p=0.000 n=20) Int32N1e8-8 4.126n ± 0% 4.131n ± 0% +0.12% (p=0.000 n=20) Int32N1e9-8 4.127n ± 0% 4.132n ± 0% +0.12% (p=0.000 n=20) Int32N2e9-8 4.132n ± 0% 4.131n ± 0% ~ (p=0.017 n=20) Float32-8 4.109n ± 0% 4.105n ± 0% ~ (p=0.379 n=20) Float64-8 4.107n ± 0% 4.106n ± 0% ~ (p=0.867 n=20) ExpFloat64-8 5.339n ± 0% 5.383n ± 0% +0.82% (p=0.000 n=20) NormFloat64-8 5.735n ± 0% 5.737n ± 1% ~ (p=0.856 n=20) Perm3-8 26.65n ± 0% 26.80n ± 1% +0.58% (p=0.000 n=20) Perm30-8 194.8n ± 1% 197.0n ± 0% +1.18% (p=0.000 n=20) Perm30ViaShuffle-8 156.6n ± 0% 157.6n ± 1% +0.61% (p=0.000 n=20) ShuffleOverhead-8 124.9n ± 0% 125.5n ± 0% +0.52% (p=0.000 n=20) Concurrent-8 2.434n ± 3% 5.066n ± 0% +108.09% (p=0.000 n=20) goos: linux goarch: 386 pkg: math/rand/v2 cpu: AMD Ryzen 9 7950X 16-Core Processor │ bbb48afeb7.386 │ 5cf807d1ea.386 │ │ sec/op │ sec/op vs base │ ChaCha8-32 11.295n ± 1% 4.748n ± 2% -57.96% (p=0.000 n=20) PCG_DXSM-32 7.693n ± 1% 7.738n ± 2% ~ (p=0.542 n=20) SourceUint64-32 7.658n ± 2% 7.622n ± 2% ~ (p=0.344 n=20) GlobalInt64-32 3.473n ± 2% 7.526n ± 2% +116.73% (p=0.000 n=20) GlobalInt64Parallel-32 0.3198n ± 0% 0.5444n ± 0% +70.22% (p=0.000 n=20) GlobalUint64-32 3.612n ± 0% 7.575n ± 1% +109.69% (p=0.000 n=20) GlobalUint64Parallel-32 0.3168n ± 0% 0.5403n ± 0% +70.51% (p=0.000 n=20) Int64-32 7.673n ± 2% 7.789n ± 1% ~ (p=0.122 n=20) Uint64-32 7.773n ± 1% 7.827n ± 2% ~ (p=0.920 n=20) GlobalIntN1000-32 6.268n ± 1% 9.581n ± 1% +52.87% (p=0.000 n=20) IntN1000-32 10.33n ± 2% 10.45n ± 1% ~ (p=0.233 n=20) Int64N1000-32 10.98n ± 2% 11.01n ± 1% ~ (p=0.401 n=20) Int64N1e8-32 11.19n ± 2% 10.97n ± 1% ~ (p=0.033 n=20) Int64N1e9-32 11.06n ± 1% 11.08n ± 1% ~ (p=0.498 n=20) Int64N2e9-32 11.10n ± 1% 11.01n ± 2% ~ (p=0.995 n=20) Int64N1e18-32 15.23n ± 2% 15.04n ± 1% ~ (p=0.973 n=20) Int64N2e18-32 15.89n ± 1% 15.85n ± 1% ~ (p=0.409 n=20) Int64N4e18-32 18.96n ± 2% 19.34n ± 2% ~ (p=0.048 n=20) Int32N1000-32 10.46n ± 2% 10.44n ± 2% ~ (p=0.480 n=20) Int32N1e8-32 10.46n ± 2% 10.49n ± 2% ~ (p=0.951 n=20) Int32N1e9-32 10.28n ± 2% 10.26n ± 1% ~ (p=0.431 n=20) Int32N2e9-32 10.50n ± 2% 10.44n ± 2% ~ (p=0.249 n=20) Float32-32 13.80n ± 2% 13.80n ± 2% ~ (p=0.751 n=20) Float64-32 23.55n ± 2% 23.87n ± 0% ~ (p=0.408 n=20) ExpFloat64-32 15.36n ± 1% 15.29n ± 2% ~ (p=0.316 n=20) NormFloat64-32 13.57n ± 1% 13.79n ± 1% +1.66% (p=0.005 n=20) Perm3-32 45.70n ± 2% 46.99n ± 2% +2.81% (p=0.001 n=20) Perm30-32 399.0n ± 1% 403.8n ± 1% +1.19% (p=0.006 n=20) Perm30ViaShuffle-32 349.0n ± 1% 350.4n ± 1% ~ (p=0.909 n=20) ShuffleOverhead-32 322.3n ± 1% 323.8n ± 1% ~ (p=0.410 n=20) Concurrent-32 3.331n ± 1% 7.312n ± 1% +119.50% (p=0.000 n=20) For #61716. Change-Id: Ibdddeed85c34d9ae397289dc899e04d4845f9ed2 Reviewed-on: https://go-review.googlesource.com/c/go/+/516860 Reviewed-by: Michael Pratt <mpratt@google.com> Reviewed-by: Filippo Valsorda <filippo@golang.org> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>

rsc · 2023-12-05T20:35:08Z

These changes are now all submitted for Go 1.22.

Move ChaCha8 code into internal/chacha8rand and use it to implement runtime.rand, which is used for the unseeded global source for both math/rand and math/rand/v2. This also affects the calculation of the start point for iteration over very very large maps (when the 32-bit fastrand is not big enough). The benefit is that misuse of the global random number generators in math/rand and math/rand/v2 in contexts where non-predictable randomness is important for security reasons is no longer a security problem, removing a common mistake among programmers who are unaware of the different kinds of randomness. The cost is an extra 304 bytes per thread stored in the m struct plus 2-3ns more per random uint64 due to the more sophisticated algorithm. Using PCG looks like it would cost about the same, although I haven't benchmarked that. Before this, the math/rand and math/rand/v2 global generator was wyrand (https://github.com/wangyi-fudan/wyhash). For math/rand, using wyrand instead of the Mitchell/Reeds/Thompson ALFG was justifiable, since the latter was not any better. But for math/rand/v2, the global generator really should be at least as good as one of the well-studied, specific algorithms provided directly by the package, and it's not. (Wyrand is still reasonable for scheduling and cache decisions.) Good randomness does have a cost: about twice wyrand. Also rationalize the various runtime rand references. goos: linux goarch: amd64 pkg: math/rand/v2 cpu: AMD Ryzen 9 7950X 16-Core Processor │ bbb48afeb7.amd64 │ 5cf807d1ea.amd64 │ │ sec/op │ sec/op vs base │ ChaCha8-32 1.862n ± 2% 1.861n ± 2% ~ (p=0.825 n=20) PCG_DXSM-32 1.471n ± 1% 1.460n ± 2% ~ (p=0.153 n=20) SourceUint64-32 1.636n ± 2% 1.582n ± 1% -3.30% (p=0.000 n=20) GlobalInt64-32 2.087n ± 1% 3.663n ± 1% +75.54% (p=0.000 n=20) GlobalInt64Parallel-32 0.1042n ± 1% 0.2026n ± 1% +94.48% (p=0.000 n=20) GlobalUint64-32 2.263n ± 2% 3.724n ± 1% +64.57% (p=0.000 n=20) GlobalUint64Parallel-32 0.1019n ± 1% 0.1973n ± 1% +93.67% (p=0.000 n=20) Int64-32 1.771n ± 1% 1.774n ± 1% ~ (p=0.449 n=20) Uint64-32 1.863n ± 2% 1.866n ± 1% ~ (p=0.364 n=20) GlobalIntN1000-32 3.134n ± 3% 4.730n ± 2% +50.95% (p=0.000 n=20) IntN1000-32 2.489n ± 1% 2.489n ± 1% ~ (p=0.683 n=20) Int64N1000-32 2.521n ± 1% 2.516n ± 1% ~ (p=0.394 n=20) Int64N1e8-32 2.479n ± 1% 2.478n ± 2% ~ (p=0.743 n=20) Int64N1e9-32 2.530n ± 2% 2.514n ± 2% ~ (p=0.193 n=20) Int64N2e9-32 2.501n ± 1% 2.494n ± 1% ~ (p=0.616 n=20) Int64N1e18-32 3.227n ± 1% 3.205n ± 1% ~ (p=0.101 n=20) Int64N2e18-32 3.647n ± 1% 3.599n ± 1% ~ (p=0.019 n=20) Int64N4e18-32 5.135n ± 1% 5.069n ± 2% ~ (p=0.034 n=20) Int32N1000-32 2.657n ± 1% 2.637n ± 1% ~ (p=0.180 n=20) Int32N1e8-32 2.636n ± 1% 2.636n ± 1% ~ (p=0.763 n=20) Int32N1e9-32 2.660n ± 2% 2.638n ± 1% ~ (p=0.358 n=20) Int32N2e9-32 2.662n ± 2% 2.618n ± 2% ~ (p=0.064 n=20) Float32-32 2.272n ± 2% 2.239n ± 2% ~ (p=0.194 n=20) Float64-32 2.272n ± 1% 2.286n ± 2% ~ (p=0.763 n=20) ExpFloat64-32 3.762n ± 1% 3.744n ± 1% ~ (p=0.171 n=20) NormFloat64-32 3.706n ± 1% 3.655n ± 2% ~ (p=0.066 n=20) Perm3-32 32.93n ± 3% 34.62n ± 1% +5.13% (p=0.000 n=20) Perm30-32 202.9n ± 1% 204.0n ± 1% ~ (p=0.482 n=20) Perm30ViaShuffle-32 115.0n ± 1% 114.9n ± 1% ~ (p=0.358 n=20) ShuffleOverhead-32 112.8n ± 1% 112.7n ± 1% ~ (p=0.692 n=20) Concurrent-32 2.107n ± 0% 3.725n ± 1% +76.75% (p=0.000 n=20) goos: darwin goarch: arm64 pkg: math/rand/v2 │ bbb48afeb7.arm64 │ 5cf807d1ea.arm64 │ │ sec/op │ sec/op vs base │ ChaCha8-8 2.480n ± 0% 2.429n ± 0% -2.04% (p=0.000 n=20) PCG_DXSM-8 2.531n ± 0% 2.530n ± 0% ~ (p=0.877 n=20) SourceUint64-8 2.534n ± 0% 2.533n ± 0% ~ (p=0.732 n=20) GlobalInt64-8 2.172n ± 1% 4.794n ± 0% +120.67% (p=0.000 n=20) GlobalInt64Parallel-8 0.4320n ± 0% 0.9605n ± 0% +122.32% (p=0.000 n=20) GlobalUint64-8 2.182n ± 0% 4.770n ± 0% +118.58% (p=0.000 n=20) GlobalUint64Parallel-8 0.4307n ± 0% 0.9583n ± 0% +122.51% (p=0.000 n=20) Int64-8 4.107n ± 0% 4.104n ± 0% ~ (p=0.416 n=20) Uint64-8 4.080n ± 0% 4.080n ± 0% ~ (p=0.052 n=20) GlobalIntN1000-8 2.814n ± 2% 5.643n ± 0% +100.50% (p=0.000 n=20) IntN1000-8 4.141n ± 0% 4.139n ± 0% ~ (p=0.140 n=20) Int64N1000-8 4.140n ± 0% 4.140n ± 0% ~ (p=0.313 n=20) Int64N1e8-8 4.140n ± 0% 4.139n ± 0% ~ (p=0.103 n=20) Int64N1e9-8 4.139n ± 0% 4.140n ± 0% ~ (p=0.761 n=20) Int64N2e9-8 4.140n ± 0% 4.140n ± 0% ~ (p=0.636 n=20) Int64N1e18-8 5.266n ± 0% 5.326n ± 1% +1.14% (p=0.001 n=20) Int64N2e18-8 6.052n ± 0% 6.167n ± 0% +1.90% (p=0.000 n=20) Int64N4e18-8 8.826n ± 0% 9.051n ± 0% +2.55% (p=0.000 n=20) Int32N1000-8 4.127n ± 0% 4.132n ± 0% +0.12% (p=0.000 n=20) Int32N1e8-8 4.126n ± 0% 4.131n ± 0% +0.12% (p=0.000 n=20) Int32N1e9-8 4.127n ± 0% 4.132n ± 0% +0.12% (p=0.000 n=20) Int32N2e9-8 4.132n ± 0% 4.131n ± 0% ~ (p=0.017 n=20) Float32-8 4.109n ± 0% 4.105n ± 0% ~ (p=0.379 n=20) Float64-8 4.107n ± 0% 4.106n ± 0% ~ (p=0.867 n=20) ExpFloat64-8 5.339n ± 0% 5.383n ± 0% +0.82% (p=0.000 n=20) NormFloat64-8 5.735n ± 0% 5.737n ± 1% ~ (p=0.856 n=20) Perm3-8 26.65n ± 0% 26.80n ± 1% +0.58% (p=0.000 n=20) Perm30-8 194.8n ± 1% 197.0n ± 0% +1.18% (p=0.000 n=20) Perm30ViaShuffle-8 156.6n ± 0% 157.6n ± 1% +0.61% (p=0.000 n=20) ShuffleOverhead-8 124.9n ± 0% 125.5n ± 0% +0.52% (p=0.000 n=20) Concurrent-8 2.434n ± 3% 5.066n ± 0% +108.09% (p=0.000 n=20) goos: linux goarch: 386 pkg: math/rand/v2 cpu: AMD Ryzen 9 7950X 16-Core Processor │ bbb48afeb7.386 │ 5cf807d1ea.386 │ │ sec/op │ sec/op vs base │ ChaCha8-32 11.295n ± 1% 4.748n ± 2% -57.96% (p=0.000 n=20) PCG_DXSM-32 7.693n ± 1% 7.738n ± 2% ~ (p=0.542 n=20) SourceUint64-32 7.658n ± 2% 7.622n ± 2% ~ (p=0.344 n=20) GlobalInt64-32 3.473n ± 2% 7.526n ± 2% +116.73% (p=0.000 n=20) GlobalInt64Parallel-32 0.3198n ± 0% 0.5444n ± 0% +70.22% (p=0.000 n=20) GlobalUint64-32 3.612n ± 0% 7.575n ± 1% +109.69% (p=0.000 n=20) GlobalUint64Parallel-32 0.3168n ± 0% 0.5403n ± 0% +70.51% (p=0.000 n=20) Int64-32 7.673n ± 2% 7.789n ± 1% ~ (p=0.122 n=20) Uint64-32 7.773n ± 1% 7.827n ± 2% ~ (p=0.920 n=20) GlobalIntN1000-32 6.268n ± 1% 9.581n ± 1% +52.87% (p=0.000 n=20) IntN1000-32 10.33n ± 2% 10.45n ± 1% ~ (p=0.233 n=20) Int64N1000-32 10.98n ± 2% 11.01n ± 1% ~ (p=0.401 n=20) Int64N1e8-32 11.19n ± 2% 10.97n ± 1% ~ (p=0.033 n=20) Int64N1e9-32 11.06n ± 1% 11.08n ± 1% ~ (p=0.498 n=20) Int64N2e9-32 11.10n ± 1% 11.01n ± 2% ~ (p=0.995 n=20) Int64N1e18-32 15.23n ± 2% 15.04n ± 1% ~ (p=0.973 n=20) Int64N2e18-32 15.89n ± 1% 15.85n ± 1% ~ (p=0.409 n=20) Int64N4e18-32 18.96n ± 2% 19.34n ± 2% ~ (p=0.048 n=20) Int32N1000-32 10.46n ± 2% 10.44n ± 2% ~ (p=0.480 n=20) Int32N1e8-32 10.46n ± 2% 10.49n ± 2% ~ (p=0.951 n=20) Int32N1e9-32 10.28n ± 2% 10.26n ± 1% ~ (p=0.431 n=20) Int32N2e9-32 10.50n ± 2% 10.44n ± 2% ~ (p=0.249 n=20) Float32-32 13.80n ± 2% 13.80n ± 2% ~ (p=0.751 n=20) Float64-32 23.55n ± 2% 23.87n ± 0% ~ (p=0.408 n=20) ExpFloat64-32 15.36n ± 1% 15.29n ± 2% ~ (p=0.316 n=20) NormFloat64-32 13.57n ± 1% 13.79n ± 1% +1.66% (p=0.005 n=20) Perm3-32 45.70n ± 2% 46.99n ± 2% +2.81% (p=0.001 n=20) Perm30-32 399.0n ± 1% 403.8n ± 1% +1.19% (p=0.006 n=20) Perm30ViaShuffle-32 349.0n ± 1% 350.4n ± 1% ~ (p=0.909 n=20) ShuffleOverhead-32 322.3n ± 1% 323.8n ± 1% ~ (p=0.410 n=20) Concurrent-32 3.331n ± 1% 7.312n ± 1% +119.50% (p=0.000 n=20) For golang#61716. Change-Id: Ibdddeed85c34d9ae397289dc899e04d4845f9ed2 Reviewed-on: https://go-review.googlesource.com/c/go/+/516860 Reviewed-by: Michael Pratt <mpratt@google.com> Reviewed-by: Filippo Valsorda <filippo@golang.org> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>

rsc added the Proposal label Aug 2, 2023

gopherbot added this to the Proposal milestone Aug 2, 2023

flyingmutant added a commit to flyingmutant/rand that referenced this issue Aug 2, 2023

Add top-level N()

c0f8905

See: golang/go#61716 https://go-review.googlesource.com/c/go/+/502502/3

komuw mentioned this issue Aug 3, 2023

track go/issues/61716: add math/rand/v2 komuw/ong#342

Closed

dmitshur modified the milestones: Backlog, Go1.22 Oct 30, 2023

mateusz834 mentioned this issue Nov 1, 2023

proposal: math/rand/v2: Add IntInRange function #63880

Open

This was referenced Nov 20, 2023

internal/chacha8rand: tests failing on big-endian builders #64284

Closed

cmd/compile: large shifts miscompiled on riscv64 #64285

Closed

mknyszek mentioned this issue Nov 22, 2023

api: audit for Go 1.22 #64343

Closed

rsc closed this as completed Dec 5, 2023

lukechampine mentioned this issue Feb 7, 2024

proposal: math/rand/v2: Add Rand.Read #65562

Open

zephyrtronium mentioned this issue Feb 11, 2024

github: make language change proposal triage less confusing to the outside #65660

Open

Artoria2e5 mentioned this issue Mar 4, 2024

Thoughts on choice of algorithm tc39/proposal-seeded-random#19

Open

jfrech mentioned this issue Apr 5, 2024

x/website: release notes for Go 1.22 mentions inexistent math/rand/v2.Uint() #66693

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

math/rand/v2: revised API for math/rand #61716

math/rand/v2: revised API for math/rand #61716

rsc commented Aug 2, 2023 •

edited

rsc commented Aug 2, 2023

zephyrtronium commented Aug 2, 2023

rsc commented Aug 2, 2023

joeshaw commented Aug 2, 2023

rsc commented Aug 2, 2023

gopherbot commented Aug 4, 2023

gopherbot commented Aug 8, 2023

gopherbot commented Aug 8, 2023

gopherbot commented Aug 8, 2023

gopherbot commented Aug 8, 2023

gopherbot commented Aug 8, 2023

gopherbot commented Aug 8, 2023

gopherbot commented Aug 8, 2023

gopherbot commented Aug 8, 2023

gopherbot commented Aug 8, 2023

gopherbot commented Aug 8, 2023

gopherbot commented Aug 8, 2023

gopherbot commented Aug 8, 2023

gopherbot commented Aug 8, 2023

gopherbot commented Aug 8, 2023

rsc commented Aug 8, 2023

rsc commented Aug 8, 2023 •

edited

rsc commented Aug 8, 2023

Merovius commented Aug 8, 2023

robpike commented Aug 8, 2023

rsc commented Aug 8, 2023 •

edited

gopherbot commented Oct 5, 2023

seebs commented Nov 23, 2023

rsc commented Dec 5, 2023

math/rand/v2: revised API for math/rand #61716

math/rand/v2: revised API for math/rand #61716

Comments

rsc commented Aug 2, 2023 • edited

Proposal

Differences since previous discussion

Discussion Summary

rsc commented Aug 2, 2023

zephyrtronium commented Aug 2, 2023

rsc commented Aug 2, 2023

joeshaw commented Aug 2, 2023

rsc commented Aug 2, 2023

gopherbot commented Aug 4, 2023

gopherbot commented Aug 8, 2023

gopherbot commented Aug 8, 2023

gopherbot commented Aug 8, 2023

gopherbot commented Aug 8, 2023

gopherbot commented Aug 8, 2023

gopherbot commented Aug 8, 2023

gopherbot commented Aug 8, 2023

gopherbot commented Aug 8, 2023

gopherbot commented Aug 8, 2023

gopherbot commented Aug 8, 2023

gopherbot commented Aug 8, 2023

gopherbot commented Aug 8, 2023

gopherbot commented Aug 8, 2023

gopherbot commented Aug 8, 2023

rsc commented Aug 8, 2023

rsc commented Aug 8, 2023 • edited

rsc commented Aug 8, 2023

Merovius commented Aug 8, 2023

robpike commented Aug 8, 2023

rsc commented Aug 8, 2023 • edited

gopherbot commented Oct 5, 2023

seebs commented Nov 23, 2023

rsc commented Dec 5, 2023

rsc commented Aug 2, 2023 •

edited

rsc commented Aug 8, 2023 •

edited

rsc commented Aug 8, 2023 •

edited