bounds check elimination for "if len(a) >= i+2 && a[i:i+2]"

[Alexandru Moșoi]

Hi,

Can the bounds checks be eliminated for "if len(a) >= i+2 && a[:i+2]" (assume i is non-negative)?

This pattern is very common, see for example: nextStdChunk in time/format.go. I think the code is buggy in the extreme case when i+2 overflows. If that's the case, should we fix the code?

Regards,

[Keith Randall]

If all we knew was that i was non-negative, then yes that's a bug.  But the places I see it we know that 0 <= i < len(something).  We can assume that the runtime prevents lengths very near maxint.

[Giovanni Bajo]

In general, it would be great if a dominant check on len(slice) would eliminate bound checks on dominated accesses, including those in loops.

For instance:

if len(a) < 128 { 

   panic("programming error")

}

// Now we know that a is at least 128, so the following loop should 

// generate zero bound checks

for i := 0; i < 128; i++ {

   a[i] = whatever

}

Giovanni

[Alexandru Moșoi]

This is what I'm trying to achieve. a[i] is the easy case. The example I posted before was one of the common case I don't have.

--
You received this message because you are subscribed to a topic in the Google Groups "golang-dev" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/golang-dev/jVP6h21OyL8/unsubscribe.
To unsubscribe from this group and all its topics, send an email to golang-dev+...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

--

Alexandru Moșoi
http://www.alexandru.mosoi.ro/

[Giovanni Bajo]

Another common example in my code

for len(a) > 8 {

     // this should generate zero bound checks

     data := binary.LittleEndian.Uint64(a)

 

     // and should eventually generate code equivalent to:

     // data := *(*uint64)(unsafe.Pointer(&a[0]))

[Alexandru Moșoi]

Isn't that already optimized after [1]?

[1] https://github.com/golang/go/commit/12e60452e9f7c21933aad1a864e1433736de807e

--

You received this message because you are subscribed to a topic in the Google Groups "golang-dev" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/golang-dev/jVP6h21OyL8/unsubscribe.
To unsubscribe from this group and all its topics, send an email to golang-dev+...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Giovanni Bajo]

