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

proposal: cmd/compile: report index and length values in bounds panics #30116

Closed
randall77 opened this Issue Feb 6, 2019 · 12 comments

Comments

Projects
None yet
6 participants
@randall77
Copy link
Contributor

randall77 commented Feb 6, 2019

Instead of reporting bounds check violations like this:

runtime error: index out of range

We could report them like this:

runtime error: index 27 out of range for length 20

We've long assumed that it would be too expensive to provide this information in a panic. But I've done some experiments, and it seems not very expensive. Adding information for both index and slice expressions has a space overhead of about 0.8% (using the go binary as the guinea pig). There is approximately no performance overhead, other than the icache cost, as the non-panic instruction path is identical.

To first order, the cost is 2 extra instructions in each panic path. We'd go from

    CALL panicindex(SB)

to

    MOVQ AX, (SP)
    MOVQ CX, 8(SP)
    CALL panicindex(SB)

That's 5 to 14 bytes on amd64. Cost will vary somewhat based on circumstances (constant indexes, for instance). Also, stack frames might need to be a bit bigger due to the extra outargs space.

The main benefit is a improved debugging experience. Especially with slicing, when an out-of-bounds panic happens it is often not clear which part of the slice expression is to blame.

I think there's some need for discussion about what the panic strings would look like. Particularly for slice expressions, how do we report the message? Should we include just the two values which triggered the violation (low and high if low > high, or high and cap if high > cap), or report all the slice args + the cap? Also, should we provide some programmatic way of accessing the failing index values, or just provide an updated string? (I vote the latter.)

This proposal was sort of discussed in #29435. The two main objections were the overhead (discussed above) and the fact that people might be depending on the text of the current messages.

@randall77 randall77 added the Proposal label Feb 6, 2019

@gopherbot gopherbot added this to the Proposal milestone Feb 6, 2019

@gopherbot

This comment has been minimized.

Copy link

gopherbot commented Feb 6, 2019

Change https://golang.org/cl/161477 mentions this issue: cmd/compile,runtime: provide index information on bounds check failure

@mvdan

This comment has been minimized.

Copy link
Member

mvdan commented Feb 6, 2019

Adding information for both index and slice expressions has a space overhead of about 0.8% (using the go binary as the guinea pig).

I seem to remember that when the compiler is made a bit slower for a wanted feature, it's "paid for" by unrelated optimizations that offset the slowness. In light of #6853, perhaps we should do the same here to ensure that binaries don't keep getting bigger and bigger, like they've already been doing in 1.11 and 1.12.

@randall77

This comment has been minimized.

Copy link
Contributor Author

randall77 commented Feb 6, 2019

@mvdan That would be nice. Speaking of which, 0.3% smaller with CL 161337.

@robpike

This comment has been minimized.

Copy link
Contributor

robpike commented Feb 7, 2019

I believe the compiler did this very early, but then we backed it out for code size reasons.
0.8% isn't much, but many 0.8%s add up. In this case, though, unlike much of the rest of the bloat, there is genuine value (for me at least) in the new behavior.

There is another way to do this, which is to arrange that the index and address are always in the same place when you call panicindex.

@randall77

This comment has been minimized.

Copy link
Contributor Author

randall77 commented Feb 7, 2019

Yeah, we could make a special calling convention for panicindex and save some bytes.

@rsc

This comment has been minimized.

Copy link
Contributor

rsc commented Feb 13, 2019

@randall77, can you see what the overhead is if the panicindex arguments are, say, AX and BX?
Personally, I'd be happy to pay 0.8% for this information. And I'd be happier to pay 0.4%. :-)

@rsc

This comment has been minimized.

Copy link
Contributor

rsc commented Feb 13, 2019

Note also that we could further reduce the space overhead on amd64 by writing 16*15 different panicindex functions (or just jump into different entry points in one long function), one for each pair of registers holding the numbers we want. Probably not worth it but if that 0.8% really needs to come down...

@rsc rsc changed the title proposal: report indexes for bounds failure proposal: cmd/compile: report index and length values in bounds panics Feb 14, 2019

@rsc

This comment has been minimized.

Copy link
Contributor

rsc commented Feb 14, 2019

Regarding the change in wording, I would suggest keeping the substring "index out of range", as in something like "runtime error: index out of range: (len %d)[%d]"

@randall77

This comment has been minimized.

Copy link
Contributor Author

randall77 commented Feb 14, 2019

I've updated my experimental CL to use a register-based calling convention for bounds check panics.
It lowers the space overhead from 0.8% to 0.6%.

There are a bunch of reasons why the register-based convention isn't more advantageous:

  1. The space overhead of the stack-based convention isn't horrendous. A MOVQ AX, c(SP) is 4 or 5 bytes, and a register-register move is 3 bytes.
  2. Sometimes the index or length is a constant, which needs to be loaded into a register (constant->register takes 5 bytes typically, constant->stack takes 8 or 9 bytes).
  3. The register-based calling convention wins when the values happen to be in the right registers, so that no reg-reg moves are required. The register allocator tries to do that, but panic branches get the lowest priority during allocation, so any other reason to select a different register takes precedence. We could up the panic branch priority, but that could mean slower non-panic code.

All 16*15 panicindex functions would help, but...

  • It doesn't solve problem 2
  • It's a lot of functions. Even without the 16*15 explosion, we need different functions for signed and unsigned indexes, length vs capacity, and which comparison failed for slicing. My CL has 8 functions and doesn't handle unsigned indexes correctly which would require another 14.

There are still things we could do:

  • We could load a particular register with a small constant that encodes what other registers the two indexes are in. It would mean one constant load in all cases (8 bit constants can be done with 2 byte instruction) instead of a varying number of reg->reg moves.
  • Maybe we don't need to report indexes or lengths when they really are compile-time constants.

I think we're getting toward diminishing return ideas here, though.

@rsc

This comment has been minimized.

Copy link
Contributor

rsc commented Feb 27, 2019

This seems worth doing. 0.6% doesn't seem like it should hold us back for something so useful. @ianlancetaylor and @griesemer say the runtime/compiler team is OK with this, and so am I. Accepted.

@gopherbot

This comment has been minimized.

Copy link

gopherbot commented Mar 8, 2019

Change https://golang.org/cl/166377 mentions this issue: cmd/compile: reverse order of slice bounds checks

gopherbot pushed a commit that referenced this issue Mar 9, 2019

cmd/compile: reverse order of slice bounds checks
Turns out this makes the fix for 28797 unnecessary, because this order
ensures that the RHS of IsSliceInBounds ops are always nonnegative.

The real reason for this change is that it also makes dealing with
<0 values easier for reporting values in bounds check panics (issue #30116).

Makes cmd/go negligibly smaller.

Update #28797

Change-Id: I1f25ba6d2b3b3d4a72df3105828aa0a4b629ce85
Reviewed-on: https://go-review.googlesource.com/c/go/+/166377
Run-TryBot: Keith Randall <khr@golang.org>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>

@gopherbot gopherbot closed this in 2c423f0 Mar 18, 2019

@randall77

This comment has been minimized.

Copy link
Contributor Author

randall77 commented Mar 18, 2019

Bounds check errors should now be reporting index+length on failures. Time to bikeshed the text!

A few examples (for accessing a slice of length 3):

   s[-1]    runtime error: index out of range [-1]
   s[3]     runtime error: index out of range [3] with length 3
   s[-1:0]  runtime error: slice bounds out of range [-1:]
   s[3:0]   runtime error: slice bounds out of range [3:0]
   s[3:-1]  runtime error: slice bounds out of range [:-1]
   s[3:4]   runtime error: slice bounds out of range [:4] with capacity 3
   s[0:3:4] runtime error: slice bounds out of range [::4] with capacity 3

You can see a complete list of errors in the test in the CL. If you think you have a better wording, send me a CL modifying the format strings in runtime/error.go.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.