golang中的字符串，字符串驻留 Intern，unique包

Go1.23

Go字符串

Go语言中的字符串是一个不可变的字节序列，这意味着一旦字符串被创建，其内容就不能被修改（尽管可以通过切片、拼接等方式生成新的字符串）。这一设计选择不仅简化了字符串的处理逻辑，还提高了程序的并发安全性。

字符串的内部结构如下

// reflect.StringHeader
//
// 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.
//
// Deprecated: Use unsafe.String or unsafe.StringData instead.
type StringHeader struct {
	Data uintptr // 指向字节数组的指针
	Len  int     // 字符串的长度
}

实际字符串类型在Go中是一个基本类型，但可以通过反射等方式观察到其内部结构。

这里，Data 是一个指向实际字节切片的指针，这些字节按照UTF-8编码（或其他指定编码）存储字符串的内容。Len 则记录了这些字节中属于字符串有效部分的长度。重要的是，这个长度信息使得Go语言能够处理包含NUL字符（\0，即ASCII码为0的字符）的字符串，因为在C或C++等传统语言中，字符串通常以NUL字符作为结束标志，而在Go中则不是。

字符串是不可改变的，如果你想改变变量的值，那么变量就会指向新的字符串。

从注释可以看到 StringHeader已经被Deprecated，使用unsafe.String or unsafe.StringData代替。

// unsafe
//
// String returns a string value whose underlying bytes
// start at ptr and whose length is len.
//
// The len argument must be of integer type or an untyped constant.
// A constant len argument must be non-negative and representable by a value of type int;
// if it is an untyped constant it is given type int.
// At run time, if len is negative, or if ptr is nil and len is not zero,
// a run-time panic occurs.
//
// Since Go strings are immutable, the bytes passed to String
// must not be modified as long as the returned string value exists.
func String(ptr *byte, len IntegerType) string

// StringData returns a pointer to the underlying bytes of str.
// For an empty string the return value is unspecified, and may be nil.
//
// Since Go strings are immutable, the bytes returned by StringData
// must not be modified.
func StringData(str string) *byte

unsafe.String()方法的第一个参数是单个字节的地址，也就是字符串的底层字节切片的第零个字节的地址，即&data[0]，第二个参数为切片长度。

unsafe.StringData()返回字符串底层字节切片的首地址。

s0 := "raoxiaoya"
fmt.Println(unsafe.StringData(s0)) // 0xc3bf0a

s1 := "raoxiaoya"
fmt.Println(unsafe.StringData(s1)) // 0xc3bf0a
// s0 和 s1 指向了同一个底层切片，这说明Go内部实现了某种字符串驻留机制

s2 := s1
fmt.Println(unsafe.StringData(s2)) // 0xc3bf0a
// 直接赋值会指向同一个底层切片

s0 = "xiao"
fmt.Println(unsafe.StringData(s0)) // 0xc3b854

ss := "rao"
fmt.Println(unsafe.StringData(ss)) // 0xc3b7e5

s2 = s1[:3]
fmt.Println(unsafe.StringData(s1)) // 0xc3bf0a
fmt.Println(unsafe.StringData(s2)) // 0xc3bf0a
// 可以引用一部分底层切片

s3 := strings.Clone(s1) // 会产生新的切片
fmt.Println(unsafe.StringData(s1)) // 0xc3bf0a
fmt.Println(unsafe.StringData(s3)) // 0xc00008c0d0

如果响要得到新的字符串结构，需要使用strings.Clone，它调用的是内置函数 copy。

// strings.CLone()
//
// Clone returns a fresh copy of s.
// It guarantees to make a copy of s into a new allocation,
// which can be important when retaining only a small substring
// of a much larger string. Using Clone can help such programs
// use less memory. Of course, since using Clone makes a copy,
// overuse of Clone can make programs use more memory.
// Clone should typically be used only rarely, and only when
// profiling indicates that it is needed.
// For strings of length zero the string "" will be returned
// and no allocation is made.
func Clone(s string) string {
	return stringslite.Clone(s)
}
func Clone(s string) string {
	if len(s) == 0 {
		return ""
	}
	b := make([]byte, len(s))
	copy(b, s)
	return unsafe.String(&b[0], len(b))
}
// The copy built-in function copies elements from a source slice into a
// destination slice. (As a special case, it also will copy bytes from a
// string to a slice of bytes.) The source and destination may overlap. Copy
// returns the number of elements copied, which will be the minimum of
// len(src) and len(dst).
func copy(dst, src []Type) int

字符串驻留 String Interning

仅保留一份相同且不可变字符串的方法，不同的值被存放在字符串的驻留池中，对相同的字符串值保留一份拷贝，后续创建相同字符串时，不会开辟新空间，而是把该字符串的地址赋给新的变量。这个技巧用于节约重复出现的字符串的空间占用，还可以用于重复出现的字符串的比较的加速。

字符串驻留的实现就是使用一个map来存储。这是一个简单的实现。

var internPool map[string]string

// Intern returns a string that is equal to s but that may share storage with
// a string previously passed to Intern.
func Intern(s string) string {
    pooled, ok := internPool[s]
    if !ok {
        // Clone the string in case it's part of some much bigger string.
        // This should be rare, if interning is being used well.
        pooled = strings.Clone(s)
        internPool[pooled] = pooled
    }
    return pooled
}

这个实现非常简单，在某些情况下运行良好，但它有一些问题：

