Since Go 1 was released in March 2012, changes to the standard library have been constrained by Go’s compatibility promise. Overall, compatibility has been a boon for Go users, providing a stable base for production systems, documentation, tutorials, books, and more. Over time, however, we’ve realized mistakes in the original APIs that cannot be fixed compatibly; in other cases, best practices and convention have changed. We need a plan for making important, breaking changes too.

This blog post is about Go 1.22’s new math/rand/v2 package, the first “v2” in the standard library. It brings needed improvements to the math/rand API, but more importantly it sets an example for how we can revise other standard library packages as the need arises.

(In Go, math/rand and math/rand/v2 are two different packages with different import paths. Go 1 and every release after it have included math/rand; Go 1.22 added math/rand/v2. A Go program can import either package, or both.)

This post discusses the specific rationale for the changes in math/rand/v2 and then reflects on the general principles that will guide new versions of other packages.

Pseudorandom Number Generators

Before we look at math/rand, which is an API for a pseudorandom number generator, let’s take a moment to understand what that means.

A pseudorandom number generator is a deterministic program that generates a long sequence of seemingly random numbers from a small seed input, although the numbers are not in fact random at all. In the case of math/rand, the seed is a single int64, and the algorithm produces a sequence of int64s using a variant of a linear-feedback shift register (LFSR). The algorithm is based on an idea by George Marsaglia, tweaked by Don Mitchell and Jim Reeds, and further customized by Ken Thompson for Plan 9 and then Go. It has no official name, so this post calls it the Go 1 generator.

The goal is for these generators to be fast, repeatable, and random enough to support simulations, shuffling, and other non-cryptographic use cases. Repeatability is particularly important for uses like numerical simulations or randomized testing. For example, a randomized tester might pick a seed (perhaps based on the current time), generate a large random test input, and repeat. When the tester finds a failure, it only needs to print the seed to allow repeating the test with that specific large input.

Repeatability also matters over time: given a particular seed, a new version of Go needs to generate the same sequence of values that an older version did. We didn’t realize this when we released Go 1; instead, we discovered it the hard way, when we tried to make a change in Go 1.2 and got reports that we had broken certain tests and other use cases. At that point, we decided Go 1 compatibility included the specific random outputs for a given seed and added a test.

It is not a goal for these kinds of generators to produce random numbers suitable for deriving cryptographic keys or other important secrets. Because the seed is only 63 bits, any output drawn from the generator, no matter how long, will also only contain 63 bits of entropy. For example, using math/rand to generate a 128-bit or 256-bit AES key would be a serious mistake, since the key would be easier to brute force. For that kind of use, you need a cryptographically strong random number generator, as provided by crypto/rand.

That’s enough background that we can move on to what needed fixing in the math/rand package.

Problems with math/rand

Over time, we noticed more and more problems with math/rand. The most serious were the following.

Generator Algorithm

The generator itself needed replacement.

The initial implementation of Go, while production ready, was in many ways a “pencil sketch” of the entire system, working well enough to serve as a base for future development: the compiler and runtime were written in C; the garbage collector was a conservative, single-threaded, stop-the-world collector; and the libraries used basic implementations throughout. From Go 1 through around Go 1.5, we went back and drew the “fully inked” version of each of these: we converted the compiler and runtime to Go; we wrote a new, precise, parallel, concurrent garbage collection with microsecond pause times; and we replaced standard library implementations with more sophisticated, optimized algorithms as needed.

Unfortunately, the repeatability requirement in math/rand meant that we couldn’t replace the generator there without breaking compatibility. We were stuck with the Go 1 generator, which is reasonably fast (about 1.8ns per number on my M3 Mac) but maintains an internal state of almost 5 kilobytes. In contrast, Melissa O’Neill’s PCG family of generators generates better random numbers in about 2.1ns per number with only 16 bytes of internal state. We also wanted to explore using Daniel J. Bernstein’s ChaCha stream cipher as a generator. A follow-up post discusses that generator specifically.

Source Interface

The rand.Source interface was wrong. That interface defines the concept of a low-level random number generator that generates non-negative int64 values:

% go doc -src math/rand.Source
package rand // import "math/rand"

// A Source represents a source of uniformly-distributed
// pseudo-random int64 values in the range [0, 1<<63).
//
// A Source is not safe for concurrent use by multiple goroutines.
type Source interface {
    Int63() int64
    Seed(seed int64)
}

func NewSource(seed int64) Source
%

(In the doc comment, “[0, N)” denotes a half-open interval, meaning the range includes 0 but ends just before 2⁶³.)

The rand.Rand type wraps a Source to implement a richer set of operations, such as generating an integer between 0 and N, generating floating-point numbers, and so on.

We defined the Source interface to return a shortened 63-bit value instead of a uint64 because that’s what the Go 1 generator and other widely-used generators produce, and it matches the convention set by the C standard library. But this was a mistake: more modern generators produce full-width uint64s, which is a more convenient interface.

Another problem is the Seed method hard-coding an int64 seed: some generators are seeded by larger values, and the interface provides no way to handle that.

Seeding Responsibility

A bigger problem with Seed is that responsibility for seeding the global generator was unclear. Most users don’t use Source and Rand directly. Instead, the math/rand package provides a global generator accessed by top-level functions like Intn. Following the C standard library, the global generator defaults to behaving as if Seed(1) is called at startup. This is good for repeatability but bad for programs that want their random outputs to be different from one run to the next. The package documentation suggests using rand.Seed(time.Now().UnixNano()) in that case, to make the generator’s output time-dependent, but what code should do this?

Probably the main package should be in charge of how math/rand is seeded: it would be unfortunate for imported libraries to configure global state themselves, since their choices might conflict with other libraries or the main package. But what happens if a library needs some random data and wants to use math/rand? What if the main package doesn’t even know math/rand is being used? We found that in practice many libraries add init functions that seed the global generator with the current time, “just to be sure”.

Library packages seeding the global generator themselves causes a new problem. Suppose package main imports two packages that both use math/rand: package A assumes the global generator will be seeded by package main, but package B seeds it in an init func. And suppose that package main doesn’t seed the generator itself. Now package A’s correct operation depends on the coincidence that package B is also imported in the program. If package main stops importing package B, package A will stop getting random values. We observed this happening in practice in large codebases.

In retrospect, it was clearly a mistake to follow the C standard library here: seeding the global generator automatically would remove the confusion about who seeds it, and users would stop being surprised by repeatable output when they didn’t want that.

Scalability

The global generator also did not scale well. Because top-level functions like rand.Intn can be called simultaneously from multiple goroutines, the implementation needed a lock protecting the shared generator state. In parallel usage, acquiring and releasing this lock was more expensive than the actual generation. It would make sense instead to have a per-thread generator state, but doing so would break repeatability in programs without concurrent use of math/rand.

The Rand implementation was missing important optimizations

The rand.Rand type wraps a Source to implement a richer set of operations. For example, here is the Go 1 implementation of Int63n, which returns a random integer in the range [0, n).

func (r *Rand) Int63n(n int64) int64 {
    if n <= 0 {
        panic("invalid argument to Int63n")
    }
    max := int64((1<<63 - 1)  - (1<<63)%uint64(n))
    v := r.Int63()
    for v > max {
        v = r.Int63()
    }
    return v % n
}

The actual conversion is easy: v % n. However, no algorithm can convert 2⁶³ equally likely values into n equally likely values unless 2⁶³ is a multiple of n: otherwise some outputs will necessarily happen more often than others. (As a simpler example, try converting 4 equally likely values into 3.) The code computes max such that max+1 is the largest multiple of n less than or equal to 2⁶³, and then the loop rejects random values greater than or equal to max+1.

Rejecting these too-large values ensures that all n outputs are equally likely. For small n, needing to reject any value at all is rare; rejection becomes more common and more important for larger values. Even without the rejection loop, the two (slow) modulus operations can make the conversion more expensive than generating the random value v in the first place.

