在合适的时机使用字符串池(string interning)

前言

stringGolang

需要了解的词

string interningunsafe.PointerGolangunsafe.PointerGolang

选择合适的字符串拼接方式

fmt.Sprintf+strings.Joinbytes.Bufferstrings.Builder

实现一下单元测试：

package test

import (
   "bytes"
   "fmt"
   "strings"
   "testing"
)

// fmt.Printf
func BenchmarkFmtSprintfMore(b *testing.B) {
   var s string
   for i := 0; i < b.N; i++ {
      s += fmt.Sprintf("%s%s", "hello", "world")
   }
   fmt.Errorf(s)
}

// 加号 拼接
func BenchmarkAddMore(b *testing.B) {
   var s string
   for i := 0; i < b.N; i++ {
      s += "hello" + "world"
   }
   fmt.Errorf(s)
}

// strings.Join
func BenchmarkStringsJoinMore(b *testing.B) {
   var s string
   for i := 0; i < b.N; i++ {
      s += strings.Join([]string{"hello", "world"}, "")
   }
   fmt.Errorf(s)
}

// bytes.Buffer
func BenchmarkBufferMore(b *testing.B) {
   buffer := bytes.Buffer{}
   for i := 0; i < b.N; i++ {
      buffer.WriteString("hello")
      buffer.WriteString("world")
   }
   fmt.Errorf(buffer.String())
}

// strings.Builder
func BenchmarkStringBuilderMore(b *testing.B) {
   builder := strings.Builder{}
   for i := 0; i < b.N; i++ {
      builder.WriteString("hello")
      builder.WriteString("world")
   }
   fmt.Errorf(builder.String())
}

运行结果：

$ go test -bench="Concat$" -benchmem .
goos: darwin
goarch: amd64
pkg: example
BenchmarkPlusConcat-8         19      56 ms/op   530 MB/op   10026 allocs/op
BenchmarkSprintfConcat-8      10     112 ms/op   835 MB/op   37435 allocs/op
BenchmarkBuilderConcat-8    8901    0.13 ms/op   0.5 MB/op      23 allocs/op
BenchmarkBufferConcat-8     8130    0.14 ms/op   0.4 MB/op      13 allocs/op
BenchmarkByteConcat-8       8984    0.12 ms/op   0.6 MB/op      24 allocs/op
BenchmarkPreByteConcat-8   17379    0.07 ms/op   0.2 MB/op       2 allocs/op
PASS
ok      example 8.627s

+fmt.Sprintffmt.Sprintf

strings.Builderbytes.Buffer[]bytepreByteConcat

fmt.Sprintf+strings.Join

bytes.Bufferstrings.Builderstrings.Builder

A Builder is used to efficiently build a string using Write methods. It minimizes memory copying.

string.BuilderGrow

func builderConcat(n int, str string) string {
	var builder strings.Builder
	builder.Grow(n * len(str))
	for i := 0; i < n; i++ {
		builder.WriteString(str)
	}
	return builder.String()
}

使用了 Grow 优化后的版本的 benchmark 结果如下：

BenchmarkBuilderConcat-8   16855    0.07 ns/op   0.1 MB/op       1 allocs/op
BenchmarkPreByteConcat-8   17379    0.07 ms/op   0.2 MB/op       2 allocs/op

[]byte[]byte

strings.Builder+

10 + 2 * 10 + 3 * 10 + ... + 10000 * 10 byte = 500 MB

strings.Builderbytes.Buffer[]bytebuilder.Cap()strings.Builder

func TestBuilderConcat(t *testing.T) {
   var str = "1"
   var builder strings.Builder
   cap := 0
   for i := 0; i < 10000; i++ {
      if builder.Cap() != cap {
         fmt.Print(builder.Cap(), " ")
         cap = builder.Cap()
      }
      builder.WriteString(str)
   }
}

func TestBufferConcat(t *testing.T) {

   var str = "1"
   buffer := bytes.Buffer{}
   cap := 0
   for i := 0; i < 10000; i++ {
      if buffer.Cap() != cap {
         fmt.Print(buffer.Cap(), " ")
         cap = buffer.Cap()
      }
      buffer.WriteString(str)
   }
}

运行结果如下：

➜  test go test -run="TestBufferConcat" . -v
=== RUN   TestBufferConcat
64 129 259 519 1039 2079 4159 8319 16639 --- PASS: TestBufferConcat (0.00s)
PASS
ok      StudyProject/src/second/test    0.321s
➜  test go test -run="TestBuilderConcat" . -v
=== RUN   TestBuilderConcat
8 16 32 64 128 256 512 896 1408 2048 3072 4096 5376 6912 9472 12288 --- PASS: TestBuilderConcat (0.00s)
PASS
ok      StudyProject/src/second/test    0.235s

bytes.Bufferstrings.Builder

比较 strings.Builder 和 bytes.Buffer

strings.Builderbytes.Buffer[]bytestrings.Builderbytes.Bufferbytes.Bufferstrings.Builder[]byte

bytes.Buffer

// To build strings more efficiently, see the strings.Builder type.
func (b *Buffer) String() string {
	if b == nil {
		// Special case, useful in debugging.
		return "<nil>"
	}
	return string(b.buf[b.off:])
}

strings.Builder

// String returns the accumulated string.
func (b *Builder) String() string {
	return *(*string)(unsafe.Pointer(&b.buf))
}

bytes.Buffer

To build strings more efficiently, see the strings.Builder type.

阶段总结

Growstring.Builder+strings.Builderbytes.Buffer[]bytestrings.Builderbytes.Bufferbytes.Bufferstrings.Builder[]byte

避免重复的字符串到字节切片的转换

golangslice

bytestringbytestringstring

比如，编译器会识别如下临时场景：

m[string(b)]mapmapkeystringbstring

编译器为这种情况实现特定的优化：

var m mapstringstring

v, ok := mstring(bytes)

如上面这样写，编译器会避免将字节切片转换为字符串到 map 中查找，这是非常特定的细节，如果你像下面这样写，这个优化就会失效：

key := string(bytes)

val, ok := mkey

字符串拼接，如<" + "string(b)" + ">
字符串比较： string(b) == "foo"

由于只是临时把byte切片转换成string，也就避免了因byte切片内容修改而导致string数据变化的问题，所以此时可以不必拷贝内存

但反过来并不是这样的，string转成byte切片需要一次内存拷贝的动作，其过程如下：

string

sliceBenchmark

// BenchmarkBad 
//  @param b *testing.B 
//  @author: Kevineluo 2022-11-06 08:43:48 
// BenchmarkBad-16    	540784207	         2.166 ns/op	       0 B/op	       0 allocs/op
func BenchmarkBad(b *testing.B) {
	for i := 0; i < b.N; i++ {
		doNothing([]byte("Hello world"))
	}
}

// BenchmarkGood 
//  @param b *testing.B 
//  @author: Kevineluo 2022-11-06 08:43:37 
// BenchmarkGood-16    	778790289	         1.591 ns/op	       0 B/op	       0 allocs/op
func BenchmarkGood(b *testing.B) {
	bytes := []byte("Hello world")
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		doNothing(bytes)
	}
}

func doNothing(input []byte) {
}

字符串和字节切片的更高效互转

stringbyte sliceaggressiveunsafe.Pointer

/*
type StringHeader struct { // reflect.StringHeader
    Data uintptr
    Len  int
}
type SliceHeader struct { // reflect.SliceHeader
    Data uintptr
    Len  int
    Cap  int
}
*/

// NOTE：注意之后不要修改 string, 它们共享了底层的Data
func str2bytes(s string) []byte {
   x := (*[2]uintptr)(unsafe.Pointer(&s))
   b := [3]uintptr{x[0], x[1], x[1]}
   return *(*[]byte)(unsafe.Pointer(&b))
}

func bytes2str(b []byte) string {
   return *(*string)(unsafe.Pointer(&b))
}

str2bytesstringDataLenCapLen*[]byte

bytes2strbyte sliceDataLen*string

在合适的时机使用字符串池(string interning)

string interning

golangstring

type stringStruct struct {
  str unsafe.Pointer
  len int
}

结构很简单：

str: 字符串的首地址
len: 字符串的长度

字符串生成时，会先构建stringStruct对象，再转成string；转换的源码如下：

// go:nosplit
func gostringnocopy(str *byte) string {
  // 先构造stringStruct
  ss := stringStruct{str: unsafe.Pointer(str), len: findnull(str)}
  // 再将stringStruct转成string
  s := *(*string)(unsafe.Pointer(&ss))
  return s
}

golangconst

package main

import (
    "fmt"
    "reflect"
    "unsafe"
)

// stringptr 返回指向字符串底层数据的指针
func stringptr(s string) uintptr {
    return (*reflect.StringHeader)(unsafe.Pointer(&s)).Data
}

func main() {
    s1 := "1234"
    s2 := s1[:2] // "12"
    // s1 和 s2 指向了同一个底层Data地址
    fmt.Println(stringptr(s1) == stringptr(s2)) // true
}

golangstring interning

s1 := "12"
s2 := "1"+"2"
fmt.Println(stringptr(s1) == stringptr(s2)) // true

string interning

s1 := "12"
s2 := strconv.Itoa(12)
fmt.Println(stringptr(s1) == stringptr(s2)) // false

实现 string interning

string interningGetSet

string interning(thread unsafe)

type stringInterner map[string]string

func (si stringInterner) InternBytes(b []byte) string {
	if interned, ok := si[string(b)]; ok {
		return interned
	}
	s := string(b)
	si[s] = s
	return s
}

stringInterner[]bytestringstringinternedstringinternstring

减少重复内存分配

string(b)stringDatastringstring[]bytestring(b)string

减少比较字符串开销

string interning

TEXT cmpbody<>(SB),NOSPLIT,$0-0
    CMPQ    SI, DI
    JEQ allsame

string interningBenchmark

func benchmarkStringCompare(b *testing.B, count int) {
    s1 := strings.Repeat("a", count)
    s2 := strings.Repeat("a", count)
    b.ResetTimer()
    for n := 0; n < b.N; n++ {
        if s1 != s2 {
            b.Fatal()
        }
    }
}

func benchmarkStringCompareIntern(b *testing.B, count int) {
    si := stringInterner{}
    s1 := si.Intern(strings.Repeat("a", count))
    s2 := si.Intern(strings.Repeat("a", count))
    b.ResetTimer()
    for n := 0; n < b.N; n++ {
        if s1 != s2 {
            b.Fatal()
        }
    }
}

func BenchmarkStringCompare1(b *testing.B)   { benchmarkStringCompare(b, 1) }
func BenchmarkStringCompare10(b *testing.B)  { benchmarkStringCompare(b, 10) }
func BenchmarkStringCompare100(b *testing.B) { benchmarkStringCompare(b, 100) }

func BenchmarkStringCompareIntern1(b *testing.B)   { benchmarkStringCompareIntern(b, 1) }
func BenchmarkStringCompareIntern10(b *testing.B)  { benchmarkStringCompareIntern(b, 10) }
func BenchmarkStringCompareIntern100(b *testing.B) { benchmarkStringCompareIntern(b, 100) }

string interning

BenchmarkStringCompare1-4               500000000            2.93 ns/op
BenchmarkStringCompare10-4              300000000            6.21 ns/op
BenchmarkStringCompare100-4             100000000            13.2 ns/op
BenchmarkStringCompareIntern1-4         1000000000           2.60 ns/op
BenchmarkStringCompareIntern10-4        1000000000           2.60 ns/op
BenchmarkStringCompareIntern100-4       1000000000           2.60 ns/op

线程安全和淘汰策略

golangmapmulti goroutinestring intern

sync.Poolsync.Pool

阶段总结

string interning

string interningstring interning

img

总结

Golang

string[]byte