【Go】strings.Replace 与 bytes.Replace 调优

标准库中函数大多数情况下更通用，性能并非最好的，还是不能过于迷信标准库，最近又有了新发现，strings.Replace 这个函数自身的效率已经很好了，但是在特定情况下效率并不是最好的，分享一下我如何优化的吧。

我的服务中有部分代码使用 strings.Replace 把一个固定的字符串删除或者替换成另一个字符串，它们有几个特点：

  • 旧的字符串大于或等于新字符串 (len(old) >= len(new)
  • 源字符串的生命周期很短，替换后就不再使用替换前的字符串
  • 它们都比较大，往往超过 2k~4k

本博文中使用函数均在 go-extend 中，优化后的函数在 exbytes.Replace 中。

发现问题

近期使用 pprof 分析内存分配情况，发现 strings.Replace 排在第二，占 7.54%, 分析结果如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
go tool pprof allocs
File: xxx
Type: alloc_space
Time: Feb 1, 2019 at 9:53pm (CST)
Entering interactive mode (type "help" for commands, "o" for options)
(pprof) top
Showing nodes accounting for 617.29GB, 48.86% of 1263.51GB total
Dropped 778 nodes (cum <= 6.32GB)
Showing top 10 nodes out of 157
      flat  flat%   sum%        cum   cum%
  138.28GB 10.94% 10.94%   138.28GB 10.94%  logrus.(*Entry).WithFields
   95.27GB  7.54% 18.48%    95.27GB  7.54%  strings.Replace
   67.05GB  5.31% 23.79%   185.09GB 14.65%  v3.(*v3Adapter).parseEncrypt
   57.01GB  4.51% 28.30%    57.01GB  4.51%  bufio.NewWriterSize
   56.63GB  4.48% 32.78%    56.63GB  4.48%  bufio.NewReaderSize
   56.11GB  4.44% 37.23%    56.11GB  4.44%  net/url.unescape
   39.75GB  3.15% 40.37%    39.75GB  3.15%  regexp.(*bitState).reset
   36.11GB  2.86% 43.23%    38.05GB  3.01%  des3_and_base64.(*des3AndBase64).des3Decrypt
   36.01GB  2.85% 46.08%    36.01GB  2.85%  des3_and_base64.(*des3AndBase64).base64Decode
   35.08GB  2.78% 48.86%    35.08GB  2.78%  math/big.nat.make

标准库中最常用的函数，居然……，不可忍必须优化，先使用 list strings.Replace 看一下源码什么地方分配的内存。

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
(pprof) list strings.Replace
Total: 1.23TB
ROUTINE ======================== strings.Replace in /usr/local/go/src/strings/strings.go
   95.27GB    95.27GB (flat, cum)  7.54% of Total
         .          .    858:	} else if n < 0 || m < n {
         .          .    859:		n = m
         .          .    860:	}
         .          .    861:
         .          .    862:	// Apply replacements to buffer.
   47.46GB    47.46GB    863:	t := make([]byte, len(s)+n*(len(new)-len(old)))
         .          .    864:	w := 0
         .          .    865:	start := 0
         .          .    866:	for i := 0; i < n; i++ {
         .          .    867:		j := start
         .          .    868:		if len(old) == 0 {
         .          .    869:			if i > 0 {
         .          .    870:				_, wid := utf8.DecodeRuneInString(s[start:])
         .          .    871:				j += wid
         .          .    872:			}
         .          .    873:		} else {
         .          .    874:			j += Index(s[start:], old)
         .          .    875:		}
         .          .    876:		w += copy(t[w:], s[start:j])
         .          .    877:		w += copy(t[w:], new)
         .          .    878:		start = j + len(old)
         .          .    879:	}
         .          .    880:	w += copy(t[w:], s[start:])
   47.81GB    47.81GB    881:	return string(t[0:w])
         .          .    882:}

