In the translated article from Slow to SIMD, a SourceGraph engineer discusses one optimization technique known as Bounds Check Elimination (BCE), and poses a question to the readers:
“
Why use
a[i:i+4:i+4]instead ofa[i:i+4]?
The first part of this article answers this question. The second part introduces a better method for bounds check elimination. The third part comprehensively reviews Go’s bounds check elimination techniques.
Why Use a[i:i+4:i+4] Instead of a[i:i+4]?
After this article was published on several platforms, many Gophers have been asking for the answer to this question, including the author of 100 Common Go Language Mistakes, who inquired on Twitter, as well as discussions on Hacker News[1] and reddit[2].
Of course, those who have not read this article may not understand the context, so let me briefly introduce it. The SourceGraph engineer uses BCE for optimization, and his code is as follows:
func DotBCE(a, b []float32) float32 {
if len(a) != len(b) {
panic("slices must have equal lengths")
}
if len(a)%4 != 0 {
panic("slice length must be multiple of 4")
}
sum := float32(0)
for i := 0; i < len(a); i += 4 {
aTmp := a[i : i+4 : i+4] // <--- This line does bounds checking
bTmp := b[i : i+4 : i+4] // <--- This line does bounds checking
s0 := aTmp[0] * bTmp[0] // <--- This line does not do bounds checking
s1 := aTmp[1] * bTmp[1] // <--- This line does not do bounds checking
s2 := aTmp[2] * bTmp[2] // <--- This line does not do bounds checking
s3 := aTmp[3] * bTmp[3] // <--- This line does not do bounds checking
sum += s0 + s1 + s2 + s3
}
return sum
}
Note the two lines that perform bounds checking; they ensure that the new slice’s length and capacity are both 4, guaranteeing that aTemp[0], aTemp[3], bTemp[0], and bTemp[3] will not go out of bounds, allowing the next four lines to skip bounds checking. However, fewer bounds checks result in fewer instructions, which can improve performance.
How do we know which lines perform bounds checking? We can use the command below to compile, which will print out the number of lines that perform bounds checking.
The results are consistent with our comments; only lines 14 and 15 perform bounds checking.
However, the SourceGraph engineer suddenly posed a question: Why use a[i:i+4:i+4] instead of a[i:i+4]?
Could it be that a[i:i+4] would cause the next four lines to perform bounds checking? This question intrigued many, and forums lacked answers. Some commenters on the translated article also inquired about this question.
First, we modify it to a[i:i+4] and compile to see the result:
There is no difference; lines 14 and 15 still perform bounds checking, and the next four lines have bounds check elimination. Isn’t that the same?
This question was briefly mentioned by Go101 on Twitter, but not elaborated upon. Those who purchased his book can refer to that chapter:
Next, I will start from the initial discussion, which goes back to a commit in the autumn of 2018.
For those who don’t want to read the history, you can skip ahead; the conclusion is: this approach is not for bounds check elimination but for performance.
This was an optimization for image/draw: optimize bounds checks in loops:
In which there is a line s := spix[i : i+4 : i+4], Sebastien Binet raised a question: why set cap here? Brad Fitzpatrick said, then I’ll remove it, while the author Ian Davis stated he tested and felt that setting cap gives the compiler a hint, thus improving performance. This led to an interesting discussion on this peculiar point. Ian Davis said that if it were changed to s := spix[i : i+4], although it wouldn’t affect bounds checking, performance would decrease. Giovanni Bajo provided the correct answer:
“
If you don’t specify the cap, the compiler needs to calculate it by computing
newcap = oldcap - offset. If you specify it with the same value as len, it does less work.Translation: If you do not specify the cap, the compiler needs to calculate the new
newcap = oldcap - offset. If you specify the cap with the same value as len, the compiler can do less work.
Nigel Tao also pointed out that this line of code could also use _ = spix[i+3] instead. Ultimately, this discussion was recorded in #27857.[5]
To answer the SourceGraph engineer’s question: Why use a[i:i+4:i+4] instead of a[i:i+4]?
The answer is for better performance, not for bounds check elimination.
Better Bounds Check Elimination Methods
The SourceGraph engineer’s code used BCE for optimization, but you still see that two lines of code still perform bounds checking. This is because Go’s BCE is not perfect, and sometimes it still performs bounds checking.
But is there a way to eliminate all bounds checks in the code? The old tortoise provided a solution. Let’s first look at the example given by the old tortoise (f8z, which I have slightly modified):
You can see that Go’s BCE is not that intelligent; in the example f8x, s[i+3], s[i+2], and s[i+1] will not go out of bounds, but these three lines still perform bounds checking.
In the example f8y, after performing bounds checking on s[3], it can ensure that s[2], s[1], and s[0] will not go out of bounds, so these three lines do not need to perform bounds checking.
In the example f8z, we check if the length of s is greater than 4 each loop; if greater than 4, s[3], s[2], s[1], and s[0] will definitely not go out of bounds, so these four lines do not perform bounds checking, and s = s[4:] will also not go out of bounds. Thus, this implementation does not require any bounds checking overall.
So the SourceGraph engineer’s code can be modified as follows:
Go’s Bounds Check Elimination Techniques
The old tortoise has a chapter dedicated to this issue[6] in Go101, which interested students can read directly or purchase his e-book.
I want to start with the proposal for Go’s bounds check elimination, which is [cmd/compile: unnecessary bounds checks are not removed #14808](https://github.com/golang/go/issues/14808), proposed by Alexandru Moșoi, who wrote a document Bounds Checking Elimination[7].
Of course, BCE has always been optimized in Go’s compiler, and the original documentation may not fully reflect the current situation, but it is still meaningful to categorize the organized BCE techniques for easier learning. I will organize and translate it.
Go has two types of bounds checks: index a[i] and slice a[i,j]. The Go compiler inserts some bounds checking code when accessing these two methods, but in most cases, it is unnecessary and redundant. Our goal is to eliminate these redundant checks during compilation to improve performance and reduce binary file size. You can disable bounds checking using -gcflags=-B.
You can check which lines performed bounds checking using go build -gcflags="-d=ssa/check_bce" xxx.go.
Here are some scenarios for bounds check elimination.
Redundant Checks
For example, in the code below, repeated indexing and slice accesses do not perform bounds checking.
var a []int
….
_ = a[i] // bounds check
_ = a[i] // repeated access, eliminate bounds check
_ = a[2*i+7] // bounds check
_ = a[2*i+7] // repeated access, eliminate bounds check
var a []int
….
_ = a[:i]
_ = a[:i] // repeated access, eliminate bounds check
var a []int
….
_ = a[i:]
_ = a[i:] // repeated access, eliminate bounds check
Constant Slice Size with Masked Index
var a[17]int
….
_ = a[i&5] // 0 <= i&5 and i&5 <= 5 < 17 == len(a), remove bounds check
_ = a[i%5] // cannot remove, because i may be negative, negative would go out of bounds
Constant Index
var a[]int
….
if 5 < len(a) { _ = a[5] } // 0 <= 5 and 5 < len(a), remove bounds check
This is also the way we completely eliminate bounds checking in the previous section.
Constant Index and Constant Size
var a[10]int
….
_ = a[5] // 0 <= 5 and 5 < len(a) == 10, remove bounds check
Trivial Bounds Checks
a[i:j] generates two bounds checks: 0 <= i <= j and 0 <= j <= cap(a). Sometimes we can remove one of them.
var a[]int
…
a[i:len(a)] // second bounds check 0 <= len(a) <= cap(a) removed
var a[]int
…
a[:len(a)>>1] // first bounds check removed 0 <= 0 <= len(a)>>1, because len(a)>>1 >= 0
var a[]int
…
a[:len(b)] // first bounds check 0 <= 0 <= len(a) removed
Bounds Checks Based on Loop Variables
var a[]int
…
for i := range a { // not applicable for string
use a[i] // remove, i loop variable
use a[i:] // remove
use a[:i] // remove
}
var a []int
...
for i := 0; i < len(a); i++ { // also applicable for string
use a[i] // remove, i loop variable
use a[i:] // remove
use a[:i] // remove
}
var a[]int
…
for i := range a { // not applicable for string
use a[:i+1] // remove, i loop variable
use a[i+1:] // remove
}
Decreasing Constant Index
var a[]int
…
_ = a[3] // one bounds check
use a[1], a[2], a[3] // no bounds check needed
// or
a = a[:3:len(a)] // one bounds check
use a[0], a[1], a[2] // no bounds check needed
// or
use a[3], a[2], a[1] // one bounds check
// or
if len(a) >= 3 {
use a[0], a[1], a[2] // one bounds check
}
Bounds Checks That Cannot Be Removed
In the following k8x, the first a[i] where i may be negative cannot be removed, while the next two can be ensured not to go out of bounds, hence they can be removed.
func k8x(a []int, i int, j uint) {
if i < len(a) {
_ = a[i] // cannot remove, because i may be negative
}
if j < uint(len(a)) {
_ = a[j] // remove, because 0 <= j < len(a)
}
if 0 <= i && i < len(a) {
_ = a[i] // remove, because 0 <= i < len(a)
}
}
In the following k8y, i+2 may overflow, for example, i = math.MaxInt, so it cannot be removed.
func k8y(a []int, i int) {
if 0 <= i && i+2 < len(a) {
_ = a[i+2] // i+2 might overflow int
}
}
This document has a few scenarios where BCE has already improved, and I have corrected them as above.
References[1]
Hacker News: https://news.ycombinator.com/item?id=39106972
[2]
reddit: https://www.reddit.com/r/golang/comments/199u7np/from_slow_to_simd_a_go_optimization_story/
[3]
Go101: https://go101.org/
[4]
image/draw: optimize bounds checks in loops: https://go-review.googlesource.com/c/go/+/136935
[5]
#27857: https://github.com/golang/go/issues/27857
[6]
This issue: https://go101.org/article/bounds-check-elimination.html
[7]
cmd/compile: unnecessary bounds checks are not removed #14808: https://docs.google.com/document/d/1vdAEAjYdzjnPA9WDOQ1e4e05cYVMpqSxJYZT33Cqw2g/edit#heading=h.ywknbkyeha6d