go cmd/compile: consider to add move-like optimization for some string< ->[]byte operations

h79rfbju  于 5个月前  发布在  Go
关注(0)|答案(9)|浏览(56)

问题

1. 构建字符串

在Go中，高效地构建字符串并不容易。与strings.Builder文档所说的不同，它并不总是比直接使用[]byte并在最后进行转换时额外分配和复制更有效。我们不能盲目地用strings.Builder替换所有地方，因为对于某些用例(需要在构建字符串时写入许多小块),它的开销是不可忽略的。快速一看，我们并不能真正让strings.Builder像我们希望的那样快：即使它不进行复制检查，我们直接调用append,一些算法仍然使用复制+按索引写入来实现快速。例如，strings.Replacer特殊化中的一些代码就使用了这种方法，而不是strings.Builder。这只是额外分配了一次，但平均而言，CPU上的速度提高了约20%。

2. 重用[]byte算法

当你编写一个返回[]byte的代码时，你可能想要提供一个返回字符串的第二个函数。对于大多数情况，你可能会从这样的代码开始：

func EncodeString(v value) string {
  return string(Encode(v))
}

这将添加额外的数据复制和分配。更不用说，如果Encode返回一个新的分配(并且只在返回中“转义”),就没有必要复制它。我们可以将它(所有权)移动(转移)到返回值中。换句话说，我们可以使用slicebytetostringtmp代替slicebytetostring。
由于Encode()返回值没有其他引用指向它，所以这是一个临时变量，我们可以轻松地将其移动。这将使上面的代码非常高效。不仅它将避免额外的分配，还将受益于这样一个事实：由于Encode()是在[]byte而不是某种跨类型方式上实现的，因此在这两种情况下的性能差异为20-30%。这种跨类型方式通常涉及传递两个[]byte给append(对于[]byte情况)以及一个布尔标志以返回字符串而不是。另一种方法是传递两个strings.Builder和bytes.Buffer,这样函数就会将数据写入由调用者提供的适当存储中。如上所述，由于编译器会对这种情况进行优化，因此这样做并不如我们可以采用另一种方法那样高效。

3. 像append-like API对字符串不好

目前，避免冗余分配的最佳技巧之一是使用append-like API,其中调用者传递一个可以在稍后重用的切片。这对字节很好用，但对字符串不太好用。
通过在这个请求中请求的优化，我们可以这样做：

buf := make([]byte, 0, size)
buf = appendSomething(buf, data)
// If appendSomething makes buf escape only to its return value,
// then we can try to prove that buf is locally created slice that can be
// converted to a string without copying.
return string(buf)

优化

当将一个 []byte 转换为一个 string 时，如果证明在此转换之后没有人引用原始切片，则可以使用 []byte 内存初始化字符串(我们可以使用类似于 slicebytetostringmove 的操作来使其更容易分离语义)。
以下是何时可以这样做的一些示例：

  1. 一个函数创建了一个本地分配的切片 b 。然后该切片作为 string(b) 返回。
  2. 一个由传递给 string 转换的临时值返回的函数，例如 string(f()) 。我们需要知道 f() 确实返回了一个新的内存分配，因为我们不应该移动已重用或全局内存。这将需要额外的功能位。
    (1)有助于解决第一个问题。我们可以在 []byte 内构建字符串并将其作为字符串返回而不会产生额外的开销。
    (2)有助于解决第二个问题。我们可以利用 string(f()) 以重用[]byte相关的例程。
    这些两种情况解决了上述概述的问题，但可能还需要额外小心区分函数参数“泄漏”的情况：泄漏到返回值是可以接受的append API,但泄漏到全局内存是不可以的。为了简单起见，我会避免处理(3)问题，但也许有人有一个很好的主意可以在付出不多的努力的情况下解决这个问题。
    我相信相反的做法可能不是那么有用，但有可能通过这个想法消除一些字符串到[]byte的复制。虽然我会要求一些使用案例来说明这一点是有用的。
    由于这看起来不像是一个微不足道的改变，所以在超越最小原型之前讨论一下似乎是公平的。
    如果我们有一个像 unsafe.BytesToString(b) 这样的内在函数(别介意命名),编译器会检查(是否可以执行这种移动)。如果它能证明它是有效的，它会插入一个无分配转换。否则，它会给出一个编译错误。
    唯一的好处可能是它可以让编译器更容易地仅对其被要求进行分析的地方进行这种分析。

