Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

cmd/compile: slice hint seems to perform better than loop bound check #32492

Open
agnivade opened this issue Jun 8, 2019 · 1 comment
Open

cmd/compile: slice hint seems to perform better than loop bound check #32492

agnivade opened this issue Jun 8, 2019 · 1 comment
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. Performance
Milestone
Backlog

Comments

@agnivade
Copy link
Contributor

agnivade commented Jun 8, 2019

CL 164966 was submitted was a BCE optimization to math/big.

It had a surprising comment -

// However, checking i < len(x) && i < len(y) as well is faster than
// having the compiler do a bounds check in the body of the loop;
// remarkably it is even faster than hoisting the bounds check
// out of the loop, by doing something like
// _, _ = x[len(z)-1], y[len(z)-1]

To test it out, I ran the same benchmarks again by hoisting the bounds check out of the loop, and got an improvement. This issue is to investigate why I see an improvement but @josharian did not.

Here is what I did:

On a quiet machine, I ran - gotip test -run=xxx -bench=BenchmarkAddV -tags=math_big_pure_go -count=10

The changes are -

--- a/src/math/big/arith.go
+++ b/src/math/big/arith.go
@@ -69,7 +69,9 @@ func divWW_g(u1, u0, v Word) (q, r Word) {
 // The resulting carry c is either 0 or 1.
 func addVV_g(z, x, y []Word) (c Word) {
        // The comment near the top of this file discusses this for loop condition.
-       for i := 0; i < len(z) && i < len(x) && i < len(y); i++ {
+       _ = x[len(z)-1]
+       _ = y[len(z)-1]
+       for i := 0; i < len(z); i++ {
                zi, cc := bits.Add(uint(x[i]), uint(y[i]), uint(c))
                z[i] = Word(zi)
                c = Word(cc)
@@ -92,7 +94,8 @@ func subVV_g(z, x, y []Word) (c Word) {
 func addVW_g(z, x []Word, y Word) (c Word) {
        c = y
        // The comment near the top of this file discusses this for loop condition.
-       for i := 0; i < len(z) && i < len(x); i++ {
+       _ = x[len(z)-1]
+       for i := 0; i < len(z); i++ {
                zi, cc := bits.Add(uint(x[i]), uint(c), 0)
                z[i] = Word(zi)
                c = Word(cc)

And the benchmark results -

name            old time/op    new time/op    delta
AddVV/1-4         6.43ns ± 2%    7.25ns ± 2%  +12.70%  (p=0.000 n=10+10)
AddVV/2-4         8.16ns ± 1%    8.59ns ± 3%   +5.32%  (p=0.000 n=10+10)
AddVV/3-4         9.79ns ± 2%    9.67ns ± 2%   -1.16%  (p=0.014 n=10+10)
AddVV/4-4         11.0ns ± 2%    10.7ns ± 1%   -2.99%  (p=0.000 n=9+10)
AddVV/5-4         11.7ns ± 3%    11.5ns ± 5%     ~     (p=0.070 n=9+10)
AddVV/10-4        18.1ns ± 6%    16.9ns ± 4%   -6.62%  (p=0.000 n=10+10)
AddVV/100-4        163ns ± 3%     159ns ± 2%   -2.57%  (p=0.005 n=10+10)
AddVV/1000-4      1.54µs ± 2%    1.52µs ± 1%     ~     (p=0.053 n=9+9)
AddVV/10000-4     15.7µs ± 4%    15.2µs ± 1%   -2.78%  (p=0.001 n=10+10)
AddVV/100000-4     167µs ± 6%     168µs ± 1%     ~     (p=0.605 n=9+9)
AddVW/1-4         6.45ns ± 2%    6.25ns ± 2%   -3.13%  (p=0.000 n=10+10)
AddVW/2-4         8.66ns ± 1%    7.37ns ± 2%  -14.89%  (p=0.000 n=10+10)
AddVW/3-4         9.07ns ± 1%    8.31ns ± 3%   -8.37%  (p=0.000 n=9+10)
AddVW/4-4         10.3ns ± 2%     9.5ns ± 3%   -8.50%  (p=0.000 n=10+10)
AddVW/5-4         10.3ns ± 2%    10.2ns ± 2%   -1.74%  (p=0.006 n=10+10)
AddVW/10-4        14.9ns ± 4%    14.1ns ± 4%   -5.31%  (p=0.000 n=10+10)
AddVW/100-4       27.1ns ± 5%    27.0ns ± 4%     ~     (p=0.956 n=10+10)
AddVW/1000-4       122ns ± 2%     121ns ± 4%     ~     (p=0.210 n=10+10)
AddVW/10000-4     3.97µs ± 1%    3.97µs ± 1%     ~     (p=0.807 n=8+10)
AddVW/100000-4    68.9µs ± 1%    69.9µs ± 1%   +1.42%  (p=0.001 n=10+10)

Josh says he did shorter runs. I set count as 10. Perhaps longer runs somehow affect the branch predictor ?

What version of Go are you using (go version)?

$ go version
go version devel +98100c56da Mon Jun 3 01:37:58 2019 +0000 linux/amd64

cc'ing folks who were in the original CL - @josharian @mundaym @griesemer

My CPU details are

Architecture:        x86_64
CPU op-mode(s):      32-bit, 64-bit
Byte Order:          Little Endian
CPU(s):              4
On-line CPU(s) list: 0-3
Thread(s) per core:  2
Core(s) per socket:  2
Socket(s):           1
NUMA node(s):        1
Vendor ID:           GenuineIntel
CPU family:          6
Model:               61
Model name:          Intel(R) Core(TM) i5-5200U CPU @ 2.20GHz
Stepping:            4
CPU MHz:             911.804
CPU max MHz:         2700.0000
CPU min MHz:         500.0000
BogoMIPS:            4389.77
Virtualization:      VT-x
L1d cache:           32K
L1i cache:           32K
L2 cache:            256K
L3 cache:            3072K
NUMA node0 CPU(s):   0-3
Flags:               fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc cpuid aperfmperf pni pclmulqdq dtes64 monitor ds_cpl vmx est tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm abm 3dnowprefetch cpuid_fault epb invpcid_single pti ssbd ibrs ibpb stibp tpr_shadow vnmi flexpriority ept vpid fsgsbase tsc_adjust bmi1 avx2 smep bmi2 erms invpcid rdseed adx smap intel_pt xsaveopt dtherm ida arat pln pts flush_l1d
@agnivade agnivade added the NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. label Jun 8, 2019
@agnivade agnivade added this to the Go1.14 milestone Jun 8, 2019
@josharian
Copy link
Contributor

Josh says he did shorter runs. I set count as 10. Perhaps longer runs somehow affect the branch predictor ?

To clarify, I meant that I set a short benchtime, probably 10ms.

@rsc rsc modified the milestones: Go1.14, Backlog Oct 9, 2019
@gopherbot gopherbot added the compiler/runtime Issues related to the Go compiler and/or runtime. label Jul 13, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. Performance
Projects
Go Compiler / Runtime
Status: Triage Backlog
Milestone
Backlog
Development

No branches or pull requests
4 participants
@josharian @rsc @agnivade @gopherbot