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

runtime: trim unnecessary fields from scase #40410

Closed
mdempsky opened this issue Jul 26, 2020 · 16 comments
Closed

runtime: trim unnecessary fields from scase #40410

mdempsky opened this issue Jul 26, 2020 · 16 comments
Labels
FrozenDueToAge NeedsFix The path to resolution is known, but the work has not been done.
Milestone

Comments

@mdempsky
Copy link
Member

Currently the runtime.scase structure is 5 words (6 words on 32-bit machines):

type scase struct {
	c           *hchan         // chan
	elem        unsafe.Pointer // data element
	kind        uint16
	pc          uintptr // race pc (for race detector / msan)
	releasetime int64
}

I think this can be trimmed down to just 2: c and elem. Here's how:

  1. The pc field is only needed for race-instrumented builds. Instead of embedding it directly into the scase array (and using stack space even for non-instrumented builds), we can split it out into a separate array that's prepended to the pollorder/lockorder arrays for race-instrumented builds, and omitted entirely for race-instrumented builds. (We'd prepend it because uintptr has stricter alignment than uint16.)

  2. The releasetime field is only needed for the case that actually succeeds. Rather than adding it to each scase, we can just have an extra casreleasetime local variable that parallels cas and casi. (I think: I'm least confident about this as I'm not familiar with the runtime's blocking profiling.)

  3. The kind field currently disambiguates four cases: send, recv, default, and nil. We can eliminate this field with a sequence of three optimizations:

    1. There can be only one default case. So instead of emitting a dummy scase to represent the default case, selectgo can just take an extra boolean parameter indicating whether the call should block or not. When in non-blocking mode, selectgo should just return -1 as the case index, and callers can handle this accordingly. This would simplify selectgo, because it wouldn't need to search for and remember where the caseDefault case is.

    2. caseNil is used internally within selectgo to simplify skipping over send/recv cases with c is nil. But instead of doing it this way, selectgo could simply omit nil-c cases from the pollorder and lockorder arrays when they're constructed. Then the rest of code will naturally skip over them.

    3. That leaves just send and recv cases. Because the runtime is going to randomize the order that cases will be processed anyway, the compiler can simply arrange that send cases always precede receive cases (or vice versa), and split ncases into nsends and nrecvs. Then selectgo can discern send and recv cases by just comparing the case index (e.g., if sends are ordered before receives, then casi < nsends would indicate cas is a send operation).

      Requiring sends before recvs will be slightly more work for reflect.Select, but it shouldn't be too bad. It already has to translate from []reflect.SelectCase to []runtime.scase (and currently it goes through an extra step and extra heap allocations with runtime.runtimeSelect). It should be easy to construct the latter by placing sends at the front of the slice and receives at the rear (remember: order in []runtime.scase doesn't matter), and just tracking a correspondence of array indices to translate selectgo's return value back.

/cc @aclements

@mdempsky mdempsky added the NeedsFix The path to resolution is known, but the work has not been done. label Jul 26, 2020
@mdempsky mdempsky added this to the Go1.16 milestone Jul 26, 2020
@josharian
Copy link
Contributor

As it stands, eliminating just one of these will likely help considerably, as it will make this struct SSA-able.

@mdempsky
Copy link
Member Author

It looks like per-scase releasetime is intended to help when the select is awoken because of a channel closing. However, it turns out this code has corner cases that would be addressed by replacing it with a single casreleasetime variable like I suggest.

When selectgo is awoken by a channel closing, it doesn't know which sudog triggered the wakeup, because closechan sets gp.param = nil. To handle this, selectgo polls all of the select cases again, knowing it will succeed this time. And to account for this, selectgo also writes each sudog's releasetime back into the corresponding scase.

However, there's no guarantee that the re-poll will actually pick the same case that triggered the wakeup. It's possible that between the channel close wakeup and the goroutine getting to run, other cases might become ready too. If one of these other cases ends up getting selected on the re-poll, we'll never end up recording a block event.

As an extreme but somewhat contrived example (involving selecting on the same channel twice), this program spends a total of 1 second blocked waiting for the select statement, but this doesn't show up in the pprof output at all: https://play.golang.org/p/HoK4YDLwEvb

The more realistic example, this program also spends 1 second blocked waiting for the select statement, but pprof only reports about 1/4 of the time spent blocked: https://play.golang.org/p/ldCvE6fYYZQ

@gopherbot
Copy link

Change https://golang.org/cl/245019 mentions this issue: runtime: add "success" field to sudog

@gopherbot
Copy link

Change https://golang.org/cl/245124 mentions this issue: runtime: split PCs out of scase

@gopherbot
Copy link

Change https://golang.org/cl/245126 mentions this issue: cmd/compile/internal/gc: cleanup walkselectcases slightly

@gopherbot
Copy link

Change https://golang.org/cl/245123 mentions this issue: runtime: omit nil-channel cases from selectgo's orders

@gopherbot
Copy link

Change https://golang.org/cl/245125 mentions this issue: runtime: eliminate scase.kind field

@gopherbot
Copy link

Change https://golang.org/cl/245122 mentions this issue: runtime: remove scase.releasetime field

@mdempsky
Copy link
Member Author

Uploaded a WIP patch series that implements this.

The change to separate the pc field into a separate array is failing on race detector builds because of a use of select within the runtime. Because we turn off instrumentation when building the runtime, it wasn't actually setting pc before. (So it was a good thing I decided in CL 245124 to be conservative about not trying to optimize argument passing just yet.)

Easy fix is probably to create and populate the pcs array when -race is set, even for packages that normally suppress instrumentation.

@mdempsky
Copy link
Member Author

Some notes to self on more cleanup still to do:

  1. The nsends and nrecvs parameters can be uint16 instead. Since nsends/nrecvs/block are all constant values at call sites, this would probably save a couple bytes of instructions at call sites.

  2. runtime.reflect_rselect needs to be tweaked to correctly handle when there's only a default case. (There should probably be a test for this too.)

  3. reflect.runtimeSelect should be updated to match runtime.scase so that reflect.Value.Select can directly call selectgo rather that another translation function.

@mdempsky
Copy link
Member Author

  1. The nsends and nrecvs parameters can be uint16 instead. Since nsends/nrecvs/block are all constant values at call sites, this would probably save a couple bytes of instructions at call sites.

We currently allow nsends and nrecvs up to 65536, and there's even a test for this: reflect.TestSelectMaxCases. So limiting nsends and nrecvs to uint16 is a little tricky.

The easiest solution would be to just reduce the max cases from 65536 to 65535. Then they'll trivially fit into uint16.

The harder solution is to take advantage of the invariant 0 < nsends+nrecvs <= 65536 to encode them into 32 bits.

@ianlancetaylor
Copy link
Contributor

I think reducing to 65535 would be OK. The point of TestSelectMaxCases is not so much that the max is 65536, but that the panic when we exceed the max is a reasonable one (it used to be slice index out of bounds, which was not reasonable).

gopherbot pushed a commit that referenced this issue Aug 18, 2020
The current wakeup protocol for channel communications is that the
second goroutine sets gp.param to the sudog when a value is
successfully communicated over the channel, and to nil when the wakeup
is due to closing the channel.

Setting nil to indicate channel closure works okay for chansend and
chanrecv, because they're only communicating with one channel, so they
know it must be the channel that was closed. However, it means
selectgo has to re-poll all of the channels to figure out which one
was closed.

This commit adds a "success" field to sudog, and changes the wakeup
protocol to always set gp.param to sg, and to use sg.success to
indicate successful communication vs channel closure.

While here, this also reorganizes the chansend code slightly so that
the sudog is still released to the pool if the send blocks and then is
awoken because the channel closed.

Updates #40410.

Change-Id: I6cd9a20ebf9febe370a15af1b8afe24c5539efc6
Reviewed-on: https://go-review.googlesource.com/c/go/+/245019
Run-TryBot: Matthew Dempsky <mdempsky@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Cuong Manh Le <cuong.manhle.vn@gmail.com>
Reviewed-by: Keith Randall <khr@golang.org>
gopherbot pushed a commit that referenced this issue Aug 18, 2020
selectgo will report at most one block event, so there's no need to
keep a releasetime for every select case. It suffices to simply track
the releasetime of the case responsible for the wakeup.

Updates #40410.

Change-Id: I72679cd43dde80d7e6dbab21a78952a4372d1e79
Reviewed-on: https://go-review.googlesource.com/c/go/+/245122
Run-TryBot: Matthew Dempsky <mdempsky@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Keith Randall <khr@golang.org>
gopherbot pushed a commit that referenced this issue Aug 18, 2020
Currently, selectgo does an initial pass over the cases array to look
for entries with nil channels, so they can be easily recognized and
skipped later on. But this still involves actually visiting the cases.

This commit changes selectgo to omit cases with nil channels when
constructing pollorder, so that they'll be skipped over entirely later
on. It also checks for caseDefault up front, which will facilitate
changing it to use a "block bool" parameter instead.

Updates #40410.

Change-Id: Icaebcb8f08df03cc33b6d8087616fb5585f7fedd
Reviewed-on: https://go-review.googlesource.com/c/go/+/245123
Run-TryBot: Matthew Dempsky <mdempsky@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Keith Randall <khr@golang.org>
gopherbot pushed a commit that referenced this issue Aug 18, 2020
Per-case PCs are only needed for race detector builds, so this allows
skipping allocating stack space for them for non-race builds.

It's possible to arrange the PCs and order arrays consecutively in
memory so that we could just reuse the order0 pointer to identify
both. However, there's more risk of that silently going wrong, so this
commit passes them as separate arguments for now. We can revisit this
in the future.

Updates #40410.

Change-Id: I8468bc25749e559891cb0cb007d1cc4a40fdd0f8
Reviewed-on: https://go-review.googlesource.com/c/go/+/245124
Reviewed-by: Keith Randall <khr@golang.org>
gopherbot pushed a commit that referenced this issue Aug 18, 2020
Remove some unnecessary code. Most significantly, we can skip testing
"if ch == nil { block() }", because this is already the semantics
implied by normal send/receive operations.

Updates #40410.

Change-Id: I4acd33383cc876719fc3b998d85244d4ac1ff9d9
Reviewed-on: https://go-review.googlesource.com/c/go/+/245126
Run-TryBot: Matthew Dempsky <mdempsky@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Cuong Manh Le <cuong.manhle.vn@gmail.com>
@gopherbot
Copy link

Change https://golang.org/cl/279735 mentions this issue: This is the gofrontend version of https://golang.org/cl/245125.

@gopherbot
Copy link

Change https://golang.org/cl/279734 mentions this issue: runtime: add "success" field to sudog

@gopherbot
Copy link

Change https://golang.org/cl/279733 mentions this issue: runtime: omit nil-channel cases from selectgo's orders

@gopherbot
Copy link

Change https://golang.org/cl/279732 mentions this issue: runtime: remove scase.releasetime field

gopherbot pushed a commit to golang/gofrontend that referenced this issue Dec 22, 2020
This is the gofrontend version of https://golang.org/cl/245122.
Original CL description:

    selectgo will report at most one block event, so there's no need to
    keep a releasetime for every select case. It suffices to simply track
    the releasetime of the case responsible for the wakeup.

    Updates golang/go#40410.

This is being brought over to gofrontend as a step toward upgrading to
Go1.16beta1.

Change-Id: I60688303cdae72f89cfa9777402933ecee2503f7
Reviewed-on: https://go-review.googlesource.com/c/gofrontend/+/279732
Trust: Ian Lance Taylor <iant@golang.org>
Reviewed-by: Than McIntosh <thanm@google.com>
gopherbot pushed a commit to golang/gofrontend that referenced this issue Dec 22, 2020
This is the gofrontend version of https://golang.org/cl/245123.
Original CL description:

    Currently, selectgo does an initial pass over the cases array to look
    for entries with nil channels, so they can be easily recognized and
    skipped later on. But this still involves actually visiting the cases.

    This commit changes selectgo to omit cases with nil channels when
    constructing pollorder, so that they'll be skipped over entirely later
    on. It also checks for caseDefault up front, which will facilitate
    changing it to use a "block bool" parameter instead.

    Updates golang/go#40410

This is being brought over to gofrontend as a step toward upgrading to
Go1.16beta1, setting up for more compiler changes related to select handling.

Change-Id: I1a7a305636fb35e2a747d79dc83292888ceeac69
Reviewed-on: https://go-review.googlesource.com/c/gofrontend/+/279733
Trust: Ian Lance Taylor <iant@golang.org>
Reviewed-by: Cherry Zhang <cherryyz@google.com>
gopherbot pushed a commit to golang/gofrontend that referenced this issue Dec 22, 2020
This is the gofrontend version of https://golang.org/cl/245019.
Original CL description:

    The current wakeup protocol for channel communications is that the
    second goroutine sets gp.param to the sudog when a value is
    successfully communicated over the channel, and to nil when the wakeup
    is due to closing the channel.

    Setting nil to indicate channel closure works okay for chansend and
    chanrecv, because they're only communicating with one channel, so they
    know it must be the channel that was closed. However, it means
    selectgo has to re-poll all of the channels to figure out which one
    was closed.

    This commit adds a "success" field to sudog, and changes the wakeup
    protocol to always set gp.param to sg, and to use sg.success to
    indicate successful communication vs channel closure.

    While here, this also reorganizes the chansend code slightly so that
    the sudog is still released to the pool if the send blocks and then is
    awoken because the channel closed.

    For golang/go#40410

This is being brought over to gofrontend as a step toward upgrading to
Go1.16beta1, setting up for more compiler changes related to select handling.

Change-Id: I8d36d7be40cae2e0fdcbdf73959a95dc815f3f1c
Reviewed-on: https://go-review.googlesource.com/c/gofrontend/+/279734
Trust: Ian Lance Taylor <iant@golang.org>
Reviewed-by: Than McIntosh <thanm@google.com>
gopherbot pushed a commit to golang/gofrontend that referenced this issue Dec 22, 2020
This is the gofrontend version of https://golang.org/cl/245125.

Original CL description:

    Currently, we include a "kind" field on scase to distinguish the three
    kinds of cases in a select statement: sends, receives, and defaults.

    This commit removes by kind field by instead arranging for the
    compiler to always place sends before receives, and to provide their
    counts separately. It also passes an explicit "block bool" parameter
    to avoid needing to include a default case in the array.

    It's safe to shuffle cases like this because the runtime will
    randomize the order they're polled in anyway.

    For golang/go#40410.

This is being brought over to gofrontend as a step toward upgrading to
Go1.16beta1.

Change-Id: I39a0a83c25e15fbd3cdfac7f31e01df9f2cddd3f
Reviewed-on: https://go-review.googlesource.com/c/gofrontend/+/279735
Trust: Ian Lance Taylor <iant@golang.org>
Reviewed-by: Than McIntosh <thanm@google.com>
Reviewed-by: Cherry Zhang <cherryyz@google.com>
sebhub pushed a commit to RTEMS/gnu-mirror-gcc that referenced this issue Dec 23, 2020
This is the gofrontend version of https://golang.org/cl/245125.

Original CL description:

    Currently, we include a "kind" field on scase to distinguish the three
    kinds of cases in a select statement: sends, receives, and defaults.

    This commit removes by kind field by instead arranging for the
    compiler to always place sends before receives, and to provide their
    counts separately. It also passes an explicit "block bool" parameter
    to avoid needing to include a default case in the array.

    It's safe to shuffle cases like this because the runtime will
    randomize the order they're polled in anyway.

    For golang/go#40410.

This is being brought over to gofrontend as a step toward upgrading to
Go1.16beta1.

Reviewed-on: https://go-review.googlesource.com/c/gofrontend/+/279735
@golang golang locked and limited conversation to collaborators Dec 22, 2021
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
FrozenDueToAge NeedsFix The path to resolution is known, but the work has not been done.
Projects
None yet
Development

No branches or pull requests

4 participants