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

[randall77]

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.

[gopherbot]

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

[mvdan]

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]

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

[robpike]

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]

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

[rsc]

@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]

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]

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]

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 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]

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

[randall77]

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.

[gopherbot]

Change https://golang.org/cl/168041 mentions this issue: runtime: fix registers for bounds check calling convention on arm

[gopherbot]

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