Go函数内联与边界检查消除的优化挑战

本文深入探讨如何通过重构Go函数实现内联和边界检查消除，详细分析函数内联预算、边界检查机制，并提供逐步优化提示和最终实现方案，展示性能提升效果。

挑战：使这个Go函数可内联且无边界检查

在这篇文章中，我挑战你重构一个小的Go函数，使其可内联且无边界检查，以获得更好的性能。

免责声明：本文假设使用（官方）Go编译器的1.24.2版本；使用其他版本的Go编译器或其他Go语言实现可能会得到不同的结果。

函数内联与边界检查消除

尝试我的挑战需要一些函数内联和边界检查消除的基础知识。以下三个部分作为这些主题的速成课程。如果需要，可以直接跳到挑战本身。

函数内联101

内联是一种编译器策略，大致可以描述为“用函数体替换对该函数的调用”。因为它消除了一些函数调用开销，内联通常会导致更快的程序执行。然而，函数内联也会增加生成的二进制文件的大小，不加选择的内联可能导致编译器产生过大的二进制文件。因此，编译器通常将内联资格限制在它们认为“足够简单”的函数上。

对于每个函数，Go编译器分配一个内联预算并计算内联成本。如果函数的内联成本不超过其预算，编译器认为该函数有资格内联（即可内联）并内联它；否则，不会内联。在撰写本文时（Go 1.24.2），默认内联预算是80，但编译器可能由于配置文件引导的优化（PGO）而决定增加热路径上调用的函数的内联预算；对于本文，让我们保持简单，忽略PGO。然而，函数中存在某些语言结构（如递归、“go”语句、“defer”语句和调用recover函数）会直接阻止其被内联。Go编译器的内联策略不是由语言本身指定的，可能会从一个版本到下一个版本发生变化。

确定函数是否有资格内联的最直接方法是运行以下形式的命令并检查其输出：

1

$ go build -gcflags '-m=2' <package-path> 2>&1 | grep <function-name>

通过重构最初不可内联的函数（和/或放宽其语义），有时可以降低函数的内联成本，使其有资格内联；然而，除非你非常熟悉Go编译器的内联器（并跟上Go项目维护者对其所做的更改），否则你可能会（正确地）觉得使函数有资格内联更像是一门艺术而不是科学。

边界检查消除101

我在今年早些时候发表在这篇博客上的文章中提到了边界检查消除（BCE）；请允许我引用它：

[…] Go被称为内存安全；特别是，根据语言规范，如果切片索引操作越界，实现必须触发运行时恐慌。这样的边界检查相对便宜，但并非免费。当编译器可以证明某些切片访问不会越界时，它可能会为了更好的性能而从生成的可执行文件中省略相应的边界检查。

我在那篇文章中写的关于切片的内容也适用于字符串，它们在底层不过是字节切片。

边界检查消除，就像内联策略一样，仍然是一个实现细节；它不是由语言本身指定的，可能会从一个Go编译器版本到下一个版本发生变化。

要识别Go编译器在包中引入边界检查的位置，请运行以下形式的命令：

1

$ go build -gcflags '-d=ssa/check_bce/debug=1' <package-path>

边界检查的存在并不总是对性能有害，而且从程序中消除所有边界检查通常被证明是不可能的。然而，消除一些边界检查，也许通过将它们提升到循环之外，通常有助于更快的程序执行。你可以在Go的标准库中找到将边界检查提升到循环之外的实例。

尽管Go编译器的BCE逻辑经常改进，但有时你需要重构代码以说服编译器消除或移动一些边界检查。这也更像是一门艺术而不是科学，通常需要一些试验和错误。

微妙的平衡行为

函数内联和BCE紧密相连。可内线性有时以几个额外的边界检查为代价；相反，消除一些边界检查可能会剥夺函数的内联资格。但在一些幸运的情况下，你可以两全其美！

这里有一个我从经验中学到的提示：首先消除边界检查，然后实现可内线性，往往比反过来或一次性完成两者更容易。

你能使这个函数可内联且无边界检查吗？

考虑以下源文件（我已上传到Gist，方便你使用）：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

package headers

// TrimOWS trims up to n bytes of optional whitespace (OWS)
// from the start of and/or the end of s.
// If no more than n bytes of OWS are found at the start of s
// and no more than n bytes of OWS are found at the end of s,
// it returns the trimmed result and true.
// Otherwise, it returns some unspecified string and false.
func TrimOWS(s string, n int) (string, bool) {
	if s == "" {
		return s, true
	}
	s, ok := trimLeftOWS(s, n)
	if !ok {
		return "", false
	}
	s, ok = trimRightOWS(s, n)
	if !ok {
		return "", false
	}
	return s, true
}

func trimLeftOWS(s string, n int) (string, bool) {
	var i int
	for len(s) > 0 {
		if i > n {
			return "", false
		}
		if !isOWS(s[0]) {
			break
		}
		s = s[1:]
		i++
	}
	return s, true
}

func trimRightOWS(s string, n int) (string, bool) {
	var i int
	for len(s) > 0 {
		if i > n {
			return "", false
		}
		if !isOWS(s[len(s)-1]) {
			break
		}
		s = s[:len(s)-1]
		i++
	}
	return s, true
}

// See https://httpwg.org/specs/rfc9110.html#whitespace.
func isOWS(b byte) bool {
	return b == '\t' || b == ' '
}

上面的TrimOWS实现不会产生边界检查，如以下命令的空输出所示：

1
2

$ go build -gcflags '-d=ssa/check_bce/debug=1'
$

然而，它不可内联：

1
2
3

$ go build -gcflags '-m=2' 2>&1 | grep TrimOWS
./ows.go:9:6: cannot inline TrimOWS: function too complex: \
    cost 130 exceeds budget 80

这是我的挑战：你能重构函数TrimOWS，使其可内联（不依赖配置文件引导的优化）且无边界检查吗？

为了让你在重构代码时捕捉错误，我包含了一套单元测试；为了让你以后能够测量实现之间的性能变化，我还包含了一些基准测试：

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103

package headers

import "testing"

const maxOWS = 1 // number of OWS bytes tolerated on either side

var trimOWStests = []struct {
	desc string
	s    string
	want string
	ok   bool
}{
	{
		desc: "empty",
		s:    "",
		want: "",
		ok:   true,
	}, {
		desc: "no OWS",
		s:    "foo",
		want: "foo",
		ok:   true,
	}, {
		desc: "internal OWS",
		s:    "foo  \t\tbar",
		want: "foo  \t\tbar",
		ok:   true,
	}, {
		desc: "leading and trailing OWS",
		s:    "\tfoo ",
		want: "foo",
		ok:   true,
	}, {
		desc: "a tolerated amount of OWS around non-OWS",
		s:    " a ",
		want: "a",
		ok:   true,
	}, {
		desc: "a tolerated amount of OWS and nothing else",
		s:    "\t ",
		want: "",
		ok:   true,
	}, {
		desc: "non-OWS whitespace",
		s:    "\nfoo\t",
		want: "\nfoo",
		ok:   true,
	}, {
		desc: "too much leading OWS",
		s:    " \tfoo\t",
		ok:   false,
	}, {
		desc: "too much trailing OWS",
		s:    " foo\t ",
		ok:   false,
	}, {
		desc: "too much leading and trailing OWS",
		s:    " \tfoo\t ",
		ok:   false,
	},
}

func TestTrimOWS(t *testing.T) {
	for _, tc := range trimOWStests {
		f := func(t *testing.T) {
			allocs := testing.AllocsPerRun(10,
				func() { str, truth = TrimOWS(tc.s, maxOWS) },
			)
			if allocs > 0 {
				const tmpl = "TrimOWS(%q, %d) allocates %.2f objects"
				t.Errorf(tmpl, tc.s, maxOWS, allocs)
			}
			got, ok := TrimOWS(tc.s, maxOWS)
			if !tc.ok && ok {
				// In cases where TrimOWS must fail,
				// its string result is unspecified.
				const tmpl = "TrimOWS(%q, %d): _, %t; want _, %t"
				t.Fatalf(tmpl, tc.s, maxOWS, ok, tc.ok)
			}
			if tc.ok && (!ok || got != tc.want) {
				const tmpl = "TrimOWS(%q, %d): %q, %t; want %q, %t"
				t.Errorf(tmpl, tc.s, maxOWS, got, ok, tc.want, tc.ok)
			}
		}
		t.Run(tc.desc, f)
	}
}

func BenchmarkTrimOWS(b *testing.B) {
	for _, tc := range trimOWStests {
		f := func(b *testing.B) {
			for range b.N {
				str, truth = TrimOWS(tc.s, maxOWS)
			}
		}
		b.Run(tc.desc, f)
	}
}

var ( // sinks for avoiding dead-code elimination in benchmarks
	str   string
	truth bool
)

准备好进行一些微优化了吗？克隆Gist并cd到你的克隆：

1
2

$ git clone https://gist.github.com/jub0bs/0aca3c6bd041e838fe4add58a060be35
$ cd 0aca3c6bd041e838fe4add58a060be35

开始吧！

提示

这里有一系列提示，如果你卡住了可能会觉得有用；根据需要点击每个提示来揭示它。

提示0

尝试消除不必要的分支。特别是，TrimOWS中的初始空字符串检查是多余的；这是一种微优化尝试，但其性能好处是模糊的。此外，TrimOWS不需要检查trimRightOWS的布尔结果；相反，它可以简单地将trimRightOWS的结果冒泡给调用者。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

 func TrimOWS(s string, n int) (string, bool) {
-       if s == "" {
-               return s, true
-       }
        s, ok := trimLeftOWS(s, n)
        if !ok {
                return "", false
        }
-       s, ok = trimRightOWS(s, n)
-       if !ok {
-               return "", false
-       }
-       return s, true
+       return trimRightOWS(s, n)
 }

这些更改没有引入任何边界检查，并稍微降低了TrimOWS的内联成本：

1
2
3
4
5

$ go build -gcflags '-d=ssa/check_bce/debug=1'
$
$ go build -gcflags '-m=2' 2>&1 | grep TrimOWS
./ows.go:9:6: cannot inline TrimOWS: function too complex: \
    cost 121 exceeds budget 80

提示1

尽管辅助函数trimLeftOWS和trimRightOWS本身是可内联的，但在TrimOWS中手动内联它们有助于可内线性而不损害可读性：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

 func TrimOWS(s string, n int) (string, bool) {
-       s, ok := trimLeftOWS(s, n)
-       if !ok {
-               return "", false
-       }
-       return trimRightOWS(s, n)
-}
-
-func trimLeftOWS(s string, n int) (string, bool) {
        var i int
        for len(s) > 0 {
                if i > n {
                        return "", false
                }
                if !isOWS(s[0]) {
                        break
                }
                s = s[1:]
                i++
        }
-       return s, true
-}
-
-func trimRightOWS(s string, n int) (string, bool) {
-       var i int
+       i = 0
        for len(s) > 0 {
                if i > n {
                        return "", false
                }
                if !isOWS(s[len(s)-1]) {
                        break
                }
                s = s[:len(s)-1]
                i++
        }
        return s, true
 }

这些更改不仅没有引入任何边界检查，而且显著降低了TrimOWS的内联成本：

1
2
3
4
5

$ go build -gcflags '-d=ssa/check_bce/debug=1'
$
$ go build -gcflags '-m=2' 2>&1 | grep TrimOWS
./ows.go:9:6: cannot inline TrimOWS: function too complex: \
    cost 88 exceeds budget 80

手动内联我的小isOWS函数在其两个调用站点是诱人的，并且确实稍微降低了TrimOWS的内联成本，但这样做并不理想，因为它违反了DRY原则：

每个知识在系统中必须有一个单一、明确、权威的表示。

提示2

尝试遍历字符串而不是反复削减它：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

 func TrimOWS(s string, n int) (string, bool) {
        var i int
-       for len(s) > 0 {
+       for i = 0; i < len(s); i++ {
                if i > n {
                        return "", false
                }
-               if !isOWS(s[0]) {
+               if !isOWS(s[i]) {
                        break
                }
-               s = s[1:]
-               i++
        }
-       i = 0
-       for len(s) > 0 {
-               if i > n {
+       var j int
+       for j = len(s) - 1; j >= i; j-- {
+               if j < len(s)-1-n {
                        return "", false
                }
-               if !isOWS(s[len(s)-1]) {
+               if !isOWS(s[j]) {
                        break
                }
-               s = s[:len(s)-1]
-               i++
        }
-       return s, true
+       return s[i : j+1], true
 }

不幸的是，这些更改有些适得其反，因为它们不仅增加了TrimOWS的内联成本，还引入了边界检查！

1
2
3
4
5
6
7

$ go build -gcflags '-d=ssa/check_bce/debug=1'
 gist.github.com/jub0bs/0aca3c6bd041e838fe4add58a060be35
./ows.go:24:14: Found IsInBounds
./ows.go:28:10: Found IsSliceInBounds
$ go build -gcflags '-m=2' 2>&1 | grep TrimOWS
./ows.go:9:6: cannot inline TrimOWS: function too complex: \
    cost 91 exceeds budget 80

别担心！性能优化很少是一条直线，最初被视为挫折的重构实际上可能解锁新的改进机会。

提示3

编译器觉得需要引入边界检查，因为它（还？）没有跟踪足够的上下文来意识到j总是在s的边界内。为了帮助编译器，我们可以在循环内子串并重新分配s，而不是稍后；这个更改还允许我们减少控制循环的两个整数变量的范围，并简单地在执行到达TrimOWS底部时返回空字符串：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

 func TrimOWS(s string, n int) (string, bool) {
-       var i int
-       for i = 0; i < len(s); i++ {
+       for i := 0; i < len(s); i++ {
                if i > n {
                        return "", false
                }
                if !isOWS(s[i]) {
+                       s = s[i:]
                        break
                }
        }
-       var j int
-       for j = len(s) - 1; j >= i; j-- {
-               if j < len(s)-1-n {
+       for i := len(s) - 1; i >= 0; i-- {
+               if i < len(s)-1-n {
                        return "", false
                }
-               if !isOWS(s[j]) {
-                       break
+               if !isOWS(s[i]) {
+                       return s[:i+1], true
                }
        }
-       return s[i : j+1], true
+       return "", true
 }

边界检查，消失吧！

1
2

$ go build -gcflags '-d=ssa/check_bce/debug=1'
$

TrimOWS的内联成本再次向错误的方向移动：

1
2
3

$ go build -gcflags '-m=2' 2>&1 | grep TrimOWS
./ows.go:9:6: cannot inline TrimOWS: function too complex: \
    cost 93 exceeds budget 80

再次，不要让这个暂时的挫折阻止你。小步前进！

提示4

尽可能使用range-over-int循环，因为它们往往比经典的三子句循环更便宜（且更容易推理！）：

1
2
3
4
5
6

 func TrimOWS(s string, n int) (string, bool) {
-       for i := 0; i < len(s); i++ {
+       for i := range len(s) {
                if i > n {
                        return "", false
                }

没有引入边界检查，TrimOWS的内联成本现在是迄今为止最低的：

1
2
3

$ go build -gcflags '-d=ssa/check_bce/debug=1'
$
$
comments powered by Disqus
© 2020 - 2025 qife
使用 Hugo 构建
主题 Stack 由 Jimmy 设计
本站总访问量次 本站访客数人次