从源码发现首先创建了一个 buffer 来起到缓冲的效果，一次分配足够的内存，这个在之前 【Go】slice的一些使用技巧 里面有讲到，另外一个是 string(t[0:w]) 类型转换带来的内存拷贝，buffer 能够理解，但是类型转换这个不能忍，就像凭空多出来的一个数拷贝。

既然类型转换这里有点浪费空间，有没有办法可以零成本转换呢，那就使用 go-extend 这个包里面的 exbytes.ToString 方法把 []byte 转换成 string，这个函数可以零分配转换 []byte 到 string。 t 是一个临时变量，可以安全的被引用不用担心，一个小技巧节省一倍的内存分配，但是这样真的就够了吗？

我记得 bytes 标准库里面也有一个 bytes.Replace 方法，如果直接使用这种方法呢就不用重写一个 strings.Replace了，使用 go-extend 里面的两个魔术方法可以一行代码搞定上面的优化效果 s = exbytes.ToString(bytes.Replace(exstrings.UnsafeToBytes(s), []byte{' '}, []byte{''}, -1))， 虽然是一行代码搞定的，但是有点长，exstrings.UnsafeToBytes 方法可以极小的代价把 string 转成 bytes， 但是 s 不能是标量或常量字符串，必须是运行时产生的字符串否者可能导致程序奔溃。

这样确实减少了一倍的内存分配，即使只有 47.46GB 的分配也足以排到前十了，不满意这个结果，分析代码看看能不能更进一步减少内存分配吧。

分析代码

使用火焰图看看究竟什么函数在调用 strings.Replace 呢：

image-20190202184040233

这里主要是两个方法在使用，当然我记得还有几个地方有使用，看来不在火焰图中应该影响比较低 ，看一下代码吧（简化的代码不一定完全合理）：

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
// 第一部分
func (v2 *v2Adapter) parse(s string) (*AdRequest, error) {
	s = strings.Replace(s, " ", "", -1)
	requestJSON, err := v2.paramCrypto.Decrypt([]byte(s))
	if err != nil {
		return nil, err
	}

	request := v2.getDefaultAdRequest()
	if err := request.UnmarshalJSON(requestJSON); err != nil {
		return nil, err
	}
	return request, nil
}

// 第二部分
func (v3 *v3Adapter) parseEncrypt(s []byte) ([]byte, error) {
    ss := strings.Replace(string(s), " ", "", -1)
    requestJSON, err := v3.paramCrypto.Decrypt([]byte(ss))
	if err != nil {
		return nil, error
	}

	return requestJSON, nil
}

// 通过搜索找到的第三部分
type LogItems []string

func LogItemsToBytes(items []string, sep, newline string) []byte {
	for i := range items {
		items[i] = strings.Replace(items[i], sep, " ", -1)
	}
	str := strings.Replace(strings.Join(items, sep), newline, " ", -1)

	return []byte(str + newline)
}

通过分析我们发现前两个主要是为了删除一个字符串，第三个是为了把一个字符串替换为另一个字符串，并且源数据的生命周期很短暂，在执行替换之后就不再使用了，能不能原地替换字符串呢，原地替换的就会变成零分配了，尝试一下吧。

优化

先写一个函数简单实现原地替换，输入的 len(old) < len(new) 就直接调用 bytes.Replace 来实现就好了 。

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
func Replace(s, old, new []byte, n int) []byte {
	if n == 0 {
		return s
	}

	if len(old) < len(new) {
		return bytes.Replace(s, old, new, n)
	}

	if n < 0 {
		n = len(s)
	}

	var wid, i, j int
	for i, j = 0, 0; i < len(s) && j < n; j++ {
		wid = bytes.Index(s[i:], old)
		if wid < 0 {
			break
		}

		i += wid
		i += copy(s[i:], new)
		s = append(s[:i], s[i+len(old)-len(new):]...)
	}

	return s
}

写个性能测试看一下效果：

1
2
3
4
5
6
$ go test -bench="." -run=nil -benchmem
goos: darwin
goarch: amd64
pkg: github.com/thinkeridea/go-extend/exbytes/benchmark
BenchmarkReplace-8                	  500000	      3139 ns/op	     416 B/op	       1 allocs/op
BenchmarkBytesReplace-8           	 1000000	      2032 ns/op	     736 B/op	       2 allocs/op

使用这个新的函数和 bytes.Replace 对比，内存分配是少了，但是性能却下降了那么多，崩溃…. 啥情况呢，对比 bytes.Replace 的源码发现我这个代码里面 s = append(s[:i], s[i+len(old)-len(new):]...) 每次都会移动剩余的数据导致性能差异很大，可以使用 go test -bench="." -run=nil -benchmem -cpuprofile cpu.out -memprofile mem.out 的方式来生成 pprof 数据，然后分析具体有问题的地方。

找到问题就好了，移动 wid 之前的数据，这样每次移动就很少了，和 bytes.Replace 的原理类似。

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 Replace(s, old, new []byte, n int) []byte {
	if n == 0 {
		return s
	}

	if len(old) < len(new) {
		return bytes.Replace(s, old, new, n)
	}

	if n < 0 {
		n = len(s)
	}

	var wid, i, j, w int
	for i, j = 0, 0; i < len(s) && j < n; j++ {
		wid = bytes.Index(s[i:], old)
		if wid < 0 {
			break
		}

		w += copy(s[w:], s[i:i+wid])
		w += copy(s[w:], new)
		i += wid + len(old)
	}

	w += copy(s[w:], s[i:])
	return s[0:w]
}

在运行一下性能测试吧：

1
2
3
4
5
6
$ go test -bench="." -run=nil -benchmem
goos: darwin
goarch: amd64
pkg: github.com/thinkeridea/go-extend/exbytes/benchmark
BenchmarkReplace-8                	 1000000	      2149 ns/op	     416 B/op	       1 allocs/op
BenchmarkBytesReplace-8           	 1000000	      2231 ns/op	     736 B/op	       2 allocs/op

运行性能差不多，而且更好了，内存分配也减少，不是说是零分配吗，为啥有一次分配呢？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var replaces string
var replaceb []byte

func init() {
	replaces = strings.Repeat("A BC", 100)
	replaceb = bytes.Repeat([]byte("A BC"), 100)
}

func BenchmarkReplace(b *testing.B) {
	for i := 0; i < b.N; i++ {
		exbytes.Replace([]byte(replaces), []byte(" "), []byte(""), -1)
	}
}

func BenchmarkBytesReplace(b *testing.B) {
	for i := 0; i < b.N; i++ {
		bytes.Replace([]byte(replaces), []byte(" "), []byte(""), -1)
	}
}

可以看到使用了 []byte(replaces) 做了一次类型转换，因为优化的这个函数是原地替换，执行过一次之后后面就发现不用替换了，所以为了公平公正两个方法每次都转换一个类型产生一个新的内存地址，所以实际优化后是没有内存分配了。

之前说写一个优化 strings.Replace 函数，减少一次内存分配，这里也写一个这样函数，然后增加两个性能测试函数，对比一下效率 性能测试代码：

1
2
3
4
5
6
7
8
9
10
$ go test -bench="." -run=nil -benchmem
goos: darwin
goarch: amd64
pkg: github.com/thinkeridea/go-extend/exbytes/benchmark
BenchmarkReplace-8                	 1000000	      2149 ns/op	     416 B/op	       1 allocs/op
BenchmarkBytesReplace-8           	 1000000	      2231 ns/op	     736 B/op	       2 allocs/op
BenchmarkStringsReplace-8         	 1000000	      2260 ns/op	    1056 B/op	       3 allocs/op
BenchmarkUnsafeStringsReplace-8   	 1000000	      2522 ns/op	     736 B/op	       2 allocs/op
PASS
ok  	github.com/thinkeridea/go-extend/exbytes/benchmark	10.260s

运行效率上都相当，优化之后的 UnsafeStringsReplace 函数减少了一次内存分配只有一次，和 bytes.Replace 相当。

修改代码

