Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

math/rand: reconsider lock-free source #49892

Closed
oakad opened this issue Dec 1, 2021 · 20 comments
Closed

math/rand: reconsider lock-free source #49892

oakad opened this issue Dec 1, 2021 · 20 comments
Labels
FrozenDueToAge NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one.
Milestone

Comments

@oakad
Copy link

oakad commented Dec 1, 2021

Hereby, I would like to petition to reopen and salvage #18514.
There are several areas where having a global, performant and lock free random source is of very high utility.

  1. Development/testing of concurrent apps/algorithms (and Go is all about concurrency). One of the most potent techniques in this area requires placing random delays all over the code to emulate uneven progress of concurrent goroutines. Present implementation of rand.Int() with a global lock in its path all but negates the usefulness of this approach.

  2. Zero communication "unfair" sharing. Go is commonly used to implement various proxies, load balancers and other similar gadgets, which require "unfair" sharing of resources across multiple instances (example applications include AB testing, canary deployments, various types of hot failovers and so on). This can be efficiently achieved by means of random selection with custom probability distribution and very efficient algorithms were developed for this purpose (such as Walker-Vose O(1) uneven sampling algorithm). Unfortunately, "unfair" selection can only be as performant as the underlying uniform random source is.

  3. "Locally distributed" data structures. A good, simple example of those is Java's java.util.concurrent.atomic.LongAccumulator and friends (however, same technique can be applied to other similarly constructed objects, such as concurrent pools, multiple producer queues, and so on). sync.Pool cunningly uses the private fastrand(), we, the users, want one too! :-)

In most other languages these problems are resolved by means of thread local PRNGs. In my opinion, Go should also expose one, or, rather, make its global PRNG instance behave like one. It does not even requires any changes to the language, because at present users have no ability to affect the private rand.globalRand object in any way and thus can have no preference on what sort of pseudo-random sequence is returned from gloabal rand functions.

@gopherbot gopherbot added this to the Proposal milestone Dec 1, 2021
@mdlayher mdlayher changed the title Proposal: reopen and salvage #18514 (because fast, lock free rand.Int() is a really useful thing) Proposal: reconsider lock-free math/rand source Dec 1, 2021
@mdlayher mdlayher changed the title Proposal: reconsider lock-free math/rand source Proposal: math/rand: reconsider lock-free source Dec 1, 2021
@DeedleFake
Copy link

Go purposefully has no thread-local storage system, and it even purposefully avoids exposing anything that would make it easy to implement one, like IDs. One could be implemented for something like this, but it would be preferable for people to just instantiate their own rand.Rands and keep track of them themselves, I think.

That being said, as you point out it wouldn't exactly be terrible for the global rand.Rand instance to behave that way. It could be considered a breaking change, however, and especially since it can be relatively easily worked around, I don't think this is likely to get accepted. I could be wrong, though.

@oakad
Copy link
Author

oakad commented Dec 1, 2021

Of course, I don't want this to be about thread local, it's a long and difficult topic (just mentioned it for the context).

All I personally need is exported and inlineable runtime.Fastrand(), but it may be called rand.Uint32() just the same. Even though having a similar 64b version will be nice too.

The previous proposal was accepted. And not, it's not easy to achieve the same behavior with rand.Rand, you're welcome to try. It's not for the fainthearted though. :-)

@DeedleFake
Copy link

DeedleFake commented Dec 1, 2021

In that case, while I would certainly not be against exporting fastrand() in some way, it should be noted that you can use a //go:linkname directive to get direct access to it. Maybe the math/rand package can just do something like

//go:linkname Runtime runtime.fastrand
func Runtime() uint32

And I very much know how difficult it is to deal with performance and concurrency with rand.Rand. I had to once and it caused me all sorts of problems. I wound up faking it, as it didn't really matter that much for what I was doing. Speaking of which, I still need to go clean that mess up... I haven't touched it in years.

@oakad
Copy link
Author

oakad commented Dec 1, 2021

I know about the go:linkname hack. Everybody who's doing the sort of thing I enumerated in my OP does. :-)

My point here that time has come to make it nice and official. In fact, this was the case even back in 2017, pretty unfortunate that the previous proposal was closed, with implementation almost ready and reviewed.

@robpike
Copy link
Contributor

robpike commented Dec 1, 2021

See #21835

The exp/rand package might help you today.

@cespare
Copy link
Contributor

cespare commented Dec 1, 2021

Using exp/rand makes it cheaper to create per-goroutine sources, but sometimes it is not convenient to structure the code this way.

I still think the best solution here is to implement #18802 in some form. Then people can create their own CPU-local RNGs easily enough.

