{{ message }}

# cmd/compile: BCE is better with reslicing than index variables #28942

Open
opened this issue Nov 25, 2018 · 5 comments
Open

# cmd/compile: BCE is better with reslicing than index variables#28942

opened this issue Nov 25, 2018 · 5 comments
Labels
Milestone

### mvdan commented Nov 25, 2018

 Take this piece of code: ``````\$ cat f.go package p func slice(p []byte) { for len(p) > 4 { // zero bounds checks. _ = p _ = p _ = p _ = p p = p[4:] // reslicing is expensive. } } func index(p []byte) { i := 0 for i < len(p) { _ = p[i+3] // BCE hint; bounds check _ = p[i] // unexpected bounds check _ = p[i+1] // unexpected bounds check _ = p[i+2] // unexpected bounds check _ = p[i+3] i += 4 // incrementing i is cheap. } } \$ go version go version devel +6d5caf38e3 Thu Nov 22 02:59:55 2018 +0000 linux/amd64 \$ go build -gcflags=-d=ssa/check_bce/debug=1 f.go # command-line-arguments ./f.go:18:8: Found IsInBounds ./f.go:20:8: Found IsInBounds ./f.go:21:8: Found IsInBounds ./f.go:22:8: Found IsInBounds `````` It's easy to see why the first variant has zero bounds checks. However, reslicing can be expensive in a hot loop, so sometimes the code is rewritten to use indexes. This is what the second variant does. I do realise that the two loops aren't equivalent - for example, if `len(p) == 5`, the second loop will panic since the length is not a multiple of 4. So I understand why the compiler needs to insert one bounds check. Still, it seems to me like it should insert one, not four, since I've added the BCE hint. My first thought was that it couldn't prove that `i >= 0`, but changing the index to be unsigned still doesn't remove all the bounds checks that I'd expect. I encountered this in the base64 encoder: ``````di, si := 0, 0 n := (len(src) / 3) * 3 for si < n { // Convert 3x 8bit source bytes into 4 bytes val := uint(src[si+0])<<16 | uint(src[si+1])<<8 | uint(src[si+2]) // 3 bounds checks dst[di+0] = enc.encode[val>>18&0x3F] // bounds check dst[di+1] = enc.encode[val>>12&0x3F] // bounds check dst[di+2] = enc.encode[val>>6&0x3F] // bounds check dst[di+3] = enc.encode[val&0x3F] // bounds check si += 3 di += 4 } `````` Rewriting the loop to use reslicing like `for len(src) >= 3 { ...; src = src[3:] }` does remove the bounds checks, but slows down the encoder noticeably. Just like in my simple example above, BCE hints like `_ = src[si+2]` and unsigned indexes didn't help either. I think there's probably a way to rewrite the loop index logic to trick BCE, but I think the compiler could be made smarter here. I'm not sure whether that should be an enhancement in the prove pass, or in the bounds check elimination pass.

### dgryski commented Nov 25, 2018

 Possibly related: #24876

### mvdan commented Nov 25, 2018

 I believe this also affects the `base64` decoder - see the comment above. The code iterates over a pair of slices in chunks, much like the encoder: ``````si := 0 for strconv.IntSize >= 64 && len(src)-si >= 8 && len(dst)-n >= 8 { if dn, ok := decode64( enc.decodeMap[src[si+0]], enc.decodeMap[src[si+1]], enc.decodeMap[src[si+2]], enc.decodeMap[src[si+3]], enc.decodeMap[src[si+4]], enc.decodeMap[src[si+5]], enc.decodeMap[src[si+6]], enc.decodeMap[src[si+7]], ); ok { `````` As before, I tried combining unsigned integers and BCE hints, but no results. I also tried juggling with the for loop conditions, but that didn't make a difference either.

### mvdan commented Nov 27, 2018

 I just realised that removing bounds checks from a loop that jumps more than one position per iteration might not be as easy as it sounds, because of overflows. Imagine: ``````i := 0 for i < len(data) { _ = data[i+0] _ = data[i+1] _ = data[i+2] _ = data[i+3] i += 4 } `````` If `len(data)` happens to be the maximum integer value, then `i+2` could overflow and give a negative number, which would always be a panic when used as an index. Still, a `_ = data[i+3]` hint should still remove that "is negative" bounds check, since `i+2` can't possibly overflow if `i+3` didn't. I presume this trouble disappears if we make the index variable unsigned, since an overflow will just get the index back to 0, which will definitely be within bounds.

### agnivade commented Feb 26, 2019

 /cc @zdjones

### mvdan commented Apr 23, 2019

 https://golang.org/cl/170125 might be interesting to the folks following this thread.