proposal: spec: allow implementations to 'relax' when runtime panics occur

[tzneal]

There are sevaral places in the compiler/runtime and standard libraries where accesses and re-slices are performed to allow bounds check elimination to improve performance:

    b = b[i : i+4 : len(b)] // Help the compiler eliminate bounds checks on the next line.
    _, _ = dst.b[len(src1.b)-1], src2.b[len(src1.b)-1] // hoist bounds checks out of the loop

An algorithmic change to BCE won't ever allow these to be removed. These BCE helpers actually change code behavior and cause the runtime panics to occur before they normally would in the loops that typically follow them.

I propose that the language in the spec be modified to allow implementations to allow runtime panics to occur at any point between function entry and evaluation of an expression that would panic, provided

1. The implementation can prove the panic will occur.
2. The panic is caused by an out of bound slice/array/string access.
3. The containing function does not have a call to defer()/recover().

This is a change in behavior from go1, as the following:

func foo(x []int) {
	for i := 0; i < 10; i++ {
                fmt.Println("at idx", i)
		x[i] = i
	}
}

could potentially behave as if it were written like this:

func foo(x []int) {
	if len(x) < 10 {
		runtime.panic(...)
	}
        for i := 0; i < 10; i++ {
                fmt.Println("at idx", i)
		x[i] = i
	}
}

If there's interest in this, I don't think it would be too difficult to modify the current compiler to automatically insert these accesses before simple loops that access slices and see if there's a performance improvement.

[randall77]

I don't think we should do this. Having panics happen at defined positions is very helpful for understanding what your program does. Putting the panics earlier just "undoes" side effects that you actually care about.

What about this:

mutex.Lock(&lock)
*p += 1
*q += 1
mutex.Unlock(&lock)
a[i] = 0

What if a[i]=0 panics? Where can the panic happen? Can it happen between *p+=1 and *q+=1? If it can, you've just destroyed the invariant that whenever the lock is not held, *p == *q.
And you've also locked the lock forever.

I guess I'm worried about the statement

allow runtime panics to occur at any point between function entry and evaluation of an expression that would panic

That doesn't seem advisable, as described above. I'm not sure what rule you'd use instead (since the last function call? Since the last not-inlined function call?).

[tzneal]

I guess I'm worried about the statement

allow runtime panics to occur at any point between function entry and evaluation of an expression that would panic

That doesn't seem advisable, as described above. I'm not sure what rule you'd use instead (since the last function call? Since the last not-inlined function call?).

I was trying to be as flexible as possible for implementations, and got into trouble :)

Maybe restricting it to hit just the sorts of cases I had in mind will make it more palatable:

     _, _ = dst.b[len(src1.b)-1], src2.b[len(src1.b)-1] // hoist bounds checks out of the loop
     for i, x := range src1.b {
            dst.b[i] = x | src2.b[i]
     }

      dst = dst[:len(src)] // eliminate bounds check from loop
      for k, v := range src {
                i += 1
                x := c.s[i]
                j += uint8(x)
                y := c.s[j]
                c.s[i], c.s[j] = y, x
                dst[k] = v ^ uint8(c.s[uint8(x+y)])
        }

func inverseBWT(tt []uint32, origPtr uint, c []uint) uint32 {
        sum := uint(0)
        for i := 0; i < 256; i++ {
                sum += c[i]
                c[i] = sum - c[i]
        }

And modifying it to allow implementations to allow runtime panics to occur immediately prior to a loop init provided:

1. The implementation can prove the panic will occur.
2. The panic is caused by an out of bound slice/array/string access.
3. The containing function does not have a call to defer()/recover().
4. The loop init, cond, post and body contain no non-builtin function/method calls.

[bcmills]

As @griesemer noted in #19624 (comment):

We need to look at language changes not from a compiler writer's point of view, but from a programmer's productivity point of view.

This proposal seems to optimize for the compiler-writer rather than the programmer: it obscures the root causes of panics in order to make it easier for the compiler to hoist (rather than prove) bounds-checks.

[bcmills]

I think all of the specific examples above would be improved more by explicit assertions than by relaxing panics: assertions not only help the compiler, but also document the important invariants of the loop for the reader of the code.

Consider as an alternative a built-in assert intrinsic, https://golang.org/doc/faq#assertions notwithstanding:

func assert(cond bool) {
	if !cond {
		panic(/* compiler-inserted description of cond */)
	}
}

Now we can write the hoisted checks explicitly:

	assert(len(dst.b) >= len(src1.b))
	assert(len(src2.b) >= len(src1.b))
	for i, x := range src1.b {
		dst.b[i] = x | src2.b[i]
	}

	assert(len(dst) >= len(src))
	assert(len(c.s) >= i + len(src))
	for k, v := range src {
		i += 1
		x := c.s[i]
		j += uint8(x)
		y := c.s[j]
		c.s[i], c.s[j] = y, x
		dst[k] = v ^ uint8(c.s[uint8(x+y)])
	}

The inverseBWT example can be made clearer and more efficient without an assertion, by using a range loop instead of index-based iteration (see also #24282):

func inverseBWT(tt []uint32, origPtr uint, c []uint) uint32 {
        sum := uint(0)
        for i, cᵢ := range c[:256] {
                sum += cᵢ
                c[i] = sum - cᵢ
        }

[mundaym]

This has probably been considered before but it seems like it would be nicer from a user perspective if the compiler inserted bounds checks before loops/multiple accesses without changing the behavior of the program. If an out of bounds condition is detected in this early check we could jump to a 'slow' version of the code that includes bounds checks. If the assertion passed then it would be safe to execute the multiple accesses/loop without any bounds checks. JIT compilers often play these sort of tricks (jumping back to interpreter mode for example).

In many cases we will know the 'slow' code is going to end up panicking so we can then do other optimizations such as putting it in a special 'cold' code section of the binary, optimizing for code size and perhaps ignoring operations that do not have side effects.

For example:

x := uint32(b[0])
x |= uint32(b[1]) << 8
x |= uint32(b[2]) << 16
x |= uint32(b[3]) << 24

Might be compiled as something like:

if unlikely(len(b) < 4) {
    switch len(b) {
    case 0: panic("line 1")
    case 1: panic("line 2")
    case 2: panic("line 3")
    default: panic("line 4")
    }  
}
x := uint32(b[0]) | uint32(b[1]) << 8 | uint32(b[2]) << 16 | uint32(b[3]) << 24 // no bounds checks

This approach has its downsides (compile time, binary size, complexity, etc.), but might reduce the need to litter code with hoisted memory accesses like _ = b[3].

[rasky]

Loop versioning is indeed possible but it would be a large effect on code size. Limiting it by heuristics seems also very hard (especially now that we don’t even have good metrics to perform inlining, like post-opt op count).

I agree that there is a problem here as most users wouldn’t expect the naive for loop to be much slower than the range loop, and explaining them why is something we should strive to solve (that is, make it unnecessary).

I also think a semantic change is probably part of the picture but I don’t have a concrete suggestion to offer. It’s also one of the areas where we can’t expect the compiler to solve the problem on most cases.

[ianlancetaylor]

There may be some good ways to tell the compiler when it can skip checks, but as people have mentioned above accurate locations of errors is very helpful for developers. While perhaps we can do something in this space, we aren't going to adopt this approach.