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.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{{ message }}
Repository navigation
cmd/compile: no way to hint to eliminate bounds checks in bvec.AndNot #20393
This can be very hot code for certain kind of input code. The core loop here contains two bounds checks, on dst.b[i] and src2.b[i]. By construction, though, len(dst.b) == len(src1.b) == len(src2.b).
The compiler should already have enough information to hoist these bounds checks out of the loop. I'd be happy enough to provide explicit hints, though, e.g. like _ = dst.b[len(src1.b)-1] at the top of the function. I'm not too particular about what they look like--I just want it to be possible. It doesn't appear to be right now; at least, I can't figure it out.
@josharian thanks for looking into this. Yes, this sounds right.
On a related note some time ago I was thinking: when there is a loop and slice accesses inside which generally needs bounds checking, for many kind of loops the compiler could transform the checks to be performed from inside loop to equivalent only one bounds check before entering the loop.
The limiting factors here are:
when something panics we want to know the exact line of failure
if there are side effects of the loop they must remain committed to memory for successfull operations executed before panic.
That means that in general if such transformation will be happenning, the loop with insides bounds check needs to be transformed into:
equivalent bounds precheck, which if successfull, would mean there won't be any bounds panic inside loop;
fast version of the loop with no bounds checking performed at runtime. (this gets executed if 1 succeeds)
slow version of the loop with runtime bounds checking still there. We know it will fail, but we want the side effects (if any) to be committed and to get correct line in the traceback.
Unfortunately that means the code could become more fat.
Fortunately with such transformation in place, if a user adds
iflen(a) <... {
panic(...)
}
or similar in function preambule with correct checks equivalent to 1, the compiler will know generating 3 is not needed at all. Similarly if the function gets inlined and in inlining context the compiler already has some information about variables it should be easy for compiler to check whether only fast loop needs to be remained becase pre-condition for that is already in top-level block of inlined function.
To me this suggest that having such transformations as one of the basis of BCE should be a good idea. Personally I'm also ok with some code size increase if that means bounds in all functions will be automatically checked before loops not inside. And for the slow loop version, since we know it will panic and is there only for correctness, the generated code could be somehow optimized more for size.
I beg you pardon if this all is too abstract or non practicall,
Kirill
P.S. for the reference some time ago I've made a-la protobuf compiler which moves such overflow checks from inside loops out:
It's possible but I am not sure it will make the cut. Bounds checks are highly predictable (which reduces the win), and when I took a stab at the analysis before it took too much time.
@dr2chase bounds checks of course feels on codes which work more with slices, like the hex encoding above (access to hextable), all gonum (dot product, matrix diagonalization, etc), search in sorted slice, permutations etc. When code works more with structures -B won't practically make a difference.
in short: json - helps some parts, http - not sure, go1 - significantly helps Fannkuch11 (-33%) not sure about the rest as it all could be noise related to source positons of jumps changed.
Once again not all codes are using slices heavily but for those who do bounds checking takes visible part of runtime and not only 10% as e.g. now famous Fannkuch11 shows above.
I benchmarked the compiler with and without -B, including some anomalous cases in which bvec.AndNot is hot code, and got no impact.
A key question for fannkuch (and the rest of these) is whether BCE could actually eliminate the relevant checks; -B is more powerful than the compiler ever can be.
Josh thanks for your feedback and for trying the compiler with -B. About fannkuch I've tried to look inside to see details about bounds checking. For this I've compiled fannkuch_test.go without and with -B, did go tool objdump -S on both, removed addresses of instruction so that the diff is less noisy, and investigated the difference. Let me show it below with my annotations and comments:
^^^ are all CALL runtime.panicindex destinations and they were all covered by my comments.
So maybe I missed something (appologize then) but above I was able to prove all runtime bounds check are unneccessary in fannkuch. I don't see any reason the compiler cannot be taught to do the same. Thus for fannkuch it is theoretically possible to reach -B level with just BCE.
About compiler itself I've tried to see myself too. For this via passing GO_GCFLAGS=-B env var to make.bash I've bootstrapped second compiler (goB) which does not check bounds at compile runtime, checked it is really the case (e.g. go tool objdump pkg/tool/linux_amd64/compile |grep panicindex |wc -l), and compared go and goB via compilebench:
The optimization proposed here is very aggressive, and the proposed gains are smaller than what we hope to obtain from either getting better inlining into the compiler or passing arguments in registers. I'd like to target 1.11 instead of 1.10.
The original issue tracked in this bug (BCE in bvec.AndNot) is fixed by CL100277 and CL100278. After the first lands, len(a) == len(b) can be used to trigger BCE; after the second, len(a) < len(b) will work too.
@navytux would it possible to move your wonderful comment about fannkuch in a separate issue? It would be easier to find and track.
@rasky, thanks for working on patches improving BCE. Sure, fannkuch case can be moved outside for easier observability and tracking -> please see #24660.
The original issue tracked in this bug (BCE in bvec.AndNot) is fixed by CL100277 and CL100278.
Awesome.
Will it require additional work or hints to be added to bvec.AndNot, or will the existing code suffice? Just want to know whether I need to send any follow-up CLs.
Yes, you need to assert that all the involved vector have equal or compatible size (eg: >= of the one you're iterating on). In the OP you say "By construction, though, len(dst.b) == len(src1.b) == len(src2.b)" but unless that is visible to the compiler, you need explicitly assert it.
Activity
josharian commentedon May 18, 2017
Looks like this might be a duplicate of #19714. Sound right, @navytux?
navytux commentedon May 19, 2017
@josharian thanks for looking into this. Yes, this sounds right.
On a related note some time ago I was thinking: when there is a loop and slice accesses inside which generally needs bounds checking, for many kind of loops the compiler could transform the checks to be performed from inside loop to equivalent only one bounds check before entering the loop.
The limiting factors here are:
That means that in general if such transformation will be happenning, the loop with insides bounds check needs to be transformed into:
Unfortunately that means the code could become more fat.
Fortunately with such transformation in place, if a user adds
or similar in function preambule with correct checks equivalent to 1, the compiler will know generating 3 is not needed at all. Similarly if the function gets inlined and in inlining context the compiler already has some information about variables it should be easy for compiler to check whether only fast loop needs to be remained becase pre-condition for that is already in top-level block of inlined function.
To me this suggest that having such transformations as one of the basis of BCE should be a good idea. Personally I'm also ok with some code size increase if that means bounds in all functions will be automatically checked before loops not inside. And for the slow loop version, since we know it will panic and is there only for correctness, the generated code could be somehow optimized more for size.
I beg you pardon if this all is too abstract or non practicall,
Kirill
P.S. for the reference some time ago I've made a-la protobuf compiler which moves such overflow checks from inside loops out:
https://lab.nexedi.com/kirr/neo/blob/391212b7/go/neo/protogen.go
P.P.S. it would be great if in Go1.10 cycle some love would be devoted to BCE
dr2chase commentedon May 19, 2017
It's possible but I am not sure it will make the cut. Bounds checks are highly predictable (which reduces the win), and when I took a stab at the analysis before it took too much time.
navytux commentedon May 19, 2017
@dr2chase
dr2chase commentedon May 19, 2017
That's one benchmark. How about json, http, and the geomean of the go1 benchmarks?
navytux commentedon May 19, 2017
@dr2chase bounds checks of course feels on codes which work more with slices, like the hex encoding above (access to hextable), all gonum (dot product, matrix diagonalization, etc), search in sorted slice, permutations etc. When code works more with structures -B won't practically make a difference.
Said that here are the benchmarks you've asked.
in short: json - helps some parts, http - not sure, go1 - significantly helps Fannkuch11 (-33%) not sure about the rest as it all could be noise related to source positons of jumps changed.
Once again not all codes are using slices heavily but for those who do bounds checking takes visible part of runtime and not only 10% as e.g. now famous Fannkuch11 shows above.
Thanks,
Kirill
josharian commentedon May 19, 2017
I benchmarked the compiler with and without -B, including some anomalous cases in which bvec.AndNot is hot code, and got no impact.
A key question for fannkuch (and the rest of these) is whether BCE could actually eliminate the relevant checks; -B is more powerful than the compiler ever can be.
navytux commentedon May 20, 2017
Josh thanks for your feedback and for trying the compiler with -B. About fannkuch I've tried to look inside to see details about bounds checking. For this I've compiled
fannkuch_test.gowithout and with -B, didgo tool objdump -Son both, removed addresses of instruction so that the diff is less noisy, and investigated the difference. Let me show it below with my annotations and comments:BCE could remove ^^^ panicindex because:
perm1is initialized withmake([]int, n)and its len is never changedso BCE knows n <= len(perm1) (actually ==), 0 <= i < n -> i < len(perm1) -> no BC needed.
For
count[r-1] = rBCE could remove ^^^ panicindex because:countis initialized withmake([]int, n)and its len is never changedris initialized asn, goes down to 1 in below loop, goes up in tail loop inside main loopfor ; r < n; r++, so it is never > n. => r ∈ [1, n] always.so BCE knows
1 <= r <= n0 <= r-1 <= n-1 < nso
count[r-1]does not need BC.if perm1[0] != 0 && perm1[n1] != n1 { - 4885f6 TESTQ SI, SI - 0f86ee010000 JBE 0x24f3 // panicindex - 4c8b1b MOVQ 0(BX), R11 - 4d85db TESTQ R11, R11 - 0f8490010000 JE 0x24a1 - 4839f7 CMPQ SI, DI - 0f83d9010000 JAE 0x24f3 // panicindex - 4e8b5cc3f8 MOVQ -0x8(BX)(R8*8), R11 - 4c39df CMPQ R11, DI - 0f846a010000 JE 0x2492 - 4c8b5c2468 MOVQ 0x68(SP), R11 - 4c8b642438 MOVQ 0x38(SP), R12 - 41bd01000000 MOVL $0x1, R13 + 4c8b0a MOVQ 0(DX), R9 + 4d85c9 TESTQ R9, R9 + 0f84e5000000 JE 0x233d + 4c8b4cf2f8 MOVQ -0x8(DX)(SI*8), R9 + 4c39cb CMPQ R9, BX + 0f84cd000000 JE 0x2333 + 4c8b4c2438 MOVQ 0x38(SP), R9 + 41ba01000000 MOVL $0x1, R10len(perm1)is known to ben-> this way perm1[0] does not need BC.
n1is initialized asn - 1and is never changedlen(perm1)is once again known to ben-> this way
perm1[n1]does not need BCfor i := 1; i < n; i++ { // perm = perm1 - eb07 JMP 0x2341 + eb0b JMP 0x227e perm[i] = perm1[i] - 4f8934eb MOVQ R14, 0(R11)(R13*8) + 4e8b1cd2 MOVQ 0(DX)(R10*8), R11 + 4f891cd1 MOVQ R11, 0(R9)(R10*8) for i := 1; i < n; i++ { // perm = perm1 - 49ffc5 INCQ R13 - 4d39c5 CMPQ R8, R13 - 7d17 JGE 0x235d - perm[i] = perm1[i] - 4939f5 CMPQ SI, R13 - 0f839d010000 JAE 0x24ec // panicindex - 4e8b34eb MOVQ 0(BX)(R13*8), R14 - 4d39e5 CMPQ R12, R13 - 72e2 JB 0x233a - e98f010000 JMP 0x24ec // panicindex - 4c894c2450 MOVQ R9, 0x50(SP) + 49ffc2 INCQ R10 + 4939f2 CMPQ SI, R10 + 7cf0 JL 0x2273permandperm1were initialized asmake([]int, n)and their len is never changed-> both
perm[i]andperm1[i]do not need BCk is initialized as
perm1[0]- no BC needed here since compiler already knows len(perm1) = n >= 1initially perm1 is initialized as
perm1[i] = ii ∈ [0, n)from ^^^ the compiler knows initially ∀ x ∈ [0, n) perm1[x] ∈ [0, n)
later elements of perm1 are only exchanged with each other, so the compiler can prove ∀ x ∈ [0, n) perm1[x] ∈ [0, n) holds always
thus k itself can be proven to be in [0, n) on first iteration (see also below about all next iterations)
the inner loop is
-> both i and j are in valid range and no BC is needed for
perm[i]andperm[j]perm[k]does not need BCpermis initialized as =perm1- this way compiler can know ∀ x ∈ [0, n)perm[x]∈ [0, n) initiallyj := perm[k]jis thus ∈ [0, n)perm[k] = kpreserves ∀ x ∈ [0, n)perm[x]∈ [0, n) property.k = jcompiler can see k continues to k ∈ [0, n) in next iterationsfor ; r < n; r++for i := 0; i < r; i++perm1[i]andperm1[i+1]does not need BCperm1[i] = perm1[i+1]the compiler can see∀ x ∈ [0, n) perm1[x] ∈ [0, n)property is preservedris initially set tonthus after this we know (at least on first mainloop iteration, see below about next)
r = 1furtnerthe outer loop, once again, is
for ; r < n; r++thus inside r ∈ [1, n)
thus
perm1[r]andcount[r]do not need BCthe outer loop only increases r which was initially known to be = 1, so after it is known to be >= 1
this way when main loop runs next time in
the compiler can prove, since
r >= 1the loop will terminate with r==1, not loop foreverif count[r] > 0 { - 4885ff TESTQ DI, DI - 7f10 JG 0x2459 + 4d85c0 TESTQ R8, R8 + 7f10 JG 0x2305 for ; r < n; r++ { - 48ffc2 INCQ DX - 4c39c2 CMPQ R8, DX - 7d0b JGE 0x245c + 48ffc1 INCQ CX + 4839f1 CMPQ SI, CX + 7d0b JGE 0x2308 perm0 := perm1[0] - 488b3b MOVQ 0(BX), DI - 4531d2 XORL R10, R10 + 4c8b02 MOVQ 0(DX), R8 + 4531db XORL R11, R11 for i := 0; i < r; i++ { - eba9 JMP 0x2402 + ebd7 JMP 0x22dc for ; r < n; r++ { - 4c39c2 CMPQ R8, DX + 4839f1 CMPQ SI, CX if r == n { - 741a JE 0x2478 - 488b7c2440 MOVQ 0x40(SP), DI - 4d89ea MOVQ R13, R10 + 7415 JE 0x231f + 4d89d0 MOVQ R10, R8 if didpr < 30 { - 4983f91e CMPQ $0x1e, R9 - 0f8d78feffff JGE 0x22e8 + 4883ff1e CMPQ $0x1e, DI + 0f8d2fffffff JGE 0x2246 didpr++ - 49ffc1 INCQ R9 + 48ffc7 INCQ DI if didpr < 30 { - e970feffff JMP 0x22e8 + e927ffffff JMP 0x2246 return flipsMax - 4c89ac2490000000 MOVQ R13, 0x90(SP) - 488b6c2478 MOVQ 0x78(SP), BP - 4881c480000000 ADDQ $0x80, SP + 4c89542458 MOVQ R10, 0x58(SP) + 488b6c2440 MOVQ 0x40(SP), BP + 4883c448 ADDQ $0x48, SP c3 RET - 4d89d5 MOVQ R10, R13 + 4d89c2 MOVQ R8, R10 if flipsMax < flips { - ebba JMP 0x244c - 4c8b5c2468 MOVQ 0x68(SP), R11 - 4c8b642438 MOVQ 0x38(SP), R12 - 4d89d5 MOVQ R10, R13 + ebc5 JMP 0x22f8 + 4c8b4c2438 MOVQ 0x38(SP), R9 + 4d89c2 MOVQ R8, R10 if perm1[0] != 0 && perm1[n1] != n1 { - ebab JMP 0x244c - 4c8b5c2468 MOVQ 0x68(SP), R11 - 4c8b642438 MOVQ 0x38(SP), R12 - 4d89d5 MOVQ R10, R13 - eb9c JMP 0x244c + ebbb JMP 0x22f8 + 4c8b4c2438 MOVQ 0x38(SP), R9 + 4d89c2 MOVQ R8, R10 + ebb1 JMP 0x22f8 return 0 - 48c784249000000000000000 MOVQ $0x0, 0x90(SP) - 488b6c2478 MOVQ 0x78(SP), BP - 4881c480000000 ADDQ $0x80, SP - c3 RET - count[r]-- - 0x24c9 e800000000 CALL 0x24ce [1:5]R_CALL:runtime.panicindex - 0x24ce 0f0b UD2 - perm1[r] = perm0 - 0x24d0 e800000000 CALL 0x24d5 [1:5]R_CALL:runtime.panicindex - 0x24d5 0f0b UD2 - perm1[i] = perm1[i+1] - 0x24d7 e800000000 CALL 0x24dc [1:5]R_CALL:runtime.panicindex - 0x24dc 0f0b UD2 - j := perm[k] - 0x24de e800000000 CALL 0x24e3 [1:5]R_CALL:runtime.panicindex - 0x24e3 0f0b UD2 - perm[i], perm[j] = perm[j], perm[i] - 0x24e5 e800000000 CALL 0x24ea [1:5]R_CALL:runtime.panicindex - 0x24ea 0f0b UD2 - perm[i] = perm1[i] - 0x24ec e800000000 CALL 0x24f1 [1:5]R_CALL:runtime.panicindex - 0x24f1 0f0b UD2 - if perm1[0] != 0 && perm1[n1] != n1 { - 0x24f3 e800000000 CALL 0x24f8 [1:5]R_CALL:runtime.panicindex - 0x24f8 0f0b UD2 - count[r-1] = r - 0x24fa e800000000 CALL 0x24ff [1:5]R_CALL:runtime.panicindex - 0x24ff 0f0b UD2 - perm1[i] = i // initial (trivial) permutation - 0x2501 e800000000 CALL 0x2506 [1:5]R_CALL:runtime.panicindex - 0x2506 0f0b UD2 + 48c744245800000000 MOVQ $0x0, 0x58(SP) + 488b6c2440 MOVQ 0x40(SP), BP + 4883c448 ADDQ $0x48, SP + c3 RET func fannkuch(n int) int { - e800000000 CALL 0x250d [1:5]R_CALL:runtime.morestack_noctxt - e9c0fcffff JMP %22%22.fannkuch(SB) + e800000000 CALL 0x235f [1:5]R_CALL:runtime.morestack_noctxt + e90efeffff JMP %22%22.fannkuch(SB)^^^ are all
CALL runtime.panicindexdestinations and they were all covered by my comments.So maybe I missed something (appologize then) but above I was able to prove all runtime bounds check are unneccessary in fannkuch. I don't see any reason the compiler cannot be taught to do the same. Thus for fannkuch it is theoretically possible to reach -B level with just BCE.
navytux commentedon May 20, 2017
About compiler itself I've tried to see myself too. For this via passing
GO_GCFLAGS=-Benv var to make.bash I've bootstrapped second compiler (goB) which does not check bounds at compile runtime, checked it is really the case (e.g.go tool objdump pkg/tool/linux_amd64/compile |grep panicindex |wc -l), and compared go and goB via compilebench:It is hard for me to say it had no impact.
Josh, what was your way of testing? Same as mine, or maybe I'm missing something?
Thanks beforehand,
Kirill
dr2chase commentedon May 20, 2017
The optimization proposed here is very aggressive, and the proposed gains are smaller than what we hope to obtain from either getting better inlining into the compiler or passing arguments in registers. I'd like to target 1.11 instead of 1.10.
josharian commentedon May 22, 2017
Effectively same as yours. My CPU's branch predictor just seems to be generally better than yours.
Agreed. @bradfitz any chance you could create 1.11 milestones for us?
navytux commentedon May 22, 2017
@josharian thanks for feedback. For the reference my CPU is this:
http://cpubenchmark.net/cpu.php?cpu=Intel+Core+i7-6600U+%40+2.60GHz&id=2608
it is the highest end one could get from 15W TDP mobile series in 6th Intel generation.
4 remaining items
gopherbot commentedon Apr 2, 2018
Change https://golang.org/cl/100278 mentions this issue:
cmd/compile: in prove, infer unsigned relations while branchinggopherbot commentedon Apr 2, 2018
Change https://golang.org/cl/100277 mentions this issue:
cmd/compile: in prove, add transitive closure of relationsrasky commentedon Apr 2, 2018
The original issue tracked in this bug (BCE in
bvec.AndNot) is fixed by CL100277 and CL100278. After the first lands,len(a) == len(b)can be used to trigger BCE; after the second,len(a) < len(b)will work too.@navytux would it possible to move your wonderful comment about fannkuch in a separate issue? It would be easier to find and track.
navytux commentedon Apr 3, 2018
@rasky, thanks for working on patches improving BCE. Sure, fannkuch case can be moved outside for easier observability and tracking -> please see #24660.
josharian commentedon Apr 3, 2018
Awesome.
Will it require additional work or hints to be added to bvec.AndNot, or will the existing code suffice? Just want to know whether I need to send any follow-up CLs.
rasky commentedon Apr 3, 2018
Yes, you need to assert that all the involved vector have equal or compatible size (eg: >= of the one you're iterating on). In the OP you say "By construction, though, len(dst.b) == len(src1.b) == len(src2.b)" but unless that is visible to the compiler, you need explicitly assert it.
josharian commentedon Apr 3, 2018
Cool. Once those CLs are in I'll find the right assertion to add.
cmd/compile: in prove, add transitive closure of relations
gopherbot commentedon May 1, 2018
Change https://golang.org/cl/110560 mentions this issue:
cmd/compile: optimize bvec routinescmd/compile: optimize bvec routines