有了优化版的 Replace 函数就替换到项目中吧：

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
// 第一部分
func (v2 *v2Adapter) parse(s string) (*AdRequest, error) {
	b := exbytes.Replace(exstrings.UnsafeToBytes(s), []byte(" "), []byte(""), -1)
	requestJSON, err := v2.paramCrypto.Decrypt(b)
	if err != nil {
		return nil, err
	}
	request := v2.getDefaultAdRequest()
	if err := request.UnmarshalJSON(requestJSON); err != nil {
		return nil, err
	}

	return request, nil
}

// 第二部分
func (v3 *v3Adapter) parseEncrypt(s []byte) ([]byte, error) {
	s = exbytes.Replace(s, []byte(" "), []byte(""), -1)
	requestJSON, err := v3.paramCrypto.Decrypt(s)
	if err != nil {
		return nil, err
	}

	return requestJSON, nil
}

// 第三部分
type LogItems []string

func LogItemsToBytes(items []string, sep, newline string) []byte {
	for i := range items {
		items[i] = exbytes.ToString(exbytes.Replace(exstrings.UnsafeToBytes(items[i]), []byte(sep), []byte(" "), -1))
	}
	b := exbytes.Replace(exstrings.UnsafeToBytes(strings.Join(items, sep)), []byte(newline), []byte(" "), -1)
	return append(b, newline...)
}

上线后性能分析

1
2
3
4
5
6
7
8
9
10
11
12
$ go tool pprof allocs2
File: xx
Type: alloc_space
Time: Feb 2, 2019 at 5:33pm (CST)
Entering interactive mode (type "help" for commands, "o" for options)
(pprof) top exbytes.Replace
Focus expression matched no samples
Active filters:
   focus=exbytes.Replace
Showing nodes accounting for 0, 0% of 864.21GB total
      flat  flat%   sum%        cum   cum%
(pprof)

居然在 allocs 上居然找不到了，确实是零分配。

优化前 profile ：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
$ go tool pprof profile
File: xx
Type: cpu
Time: Feb 1, 2019 at 9:54pm (CST)
Duration: 30.08s, Total samples = 12.23s (40.65%)
Entering interactive mode (type "help" for commands, "o" for options)
(pprof) top strings.Replace
Active filters:
   focus=strings.Replace
Showing nodes accounting for 0.08s, 0.65% of 12.23s total
Showing top 10 nodes out of 27
      flat  flat%   sum%        cum   cum%
     0.03s  0.25%  0.25%      0.08s  0.65%  strings.Replace
     0.02s  0.16%  0.41%      0.02s  0.16%  countbody
     0.01s 0.082%  0.49%      0.01s 0.082%  indexbytebody
     0.01s 0.082%  0.57%      0.01s 0.082%  memeqbody
     0.01s 0.082%  0.65%      0.01s 0.082%  runtime.scanobject

优化后 profile ：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
$ go tool pprof profile2
File: xx
Type: cpu
Time: Feb 2, 2019 at 5:33pm (CST)
Duration: 30.16s, Total samples = 14.68s (48.68%)
Entering interactive mode (type "help" for commands, "o" for options)
(pprof) top exbytes.Replace
Active filters:
   focus=exbytes.Replace
Showing nodes accounting for 0.06s, 0.41% of 14.68s total
Showing top 10 nodes out of 18
      flat  flat%   sum%        cum   cum%
     0.03s   0.2%   0.2%      0.03s   0.2%  indexbytebody
     0.02s  0.14%  0.34%      0.05s  0.34%  bytes.Index
     0.01s 0.068%  0.41%      0.06s  0.41%  github.com/thinkeridea/go-extend/exbytes.Replace

通过 profile 来分配发现性能也有一定的提升，本次 strings.Replace 和 bytes.Replace 优化圆满结束。

本博文中使用函数均在 go-extend 中，优化后的函数在 exbytes.Replace 中。

赏

谢谢你请我吃糖果

支付宝
微信

扫一扫，分享到微信

微信分享二维码

tag: