0%

【Go语言设计与实现】String

字符串是 Go 语言中最常用的基础数据类型之一,虽然字符串往往被看做一个整体,但是实际上字符串是一片连续的内存空间,我们也可以将它理解成一个由字符组成的数组,在这一节中就会详细介绍字符串的实现原理、相关转换过程以及常见操作的实现。

基本使用

字符串定义

Go 语言字符串可以使用双引号 " 和 反引号 “`” 两种方法创建:

  • 双引号用来创建可解析的字符串字面量,支持转义,但是不能用来引用多行。这种方式使用最为广泛。
  • 反引号用来创建原生的字符串字面量,不支持转义,可以由多行组成,并且可以包含除了反引号之外的任何字符。这种方式多用于书写多行消息、HTML以及正则表达式。
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
package main

import (
"fmt"
)

func main() {
text1 := "\"what's that?\", he said" // The interpreted form
text2 := `"what's that?", he said` // The raw form
fmt.Println(text1)
fmt.Println(text2)
fmt.Println("text1 == text2: ", text1 == text2)

// The interpreted form.
text3 := "Hello\nworld!\n\"你好世界\""
text4 :=
`Hello
world!
"你好世界"`
fmt.Println(text3)
fmt.Println(text4)
fmt.Println("text3 == text4: ", text3 == text4)

// Unicode and UTF-8 encode
text5 := "中国"
text6 := "\xe4\xb8\xad\xe5\x9b\xbd"
text7 := "\u4E2D\u56FD"
fmt.Println(text5)
fmt.Println(text6)
fmt.Println(text7)
fmt.Println("text5 == text6: ", text5 == text6)
fmt.Println("text5 == text7: ", text5 == text7)

}

执行上面程序,输出如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
"what's that?", he said
"what's that?", he said
text1 == text2: true
Hello
world!
"你好世界"
Hello
world!
"你好世界"
text3 == text4: true
中国
中国
中国
text5 == text6: true
text5 == text7: true

下面列出了 Go 语言中常用的转移字符:

UTF-8 编码的变宽字符序列

Go 语言中的 string 本质上是 只读的字节数组 (read only slice of bytes),类似于 C 语言中的字符数组 char[],但是 Go 语言中专门封装了 string 类型。该 只读字节数组 作为数组会占用一片连续的内存空间,这片内存空间存储了的字节共同组成了字符串。

Go 语言字符串的 只读的字节数组 使用 UTF-8 编码来表示 Unicode 文本,关于 Unicode 字符集和 UTF-8 编码可以参考 我的这篇博客 。Java 的 String、C++ 的 std::string、Python3 的 str 类型都是定宽字符序列,而 Go 语言的字符串是一个用 UTF-8 编码的变宽字符序列,它的每一个字符长度不定,根据字符在 UTF-8 编码的大小确定长度。

如果是代码中存在的字符串,会在编译期间被标记成只读数据 SRODATA 符号,假设我们有以下的一段代码,其中包含了一个字符串,当我们将这段代码编译成汇编语言时,就能够看到 hello 字符串有一个 SRODATA 的标记。只读只意味着字符串会分配到只读的内存空间并且这块内存不会被修改,但是在运行时我们其实还是可以将这段内存拷贝到堆或者栈上,将变量的类型转换成 []byte 之后就可以进行,修改后通过类型转换就可以变回 string,Go 语言只是不支持直接修改 string 类型变量的内存空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
$ cat main.go
package main

func main() {
str := "hello, 中国"
println([]byte(str))
}

$ GOOS=linux GOARCH=amd64 go tool compile -S main.go
...
go.string."hello, 中国" SRODATA dupok size=13
0x0000 68 65 6c 6c 6f 2c 20 e4 b8 ad e5 9b bd hello, ......
...

可以看到,因为汉字 的 Unicode 的 code point 为 U+4E2D,其UTF-8编码为 e4 b8 ad ;汉字 的 Unicode 的 code point 为 U+56FD,其UTF-8编码为 e5 9b bd 。下图展示了 "hello" 字符串在内存中的存储方式:

正是因为采用 UTF-8 编码,Go 语言中字符串是变长的字符序列,Go 语言中我们不能直接用字节索引字符串中的字符(ASCII字符除外,因为它们都用一个单一的UTF-8字节表示)。直接索引一个字符串,我们得到的是 byte,而不是字符,因为 Go 语言中的字符串本来就是一个字节数组。

1
2
3
4
5
const china = "中国"
for i := 0; i < len(china); i++ {
fmt.Printf("%x ", china[i])
}
// e4 b8 ad e5 9b bd

通过 我的这篇博客 ,我们知道 Unicode 使用 Code Point 表示一个字符,比如汉字 的 Code Point 为 U+4E2D。在 Go 语言中,使用 rune,即符文来表示代码点的含义,它和代码点表达的意思完全相同。Go语言将rune定义为 int32 类型的别名,因此在使用一个整型值表达一个 Code Point 时,代码更加清晰。

上面我们看到,直接索引 Go 语言字符串不总是得到单个字符,不过 Go 提供了 for range 的方式来遍历字符串。一个 range 循环会在每次迭代时,解码 UTF-8 编码的符文。每次循环时,循环的 index 是当前字符的起始地址,以字节为单位,循环的 value 是 rune 的值。下面是一个使用%#U格式化的例子,它显示了代码点的Unicode值及其打印的表现形式。

1
2
3
4
5
6
7
const china = "中国"
for index, runeValue := range china {
fmt.Printf("%#U starts at byte position %d\n", runeValue, index)
}

// U+4E2D '中' starts at byte position 0
// U+56FD '国' starts at byte position 3

Go语言标准库强有力地支持解码UTF-8文本。如果for range循环不能满足你的需求,那就需要一些别的包来解决问题。

最重要的库为unicode/utf8,它包含帮助程序例程来验证,反汇编和重组UTF-8字符串。下面的例子功能和上面for range实现一样的功能,不同的是使用了DecodeRuneInString函数。

1
2
3
4
5
6
7
8
9
const china = "中国"
for i, w := 0, 0; i < len(china); i += w {
runeValue, width := utf8.DecodeRuneInString(china[i:])
fmt.Printf("%#U starts at byte position %d\n", runeValue, i)
w = width
}

// U+4E2D '中' starts at byte position 0
// U+56FD '国' starts at byte position 3

拼接切割

下图展示了 Go 语言字符串拼接、比较、索引的方法。注意,字符串的索引是 unaddressable and immutable ,直接修改或者寻找地址都是错误的。

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
package main

import (
"fmt"
"strings"
)

func main() {
const World = "world"
var hello = "hello"

// Concatenate strings.
var helloWorld = hello + " " + World
helloWorld += "!"
fmt.Println(helloWorld) // hello world!

// Compare strings.
fmt.Println(hello == "hello") // true
fmt.Println(hello > helloWorld) // false

hello = helloWorld[:5] // substring
// 104 is the ASCII code (and Unicode) of char 'h'.
fmt.Println(hello[0]) // 104
fmt.Printf("%T \n", hello[0]) // uint8

// hello[0] is unaddressable and immutable,
// so the following two lines fail to compile.
/*
hello[0] = 'H' // error
fmt.Println(&hello[0]) // error
*/

// The next statement prints: 5 12 true
fmt.Println(len(hello), len(helloWorld),
strings.HasPrefix(helloWorld, hello))
}

类型转换

当我们使用 Go 语言解析和序列化 JSON 等数据格式时,经常需要将数据在 string[]byte 之间来回转换,下面代码展示了转换方法。

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
package main

import (
"bytes"
"unicode/utf8"
)

func Runes2Bytes(rs []rune) []byte {
n := 0
for _, r := range rs {
n += utf8.RuneLen(r)
}
n, bs := 0, make([]byte, n)
for _, r := range rs {
n += utf8.EncodeRune(bs[n:], r)
}
return bs
}

func main() {
s := "Color Infection is a fun game."
bs := []byte(s) // string -> []byte
s = string(bs) // []byte -> string
rs := []rune(s) // string -> []rune
s = string(rs) // []rune -> string
rs = bytes.Runes(bs) // []byte -> []rune
bs = Runes2Bytes(rs) // []rune -> []byte
}

数据结构

字符串在 Go 语言中的接口其实非常简单,每一个字符串在运行时都会使用如下的 StringHeader 结构体表示,在运行时包的内部其实有一个私有的结构 stringHeader,它有着完全相同的结构只是用于存储数据的 Data 字段使用了 unsafe.Pointer 类型:

1
2
3
4
type StringHeader struct {
Data uintptr
Len int
}

我们会经常会说字符串是一个只读的切片类型,这是因为切片在 Go 语言的运行时表示与字符串高度相似:

1
2
3
4
5
type SliceHeader struct {
Data uintptr
Len int
Cap int
}

与切片的结构体相比,字符串少了一个表示容量的 Cap 字段,因为字符串作为只读的类型,我们并不会直接向字符串直接追加元素改变其本身的内存空间,所有在字符串上执行的写入操作实际都是通过拷贝实现的。

解析过程

字符串的解析一定是解析器在词法分析时就完成的,词法分析阶段会对源文件中的字符串进行切片和分组,将原有无意义的字符流转换成 Token 序列,在 Go 语言中,有两种字面量方式可以声明一个字符串,一种是使用双引号,另一种是使用反引号:

1
2
3
str1 := "this is a string"
str2 := `this is another
string`

使用双引号声明的字符串和其他语言中的字符串没有太多的区别,它只能用于单行字符串的初始化,如果字符串内部出现双引号,需要使用 \ 符号避免编译器的解析错误,而反引号声明的字符串就可以摆脱单行的限制,因为双引号不再负责标记字符串的开始和结束,我们可以在字符串内部直接使用 ",在遇到需要手写 JSON 或者其他复杂数据格式的场景下非常方便。

1
json := `{"author": "draven", "tags": ["golang"]}`

两种不同的声明方式其实也意味着 Go 语言的编译器需要在解析的阶段能够区分并且正确解析这两种不同的字符串格式,解析字符串使用的 scanner 扫描器,它的功能就是将输入的字符流转换成 Token 流,cmd/compile/internal/syntax.scanner.stdString 方法就是它用来解析使用双引号包裹的标准字符串:

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
func (s *scanner) stdString() {
s.startLit()
for {
r := s.getr()
if r == '"' {
break
}
if r == '\\' {
s.escape('"')
continue
}
if r == '\n' {
s.ungetr()
s.error("newline in string")
break
}
if r < 0 {
s.errh(s.line, s.col, "string not terminated")
break
}
}
s.nlsemi = true
s.lit = string(s.stopLit())
s.kind = StringLit
s.tok = _Literal
}

从这个方法的实现我们能分析出 Go 语言处理标准字符串的逻辑:

  1. 标准字符串使用双引号表示开头和结尾;
  2. 标准字符串中需要使用反斜杠 \escape 双引号;
  3. 标准字符串中不能出现如下所示的隐式换行符号 \n
1
2
str := "start
end"

使用反引号声明的原始字符串的解析规则就非常简单了,cmd/compile/internal/syntax.scanner.rawString 会将非反引号的所有字符都划分到当前字符串的范围中,所以我们可以使用它来支持复杂的多行字符串:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func (s *scanner) rawString() {
s.startLit()
for {
r := s.getr()
if r == '`' {
break
}
if r < 0 {
s.errh(s.line, s.col, "string not terminated")
break
}
}
s.nlsemi = true
s.lit = string(s.stopLit())
s.kind = StringLit
s.tok = _Literal
}

无论是标准字符串还是原始字符串最终都会被标记成 StringLit 类型的 Token 并传递到编译的下一个阶段 — 语法分析,在语法分析阶段,与字符串相关的表达式都会使用如下的方法 cmd/compile/internal/gc.noder.basicLit 处理:

1
2
3
4
5
6
7
8
9
10
func (p *noder) basicLit(lit *syntax.BasicLit) Val {
switch s := lit.Value; lit.Kind {
case syntax.StringLit:
if len(s) > 0 && s[0] == '`' {
s = strings.Replace(s, "\r", "", -1)
}
u, _ := strconv.Unquote(s)
return Val{U: u}
}
}

无论是 import 语句中包的路径、结构体中的字段标签还是表达式中的字符串都会使用这个方法将原生字符串中最后的换行符删除并对字符串 Token 进行 Unquote,也就是去掉字符串两遍的引号等无关干扰,还原其本来的面目。

strconv.Unquote 方法处理了很多边界条件导致整个函数非常复杂,不仅包括各种不同引号的处理,还包括 UTF-8 等编码的相关问题,所以在这里也就不展开介绍了。

拼接

Go 语言拼接字符串会使用 + 符号,编译器会将该符号对应的 OADD 节点转换成 OADDSTR 类型的节点,随后在 cmd/compile/internal/gc.walkexpr 函数中调用 cmd/compile/internal/gc.addstr 函数生成用于拼接字符串的代码:

1
2
3
4
5
6
7
func walkexpr(n *Node, init *Nodes) *Node {
switch n.Op {
...
case OADDSTR:
n = addstr(n, init)
}
}

cmd/compile/internal/gc.addstr 函数能帮助我们在编译期间选择合适的函数对字符串进行拼接,如果需要拼接的字符串小于或者等于 5 个,那么就会直接调用 concatstring{2,3,4,5} 等一系列函数,如果超过 5 个就会直接选择 runtime.concatstrings 传入一个数组切片。

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 addstr(n *Node, init *Nodes) *Node {
c := n.List.Len()

buf := nodnil()
args := []*Node{buf}
for _, n2 := range n.List.Slice() {
args = append(args, conv(n2, types.Types[TSTRING]))
}

var fn string
if c <= 5 {
fn = fmt.Sprintf("concatstring%d", c)
} else {
fn = "concatstrings"

t := types.NewSlice(types.Types[TSTRING])
slice := nod(OCOMPLIT, nil, typenod(t))
slice.List.Set(args[1:])
args = []*Node{buf, slice}
}

cat := syslook(fn)
r := nod(OCALL, cat, nil)
r.List.Set(args)
...

return r
}

其实无论使用 concatstring{2,3,4,5} 中的哪一个,最终都会调用 runtime.concatstrings,该函数会先对传入的切片参数进行遍历,先过滤空字符串并计算拼接后字符串的长度。

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
func concatstrings(buf *tmpBuf, a []string) string {
idx := 0
l := 0
count := 0
for i, x := range a {
n := len(x)
if n == 0 {
continue
}
l += n
count++
idx = i
}
if count == 0 {
return ""
}
if count == 1 && (buf != nil || !stringDataOnStack(a[idx])) {
return a[idx]
}
s, b := rawstringtmp(buf, l)
for _, x := range a {
copy(b, x)
b = b[len(x):]
}
return s
}

如果非空字符串的数量为 1 并且当前的字符串不在栈上就可以直接返回该字符串,不需要进行额外的任何操作。

字符串的拼接和拷贝

但是在正常情况下,运行时会调用 copy 将输入的多个字符串拷贝到目标字符串所在的内存空间中,新的字符串是一片新的内存空间,与原来的字符串也没有任何关联,一旦需要拼接的字符串非常大,拷贝带来的性能损失就是无法忽略的。

类型转换

当我们使用 Go 语言解析和序列化 JSON 等数据格式时,经常需要将数据在 string[]byte 之间来回转换,类型转换的开销并没有想象的那么小,我们经常会看到 runtime.slicebytetostring 等函数出现在火焰图中,成为程序的性能热点。

从字节数组到字符串的转换就需要使用 runtime.slicebytetostring 函数,例如:string(bytes),该函数在函数体中会先处理两种比较常见的情况,也就是字节数组的长度为 0 或者 1,这两个情况处理起来都非常简单:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func slicebytetostring(buf *tmpBuf, b []byte) (str string) {
l := len(b)
if l == 0 {
return ""
}
if l == 1 {
stringStructOf(&str).str = unsafe.Pointer(&staticbytes[b[0]])
stringStructOf(&str).len = 1
return
}
var p unsafe.Pointer
if buf != nil && len(b) <= len(buf) {
p = unsafe.Pointer(buf)
} else {
p = mallocgc(uintptr(len(b)), nil, false)
}
stringStructOf(&str).str = p
stringStructOf(&str).len = len(b)
memmove(p, (*(*slice)(unsafe.Pointer(&b))).array, uintptr(len(b)))
return
}

处理过后会根据传入的缓冲区大小决定是否需要为新的字符串分配一片内存空间,runtime.stringStructOf 会将传入的字符串指针转换成 stringStruct 结构体指针,然后设置结构体持有的字符串指针 str 和长度 len,最后通过 memmove 将原 []byte 中的字节全部复制到新的内存空间中。

当我们想要将字符串转换成 []byte 类型时,就需要使用 runtime.stringtoslicebyte 函数,该函数的实现非常容易理解:

1
2
3
4
5
6
7
8
9
10
11
func stringtoslicebyte(buf *tmpBuf, s string) []byte {
var b []byte
if buf != nil && len(s) <= len(buf) {
*buf = tmpBuf{}
b = buf[:len(s)]
} else {
b = rawbyteslice(len(s))
}
copy(b, s)
return b
}

如果向该函数传入了缓冲区,那么它会使用传入的缓冲区存储 []byte,没有传入缓冲区时,运行时会调用 runtime.rawbyteslice 创建一个新的字节切片,copy 就会将字符串中的内容拷贝到新的 []byte 中。

字符串和字节数组的转换

字符串和 []byte 中的内容虽然一样,但是字符串的内容是只读的,我们不能通过下标或者其他形式改变其中的数据,而 []byte 中的内容是可以读写的,无论从哪种类型转换到另一种都需要对其中的内容进行拷贝,而内存拷贝的性能损耗会随着字符串和 []byte 长度的增长而增长。

小结

字符串是 Go 语言中相对来说比较简单的一种数据结构,我们在这一节中详细分析了字符串与 []byte 类型的关系,从词法分析阶段理解字符串是如何被解析的,作为只读的数据类型,我们无法改变其本身的结构,但是在做拼接和类型转换等操作时时一定要注意性能的损耗,遇到需要极致性能的场景一定要尽量减少类型转换的次数。

参考资料