手动优化

虽然可以这样做：

return unsafeutil.BytesAsString(b)

但这会使代码相当脆弱，并要求不安全的使用。它也可能会在 b 以某种不可预测的方式开始逃逸，或者我们开始使用一个 sync.Pool 用于字节，因此 b 可以共享。

额外：使用 strings.Builder 重写 strings.Replacer

@@ -524,18 +524,21 @@ func (r *byteStringReplacer) Replace(s string) string {
        if !anyChanges {
                return s
        }
-       buf := make([]byte, newSize)
-       j := 0
+       var buf Builder
+       buf.Grow(newSize)
+       from := 0
        for i := 0; i < len(s); i++ {
-               b := s[i]
-               if r.replacements[b] != nil {
-                       j += copy(buf[j:], r.replacements[b])
-               } else {
-                       buf[j] = b
-                       j++
+               rep := r.replacements[s[i]]
+               if rep != nil {
+                       buf.WriteString(s[from:i])
+                       buf.Write(rep)
+                       from = i + 1
                }
        }
-       return string(buf)
+       if from != len(s) {
+               buf.WriteString(s[from:])
+       }
+       return buf.String()
 }

基准测试：

func BenchmarkReplacer(b *testing.B) {
	// smallString is exactly 32 bytes long.
	const smallString = "Hello  world  strings Rep lacer "

	type testCase struct {
		input string
		from []string
		to []string
	}

	tests := []testCase{
		{
			input: smallString,
			from: []string{"$"},
			to: []string{""},
		},
		{
			input: smallString,
			from: []string{"R"},
			to: []string{""},
		},
		{
			input: smallString,
			from: []string{" "},
			to: []string{""},
		},
		{
			input: smallString,
			from: []string{" ", "l", "s"},
			to: []string{"", "", ""},
		},
		{
			input: smallString,
			from: []string{" ", "l", "s", "e", "o"},
			to: []string{"", "", "", "", ""},
		},
	}

	var allTests []testCase
	for i := range tests {
		testX4 := tests[i]
		testX4.input = strings.Repeat(testX4.input, 4)
		testX16 := tests[i]
		testX16.input = strings.Repeat(testX16.input, 16)
		testX96 := tests[i]
		testX96.input = strings.Repeat(testX96.input, 96)
		testX512 := tests[i]
		testX512.input = strings.Repeat(testX512.input, 512)
		allTests = append(allTests, tests[i], testX4, testX16, testX96, testX512)
	}

	for i := range allTests {
		test := allTests[i]
		var pairs []string
		numMatches := 0
		for j := range test.from {
			pairs = append(pairs, test.from[j], test.to[j])
			if matches := strings.Count(test.input, string(test.from[j])); matches != -1 {
				numMatches += matches
			}
		}
		replacer := strings.NewReplacer(pairs...)
		matchesSuffix := "Matched0%"
		if numMatches != 0 {
			percentage := int((float64(numMatches) / float64(len(test.input))) * 100)
			matchesSuffix = fmt.Sprintf("Matched%d%%", percentage)
		}
		key := fmt.Sprintf("Len%d%s", len(test.input), matchesSuffix)
		b.Run(key, func(b *testing.B) {
			for i := 0; i < b.N; i++ {
				replacer.Replace(test.input)
			}
		})
	}
}

结果(TL;DR - 更少的分配，较慢的执行时间):

name                           old time/op    new time/op    delta
Replacer/Len32Matched0%-8        20.5ns ± 1%    20.4ns ± 0%     ~     (p=0.183 n=5+5)
Replacer/Len128Matched0%-8       27.0ns ± 0%    27.5ns ± 0%   +1.88%  (p=0.008 n=5+5)
Replacer/Len512Matched0%-8       43.3ns ± 1%    43.3ns ± 1%     ~     (p=1.000 n=5+5)
Replacer/Len3072Matched0%-8       152ns ± 1%     156ns ± 0%   +2.93%  (p=0.008 n=5+5)
Replacer/Len16384Matched0%-8      650ns ± 0%     705ns ± 0%   +8.51%  (p=0.008 n=5+5)
Replacer/Len32Matched3%-8         188ns ± 0%     143ns ± 1%  -24.16%  (p=0.008 n=5+5)
Replacer/Len128Matched3%-8        499ns ± 0%     360ns ± 2%  -27.88%  (p=0.008 n=5+5)
Replacer/Len512Matched3%-8       1.47µs ± 0%    1.40µs ± 0%   -4.52%  (p=0.008 n=5+5)
Replacer/Len3072Matched3%-8      9.33µs ± 0%    7.08µs ± 1%  -24.10%  (p=0.008 n=5+5)
Replacer/Len16384Matched3%-8     50.3µs ± 0%    40.8µs ± 1%  -19.06%  (p=0.008 n=5+5)
Replacer/Len32Matched21%-8        191ns ± 1%     208ns ± 1%   +8.86%  (p=0.008 n=5+5)
Replacer/Len128Matched21%-8       531ns ± 0%     694ns ± 1%  +30.72%  (p=0.008 n=5+5)
Replacer/Len512Matched21%-8      1.76µs ± 1%    2.55µs ± 2%  +44.46%  (p=0.008 n=5+5)
Replacer/Len3072Matched21%-8     10.1µs ± 0%    14.8µs ± 1%  +46.53%  (p=0.008 n=5+5)
Replacer/Len16384Matched21%-8    51.1µs ± 1%    77.5µs ± 1%  +51.88%  (p=0.008 n=5+5)
Replacer/Len32Matched40%-8        248ns ± 1%     305ns ± 1%  +23.17%  (p=0.008 n=5+5)
Replacer/Len128Matched40%-8       661ns ± 0%     981ns ± 1%  +48.40%  (p=0.008 n=5+5)
Replacer/Len512Matched40%-8      2.22µs ± 1%    3.59µs ± 1%  +61.64%  (p=0.008 n=5+5)
Replacer/Len3072Matched40%-8     12.7µs ± 0%    21.2µs ± 1%  +66.85%  (p=0.008 n=5+5)
Replacer/Len16384Matched40%-8    64.8µs ± 0%   112.8µs ± 1%  +74.08%  (p=0.008 n=5+5)
Replacer/Len32Matched56%-8        287ns ± 1%     351ns ± 1%  +22.20%  (p=0.008 n=5+5)
Replacer/Len128Matched56%-8       758ns ± 0%    1208ns ± 1%  +59.49%  (p=0.008 n=5+5)
Replacer/Len512Matched56%-8      2.49µs ± 0%    4.39µs ± 1%  +76.53%  (p=0.008 n=5+5)
Replacer/Len3072Matched56%-8     14.3µs ± 1%    26.1µs ± 1%  +82.71%  (p=0.008 n=5+5)
Replacer/Len16384Matched56%-8    75.2µs ± 0%   138.4µs ± 1%  +84.06%  (p=0.008 n=5+5)
[Geo mean]                       1.37µs         1.68µs       +22.67%

name                           old alloc/op   new alloc/op   delta
Replacer/Len32Matched0%-8         0.00B          0.00B          ~     (all equal)
Replacer/Len128Matched0%-8        0.00B          0.00B          ~     (all equal)
Replacer/Len512Matched0%-8        0.00B          0.00B          ~     (all equal)
Replacer/Len3072Matched0%-8       0.00B          0.00B          ~     (all equal)
Replacer/Len16384Matched0%-8      0.00B          0.00B          ~     (all equal)
Replacer/Len32Matched3%-8         64.0B ± 0%     32.0B ± 0%  -50.00%  (p=0.008 n=5+5)
Replacer/Len128Matched3%-8         256B ± 0%      128B ± 0%  -50.00%  (p=0.008 n=5+5)
Replacer/Len512Matched3%-8       1.02kB ± 0%    0.51kB ± 0%  -50.00%  (p=0.008 n=5+5)
Replacer/Len3072Matched3%-8      6.14kB ± 0%    3.07kB ± 0%  -50.00%  (p=0.008 n=5+5)
Replacer/Len16384Matched3%-8     32.8kB ± 0%    16.4kB ± 0%  -50.00%  (p=0.008 n=5+5)
Replacer/Len32Matched21%-8        64.0B ± 0%     32.0B ± 0%  -50.00%  (p=0.008 n=5+5)
Replacer/Len128Matched21%-8        224B ± 0%      112B ± 0%  -50.00%  (p=0.008 n=5+5)
Replacer/Len512Matched21%-8        832B ± 0%      416B ± 0%  -50.00%  (p=0.008 n=5+5)
Replacer/Len3072Matched21%-8     5.38kB ± 0%    2.69kB ± 0%  -50.00%  (p=0.008 n=5+5)
Replacer/Len16384Matched21%-8    27.1kB ± 0%    13.6kB ± 0%  -50.00%  (p=0.008 n=5+5)
Replacer/Len32Matched40%-8        48.0B ± 0%     24.0B ± 0%  -50.00%  (p=0.008 n=5+5)
Replacer/Len128Matched40%-8        160B ± 0%       80B ± 0%  -50.00%  (p=0.008 n=5+5)
Replacer/Len512Matched40%-8        640B ± 0%      320B ± 0%  -50.00%  (p=0.008 n=5+5)
Replacer/Len3072Matched40%-8     4.10kB ± 0%    2.05kB ± 0%  -50.00%  (p=0.008 n=5+5)
Replacer/Len16384Matched40%-8    19.5kB ± 0%     9.7kB ± 0%  -50.00%  (p=0.008 n=5+5)
Replacer/Len32Matched56%-8        32.0B ± 0%     16.0B ± 0%  -50.00%  (p=0.008 n=5+5)
Replacer/Len128Matched56%-8        128B ± 0%       64B ± 0%  -50.00%  (p=0.008 n=5+5)
Replacer/Len512Matched56%-8        448B ± 0%      224B ± 0%  -50.00%  (p=0.008 n=5+5)
Replacer/Len3072Matched56%-8     2.82kB ± 0%    1.41kB ± 0%  -50.00%  (p=0.008 n=5+5)
Replacer/Len16384Matched56%-8    16.4kB ± 0%     8.2kB ± 0%  -50.00%  (p=0.008 n=5+5)
[Geo mean]                         921B           461B       -50.00%

name                           old allocs/op  new allocs/op  delta
Replacer/Len32Matched0%-8          0.00           0.00          ~     (all equal)
Replacer/Len128Matched0%-8         0.00           0.00          ~     (all equal)
Replacer/Len512Matched0%-8         0.00           0.00          ~     (all equal)
Replacer/Len3072Matched0%-8        0.00           0.00          ~     (all equal)
Replacer/Len16384Matched0%-8       0.00           0.00          ~     (all equal)
Replacer/Len32Matched3%-8          2.00 ± 0%      1.00 ± 0%  -50.00%  (p=0.008 n=5+5)
Replacer/Len128Matched3%-8         2.00 ± 0%      1.00 ± 0%  -50.00%  (p=0.008 n=5+5)
Replacer/Len512Matched3%-8         2.00 ± 0%      1.00 ± 0%  -50.00%  (p=0.008 n=5+5)
Replacer/Len3072Matched3%-8        2.00 ± 0%      1.00 ± 0%  -50.00%  (p=0.008 n=5+5)
Replacer/Len16384Matched3%-8       2.00 ± 0%      1.00 ± 0%  -50.00%  (p=0.008 n=5+5)
Replacer/Len32Matched21%-8         2.00 ± 0%      1.00 ± 0%  -50.00%  (p=0.008 n=5+5)
Replacer/Len128Matched21%-8        2.00 ± 0%      1.00 ± 0%  -50.00%  (p=0.008 n=5+5)
Replacer/Len512Matched21%-8        2.00 ± 0%      1.00 ± 0%  -50.00%  (p=0.008 n=5+5)
Replacer/Len3072Matched21%-8       2.00 ± 0%      1.00 ± 0%  -50.00%  (p=0.008 n=5+5)
Replacer/Len16384Matched21%-8      2.00 ± 0%      1.00 ± 0%  -50.00%  (p=0.008 n=5+5)
Replacer/Len32Matched40%-8         2.00 ± 0%      1.00 ± 0%  -50.00%  (p=0.008 n=5+5)
Replacer/Len128Matched40%-8        2.00 ± 0%      1.00 ± 0%  -50.00%  (p=0.008 n=5+5)
Replacer/Len512Matched40%-8        2.00 ± 0%      1.00 ± 0%  -50.00%  (p=0.008 n=5+5)
Replacer/Len3072Matched40%-8       2.00 ± 0%      1.00 ± 0%  -50.00%  (p=0.008 n=5+5)
Replacer/Len16384Matched40%-8      2.00 ± 0%      1.00 ± 0%  -50.00%  (p=0.008 n=5+5)
Replacer/Len32Matched56%-8         2.00 ± 0%      1.00 ± 0%  -50.00%  (p=0.008 n=5+5)
Replacer/Len128Matched56%-8        2.00 ± 0%      1.00 ± 0%  -50.00%  (p=0.008 n=5+5)
Replacer/Len512Matched56%-8        2.00 ± 0%      1.00 ± 0%  -50.00%  (p=0.008 n=5+5)
Replacer/Len3072Matched56%-8       2.00 ± 0%      1.00 ± 0%  -50.00%  (p=0.008 n=5+5)
Replacer/Len16384Matched56%-8      2.00 ± 0%      1.00 ± 0%  -50.00%  (p=0.008 n=5+5)
[Geo mean]                         2.00           1.00       -50.00%

字符串到 []byte 的情况

我没有足够的信息和统计数据来支持这种情况，但我仍然可以提供一些示例。
首先，我们需要一个 stringtoslicebytetmp 函数来使其成为可能。
一些明显适用的情况(这个列表是不完整的):

  • []byte(x + y)
  • append([]byte(s), data...)

如果我们利用关于新分配数据的这种知识，一些表达式如上所示可以避免过度的字符串到字节的分配：

// If we know that f() always returns a fresh string (for example, it uses `string(b)` for its result)
// Also let's suppose that w is io.Writer that doesn't have WriteString method.
w.Write([]byte(f()))
go

9条答案

按热度按时间
oogrdqng

oogrdqng1#

我认为，如果我们能创建一个通用的传递，它可以回答这个问题：这个内存片段(字节切片后备数组)泄漏了吗？还是说，在这一点上，这是唯一的活跃引用？那么，我们可以添加一个通用的转换，将 slicebytetostring 转换为 slicebytetostringtmp。然后，这也可以用于字符串到 []byte 的优化。

另一种使用该传递的方法是，允许在 b 是本地唯一引用时调用 f(string(b))。因为在 f 使用它的时候，没有其他东西可以改变它。这也要求有一个能够证明字符串没有泄漏的传递。

赞(0）分享  回复(0）举报  5个月前
uttx8gqw

uttx8gqw2#

感谢您提供的详细问题。我将把这个问题标记为功能请求。

赞(0）分享  回复(0）举报  5个月前
wi3ka0sx

wi3ka0sx3#

CC @aclements@dr2chase@cherrymui@thanm
赞(0）分享  回复(0）举报  5个月前
vulvrdjw

vulvrdjw4#

是的，感谢你非常详细的撰写。
这似乎与#2205.@quasilyte非常相关，如果不是相同的，你能看一下这个问题吗？看看你认为这些是否应该合并？

赞(0）分享  回复(0）举报  5个月前
v1uwarro

v1uwarro5#

这似乎在某种程度上是相关的，因为这两个问题都想避免过度分配。
我看到了许多类似的问题，它们描述了各种情况下的转换。
也许可以定义一些通用规则，可以应用，或者仍然最好将这些视为一些临时优化，严重依赖上下文。
我认为当我们的缓冲区足够小的时候(我相信它是分配在栈上的),我们至少部分解决了传递转换的问题。
返回转换后的值是一个目前无法优化的情况。
如果可能的话，我会很高兴能够手动优化这段代码，避免这个显式的 return string(bytes) ,但我们当前的机制并不总是有效(实际上可能会引入性能下降，如 strings.Replacer 情况所述)。
如果编译器能识别到某种模式，就可以调整代码以触发这种优化。目前我还没有意识到这样的方法(如果存在这样的方法，除了不安全的 []byte -> string 转换，我会很高兴学习它)。

赞(0）分享  回复(0）举报  5个月前
ecr0jaav

ecr0jaav6#

简单的示例(已在Go 1.17.8/1.18中测试过):
pkg.go

package pkg

// ToLower converts ascii string s to lower-case
func ToLower(s string) string {
	if s == "" {
		return ""
	}
	buf := make([]byte, len(s))

	for i := 0; i < len(s); i++ {
		c := s[i]
		if 'A' <= c && c <= 'Z' {
			c |= 32
		}
		buf[i] = c
	}
	return string(buf)
}

pkg_test.go

package pkg

import "testing"

func BenchmarkToLower(b *testing.B) {
	str := "SomE StrInG"
	want := "some string"
	var res string

	for i := 0; i < b.N; i++ {
		res = ToLower(str)
	}
	if res != want {
		b.Fatal("ToLower error")
	}
}

go test -v -bench ToLower -benchmem -count=3 打印

BenchmarkToLower-4      18710726                66.86 ns/op           32 B/op          2 allocs/op
BenchmarkToLower-4      17420910                65.57 ns/op           32 B/op          2 allocs/op
BenchmarkToLower-4      17085405                63.16 ns/op           32 B/op          2 allocs/op

在 return string(buf) 中存在冗余分配和复制。对我来说，这看起来太简单了，以至于我惊讶于Go编译器无法处理这个问题。

赞(0）分享  回复(0）举报  5个月前
ztyzrc3y

ztyzrc3y7#

这是一个使用strings.Builder的用例：

func ToLower(s string) string {
	if s == "" {
		return ""
	}
	var b strings.Builder
	b.Grow(len(s))

	for i := 0; i < len(s); i++ {
		c := s[i]
		if 'A' <= c && c <= 'Z' {
			c |= 32
		}
		b.WriteByte(c)
	}
	return b.String()
}
赞(0）分享  回复(0）举报  5个月前
kpbpu008

kpbpu0088#

builder.go 有 126 行代码，一个结构体类型，12 个函数，它的 String() 方法是 *(*string)(unsafe.Pointer(&b.buf))。我们只需要在原始的 ToLower() 中使用 *(*string)(unsafe.Pointer(&buf)) 就可以达到相同的效果。但是问题是为什么编译器不能检测到这样的简单情况？

赞(0）分享  回复(0）举报  5个月前
eit6fx6z

eit6fx6z9#

你是对的，编译器可能能检测到这种情况。
buf 没有转义，而 return string(buf) 确保在字符串转换后没有人写入 buf 。

赞(0）分享  回复(0）举报  5个月前
我来回答

相关问题

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新问答

    更多
    • 蜀ICP备13028337号-1 大数据知识库 https://www.saoniuhuo.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com