它并不会从池子里删除字符串。
并不是并发安全的。
只能用于字符串类型。

在使用字符串驻留的时候，比较字符串就只需要比较底层切片指针，这就是字符串规范化的好处。否则的话，需要先比较底层切片指针，如果不相等的话还要去比较字符串内容。尤其是在比较长字符串时，Intern 机制将会大大节省开销。

unique 包

Go1.23中引入的unique包就是 String Interning 技术的Go官方实现。并且unique包不仅支持字符串，还支持任何comparable类型。Go社区interning技术的讨论过程：

由于其他主流语言都或多或少有了对string intemning的支持，Go社区显然也需要这样的包，在Go issues列表中，我能找到的最早提出在Go中添加intemming技术实现的是2013年go核心开发人员Brad Fitzpatrick提出的 proposal: runtime.optionally allow callers to intem strings

2019年，josh Bleecher Snvder发表了一篇博文 Inteming strings in Go，探讨了interning的Go实现方法，并给出一个简单但重度使用 sync.Pool 的 interning 实现，该实现支持对string和字节切片的interning。

2021年，tailscale为了实现可以高效表示ip地址的netaddr包，构建和开源了 go4.org/intern包，这是一个可用于生产级别的interning实现。

之后，Brad Fitzpatrick将inetaf/netaddr包的实现合并到了Go标准库net/netip中，而netaddr包依赖的go4.org/intern包也被移入Go项目，变为internal/intern包，并被net/netip包所使用。

直到2023年9月，mknyszek提出 unique: new package with unique.Handle 的proposal，给出unique包的API设计和参考实现。unique落地后，原先使用internal/intern包的net/netip也都改为使用unique包了，internal/intern在Go 1.23版本被移除。

unique 包提供了一个类似于 Intern 的函数 Make。Make 在内部使用一个全局 Map（一个快速的泛型并发 Map）来查找值。与之前的简单实现不同，Make 有两个显著的区别：

支持泛型：它可以接受任何可比较的类型，而不仅限于字符串。
Handle[T]：它返回一个 Handle[T]，可以通过它检索规范化的值。

unique包并没有使用sync.Map，因为其参数是 interface{}，使用起来不方便，于是特地新增了HashTrieMap。

// internal/concurrent/hashtriemap.go
// 
// HashTrieMap is an implementation of a concurrent hash-trie. The implementation
// is designed around frequent loads, but offers decent performance for stores
// and deletes as well, especially if the map is larger. It's primary use-case is
// the unique package, but can be used elsewhere as well.
type HashTrieMap[K, V comparable] struct {
	root     *indirect[K, V]
	keyHash  hashFunc
	keyEqual equalFunc
	valEqual equalFunc
	seed     uintptr
}

Handle[T] 的关键作用

Handle[T] 是该包设计的核心。两个 Handle[T] 只有在用相等的值创建时才相等。其优势在于：两个 Handle[T] 的比较只需进行指针比较，而不用比较具体的内容，这大大提高了效率。

此外，只要 Map 中存在某个值的 Handle[T]，该值的规范化副本就会被保留。一旦所有指向特定值的 Handle[T] 消失，该值就可以被垃圾回收器移除。

如果你曾接触过 Lisp，这可能会让你想起 Lisp 中的符号系统。Lisp 中的符号类似于驻留的字符串，但符号本身并不是字符串。Handle[string] 与 string 的关系就像 Lisp 中符号与字符串的关系。

实际应用示例

Go 标准库中的 net/netip 包使用 unique 包对 addrDetail 类型的值进行了驻留。以下是该代码的简化版本：

type Addr struct {
	addr uint128
	z unique.Handle[addrDetail]
}
type addrDetail struct {
	isV6   bool   // IPv4 is false, IPv6 is true.
	zoneV6 string // != "" only if IsV6 is true.
}
func (ip Addr) WithZone(zone string) Addr {
	if !ip.Is6() {
		return ip
	}
	if zone == "" {
		ip.z = z6noz
		return ip
	}
	ip.z = unique.Make(addrDetail{isV6: true, zoneV6: zone})
	return ip
}

由于许多 IP 地址可能使用相同的 zone，且 zone 是地址标识的一部分，因此对其进行规范化有助于减少内存占用。驻留后，zone 名称的比较仅需指针比较，从而提升性能。

关于字符串驻留的说明

尽管 unique 包非常有用，但它在处理字符串驻留时存在一些不同之处。要防止字符串被从内部 Map 中移除，必须同时保留 Handle[T] 和字符串值。

字符串的特殊之处在于，它们虽然像值一样工作，但实际上是指针。因此，理论上可以只对字符串的底层存储进行驻留，而不暴露 Handle[T] 的细节。未来可能会实现所谓的透明字符串驻留，类似于 Intern 函数，但具有更灵活的语义。

目前，可以通过 unique.Make("my string").Value() 进行一定程度的字符串驻留。尽管没有保留 Handle[T]，字符串仍会在下次垃圾回收后被清理，因此在短期内依然能达到驻留效果。

h1 := unique.Make("hello")
h2 := unique.Make("hello")
h3 := unique.Make("world")
fmt.Println(h1 == h2) // true
fmt.Println(h1 == h3) // false

p1 := Person{"rao", 12}
p2 := Person{"rao", 12}
fmt.Println(p1 == p2) // true

h1 := unique.Make(p1)
h2 := unique.Make(p2)
fmt.Println(h1 == h2) // true