cover

Go 的 String Interning

sorcererxw

介绍

在 Java 里面,JVM 默认为字符串建立了缓存池,以避免频繁创建新的 string 对象。但是 Go 并没有实现这一层优化(Go 仅仅会在编译期缓存字符串),所以在处理大量的动态字符串的时候,会带来不小的性能损耗。那么是否可以仿造 Java 实现一个 string pool,以局部缓存热点字符串,这就是 String Interning 技术。

source: https://stackabuse.com/guide-to-string-interning-in-python/

实现

观察一下 Go string 的内部结构:

package reflect

// StringHeader is the runtime representation of a string.
// It cannot be used safely or portably and its representation may
// change in a later release.
// Moreover, the Data field is not sufficient to guarantee the data
// it references will not be garbage collected, so programs must keep
// a separate, correctly typed pointer to the underlying data.
type StringHeader struct {
	Data uintptr
	Len  int
}

可以看到 string 本质上就是一个内存指针加上长度,由于 Go string 不可变的特性,我们可以认为复用 string 是安全的。下面是一个简单的实现:

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 在将 []byte 转换为 string 的同时,检查此 string 是否已经被 interned,如果是则直接返回老的 string,否则 intern 新的 string。这段函数看上去非常违背直觉,相比直接 string(b) 明明多做了这么多操作,居然性能更好。那么可以分析一下:

由于 string(b) 的原理是直接将 b 作为 string 的 Data,如果程序不断读入新的字节流,会不断生成新的 string 对象,string 占用的空间呈线性增长。上面这段函数,只使用 []byte 作为比较的依据,新生成的 string(b) (分配在栈上)会随着函数结束而被回收,只有未命中的 string 会被缓存在堆上。

另外还有一个点值得注意的是,我们知道 Go 在函数调用的时候是完全通过值拷贝的方式传递参数和返回结果的,为什么返回的 string 就是被 interning 的 string 呢,而不是拷贝一份新的返回?是否拷贝数据决定了这段函数是否成立。 根据 Go Internal ABI 的说明:

The string type is a sequence of a *[len]byte pointer to the string backing store, and an int giving the len of the string.

可以知道无论在参数传递还是结果返回的时候,string 都是通过引用的方式指向实际数据,不会出现在传递 string 的时候复制数据的情况。

综上,以上的 stringInterning 在重复文本较多的时候,能够一定程度降低内存消耗;但是在文本几乎没有重复的时候,因为多做了比较操作,会降低一点执行效率。

实验

现在我们可以设计一个真实的场景,来验证一下 stringInterning 的实际效果。

假设我们需要反序列化一个 JSON 数据,其中包含了大量的重复字符串:

[
		{"year":"2021","month":"January","day":"1"}
		{"year":"2021","month":"January","day":"2"}
		...
		{"year":"2021","month":"December","day":"31"}
]


// calendar generate JSON of 2021
func calendarJSON() []byte {
	var calendar []interface{}
	d := time.Date(2021, 0, 0, 0, 0, 0, 0, time.UTC)
	for d.Year() < 2022 {
		d = d.Add(time.Hour * 24)
		calendar = append(calendar, map[string]string{
			"year":  strconv.Itoa(d.Year()),
			"month": d.Month().String(),
			"day":   strconv.Itoa(d.Day()),
		})
	}
	ret, _ := json.Marshal(calendar)
	return ret
}

分别编写两个函数:

// SimpleString wraps go string.
type SimpleString struct {
	data string
}

func (i *SimpleString) UnmarshalJSON(b []byte) error {
	i.data = string(b)
	return nil
}

func BenchmarkUnmarshal(b *testing.B) {
	raw := calendarJSON()

	var dest []struct {
		Year     *SimpleString `json:"year"`
		Calendar *SimpleString `json:"calendar"`
		Day      *SimpleString `json:"day"`
	}

	for i := 0; i < b.N; i++ {
		json.Unmarshal(raw, &dest)
	}
}

var si = make(stringInterner)

// InterningString wraps go string with string interning.
type InterningString struct {
	data string
}

func (i *InterningString) UnmarshalJSON(b []byte) error {
	i.data = si.InternBytes(b)
	return nil
}

func BenchmarkUnmarshalWithInterning(b *testing.B) {
	raw := calendarJSON()

	var dest []struct {
		Year     *InterningString `json:"year"`
		Calendar *InterningString `json:"calendar"`
		Day      *InterningString `json:"day"`
	}

	for i := 0; i < b.N; i++ {
		json.Unmarshal(raw, &dest)
	}
}

为了控制变量,两个函数的 string 都使用结构体进行了封装,唯一的区别是 InterningString 在读入的时候会做一遍 interning。

go test -bench=. -benchmem
goos: darwin
goarch: amd64
pkg: github.com/sorcererxw/demo
cpu: Intel(R) Core(TM) i5-7267U CPU @ 3.10GHz
BenchmarkUnmarshal-4                        4778            249779 ns/op            6060 B/op        800 allocs/op
BenchmarkUnmarshalWithInterning-4           4764            252346 ns/op             324 B/op          6 allocs/op

可以看到,两者在运行速度上没有显著的差异,但是使用 interning 之后占用内存显著降低。

总结

StringInterning 可以帮助 Go 程序在特定场景下,降低内存占用,提高性能。

同时这个技巧也已经被广泛地使用,比如 easyjson 可以通过在 json tag 上标记 intern 表示这个字段会有大量重复的值,让 easyjson 在反序列化这个字段的时候引入 StringInterning:

GitHub - mailru/easyjson: Fast JSON serializer for golang.
Fast JSON serializer for golang. Contribute to mailru/easyjson development by creating an account on GitHub.
https://github.com/mailru/easyjson#string-interning