Well, I had missed that commit and I checked. It does collate the loads correctly but still obviously generates 4 bound checks, and a dominant check is not sufficient right now (though I understand you're working on this).

It also doesn't handle writes (PutUint32, PutUint64).

And BTW, in the cases where the compiler can't eliminate bound checks, the generated code is:

main.go:55 0x213f 4883f900 CMPQ $0x0, CX

main.go:55 0x2143 0f8601020000 JBE 0x234a

main.go:55 0x2149 4883f901 CMPQ $0x1, CX

main.go:55 0x214d 0f86f7010000 JBE 0x234a

main.go:55 0x2153 4883f902 CMPQ $0x2, CX

main.go:55 0x2157 0f86ed010000 JBE 0x234a

main.go:55 0x215d 4883f903 CMPQ $0x3, CX

main.go:55 0x2161 0f86e3010000 JBE 0x234a

main.go:55 0x2167 8b0a MOVL 0(DX), CX

obviously 1 bound check (for a[3]) would be sufficient in this case. 

Generically speaking, if the code is accessing values 1..n of a slice (in linear code or in a loop), a single bound check (for n) at the beginning should be sufficient, but that of course brings the question that the program would mutate the observable behavior of when exactly the panic is generated. I'm not sure what the guarantees are on this respect. The alternative is asking the programmer to add an explicit bound check + panic before the loop to optimize it; similar to LLVM's __builtin_assume, in a way.

Giovanni Bajo

[Keith Randall]

[1] combines the loads into a MOVQ.  But the bounds checks are all still there.

func f(a []byte) uint64 {

if len(a) > 8 {

return binary.LittleEndian.Uint64(a)

}

return 0

}

0x000f 00015 (/home/khr/go/tmp1.go:6) MOVQ "".a+16(FP), CX

0x0014 00020 (/home/khr/go/tmp1.go:6) CMPQ CX, $8

0x0018 00024 (/home/khr/go/tmp1.go:6) JLE $0, 95

0x001a 00026 (/home/khr/go/tmp1.go:7) CMPQ CX, $0

0x001e 00030 (/home/khr/go/tmp1.go:7) JLS $0, 88

0x0020 00032 (/home/khr/go/tmp1.go:7) CMPQ CX, $1

0x0024 00036 (/home/khr/go/tmp1.go:7) JLS $0, 88

0x0026 00038 (/home/khr/go/tmp1.go:7) CMPQ CX, $2

0x002a 00042 (/home/khr/go/tmp1.go:7) JLS $0, 88

0x002c 00044 (/home/khr/go/tmp1.go:7) CMPQ CX, $3

0x0030 00048 (/home/khr/go/tmp1.go:7) JLS $0, 88

0x0032 00050 (/home/khr/go/tmp1.go:7) CMPQ CX, $4

0x0036 00054 (/home/khr/go/tmp1.go:7) JLS $0, 88

0x0038 00056 (/home/khr/go/tmp1.go:7) CMPQ CX, $5

0x003c 00060 (/home/khr/go/tmp1.go:7) JLS $0, 88

0x003e 00062 (/home/khr/go/tmp1.go:7) CMPQ CX, $6

0x0042 00066 (/home/khr/go/tmp1.go:7) JLS $0, 88

0x0044 00068 (/home/khr/go/tmp1.go:7) CMPQ CX, $7

0x0048 00072 (/home/khr/go/tmp1.go:7) JLS $0, 88

0x004a 00074 (/home/khr/go/tmp1.go:7) MOVQ "".a+8(FP), CX

0x004f 00079 (/home/khr/go/tmp1.go:7) MOVQ (CX), CX

0x0052 00082 (/home/khr/go/tmp1.go:7) MOVQ CX, "".~r1+32(FP)

0x0057 00087 (/home/khr/go/tmp1.go:7) RET

0x0058 00088 (/home/khr/go/tmp1.go:7) PCDATA $0, $0

0x0058 00088 (/home/khr/go/tmp1.go:7) CALL runtime.panicindex(SB)

0x005d 00093 (/home/khr/go/tmp1.go:7) UNDEF

0x005f 00095 (/home/khr/go/tmp1.go:9) MOVQ $0, "".~r1+32(FP)

0x0068 00104 (/home/khr/go/tmp1.go:9) RET

[Alexandru Moșoi]

func (littleEndian) Uint64(b []byte) uint64 {

return uint64(b[0]) | uint64(b[1])<<8 | uint64(b[2])<<16 | uint64(b[3])<<24 |

uint64(b[4])<<32 | uint64(b[5])<<40 | uint64(b[6])<<48 | uint64(b[7])<<56

}

This is what Uint64 looks like. We could eliminate some bounds much easier if the order of operations was reversed (i.e. read b[7] first, etc).

[Alexandru Moșoi]

Another observation: If we have

if b {

   if a {

      // do something

   }

}

and a implies b  (a -> b) then we could drop the first condition if there is nothing between "if b {" and "if a {"

However for the go compiler that's not true, because the tighten pass is very simple and doesn't move stuff across if blocks. Before lowering the code looks like below. Everything except the control variable can be pushed way down.

  b8: <- b6

    v43 = AddPtr <*byte> v68 v39

    v45 = Load <byte> v43 v22

    v46 = ZeroExt8to64 <uint64> v45

    v53 = IsInBounds <bool> v51 v62

    v47 = Const64 <uint> [8]

    v37 = ZeroExt8to64 <uint64> v36

    v48 = Lsh64x64 <uint64> v46 v47

    v49 = Or64 <uint64> v37 v48

    If v53 -> b9 b7 (likely)

  b9: <- b8

    v55 = AddPtr <*byte> v68 v51

    v57 = Load <byte> v55 v22

    v58 = ZeroExt8to64 <uint64> v57

    v65 = IsInBounds <bool> v63 v62

    v59 = Const64 <uint> [16]

    v60 = Lsh64x64 <uint64> v58 v59

    v61 = Or64 <uint64> v49 v60

    If v65 -> b10 b7 (likely)

  b10: <- b9

    v67 = AddPtr <*byte> v68 v63

    v69 = Load <byte> v67 v22

    v70 = ZeroExt8to64 <uint64> v69

    v77 = IsInBounds <bool> v75 v62

    v71 = Const64 <uint> [24]

    v72 = Lsh64x64 <uint64> v70 v71

    v73 = Or64 <uint64> v61 v72

    If v77 -> b11 b7 (likely)

[Alexandru Moșoi]

Can you patch in https://go-review.googlesource.com/#/c/20517/ and test for your code?

In particular it should remove the bound checks on:

if len(a) < 128 { 

   panic("programming error")

}

for i := range a[:128] {

   a[i] = whatever

[Alexandru Moșoi]

Spoke too soon:

c := a[:128]

for i := range c {

   c[i] = whatever

[Russ Cox]

On Thu, Mar 10, 2016 at 2:04 PM, Alexandru Moșoi <alex...@mosoi.ro> wrote:

func (littleEndian) Uint64(b []byte) uint64 {

return uint64(b[0]) | uint64(b[1])<<8 | uint64(b[2])<<16 | uint64(b[3])<<24 |

uint64(b[4])<<32 | uint64(b[5])<<40 | uint64(b[6])<<48 | uint64(b[7])<<56

}

This is what Uint64 looks like. We could eliminate some bounds much easier if the order of operations was reversed (i.e. read b[7] first, etc).

There is no requirement that the compiled code for this expression do the b[0] bounds check before the b[7] bounds check.

Russ

[Alexandru Moșoi]

There is some discussion in https://go-review.googlesource.com/#/c/20654/ why we cannot do this for PutUint*. tl;dr: partial writes are not observed anymore if it panics.

In your case, if you really want to get rid of the bound checks you can do:

        binary.LittleEndian.PutUint64(a[:8], u)

PutUint64 gets inlined and since the slice as fixed length the bound checks are removed.

This is just my suggestion and I don't know whether it will still work or be needed in the future.

[Russ Cox]

On Mon, Mar 14, 2016 at 5:44 AM Alexandru Moșoi <alex...@mosoi.ro> wrote:

There is some discussion in https://go-review.googlesource.com/#/c/20654/ why we cannot do this for PutUint*. tl;dr: partial writes are not observed anymore if it panics.

In your case, if you really want to get rid of the bound checks you can do:

        binary.LittleEndian.PutUint64(a[:8], u)

PutUint64 gets inlined and since the slice as fixed length the bound checks are removed.

If this is true, then it seems like we should change PutUint64 to add a new statement at the beginning:

func (littleEndian) PutUint64(b []byte, v uint64) {

b = b[:8] // eliminate bounds checks below

b[0] = byte(v)

b[1] = byte(v >> 8)

b[2] = byte(v >> 16)

b[3] = byte(v >> 24)

b[4] = byte(v >> 32)

b[5] = byte(v >> 40)

b[6] = byte(v >> 48)

b[7] = byte(v >> 56)

}

Adding that line is not a valid change that could be made by the compiler. As written, the code must perform the valid writes before reaching the panicking one. But it's a change I'm comfortable making explicitly in the encoding/binary source code, especially if it cuts 8 bounds checks down to 1.

That would make your suggestion no longer necessary, and all call sites should get faster, not just the ones that know about the trick.

If you agree that this will help the compiler eliminate bounds checks, feel free to send a CL adding that line.

Russ

[Alexandru Moșoi]

Added you as reviewer to https://go-review.googlesource.com/#/c/20654/. It handles both Put&Get but I'm fine to limit it to Put only.

[roger peppe]

Does the compiler know that it can eliminate bounds checks
if it sees code like this?

x[3] = a
x[2] = b
x[1] = c

ISTM that it could infer from the fact that the first bounds check
has succeeded that the other ones will too.

If so, we could get the required optimisation in the encoding/binary
Put methods by simply reversing the lines rather than adding the
explicit slice.

> --
> You received this message because you are subscribed to the Google Groups
> "golang-dev" group.
> To unsubscribe from this group and stop receiving emails from it, send an

[Brad Fitzpatrick]

That was my comment at https://go-review.googlesource.com/#/c/20654/1/src/encoding/binary/binary.go@72 as well.

I'm not sure if I missed it, but I never seemed to get a satisfying reply about why that isn't desirable.

[Alexandru Moșoi]

a[3], a[2], a[1], a[0] requires compiler changes unlike a = a[:4] which is handled today. I hope the compiler will eventually handle the suggested solution because there are many examples in the stdlib where this is useful.

[minux]

But what if we make the compiler assume that partial writes (i.e. 1 <= len(b) < 8) are rare

and compile the code to something like:

if len(b) >= 8 { // fast path

     // do 8 writes without bound checks, and on architectures with unaligned write support

     // just do a qword write.

     return

}

// the original code, the slow path

Then no source code modification is necessary, and I expect this to benefit all code

that does manual serialization of data.

[ron minnich]

On Thu, Mar 17, 2016 at 9:53 AM roger peppe <rogp...@gmail.com> wrote:

Does the compiler know that it can eliminate bounds checks
if it sees code like this?

   x[3] = a
   x[2] = b
   x[1] = c

ISTM that it could infer from the fact that the first bounds check
has succeeded that the other ones will too.

If you assume that the generated code executes in the order it appears in the source, yes. As Russ pointed out in an earlier comment, that assumption may not hold. I don't see any reason for it to hold in this case.

The CL as written seems pretty reasonable. 

ron

[Keith Randall]

Minux, I don't think what you're suggesting is an easy thing to do.  It involves duplicating code, which is always dangerous to overdo.

What about:

   b[0] = x

   f()

   b[1] = y

Should we transform that to:

  if len(b) >= 2 {

     b[0] = x  // no bounds check

     f()

     b[1] = y  // no bounds check

  }

  b[0] = x

  f()

  b[1] = y

What if more code is in the middle there?  How far afield should we search for constant indexes that we can fold in this way?  How much duplication is worth the benefit?

[Govert Versluis]

On Thu, Mar 17, 2016 at 6:12 PM, ron minnich <rmin...@gmail.com> wrote:

If you assume that the generated code executes in the order it appears in the source, yes. As Russ pointed out in an earlier comment, that assumption may not hold. I don't see any reason for it to hold in this case.

The CL as written seems pretty reasonable. 

ron

Ron, could you help me understand why that would NOT be the case for the reverse code like so:

   x[3] = a
   x[2] = b

   x[1] = c

But would be the case for the regular code:

   x[1] = a
   x[2] = b

   x[3] = c 

?

Russ's remark was regarding a single-line statement:

   return uint64(b[0]) | uint64(b[1])<<8 | uint64(b[2])<<16 | uint64(b[3])<<24 | uint64(b[4])<<32 | uint64(b[5])<<40 | uint64(b[6])<<48 | uint64(b[7])<<56

It seems to me that the order for the slice access must be the same in both source and generated code for the regular (1,2,3) case. For the reverse case, the compiler could decide to do them in a different order, but only after having done a bounds check on the highest access, since that write must succeed for the others to be viable.

[minux]

On Thu, Mar 17, 2016 at 1:17 PM, Keith Randall <k...@google.com> wrote:

Minux, I don't think what you're suggesting is an easy thing to do.  It involves duplicating code, which is always dangerous to overdo.

What about:

   b[0] = x

   f()

   b[1] = y

Should we transform that to:

  if len(b) >= 2 {

     b[0] = x  // no bounds check

     f()

     b[1] = y  // no bounds check

  }

  b[0] = x

  f()

  b[1] = y

What if more code is in the middle there?  How far afield should we search for constant indexes that we can fold in this way?  How much duplication is worth the benefit?

The optimization applies only to cases there is clear benefit of duplicating

the code. For example, even there are intervening side effects, then it doesn't

apply.

I'm not aiming to speculatively optimize out all such bound checks (gccgo

might want to do that), but just optimizing the common case: data serialization.

[minux]

This whole discussion reminds me the debate on whether FP exception generated

by processor should be precise.

For this snippet of code:

x[1] = a

x[2] = b

x[3] = c

the compiler must do the bound check in sequence because at the index out

of range panic, we must report the correct line that triggered the panic. I agree

that the compiler can reorder the actual writes to the slice. And we must also

make sure in the panic handler, the side effects (partial writes) are correct.

We all know that imprecise FP exception could dramatically increase FP performance,

but unfortunately the current Go spec seems to require the equivalent of precise

FP exceptions.

[ron minnich]

On Thu, Mar 17, 2016 at 10:28 AM Govert Versluis <gov...@ver.slu.is> wrote:

   x[3] = a
   x[2] = b

   x[1] = c

But would be the case for the regular code:

   x[1] = a
   x[2] = b

   x[3] = c 

It's probably me not understanding the rules again.  I've used compilers that would happily reorder those types of statements, and worked with people who got burned by assuming that they were executed in the order written. But those were other languages.

But there's something here I'm clearly missing.

ron

[Josh Bleecher Snyder]

Here's an interesting bit of code, from crypto/aes/block.go:78:

dst[0], dst[1], dst[2], dst[3] = byte(s0>>24), byte(s0>>16),
byte(s0>>8), byte(s0)

According to the spec, the index expressions on the LHS are evaluated
before the assignments occur. So we have yet another way to write this
in which the compiler should be able to do a single bounds check and a
single store. (The others being adding `b = b[:4]` or `_ = b[3]`
before the stores.)

I'm not going to suggest that we encourage people to write this, just
offering it as something interesting. :)

-josh

P.S. I noticed this because I was curious how many distinct places in
the tree there is code like PutUint32. Answer: A whole, whole lot.
(Although a lot of them in the compiler and linker should just use
PutUint32.)

On Thu, Mar 17, 2016 at 9:53 AM, roger peppe <rogp...@gmail.com> wrote:

[Giovanni Bajo]

This is just one specific case. There are many cases where slices of unknown sizes are used in hot performance paths/loops, and we ought to agree on a general syntax that allows the programmer to specify that a given slice is “at least N” in size, so that the compiler is then allowed to perform bound checking removal on dominant code. LLVM has __builin_assume() for letting the programmers give this kind of hints to the compiler (and it’s of course more generic, we’re focusing just on slice size now).

IMHO, the best syntax would be:

func (littleEndian) PutUint64(b []byte, v uint64) {

if len(slice) < 8 {

panic(“slice too short”)

}

b[0] = byte(v)

b[1] = byte(v >> 8)

b[2] = byte(v >> 16)

b[3] = byte(v >> 24)

b[4] = byte(v >> 32)

b[5] = byte(v >> 40)

b[6] = byte(v >> 48)

b[7] = byte(v >> 56)

}

but I understand that it doesn’t work now, and Alexandru was worried about the cost of implementing it.

--

Giovanni Bajo

[Austin Clements]

If the compiler knows that none of those bounds checks will fail, then it can (in principle) reorder them. But the key difference with other compilers (namely, C compilers) is that the bounds check can fail *and* that failure can be caught. The state observed by the defer handler must be consistent with a sequential execution. So, if, say, the x[3] = c fails the bounds check, a defer on the stack must see the writes to x[1] and x[2].

[Alexandru Moșoi]

https://go-review.googlesource.com/#/c/20654/ was submitted to end the bike-shed. Thanks Russ for the LGTM.

[minux]

A related question, what if the code is written as:

b[0], b[1], b[2], ... = byte(v), byte(v>>8), byte(v>>16), ....

could the compiler only do one bound check in this case?

do we need to care about partial writes in this case?

[Austin Clements]

We do care about partial writes even in this case. https://golang.org/ref/spec#Assignments gives exactly this example:

x[1], x[3] = 4, 5  // set x[1] = 4, then panic setting x[3] = 5.

(I'm slightly fuzzy on what in the text implies this, but the Assignments section does say that assignments are carried out in left-to-right order.)

--

[Keith Randall]

See issue https://github.com/golang/go/issues/14849

I think we still don't know long-term the idiom we should use to tell the compiler to do the bounds check first.  We currently use b = b[:8].  But there are lots of other options:

_ = b[:8]

b = b[:8:8]

_ = b[:8:8]

etc.  I think we need to:

 A) pick one, and

 B) make sure the compiler does the right thing on the one we pick.