In 2018, Daniel Lemire found an algorithm that avoids the divisions nearly all the time (see also his 2019 blog post). In math/rand, adopting Lemire’s algorithm would make Intn(1000) 20-30% faster, but we can’t: the faster algorithm generates different values than the standard conversion, breaking repeatability.

Other methods are also slower than they could be, constrained by repeatability. For example, the Float64 method could easily be sped up by about 10% if we could change the generated value stream. (This was the change we tried to make in Go 1.2 and rolled back, mentioned earlier.)

The Read Mistake

As mentioned earlier, math/rand is not intended for and not suitable for generating cryptographic secrets. The crypto/rand package does that, and its fundamental primitive is its Read function and Reader variable.

In 2015, we accepted a proposal to make rand.Rand implement io.Reader as well, along with adding a top-level Read function. This seemed reasonable at the time, but in retrospect we did not pay enough attention to the software engineering aspects of this change. Now, if you want to read random data, you have two choices: math/rand.Read and crypto/rand.Read. If the data is going to be used for key material, it is very important to use crypto/rand, but now it is possible to use math/rand instead, potentially with disastrous consequences.

Tools like goimports and gopls have a special case to make sure they prefer to use rand.Read from crypto/rand instead of math/rand, but that’s not a complete fix. It would be better to remove Read entirely.

Fixing math/rand directly

Making a new, incompatible major version of a package is never our first choice: that new version only benefits programs that switch to it, leaving all existing usage of the old major version behind. In contrast, fixing a problem in the existing package has much more impact, since it fixes all the existing usage. We should never create a v2 without doing as much as possible to fix v1. In the case of math/rand, we were able to partly address a few of the problems described above:

These fixes are imperfect and incomplete but also real improvements that helped all users of the existing math/rand package. For more complete fixes, we needed to turn our attention to math/rand/v2.

Fixing the rest in math/rand/v2

Defining math/rand/v2 took significant planning, then a GitHub Discussion and then a proposal discussion. It is the same as math/rand with the following breaking changes addressing the problems outlined above:

Principles for evolving the Go standard library

As mentioned at the start this post, one of the goals for this work was to establish principles and a pattern for how we approach all v2 packages in the standard library. There will not be a glut of v2 packages in the next few Go releases. Instead, we will handle one package at a time, making sure we set a quality bar that will last for another decade. Many packages will not need a v2 at all. But for those that do, our approach boils down to three principles.

First, a new, incompatible version of a package will use that/package/v2 as its import path, following semantic import versioning just like a v2 module outside the standard library would. This allows uses of the original package and the v2 package to coexist in a single program, which is critical for a gradual conversion to the new API.

Second, all changes must be rooted in respect for existing usage and users: we must not introduce needless churn, whether in the form of unnecessary changes to an existing package or an entirely new package that must be learned instead. In practice, that means we take the existing package as the starting point and only make changes that are well motivated and provide a value that justifies the cost to users of updating.

Third, the v2 package must not leave v1 users behind. Ideally, the v2 package should be able to do everything the v1 package could do, and when v2 is released, the v1 package should be rewritten to be a thin wrapper around v2. This would ensure that existing uses of v1 continue to benefit from bug fixes and performance optimizations in v2. Of course, given that v2 is introducing breaking changes, this is not always possible, but it is always something to consider carefully.

For math/rand/v2, we arranged for the auto-seeded v1 functions to call the v2 generator, but we were unable to share other code due to the repeatability violations. Ultimately math/rand is not a lot of code and does not require regular maintenance, so the duplication is manageable. In other contexts, more work to avoid duplication could be worthwhile. For example, in the encoding/json/v2 design (still in progress), although the default semantics and the API are changed, the package provides configuration knobs that make it possible to implement the v1 API.

When we eventually ship encoding/json/v2, encoding/json (v1) will become a thin wrapper around it, ensuring that users who don’t migrate from v1 still benefit from optimizations and security fixes in v2.

A follow-up blog post presents the ChaCha8 generator in more detail.

By Russ Cox

This article is available on The Go Blog under a CC BY 4.0 DEED license.

Photo by Roman Mager on Unsplash