현재 3권의 신간들인 Go Optimizations 101, Go Details & Tips 101Go Generics 101이 출간되어 있습니다. Leanpub 서점에서 번들을 모두 구입하시는 방법이 비용 대비 효율이 가장 좋습니다.

Go에 대한 많은 정보들과 Go 101 책들의 최신 소식을 얻으시려면 Go 101 트위터 계정인 @Go100and1을 팔로잉 해주세요.

Bounds Check Elimination

Go is a memory safe language. In array/slice element indexing and subslice operations, Go runtime will check whether or not the involved indexes are out of range. If an index is out of range, a panic will be produced to prevent the invalid index from doing harm. This is called bounds check. Bounds checks make our code run safely, on the other hand, they also make our code run a little slower.

Since Go Toolchain 1.7, the standard Go compiler has used a new compiler backend, which based on SSA (static single-assignment form). SSA helps Go compilers effectively use optimizations like BCE (bounds check elimination) and CSE (common subexpression elimination). BCE can avoid some unnecessary bounds checks, and CSE can avoid some duplicate calculations, so that the standard Go compiler can generate more efficient programs. Sometimes the improvement effects of these optimizations are obvious.

This article will list some examples to show how BCE works with the standard Go compiler 1.7+.

For Go Toolchain 1.7+, we can use -gcflags="-d=ssa/check_bce" compiler flag to show which code lines still need bounds checks.

Example 1

// example1.go
package main

func f1(s []int) {
	_ = s[0] // line 5: bounds check
	_ = s[1] // line 6: bounds check
	_ = s[2] // line 7: bounds check
}

func f2(s []int) {
	_ = s[2] // line 11: bounds check
	_ = s[1] // line 12: bounds check eliminated!
	_ = s[0] // line 13: bounds check eliminated!
}

func f3(s []int, index int) {
	_ = s[index] // line 17: bounds check
	_ = s[index] // line 18: bounds check eliminated!
}

func f4(a [5]int) {
	_ = a[4] // line 22: bounds check eliminated!
}

func main() {}
$ go run -gcflags="-d=ssa/check_bce" example1.go
./example1.go:5: Found IsInBounds
./example1.go:6: Found IsInBounds
./example1.go:7: Found IsInBounds
./example1.go:11: Found IsInBounds
./example1.go:17: Found IsInBounds

We can see that there are no needs to do bounds checks for line 12 and line 13 in function f2, for the bounds check at line 11 ensures that the indexes in line 12 and line 13 will not be out of range.

But in function f1, bounds checks must be performed for all three lines. The bounds check at line 5 can't ensure line 6 and line 7 are safe, and the bounds check at line 6 can't ensure line 7 is safe.

For function f3, the compiler knows the second s[index] is absolutely safe if the first s[index] is safe.

The compiler also correctly thinks the only line (line 22) in function f4 is safe.

Please note that, up to now (Go Toolchain 1.20), the standard compiler doesn't check BCE for an operation in a generic function if the operation involves type parameters and the generic function is never instantiated.

A demo case:
// example1b.go
package main

func foo[E any](s []E) {
	_ = s[0] // line 5
	_ = s[1] // line 6
	_ = s[2] // line 7
}

// var _ = foo[bool]

func main() {
}
When the variable declaration line is disabled, the compiler outputs nothing:
$ go run -gcflags="-d=ssa/check_bce" example1b.go

When the variable declaration line is enabled, the compiler outputs:
./aaa.go:5:7: Found IsInBounds
./example1b.go:6:7: Found IsInBounds
./example1b.go:7:7: Found IsInBounds
./example1b.go:4:6: Found IsInBounds

Example 2

// example2.go
package main

func f5(s []int) {
	for i := range s {
		_ = s[i]
		_ = s[i:len(s)]
		_ = s[:i+1]
	}
}

func f6(s []int) {
	for i := 0; i < len(s); i++ {
		_ = s[i]
		_ = s[i:len(s)]
		_ = s[:i+1]
	}
}

func f7(s []int) {
	for i := len(s) - 1; i >= 0; i-- {
		_ = s[i]
		_ = s[i:len(s)]
	}
}

func f8(s []int, index int) {
	if index >= 0 && index < len(s) {
		_ = s[index]
		_ = s[index:len(s)]
	}
}

func f9(s []int) {
	if len(s) > 2 {
	    _, _, _ = s[0], s[1], s[2]
	}
}

func main() {}
$ go run -gcflags="-d=ssa/check_bce" example2.go

Cool! The standard compiler removes all bound checks in this program.

Note: before Go Toolchain version 1.11, the standard compiler is not smart enough to detect line 22 is safe.

Example 3

// example3.go
package main

import "math/rand"

func fa() {
	s := []int{0, 1, 2, 3, 4, 5, 6}
	index := rand.Intn(7)
	_ = s[:index] // line 9: bounds check
	_ = s[index:] // line 10: bounds check eliminated!
}

func fb(s []int, i int) {
	_ = s[:i] // line 14: bounds check
	_ = s[i:] // line 15: bounds check, not smart enough?
}