I was hesitant on 20654 because it does A (and de-facto announces it by checking it into the std lib) without really doing B.  I'd like to get B done quickly so if we have to change our A decision for whatever reason, we don't have to retrain anyone who saw A.

[Russ Cox]

For what it's worth, b = b[:8] seems the clearest of the four you suggested. The _= versions might also be made to work, but it seems more confusing. And the ones setting the cap seem more complex for no reason. I don't see why the compiler would need to know that cap is constant, and almost no one uses that form, so it would look extra strange.

I checked that both the non-ssa and the ssa back ends know that b = b[:8] only updates one of the three slice fields.

Russ

[Keith Randall]

One problem I just noticed with [:8] is that it might read beyond the original length of the b.

var bytes [8]byte

b := b[:4]

binary.Uint64(b)

Used to panic, now it succeeds and reads (or writes, for PutUint64) all 8 bytes.

This is an argument for using _=b[7] instead.  Not a terribly strong one, but still.

[roger peppe]

That argument clinches it for me. If I do PutUint64(b[0:n], x) I think it's

important that it panics if n < 8.

[Alexandru Moșoi]

Yep, that looks like a regression which I missed when I compared the generated code.

The proper slicing should have been b = b[:8:len(b)] to make sure we don't extend past the original length of the array.

[Russ Cox]

I agree about b = b[:8:len(b)].