proposal: runtime: expose current thread id or processor id

[funny-falcon]

Often there is a need to reduce lock contention in algorithms.
Usual way to acomplish this is sharding, ie several separate locks protects non-intersecting parts of greater state.
But then there is a need for fast (and preferably non-locking) way to determine shard id.
And it will be great, if such shard id will further reduce lock contention.

• Best way to do it is exposing current cpu number. On Intel cpu it could be done with CPUID instruction.
  CPUID it returns APIC-ID which are not consecutive, so probably runtime should analyze CPU topology to convert APIC-ID to consecutive cpu-number. On the other way, given some architectures allows hot cpu swapping, probably it is better to return APIC-ID as is.
• Simple way is to expose thread id getg().m.id as runtime.Mid() . Cause program could contain a lot of threads (due to system calls, or cgo calls), there is a need to additional fast random value, so I propose to additionally expose runtime.fastrand() as runtime.Fastrand() (mixing it with secure random key to hide original fastrand value).

"Best way" could be implemented in some "golang/x/" package. "Simple way" needs to implement in "runtime" at least wrapper around "getg().m.id", to link with this wrapper from external library (if there is a way to call private "runtime" function from external package).

[ianlancetaylor]

Historically we have always rejected goroutine-local information.

Your proposal is incomplete: you need to define exactly when the value is permitted to change, and you need to do so without overly constraining the runtime. Right now a g is permitted to move to a different m or p at any function call, which includes several implicit function calls inserted by the compiler for things like map opertions. In order to address #10958 it is likely that in future a releases a g will be permitted to move to a different m or p in any loop. It's not enough to define runtime.Mid without also providing a clear explanation for when it will return a different value.

The discussion in #17973 may be of interest.

[funny-falcon]

Result of runtime.Mid() could be changed at any moment.
Value, returned from Mid() doesn't eliminate need of locking: since number of threads could be much larger than preallocated number of shards, locks are inevitable.
And since several threads could map into same shard number, there is a need for runtime.Fastrand(): shards are bucketized, bucket is choosen by Mid, shard in the bucket by Fastrand.
Mid() combined with Fastrand() are just a hint for reducing lock contention, but doesn't eliminates locks completely.

[mdempsky]

And since several threads could map into same shard number, there is a need for runtime.Fastrand(): shards are bucketized, bucket is choosen by Mid, shard in the bucket by Fastrand.

If runtime.Mid changes (e.g., because the goroutine is now being run on a new OS thread), how do you make sure a goroutine continues to use the correct bucket?

In case the answer is that each goroutine only calls runtime.Mid once, then why not just use math/rand.Int?

[funny-falcon]

make sure a goroutine continues to use the correct bucket?

It is just hint to select a bucket. Per-shard mutex still will be acquired, so there is no "fail" if runtime.Mid will be changed after call. But most of time it will be not changed, and this will help to reduce mutex contention.

Problem with math/rand.Int is single global mutex around this call. See my previous closed proposal: #18514

BenchmarkFastRand-4             500000000                3.49 ns/op
BenchmarkFastRand-4             500000000                3.49 ns/op
BenchmarkMathRand-4             10000000               162 ns/op
BenchmarkMathRand-4             10000000               159 ns/op

[quentinmit]

Does syscall.Gettid not give you a thread ID that roughly meets this criteria already? Why does the runtime need to provide it?

[funny-falcon]

I bet syscall.Gettid is expensive. No?

[kostya-sh]

Somewhat related note. One way to make a thread safe and reasonably scalable random generator using currently available in the standard library functionality is by pooling rand.Rand instances in sync.Pool: https://github.com/kostya-sh/talk-golangsg-scalability/blob/master/benchmarks/rand_test.go

…

On Jan 10, 2017 4:25 PM, "Sokolov Yura" ***@***.***> wrote: make sure a goroutine continues to use the correct bucket? It is just hint to select a bucket. Per-shard mutex still will be acquired, so there is no "fail" if runtime.Mid will be changed after call. But most of time it will be not changed, and this will help to reduce mutex contention. Problem with math/rand.Int is single global mutex around this call. See my previous closed proposal: #18514 <#18514> BenchmarkFastRand-4 500000000 3.49 ns/op BenchmarkFastRand-4 500000000 3.49 ns/op BenchmarkMathRand-4 10000000 162 ns/op BenchmarkMathRand-4 10000000 159 ns/op — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#18590 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AGy9A73TrfgcihZjqfmkzuspR9S9FgBLks5rQ7D5gaJpZM4LfTNe> .

[funny-falcon]

Probably, syscall.Gettid() is not so expensive on Linux, but it is much more expensive on other platforms (and probably doesn't exists on Windows).

[funny-falcon]

@kostya-sh Here is example of usage of runtime.Mid() and runtime.Fastrand() based on your benchmark: https://gist.github.com/funny-falcon/d8adc39e777b79e56274a65abca29e78

results are:

BenchmarkRandInt63_Global-4                     10000000               154 ns/op
BenchmarkRandInt63_Channel-4                    10000000               220 ns/op
BenchmarkRandInt63_Pool-4                       50000000                28.8 ns/op
BenchmarkSourceInt63_Pool-4                     50000000                34.9 ns/op
BenchmarkRandInt63_Source-4                     300000000                5.71 ns/op
BenchmarkRandInt63_ShardsGettid-4               50000000                29.2 ns/op
BenchmarkRandInt63_ShardsMid-4                  100000000               14.2 ns/op
BenchmarkRandInt63_ShardsFastrand-4             30000000                49.0 ns/op
BenchmarkRandInt63_ShardsMidFastrand-4          100000000               17.1 ns/op

It shows that using Mid() (and combination with Fastrand()) could be almost twice faster than single Pool.

[funny-falcon]

Looks like exposing getg().m.p.ptr().id gives even better results.

[funny-falcon]

Looks like sync.Pool already uses hiddenly exposed getg().m.p.ptr().id (through runtime_procPin). So, effectiveness of sharding by P.id is known to core team.

So why not expose it to regular Go users?

(of cause, runtime_procPin does more than simply returning current P.id.
But just returning P.id with runtime.Pid() will be already great help).

[bradfitz]

So why not expose it to regular Go users?

Because Go considers simplicity a virtue. When there are trade-offs between simplicity and performance, Go considers simplicity. You seem to have a different value trade-off, and it's obvious you prefer performance above all else. That's probably why many of your proposals to Go end up getting rejected. Please keep that in mind for future proposals.

We understand that things can be always be faster, and we want things to be fast, but only if things are also simple and have clean APIs. We do not want to document and support and export all possible innards.

[funny-falcon]

But such thing as P.id is very simple thing. Does anyone expect changing of Go runtime scheduler core schema? Will P ever be removed?