func fc() {
	s := []int{0, 1, 2, 3, 4, 5, 6}
	s = s[:4]
	i := rand.Intn(7)
	_ = s[:i] // line 22: bounds check
	_ = s[i:] // line 23: bounds check, not smart enough?
}

func main() {}
$ go run -gcflags="-d=ssa/check_bce" example3.go
./example3.go:9: Found IsSliceInBounds
./example3.go:14: Found IsSliceInBounds
./example3.go:15: Found IsSliceInBounds
./example3.go:22: Found IsSliceInBounds
./example3.go:23: Found IsSliceInBounds

Oh, so many places still need to do bounds check!

But wait, why does the standard Go compiler think line 10 is safe but line 15 and line 23 are not? Is the compiler still not smart enough?

In fact, the compiler is right here! Why? The reason is the start index in a subslice expression may be larger than the length of the base slice. Let's view a simple example:

package main

func main() {
	s0 := make([]int, 5, 10) // len(s0) == 5, cap(s0) == 10

	index := 8

	// In Go, for the subslice syntax s[a:b],
	// the relations 0 <= a <= b <= cap(s) must
	// be ensured to avoid panicking.

	_ = s0[:index]
	// The above line is safe can't ensure the
	// following line is also safe. In fact, the
	// following line will panic, for the starting
	// index is larger than the end index.
	_ = s0[index:] // panic
}

So the conclusion that if s[:index] is safe then s[index:] is also safe is only right when len(s) is equal to cap(s). This is why the code lines in function fb and fc of example 3 still need to do bounds checks.

Standard Go compiler successfully detects len(s) is equal to cap(s) in function fa. Great work! Go team!

Example 4

// example4.go
package main

import "math/rand"

func fb2(s []int, index int) {
	_ = s[index:] // line 7: bounds check
	_ = s[:index] // line 8: bounds check eliminated!
}

func fc2() {
	s := []int{0, 1, 2, 3, 4, 5, 6}
	s = s[:4]
	index := rand.Intn(7)
	_ = s[index:] // line 15 bounds check
	_ = s[:index] // line 16: bounds check eliminated!
}

func main() {}
$ go run -gcflags="-d=ssa/check_bce" example4.go
./example4.go:7:7: Found IsSliceInBounds
./example4.go:15:7: Found IsSliceInBounds
In this example, The standard Go compiler successfully concludes

Note: the standard Go compiler in Go Toolchain earlier than version 1.9 fails to detect line 8 doesn't need bounds check.

Example 5

The current version of the standard Go compiler is not smart enough to eliminate all unnecessary bounds checks. Sometimes, we can make some hints to help the compiler eliminate some unnecessary bounds checks.
// example5.go
package main

func fd(is []int, bs []byte) {
	if len(is) >= 256 {
		for _, n := range bs {
			_ = is[n] // line 7: bounds check
		}
	}
}

func fd2(is []int, bs []byte) {
	if len(is) >= 256 {
		is = is[:256] // line 14: a hint
		for _, n := range bs {
			_ = is[n] // line 16: BCEed!
		}
	}
}

func main() {}
$ go run -gcflags="-d=ssa/check_bce" example5.go
./example5.go:7: Found IsInBounds

Summary

There are more BCE optimizations made by the standard Go compiler. They might be not as obvious as the above listed ones, So this article will not show them all.

Although the BCE feature in the standard Go compiler is still not perfect, it really does well for many common cases. It is no doubt that standard Go compiler will do better in later versions so that it is possible the hints made in the above 5th example will become unnecessary. Thank Go team for adding this wonderful feature!

References:

  1. Bounds Check Elimination
  2. Utilizing the Go 1.7 SSA Compiler (and the second part)

Index↡

The Go 101 프로젝트는 Github 에서 호스팅됩니다. 오타, 문법 오류, 부정확한 표현, 설명 결함, 코드 버그, 끊어진 링크와 같은 모든 종류의 실수에 대한 수정 사항을 제출하여 Go 101을 개선을 돕는 것은 언제나 환영합니다.

주기적으로 Go에 대한 깊이 있는 정보를 얻고 싶다면 Go 101의 공식 트위터 계정인 @go100and1을 팔로우하거나 Go 101 슬랙 채널에j가입해주세요.

이 책의 디지털 버전은 아래와 같은 곳을 통해서 구매할 수 있습니다.
Go 101의 저자인 Tapir는 2016년 7월부터 Go 101 시리즈 책들을 집필하고 go101.org 웹사이트를 유지 관리하고 있습니다. 새로운 콘텐츠는 책과 웹사이트에 수시로 추가될 예정입니다. Tapir는 인디 게임 개발자이기도 합니다. Tapir의 게임을 플레이하여 Go 101을 지원할 수도 있습니다. (안드로이드와 아이폰/아이패드용):
  • Color Infection (★★★★★), 140개 이상의 단계로 이루어진 물리 기반의 캐주얼 퍼즐 게임
  • Rectangle Pushers (★★★★★), 2가지 모드와 104개 이상의 단계로 이루어진 캐주얼 퍼즐 게임
  • Let's Play With Particles, 세가지 미니 게임이 있는 캐주얼 액션 게임
페이팔을 통한 개인 기부도 환영합니다.

색인: