go ``` cmd/compile: 优化字符串(byteSlice)范围 ```

drkbr07n  于 3个月前  发布在  Go
关注(0)|答案(9)|浏览(42)

Take these two benchmarks: https://play.golang.org/p/QI4BxUq8MGp
The first code is cleaner, more idiomatic, and easier to write/maintain. The second is much trickier, and I'm not even sure I wrote it correctly.
Lucky for us, the first tends to perform about the same or slightly better in terms of time:

$ go test -bench=. -benchmem
goos: linux
goarch: amd64
pkg: mvdan.cc/p
BenchmarkIdiomatic-4      500000              2389 ns/op            2688 B/op          1 allocs/op
BenchmarkManual-4         500000              2645 ns/op               0 B/op          0 allocs/op
PASS
ok      mvdan.cc/p      2.578s

However, as one can see, it still incurs an extra allocation. I'm not sure why that is - via go test -gcflags=-m , I can see ./f_test.go:16:27: BenchmarkIdiomatic string(Input) does not escape .
We have optimized other common string conversion patterns, such as switch string(byteSlice)
in 566e3e0 , and I believe someMap[string(byteSlice)] was optimized too.
Would it be possible to get rid of this allocation somehow? My knowledge of the runtime and compiler is a bit limited, but I'd think that it is possible.
As for a real use case - there's a few occurrences in the standard library that could be greatly simplified. For example, in encoding/json we'd remove ten lines of tricky code:

diff --git a/src/encoding/json/decode.go b/src/encoding/json/decode.go
index 2e734fb39e..fa09b85aab 100644
--- a/src/encoding/json/decode.go
+++ b/src/encoding/json/decode.go
@@ -1210,20 +1210,11 @@ func unquoteBytes(s []byte) (t []byte, ok bool) {
 	// then no unquoting is needed, so return a slice of the
 	// original bytes.
 	r := 0
-	for r < len(s) {
-		c := s[r]
-		if c == '\\' || c == '"' || c < ' ' {
-			break
-		}
-		if c < utf8.RuneSelf {
-			r++
-			continue
-		}
-		rr, size := utf8.DecodeRune(s[r:])
-		if rr == utf8.RuneError && size == 1 {
+	for i, c := range string(s) {
+		if c == '\\' || c == '"' || c < ' ' || c == utf8.RuneError {
 			break
 		}
-		r += size
+		r = i
 	}
 	if r == len(s) {
 		return s, true

However, that currently means a bad regression in speed and allocations:

name           old time/op    new time/op    delta
CodeDecoder-4    27.3ms ± 1%    31.2ms ± 1%   +14.16%  (p=0.002 n=6+6)

name           old speed      new speed      delta
CodeDecoder-4  71.1MB/s ± 1%  62.3MB/s ± 1%   -12.41%  (p=0.002 n=6+6)

name           old alloc/op   new alloc/op   delta
CodeDecoder-4    2.74MB ± 0%    5.13MB ± 0%   +87.28%  (p=0.002 n=6+6)

name           old allocs/op  new allocs/op  delta
CodeDecoder-4     77.5k ± 0%    184.3k ± 0%  +137.72%  (p=0.002 n=6+6)

I haven't investigated why my microbenchmark is faster when simpler, while json gets so much slower when made simpler.
Any input appreciated. cc @josharian@martisch@randall77@TocarIP

kq0g1dla

kq0g1dla1#

另一个类似的优化:https://go-review.googlesource.com/c/go/+/108985
也许有一种更好的方法可以遍历字节切片中的utf8字符,我遗漏了。希望不是这样,否则会有点尴尬 :)

gpnt7bae

gpnt7bae2#

这个问题之所以尚未像range []byte(string)那样进行优化,是因为在一般情况下很难证明在"for i, c := range string(s)"中,s在for循环内部没有被改变。在for循环内部计算过程中(即使在其他包或通过接口),单个字节指针的任何更改都可能改变s,从而导致结果与s在循环入口处被复制的情况不同。

然而,可能会有一些情况,通过非常保守的分析,它可能会触发这种情况。也许我们可以通过有一个遍历字节切片的range循环变体来解决这个问题(考虑到对字节切片的一些更改),并且通常不需要分配。类似于map迭代不迭代循环入口处的Map快照。

另一个问题是为什么BenchmarkManual即使不需要分配,运行速度也慢得多?

cbjzeqam

cbjzeqam3#

请注意,给出的两个版本的代码之间存在一个细微的差别:
c == utf8.RuneError 并不等同于 rr == utf8.RuneError && size == 1。

rlcwz9us

rlcwz9us4#

保守的分析对我来说听起来不错。我想象大多数重要的用例都不会涉及到指针、反射或其他任何魔法。
范围循环变体似乎很有趣。这种方法有什么缺点吗?我想象它基本上就像是编译器将惯用的代码“展开”成手动代码。
另一个问题是为什么BenchmarkManual即使不需要分配内存,运行速度也慢得多。
是的,但请注意,在encoding/json中,情况正好相反。所以这可能只是我的基准测试代码的问题。
c == utf8.RuneError与rr == utf8.RuneError && size == 1的检查不完全相同。
这是我想到的,但我不确定。我如何编写惯用的版本以表现得相同?
至少在encoding/json中,两者都不关心——两种代码都通过了所有测试。这并不是说它们等效或同样有效,但至少惯用的版本没有严重损坏。

pw136qt2

pw136qt25#

请注意,不仅仅是任何无法使用的"魔法",而且在编译期间未知的函数(甚至是由编译器插入的函数)和更改字节指针或字节切片的函数都不能使用,因为我们需要证明它们不能与我们正在迭代的切片进行别名。这将需要每个函数的信息 #25999

yhxst69z

yhxst69z6#

然而,正如你所看到的,它仍然会产生额外的分配。
分配到底在哪里?pprof应该告诉你。

nfzehxib

nfzehxib7#

string(Input) 没有转义,但该表达式被编译为
runtime.slicebytetostring ,它确实分配了内存(但并非总是如此,请参阅下文)。
现在进行一个小实验:

- var Input = bytes.Repeat([]byte("abcde"), 500)
+ var Input = bytes.Repeat([]byte("abcde"), 5)
BenchmarkIdiomatic-8 50000000  20.9 ns/op 0 B/op 0 allocs/op
BenchmarkManual-8    100000000 23.1 ns/op 0 B/op 0 allocs/op

问题在于非转义的临时缓冲区是在栈上分配的,并且具有非常有限的容量。
因此,如果正在转换的字符串不适合该缓冲区,它将被堆分配:

// The constant is known to the compiler.
// There is no fundamental theory behind this number.
const tmpStringBufSize = 32

type tmpBuf [tmpStringBufSize]byte

slicebytetostring 内部的某个地方:

// buf is tmpBuf
if buf != nil && len(b) <= len(buf) {
	p = unsafe.Pointer(buf)
} else {
	p = mallocgc(uintptr(len(b)), nil, false)
}

我认为在创建只读 []byte 切片视图时存在一些问题,用于临时非转义字符串。问题在于,如果有人持有该 []byte 并在此期间迭代该只读视图时对其进行变异,代码将表现出不同的行为,因为 string(s) 会创建一个副本。 (更新: #2205 )

6psbrbz9

6psbrbz98#

看起来没有人打算处理这个问题,所以我暂时将其从1.12版本中移除。我认为我们应该保持这个问题开放一段时间,看看是否有任何兴趣。

pnwntuvh

pnwntuvh9#

encoding/json周围闲逛时,我找到了手捻版本较慢的一个原因;r += size语句会干扰证明传递,因为r可能会作为有符号整数溢出变为负数,所以c := s[r]需要进行边界检查。这是不幸的,并且确实出现在CPU分析中。
我无法想象除了让编译器以特殊方式对待utf8.DecodeRune之外,还有其他方法可以消除这个边界检查。像if r += size; r < 0 { break }这样的技巧似乎也无法安抚证明;但无论如何,这都是用另一个分支替换边界检查。
我认为仍然应该有一种简单且性能优越的方法来遍历[]byte中的runes,既不损失性能,也不产生分配/复制。

相关问题