cmd/compile: Fannkuch11 can be speed up by ~ 30% via improving BCE #24660
Comments
|
Fannkuch11 begins with a boundcheck that I thought was a low-hanging fruit: func s1(n int) []int {
s := make([]int, n)
for i := 0; i < n; i++ {
s[i] = i
}
return s
}I thought that proving @randall77 @mdempsky @aclements any suggestion on how to handle this? Is a new intermediate SSA op |
|
Some of our rewrite rules look into the load/store/call ops to extract useful information. see cmd/compile/internal/ssa/gen/generic.rules, particularly those for calling I think adding a SliceAlloc op might be better long term, but it is a bigger change. |
rasky
added
Performance
NeedsFix
|
/cc @zdjones |
|
Change https://golang.org/cl/190657 mentions this issue: |
|
@navytux By my count, The CL above removes 6 of 12 bounds checks from Fannkuch. |
|
@zdjones, thanks. It is good to see that BCE is being worked on. |
|
Some BCEs in Funnkuch11 are possibly too hard, like those that require tracking that all values within a slice have a certain upper bound (since they are effectively slices of indices to another slice). @zdjones which are the ones left after your patch? |
|
I've marked the 12 remaining checks and noted which ones the patch removes. |
|
Change https://golang.org/cl/195220 mentions this issue: |
|
Thanks! I noticed that this loop: wasn't being detected by loopbce, and the fix was easy enough (just mailed). CL 195220 detects If we fix that, and manage to merge your trace CL series, I think we're basically done with Fannkuch, as tracking the contents of a slice is probably outside of what we can reasonably implement, and is possibly useful only for algorithms storing indexes to arrays within other arrays, which doesn't sound common enough to be worth design and resolving this problem. |
|
Awesome! I'm going to take a closer look at your CL, and that second bounds check, when I have the time. I suspect that CL will remove a decent number bounds checks from std/cmd as well? I think we may be able to get this one as well: I'll investigate. My suspicion is that this is also a Phi issue. My plan is to try adding Phi to trace... maybe that will be enough. I agree about the remaining 3 checks; |
I actually have not had time to check.
The problem with this one is that the current induction variable logic can't handle a loop whose bounding condition is If trace grows to be able to handle this case, then it probably can substitute the whole induction variable detection code. |
So, the problem there is that, in prove, we don't update ft.limits when we record relations between dependencies not involving constants. For instance if learn that Eventually, we should get rid of |
|
Change https://golang.org/cl/196784 mentions this issue: |
Now that OpSliceMake is called by runtime.makeslice callers, prove can see and record the actual length and cap of each slice being constructed. This small patch is enough to remove 260 additional bound checks from cmd+std. Thanks to Martin Möhrmann for pointing me to CL141822 that I had missed. Updates #24660 Change-Id: I14556850f285392051f3f07d13b456b608b64eb9 Reviewed-on: https://go-review.googlesource.com/c/go/+/196784 Run-TryBot: Giovanni Bajo <[email protected]> TryBot-Result: Gobot Gobot <[email protected]> Reviewed-by: David Chase <[email protected]>
prove wasn't able to detect induction variables that was bound by another inducation variable. This happened because an indvar is a Phi, and thus in case of a dependency, the loop bounding condition looked as Phi < Phi. This triggered an existing codepath that checked whether the upper bound was a Phi to detect loop conditions written in reversed order respect to the idiomatic way (eg: for i:=0; len(n)>i; i++). To fix this, we call the indvar pattern matching on both operands of the loop condition, so that the first operand that matches will be treated as the indvar. Updates #24660 (removes a boundcheck from Fannkuch) Change-Id: Iade83d8deb54f14277ed3f2e37b190e1ed173d11 Reviewed-on: https://go-review.googlesource.com/c/go/+/195220 Reviewed-by: David Chase <[email protected]>
|
After the two CLs that just landed, I think we're only missing the check analyzed here among those that are remotely feasible. I'm still experimenting with bound calculations in poset, but it's getting hairy. Not sure if I'll manage to land it, it might not be worth it, depending on how good it turns out to be when it's done. If I don't land it, I have another CL that improve ft.limits a little bit, enough to tackle this case and close this bug for good. |
gopherbot
added
the
compiler/runtime
This is spin-off issue from #20393. There in the discussion it was shown that Fannkuch11 benchmark from go1 benchmark suite runs ~30% faster with
-gcflags=-B. A proof was also provided showing that all the bounds checks emitted by the compiler are actually not needed, and thus with clever BCE it should be possible to reach ~30% Fannkuch11 speedup level demonstrated by-gcflags=-B.That discussion is from May 2017. However I've just rechecked with today's go tip
and current state is:
in other words there is still ~30% room for BCE related improvement.
Below comes verbatim copy of my original proof that all bounds checks are not actually needed in Fannkuch case. Even though it discusses code emitted by old compilers, all points about bounds checks not needed should stand still valid today.
Thanks,
Kirill
/cc @josharian, @rasky, @dr2chase, @brtzsnr, @aclements
---- 8< ----
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.
The text was updated successfully, but these errors were encountered: