【go】高性能编程

常见拼接方式

使用+

func plusConcat(n int, str string) string {
    s := ""
    for i := 0; i < n; i++ {
        s += str
    }
    return s
}

使用strings.Builder

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

使用bytes.Buffer

func bufferConcat(n int, s string) string {
    buf := new(bytes.Buffer)
    for i := 0; i < n; i++ {
        buf.WriteString(s)
    }
    return buf.String()
}

使用[]byte

func byteConcat(n int, str string) string {
    buf := make([]byte, 0)
    for i := 0; i < n; i++ {
        buf = append(buf, str...)
    }
    return string(buf)
}
// 如果知道长度，可以提前预分配切片的容量
func preByteConcat(n int, str string) string {
    buf := make([]byte, 0, n*len(str))
    for i := 0; i < n; i++ {
        buf = append(buf, str...)
    }
    return string(buf)
}

使用+这种方式的效率是最低的，消耗的时间和内存几乎是其他方法的1000倍，其他几种的性能消耗相近，最好的是最后一种，因为在拼接的过程，不需要进行字符串的拷贝，不需要分配新的内存。

但总和易用性和性能，一般推荐使用strings.Builder。

strings.Builder也提供了预分配内存的方式Grow：

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()
}

原理

+方式慢原因是因为go语言中字符串是不可变类型，占用内存大小是固定的，当+拼接2个字符串时，生成一个新的字符串，那么需要开辟一段新的空间，大小是原来两个字符串大小之和。那进行第三次拼接时需要再开辟新的空间，因此需要的时间和内存开销较大。

strings.Builder，bytes.Buffer和切片的内存是以倍数申请的。例如需要一个10byte的内存时，当buffer不够时，会自动申请大小为16byte的内存，再次申请时会申请32byte，然后64byte，这样2的倍数增长，但当超过2048byte时申请策略会调整。

16 32 64 128 256 512 1024 2048 2688 3456 4864 6144 8192 10240 13568 18432 24576 32768 40960 57344 73728 98304 122880

strings.Builder和bytes.Buffer底层都是[]byte数组，但前者比后者性能略快10%，一个比较重要的原因是byte.Buffer转化为字符串时重新申请了一块空间，存放生成的字符串变量，而strings.Builder直接将底层的[]byte直接转换成了字符串类型返回了。

切片性能

func make([]T, len, cap) []T

len是指定长度，即初始化切片时拥有多少个元素；

cap是指定容量，即申请的内存的大小，默认等于len。

当切片容纳的元素的个数超过cap之后就会重新分配内存，并将当前切片所有元素拷贝到新的内存空间上。因此为了减少内存的拷贝次数，容量在比较小的时候，一般以2的倍数扩大的，例如2, 4, 8, ..., 当达到2048时，会采取新的策略，避免申请内存过大浪费空间。

切片操作及性能

copy

b = make([]T, len(a))
copy(b, a)
// b = append([]T(nil), a...)
// b = append(a[:0:0], a...)
// O(n)

append

a = append(a, b...)
// 当append后的长度大于cap时，会分配一块更大的区域来容纳新的底层数组

delete

// 删除a[i]
a = append(a[:i], a[i+1:]...)
a = a[:i+copy(a[i:], a[i+1:])]
// O(n)

delete(gc)

// 删除a[i]
if i < len(a)-1 {
    copy(a[i:], a[i+1:])
}
a[len(a)-1] = nil
a = a[:len(a)-1]
// 将i后的元素前移并删除最后一个元素，有利于垃圾回收

insert

// 在i出插入一个元素
a = append(a[:i], append([]T{x}, a[i:]...))
// O(n)

filter

n := 0
for _, x := range a{
    if keep(x) {
        a[n] = x
        n++
    }
}
a = a[:n]

push

a = append(a, x)

pop

x, a = a[len(a)-1], a[:len(a)-1]
// pop front
x, a = a[0], a[1:]
// 但是这种方式会导致头部的内存不会释放掉

！切片陷阱

大量内存得不到释放

在已有切片的基础上再进行切片，不会创建新的底层数组，也就是两个切片引用了同一块内存。那么存在一种情况，原切片存在大量数据，新切片只是使用了一小段，但底层数组仍占据了大量的空间，得不到释放。

对于这种情况可以使用copy替代re-slice。

// b = a[start:end]
b = make([]int, len)
copy(b, a[start:end])