Failing that, I think adding a CPU-local RNG in the stdlib would be good. It doesn't have the API concerns of a more general sharding mechanism: the per-CPU-ness isn't user-observable except insofar that the global functions don't see a huge slowdown in highly parallel contexts.

I have an experimental demonstration of one #18802 solution at github.com/cespare/percpu and it includes a wrapper around exp/rand as github.com/cespare/percpu/clrand, in case anyone would like to see how these ideas could look and perform. (But beware that there's a go:linkname hack under the hood.)

@oakad
Copy link
Author

oakad commented Dec 2, 2021

We can either make sharded values with fast random sources or we can make fast random sources with sharded values. Sort of like chickens and eggs. :-)

@ianlancetaylor ianlancetaylor changed the title Proposal: math/rand: reconsider lock-free source proposal: math/rand: reconsider lock-free source Dec 2, 2021
@ianlancetaylor ianlancetaylor added this to Incoming in Proposals (old) Dec 2, 2021
@ianlancetaylor
Copy link
Contributor

There are lots of things we could shared on a per-goroutine or per-thread or per-P basis (a P is the entity counted by GOMAXPROCS). For example, we've built magic into sync.Pool to shard it across P's (but that's not so bad since sync.Pool is also magic with respect to garbage collection). It's not clear to me that random numbers are important enough to shard in this away. Or, perhaps the desire to shard them suggests that there should be some general mechanism to support sharding. While there are natural concerns with sharding across goroutines, as that can easily lead to a complicated programming model, sharding across threads or P's is perhaps less bad; the lack of a persistent connection between a goroutine and a thread or P may sufficiently limit the effect on the programming model. Maybe.

@oakad
Copy link
Author

oakad commented Dec 2, 2021

What's wrong with defining user visible rand.Uint32() in terms of internal runtime.fastrand()? No fancy stuff, just that and call it a day.

This is the de-facto situation today with the linkname thing.

@josharian
Copy link
Contributor

See also a slightly more general discussion of the interaction between concurrency and reproducibility guarantees at #26263.

@ianlancetaylor
Copy link
Contributor

@oakad I think that in effect you are suggesting that random numbers are important enough that we should shard them across P's. Why is that?

(The fact that the current implementation happens to have an existing mechanism for doing that isn't an argument for why it should be done in user space. We shouldn't in general reason from a particular implementation.)

@oakad
Copy link
Author

oakad commented Dec 3, 2021

(Original comment replaced with this. Sorry.)

I have went on to see what people do on Github in general. Right now, there are several common techniques to obtain fast randoms:

  1. Linkname to runtime.fastrand. Generally, appears to be a favorite approach, but requires unsafe and generally suboptimal, because fastrand is not inlined.
  2. sync.Pool of PRNGs seeded from something. This approach feels totally dubious to me, especially considering how sync.Pool is implemented. Sort of like always driving in reverse.
  3. Fake "thread local" by means of syscall.Gettid. Various approaches possible, but again, a strong feeling of "driving in reverse".
  4. Assembler (rdrand or rdtsc sometimes). We are at the mercy of the hardware platform, especially considering all the evils Intel had done to rdrand (on some CPUs it's actually very slow these days).

@oakad
Copy link
Author

oakad commented Jul 22, 2022

Somehow it feels that newly added maphash.MakeSeed could solve the present problem.

The users are allowed to call it at will affecting the generator state, but god forbid mere mortals from using that puny random value directly without jumping through hoops. :-)

@aclements
Copy link
Member

Now that #54880 has been accepted and the implementation has landed, it should be possible to make the global source lock-free.

@rsc
Copy link
Contributor

rsc commented Feb 1, 2023

Now that math/rand defaults to a pre-seeded random generator, this is not an API change and does not need to be a proposal. (Of course, any implementation needs to respect the GODEBUG to get back to the old behavior, and it needs to disable the lock-free generator when rand.Seed has been called.)

@rsc
Copy link
Contributor

rsc commented Feb 1, 2023

Removed from the proposal process.
This was determined not to be a “significant change to the language, libraries, or tools”
or otherwise of significant importance or interest to the broader Go community.
— rsc for the proposal review group

@ianlancetaylor
Copy link
Contributor

My understanding is that the specific suggestion is that we change the functions that currently use globalRand such that if

  • the GODEBUG setting randautoseed=0 is not used, and
  • nothing has called rand.Seed

then those functions will use a more efficient lock-free random number generator.

The affected functions would be: Int63, Uint32, Uint64, Int31, Int, Int63n, Int31n, Intn, Float64, Float32, Perm, Shuffle, Read, NormFloat64, ExpFloat64.

Those functions will become some sort of atomic load to see if we can call the fast random number generator, followed by that call.

@oakad
Copy link
Author

oakad commented Feb 2, 2023

"it should be possible to make the global source lock-free"

How creating another level of PRNG indirection in some unspecified future is any better than simply exposing fastrand?

@flyingmutant
Copy link
Contributor

flyingmutant commented Feb 2, 2023

If you just want to access runtime.fastrand64, it is possible even without unsafe and with relatively low overhead. I've used this trick in my take on rand:

import "hash/maphash"

func rand64() uint64 {
	return maphash.Bytes(maphash.MakeSeed(), nil)
}

@seankhliao seankhliao changed the title proposal: math/rand: reconsider lock-free source math/rand: reconsider lock-free source Feb 2, 2023
@seankhliao seankhliao added NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. and removed Proposal labels Feb 2, 2023
@seankhliao seankhliao modified the milestones: Proposal, Unplanned Feb 2, 2023
@gopherbot
Copy link

Change https://go.dev/cl/465037 mentions this issue: math/rand: use fastrand64 if possible

johanbrandhorst pushed a commit to Pryz/go that referenced this issue Feb 12, 2023
Now that the top-level math/rand functions are auto-seeded by default
(issue golang#54880), use the runtime fastrand64 function when 1) Seed
has not been called; 2) the GODEBUG randautoseed=0 is not used.

The benchmarks run quickly and are relatively noisy, but they show
significant improvements for parallel calls to the top-level functions.

goos: linux
goarch: amd64
pkg: math/rand
cpu: 11th Gen Intel(R) Core(TM) i7-11850H @ 2.50GHz
                           │  /tmp/foo.1   │              /tmp/foo.2               │
                           │    sec/op     │    sec/op      vs base                │
Int63Threadsafe-16            11.605n ± 1%    3.094n ±  1%  -73.34% (p=0.000 n=10)
Int63ThreadsafeParallel-16   67.8350n ± 2%   0.4000n ±  1%  -99.41% (p=0.000 n=10)
Int63Unthreadsafe-16           1.947n ± 3%    1.924n ±  2%        ~ (p=0.189 n=10)
Intn1000-16                    4.295n ± 2%    4.287n ±  3%        ~ (p=0.517 n=10)
Int63n1000-16                  4.379n ± 0%    4.192n ±  2%   -4.27% (p=0.000 n=10)
Int31n1000-16                  3.641n ± 3%    3.506n ±  0%   -3.69% (p=0.000 n=10)
Float32-16                     3.330n ± 7%    3.250n ±  2%   -2.40% (p=0.017 n=10)
Float64-16                     2.194n ± 6%    2.056n ±  4%   -6.31% (p=0.004 n=10)
Perm3-16                       43.39n ± 9%    38.28n ± 12%  -11.77% (p=0.015 n=10)
Perm30-16                      324.4n ± 6%    315.9n ± 19%        ~ (p=0.315 n=10)
Perm30ViaShuffle-16            175.4n ± 1%    143.6n ±  2%  -18.15% (p=0.000 n=10)
ShuffleOverhead-16             223.4n ± 2%    215.8n ±  1%   -3.38% (p=0.000 n=10)
Read3-16                       5.428n ± 3%    5.406n ±  2%        ~ (p=0.780 n=10)
Read64-16                      41.55n ± 5%    40.14n ±  3%   -3.38% (p=0.000 n=10)
Read1000-16                    622.9n ± 4%    594.9n ±  2%   -4.50% (p=0.000 n=10)
Concurrent-16                136.300n ± 2%    4.647n ± 26%  -96.59% (p=0.000 n=10)
geomean                        23.40n         12.15n        -48.08%

Fixes golang#49892

Change-Id: Iba75b326145512ab0b7ece233b98ac3d4e1fb504
Reviewed-on: https://go-review.googlesource.com/c/go/+/465037
Run-TryBot: Ian Lance Taylor <iant@golang.org>
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Ian Lance Taylor <iant@google.com>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
Reviewed-by: Russ Cox <rsc@golang.org>
Auto-Submit: Ian Lance Taylor <iant@google.com>
tklauser added a commit to cilium/cilium that referenced this issue Dec 8, 2023
Since Go 1.20 the top-level math/rand functions are auto-seeded by
default, see https://go.dev/doc/go1.20#library and
golang/go#54880. They also use the runtime's
lock-free fastrand64 function when 1. Seed has not been called and 2.
GODEBUG=randautoseed=0 is not used, see
golang/go#49892.

This allows to drop SafeRand and use the global source again. SafeRand
was introduced in commit fac5dde ("rand: add and use
concurrency-safe PRNG source") to fix #10988 by providing a
concurrency-safe PRNG source other than the global math/rand source
which couldn't be used at the time because it can't be interfered with
from unrelated packages by means of calling rand.Seed, see #10575.
rand.Seed is deprecated since GO 1.20 and per the paragraph above the
global source is seeded by default. This makes it unlikely that packages
would interfere with the global PRNG state anymore and the top-level
math/rand functions are safe to use again.

Signed-off-by: Tobias Klauser <tobias@cilium.io>
tklauser added a commit to cilium/cilium that referenced this issue Dec 8, 2023
Since Go 1.20 the top-level math/rand functions are auto-seeded by
default, see https://go.dev/doc/go1.20#library and
golang/go#54880. They also use the runtime's
lock-free fastrand64 function when 1. Seed has not been called and 2.
GODEBUG=randautoseed=0 is not used, see
golang/go#49892.

This allows to drop SafeRand and use the global source again. SafeRand
was originally introduced in commit fac5dde ("rand: add and use
concurrency-safe PRNG source") to fix #10988 by providing a
concurrency-safe PRNG source other than the global math/rand source
which could be used at the time because it can't be interfered with from
unrelated packages by means of calling rand.Seed, see #10575. rand.Seed
is deprecated since Go 1.20 and per the paragraph above the global
source is seeded by default. This makes it unlikely that packages would
interfere with the global PRNG state anymore and the top-level math/rand
functions are safe to use again.

Signed-off-by: Tobias Klauser <tobias@cilium.io>
tklauser added a commit to cilium/cilium that referenced this issue Dec 8, 2023
Since Go 1.20 the top-level math/rand functions are auto-seeded by
default, see https://go.dev/doc/go1.20#library and
golang/go#54880. They also use the runtime's
lock-free fastrand64 function when 1. Seed has not been called and 2.
GODEBUG=randautoseed=0 is not used, see
golang/go#49892.

This allows to drop SafeRand and use the global source again. SafeRand
was originally introduced in commit fac5dde ("rand: add and use
concurrency-safe PRNG source") to fix #10988 by providing a
concurrency-safe PRNG source other than the global math/rand source
which could be used at the time because it can't be interfered with from
unrelated packages by means of calling rand.Seed, see #10575. rand.Seed
is deprecated since Go 1.20 and per the paragraph above the global
source is seeded by default. This makes it unlikely that packages would
interfere with the global PRNG state anymore and the top-level math/rand
functions are safe to use again.

Signed-off-by: Tobias Klauser <tobias@cilium.io>
tklauser added a commit to cilium/cilium that referenced this issue Dec 8, 2023
Since Go 1.20 the top-level math/rand functions are auto-seeded by
default, see https://go.dev/doc/go1.20#library and
golang/go#54880. They also use the runtime's
lock-free fastrand64 function when 1. Seed has not been called and 2.
GODEBUG=randautoseed=0 is not used, see
golang/go#49892.

This allows to drop SafeRand and use the global source again. SafeRand
was originally introduced in commit fac5dde ("rand: add and use
concurrency-safe PRNG source") to fix #10988 by providing a
concurrency-safe PRNG source other than the global math/rand source
which could be used at the time because it can't be interfered with from
unrelated packages by means of calling rand.Seed, see #10575. rand.Seed
is deprecated since Go 1.20 and per the paragraph above the global
source is seeded by default. This makes it unlikely that packages would
interfere with the global PRNG state anymore and the top-level math/rand
functions are safe to use again.

Signed-off-by: Tobias Klauser <tobias@cilium.io>
tklauser added a commit to cilium/cilium that referenced this issue Dec 8, 2023
Since Go 1.20 the top-level math/rand functions are auto-seeded by
default, see https://go.dev/doc/go1.20#library and
golang/go#54880. They also use the runtime's
lock-free fastrand64 function when 1. Seed has not been called and 2.
GODEBUG=randautoseed=0 is not used, see
golang/go#49892.

This allows to drop SafeRand and use the global source again. SafeRand
was originally introduced in commit fac5dde ("rand: add and use
concurrency-safe PRNG source") to fix #10988 by providing a
concurrency-safe PRNG source other than the global math/rand source
which could be used at the time because it can't be interfered with from
unrelated packages by means of calling rand.Seed, see #10575. rand.Seed
is deprecated since Go 1.20 and per the paragraph above the global
source is seeded by default. This makes it unlikely that packages would
interfere with the global PRNG state anymore and the top-level math/rand
functions are safe to use again.

Signed-off-by: Tobias Klauser <tobias@cilium.io>
@golang golang locked and limited conversation to collaborators Feb 7, 2024
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
FrozenDueToAge NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one.
Projects
No open projects
Development

No branches or pull requests