SpaceX
Go Slice的底层实现原理深度解析
编辑
2023-12-21
服务端
0
请注意，本文编写于 337 天前，最后修改于 113 天前，其中某些信息可能已经过时。

目录

数组的延伸
切片的结构
初始化
内存管理
扩容策略
垃圾回收
内存泄漏
原理剖析
编译过程
扩容函数
性能优化
预分配与扩容
避免不必要的切片操作
并发安全
读写锁
Channle
高级应用
队列
栈
二叉搜索树
迭代器
数据流

数组的延伸

在Go语言中，数组是一种固定长度的数据结构，一旦创建，长度就不能改变。这在某些情况下可能会限制它的使用。为了提供更灵活的数据结构，Go引入了切片（slice），它基于数组实现，但具有动态调整大小的能力。

切片的结构

切片的内部结构在src/runtime/slice.go中定义，如下图，它包含三个主要部分：

  • array：指向底层数组的指针。
  • len：切片的长度，即当前切片包含的元素数量。
  • cap：切片的容量，即底层数组能够容纳的元素数量。

初始化

切片在 Go 语言中有多种初始化方式，每种方式都有其特点和适用场景。下面简要介绍一下这些初始化方式：

  • 直接声明：可以通过 var 关键字声明一个切片变量，这时切片的默认值为 nil，需要使用 make 函数进行初始化后才能使用。
go
var s []int
  • 使用字面量：可以使用字面量来初始化切片，直接指定切片中的元素值，适用于已知元素值的情况。
go
s := []int{1, 2, 3, 4, 5}
  • 使用make函数：使用 make 函数可以创建一个指定长度和容量的切片，适用于需要预先分配内存空间的情况。
go
s := make([]int, 5) // 创建长度为 5 的切片
  • 从已有的切片或数组中截取：可以通过切片表达式 [low
    ] 来截取已有切片或数组的一部分作为新的切片。
go
arr := [5]int{1, 2, 3, 4, 5}

s := arr[1:3] // 截取索引为 1~2 的部分作为新切片

在底层，这些初始化方式会调用相应的函数来完成内存的分配和初始化工作。例如，make 函数实际上调用了 runtime.makeslice 函数来计算所需内存大小，并分配对应的内存空间。这些底层函数负责处理内存管理，确保切片的正确分配和初始化，使得开发者能够更方便地使用切片来操作数据。

内存管理

切片的内存管理是其高效性的关键之一。切片是基于底层数组的动态大小视图，它通过指针、长度和容量来描述底层数组的一部分。

当切片的长度 len 小于容量 cap 时，我们可以通过追加元素来扩展切片，而不需要重新分配整个底层数组。当我们追加一个元素到切片时，如果新的长度仍然小于容量，则内部的指针和长度会被更新，但是底层数组不会改变。这样，我们可以保持对同一个底层数组的引用，避免了内存的重新分配和复制，提高了效率。

当切片的长度超过容量时，追加元素将导致底层数组的重新分配和复制。这个时候，Go会分配一个新的更大的底层数组，并将原数组中的元素复制到新数组中。这个过程在runtime.growslice函数中实现。新的底层数组通常会比原来的大一些，以容纳更多的元素。这时，切片的指针和长度会指向新的底层数组，旧的底层数组会被垃圾回收。

扩容策略

我们先通过一个简单的例子来观察切片的动态特性。在这个例子中，我们可以看到切片在追加元素时如何动态调整其大小。

go
import "fmt"

func main() {
	slice := make([]int, 0, 4) // 初始化一个长度为0，容量为3的切片

	slice = append(slice, 1, 2) // 追加元素

	newSlice := append(slice, 3) // First

	fmt.Printf("First, slice = %v, Pointer = %p, len = %d, cap = %d\n", slice, slice, len(slice), cap(slice))
	fmt.Printf("First, newSlice = %v, Pointer = %p, len = %d, cap = %d\n", newSlice, newSlice, len(newSlice), cap(newSlice))

	slice = append(slice, 4) // Second

	fmt.Printf("Second, slice = %v, Pointer = %p, len = %d, cap = %d\n", slice, slice, len(slice), cap(slice))
	fmt.Printf("Second, newSlice = %v, Pointer = %p, len = %d, cap = %d\n", newSlice, newSlice, len(newSlice), cap(newSlice))

	slice = append(slice, 5, 6) // Third

	fmt.Printf("Third, slice = %v, Pointer = %p, len = %d, cap = %d\n", slice, slice, len(slice), cap(slice))
	fmt.Printf("Third, newSlice = %v, Pointer = %p, len = %d, cap = %d\n", newSlice, newSlice, len(newSlice), cap(newSlice))

	newSlice[1] = 10 // Fourth

	fmt.Printf("Fourth, slice = %v, Pointer = %p, len = %d, cap = %d\n", slice, slice, len(slice), cap(slice))
	fmt.Printf("Fourth, newSlice = %v, Pointer = %p, len = %d, cap = %d\n", newSlice, newSlice, len(newSlice), cap(newSlice))
}

// output
// First, slice = [1 2], Pointer = 0xc000132000, len = 2, cap = 4
// First, newSlice = [1 2 3], Pointer = 0xc000132000, len = 3, cap = 4
// Second, slice = [1 2 4], Pointer = 0xc000132000, len = 3, cap = 4
// Second, newSlice = [1 2 4], Pointer = 0xc000132000, len = 3, cap = 4
// Third, slice = [1 2 4 5 6], Pointer = 0xc0001240c0, len = 5, cap = 8
// Third, newSlice = [1 2 4], Pointer = 0xc000132000, len = 3, cap = 4
// Fourth, slice = [1 2 4 5 6], Pointer = 0xc0001240c0, len = 5, cap = 8
// Fourth, newSlice = [1 10 4], Pointer = 0xc000132000, len = 3, cap = 4
  • First: slice和newSlice底层数组是同一个，但是newSlice append的新元素并不会影响slice。
  • Second：slice append了4，指向底层数组的第三个元素变成了4，影响到了newSlice。
  • Third：slice append了5、6。此时，slice的len大于了cap，需要扩容，所以slice的底层数组发生了变化，slice指向了在内存中重新开辟的一个区域。所以，slice 和 newSlice的内容和地址都不一样了。
  • Fourth：由于上个步骤改了两个切片的底层数组指向，所以改变newSlice的第二个元素并没有影响slice。

这里也简单介绍下Go的切片扩容策略

  • 如果新申请容量（cap）大于 2 倍的旧容量（old.cap）：最终容量（newcap）就是新申请的容量（cap）。
  • 否则，如果旧切片的长度（old.len）小于 1024：最终容量（newcap）就是旧容量（old.cap）的两倍。
  • 否则，如果旧切片的长度（old.len）大于等于 1024：最终容量（newcap）从旧容量（old.cap）开始，循环增加原来的 1/4，直到最终容量（newcap）大于等于新申请的容量（cap）。
  • 如果最终容量（newcap）计算值溢出：最终容量（newcap）就是新申请容量（cap）。

垃圾回收

当一个切片不再被任何变量引用时，垃圾回收器会自动回收其占用的内存，包括其底层数组的内存（前提是没有其他切片或数据结构引用该底层数组）。切片的生命周期由垃圾回收器管理，当切片变量超出作用域或被显式设置为 nil 时，垃圾回收器将其标记为可回收对象。在下一次垃圾回收周期中，如果没有其他引用存在，相关内存会被释放。

内存泄漏

由于slice的底层是数组，很可能数组很大，但slice所取的元素数量却很小，这就导致数组占用的绝大多数空间是被浪费的。

比如下面的代码，如果传入的slice b是很大的，然后引用很小部分给全局量a，那么b未被引用的部分就不会被释放，造成了所谓的内存泄漏。只要全局量a在，b就不会被回收。

go
var a []int

func makSlice(b []int) {
	a = b[:1] // 和b共用一个底层数组
	return
}

解决方式：如果我们只用到一个slice的一小部分，那么底层的整个数组也将继续保存在内存中。当这个底层数组很大，或者类似这样的场景很多时，可能会造成内存增加，造成崩溃。在这样的情况下，我们可以将需要的分片复制到一个新的slice中去，减少内存的占用。

原理剖析

append 是 Go 语言中的一个内置函数，用户可以直接调用它来操作切片，而不需要引入额外的包。append 函数的定义位于 Go 语言的源码包 builtin 中的 builtin.go 文件中。虽然我们不能直接修改内置函数，但理解其工作原理可以帮助我们更好地使用它。

go
// The append built-in function appends elements to the end of a slice. If
// it has sufficient capacity, the destination is resliced to accommodate the
// new elements. If it does not, a new underlying array will be allocated.
// Append returns the updated slice. It is therefore necessary to store the
// result of append, often in the variable holding the slice itself:
//
//	slice = append(slice, elem1, elem2)
//	slice = append(slice, anotherSlice...)
//
// As a special case, it is legal to append a string to a byte slice, like this:
//
//	slice = append([]byte("hello "), "world"...)
func append(slice []Type, elems ...Type) []Type

该文件中仅仅定义了函数签名，并没有包含函数实现的任何代码。这里我想要深究一下，append究竟是如何实现的呢？

go
// append函数的简化实现（伪代码）
func append(slice []T, elems ...T) []T {
    var newSlice []T
    newLen := len(slice) + len(elems)
    if newLen <= cap(slice) {
        // 容量足够，直接追加
        newSlice = slice[:newLen]
    } else {
        // 容量不足，分配新的底层数组
        newCap := newLen
        if newCap < 2*len(slice) {
            newCap = 2 * len(slice)
        }
        newSlice = make([]T, newLen, newCap)
        copy(newSlice, slice)
    }
    copy(newSlice[len(slice):], elems)
    return newSlice
}

编译过程

Go 编译过程大致可以分为以下四个阶段：词法与语法分析、类型检查与抽象语法树（AST）转换、中间代码生成和生成最终的机器码。

  • 词法与语法分析：在这个阶段，编译器将源代码转换为标记（tokens），并检查代码的语法是否正确。
    • 词法分析：将源代码转换为一系列标记（tokens），每个标记代表一个基本的语法单元，如关键字、标识符、操作符和分隔符。词法分析器（lexer）负责扫描源代码并生成这些标记。
    • 语法分析：将标记序列组织成语法结构，生成抽象语法树（AST）。语法分析器（parser）根据语言的语法规则检查代码的结构是否正确，并构建 AST。
  • 类型检查与抽象语法树（AST）转换：在这个阶段，编译器对代码进行类型检查，并对 AST 进行转换和优化。
    • 类型检查：检查变量、函数和表达式的类型是否正确，确保类型安全。识别和处理类型转换、类型推断、接口实现等。
    • AST 转换：对 AST 进行转换和优化，例如常量折叠、死代码消除和内联展开等。生成更优化的中间表示（IR），为后续的中间代码生成做准备。
  • 中间代码生成：在这个阶段，编译器将优化后的 AST 转换为中间代码（Intermediate Representation, IR）。
    • 中间代码生成：将 AST 转换为中间代码，通常是一种与具体机器无关的中间表示。中间代码便于进一步的优化和分析，例如循环优化、寄存器分配等。
    • 中间代码优化：对中间代码进行各种优化，以提高最终生成的机器码的性能。包括数据流分析、控制流分析、常量传播、循环展开等。
  • 生成最终的机器码：在这个阶段，编译器将优化后的中间代码转换为目标机器的机器码。
    • 目标代码生成：将中间代码转换为目标机器的汇编代码或机器码。处理具体的硬件架构和指令集相关的优化，例如指令调度、寄存器分配等。
    • 链接与生成可执行文件：将生成的机器码与库和其他模块链接，生成最终的可执行文件。处理符号解析、重定位和地址修正等。

编译的第二和第三阶段的代码，分别是位于 cmd/compile/internal/typecheck/typecheck.go 下的类型检查逻辑

go
func typecheck1(n *Node, top int) (res *Node) {
    ...
    switch n.Op {
    case ir.OAPPEND:
		n := n.(*ir.CallExpr)
		return tcAppend(n)
}

位于cmd/compile/internal/walk/assign.go 下的抽象语法树转换逻辑

go
func walkAssign(init *ir.Nodes, n ir.Node) ir.Node {
    case ir.OAPPEND:
    // x = append(...)
        call := as.Y.(*ir.CallExpr)
        if call.Type().Elem().NotInHeap() {
            base.Errorf("%v can't be allocated in Go; it is incomplete (or unallocatable)", call.Type().Elem())
        }
        var r ir.Node
        switch {
        case isAppendOfMake(call):
            // x = append(y, make([]T, y)...)
            r = extendSlice(call, init)
        case call.IsDDD:
            r = appendSlice(call, init) // also works for append(slice, string).
        default:
            r = walkAppend(call, init, as)
        }
        as.Y = r
        if r.Op() == ir.OAPPEND {
            r := r.(*ir.CallExpr)
            // Left in place for back end.
            // Do not add a new write barrier.
            // Set up address of type for back end.
            r.X = reflectdata.AppendElemRType(base.Pos, r)
            return as
        }
    // Otherwise, lowered for race detector.
    // Treat as ordinary assignment.
	}
}

位于 cmd/compile/internal/ssagen/ssa.go的中间代码生成逻辑

go
// append converts an OAPPEND node to SSA.
// If inplace is false, it converts the OAPPEND expression n to an ssa.Value,
// adds it to s, and returns the Value.
// If inplace is true, it writes the result of the OAPPEND expression n
// back to the slice being appended to, and returns nil.
// inplace MUST be set to false if the slice can be SSA'd.
// Note: this code only handles fixed-count appends. Dotdotdot appends
// have already been rewritten at this point (by walk).
func (s *state) append(n *ir.CallExpr, inplace bool) *ssa.Value {
    // If inplace is false, process as expression "append(s, e1, e2, e3)":
	//
	// ptr, len, cap := s
	// len += 3
	// if uint(len) > uint(cap) {
	//     ptr, len, cap = growslice(ptr, len, cap, 3, typ)
	//     Note that len is unmodified by growslice.
	// }
	// // with write barriers, if needed:
	// *(ptr+(len-3)) = e1
	// *(ptr+(len-2)) = e2
	// *(ptr+(len-1)) = e3
	// return makeslice(ptr, len, cap)
	//
	//
	// If inplace is true, process as statement "s = append(s, e1, e2, e3)":
	//
	// a := &s
	// ptr, len, cap := s
	// len += 3
	// if uint(len) > uint(cap) {
	//    ptr, len, cap = growslice(ptr, len, cap, 3, typ)
	//    vardef(a)    // if necessary, advise liveness we are writing a new a
	//    *a.cap = cap // write before ptr to avoid a spill
	//    *a.ptr = ptr // with write barrier
	// }
	// *a.len = len
	// // with write barriers, if needed:
	// *(ptr+(len-3)) = e1
	// *(ptr+(len-2)) = e2
	// *(ptr+(len-1)) = e3
}

上面这个函数的入参 inplace 代表返回值是否覆盖原变量，如果是true，例如 slice = append(slice, 1, 2, 3) 语句，那么返回值会覆盖原变量。

不管 inpalce 是否为true，我们均会获取切片的数组指针、大小和容量，如果在追加元素后，切片新的大小大于原始容量，就会调用 runtime.growslice 对切片进行扩容，并将新的元素依次加入切片。 因此，通过 append向 元素类型为 int 的切片追加元素 1 可分为两种情况。

  • case1，切片的底层数组还有可容纳追加元素的空间。
  • case2，切片的底层数组已无可容纳追加元素的空间，需调用扩容函数，进行扩容。

扩容函数

前面提到追加操作时，当切片底层数组的剩余空间不足以容纳追加的元素，就会调用 growslice（实现在 runtime 包中）。growslice 函数的主要任务是分配一个新的底层数组，并将旧数组的数据复制到新数组中。其调用的入参 cap 为追加元素后切片的总长度。

go
// growslice函数的简化实现（伪代码）
func growslice(slice []T, newLen int) []T {
    oldCap := cap(slice)
    newCap := oldCap

    // 扩展容量，通常是原来容量的两倍
    if newLen > oldCap {
        newCap = oldCap * 2
        if newCap < newLen {
            newCap = newLen
        }
    }

    // 分配新的底层数组
    newSlice := make([]T, newLen, newCap)
    
    // 将旧数组的数据复制到新数组中
    copy(newSlice, slice)
    
    return newSlice
}

具体说来，我们可以根据逻辑分为三个部分。

  • 初步确定切片容量
go
func growslice(et *_type, old slice, cap int) slice {
    ...
    newcap := old.cap
    doublecap := newcap + newcap
    if cap > doublecap {
        newcap = cap
    } else {
        if old.len < 1024 {
            newcap = doublecap
        } else {
            // Check 0 < newcap to detect overflow
            // and prevent an infinite loop.
            for 0 < newcap && newcap < cap {
                newcap += newcap / 4
            }
            // Set newcap to the requested cap when
            // the newcap calculation overflowed.
            if newcap <= 0 {
                newcap = cap
            }
        }
    }
  ...
}

如果需要的容量 cap 超过原切片容量的两倍 doublecap，会直接使用需要的容量作为新容量newcap。否则，当原切片长度小于1024时，新切片的容量会直接翻倍。而当原切片的容量大于等于1024时，会反复地增加25%，直到新容量超过所需要的容量。

  • 计算容量所需内存大小

通过判断切片元素的字节大小是否为1，系统指针大小（32位为4，64位为8）或2的倍数，进入相应所需内存大小的计算逻辑。

go
var overflow bool
var lenmem, newlenmem, capmem uintptr
// Specialize for common values of et.size.
// For 1 we don't need any division/multiplication.
// For goarch.PtrSize, compiler will optimize division/multiplication into a shift by a constant.
// For powers of 2, use a variable shift.
switch {
case et.size == 1:
    lenmem = uintptr(oldLen)
    newlenmem = uintptr(newLen)
    capmem = roundupsize(uintptr(newcap))
    overflow = uintptr(newcap) > maxAlloc
    newcap = int(capmem)
case et.size == goarch.PtrSize:
    lenmem = uintptr(oldLen) * goarch.PtrSize
    newlenmem = uintptr(newLen) * goarch.PtrSize
    capmem = roundupsize(uintptr(newcap) * goarch.PtrSize)
    overflow = uintptr(newcap) > maxAlloc/goarch.PtrSize
    newcap = int(capmem / goarch.PtrSize)
case isPowerOfTwo(et.size):
    var shift uintptr
    if goarch.PtrSize == 8 {
        // Mask shift for better code generation.
        shift = uintptr(sys.TrailingZeros64(uint64(et.size))) & 63
    } else {
        shift = uintptr(sys.TrailingZeros32(uint32(et.size))) & 31
    }
    lenmem = uintptr(oldLen) << shift
    newlenmem = uintptr(newLen) << shift
    capmem = roundupsize(uintptr(newcap) << shift)
    overflow = uintptr(newcap) > (maxAlloc >> shift)
    newcap = int(capmem >> shift)
    capmem = uintptr(newcap) << shift
default:
    lenmem = uintptr(oldLen) * et.size
    newlenmem = uintptr(newLen) * et.size
    capmem, overflow = math.MulUintptr(et.size, uintptr(newcap))
    capmem = roundupsize(capmem)
    newcap = int(capmem / et.size)
    capmem = uintptr(newcap) * et.size
}

这里需要注意的是 roundupsize 函数，它根据输入期望大小 size ，返回 mallocgc 实际将分配的内存块的大小。

Go 语言的内存分配器在处理不同大小的内存分配请求时，使用了不同的策略来提高分配效率并减少内存碎片。roundupsize 函数是内存分配器中的一个关键函数，用于根据输入的期望大小（size）返回实际将分配的内存块大小。

具体来说，roundupsize 函数根据内存分配请求的大小（size），决定分配的内存块大小。如果请求的内存大小是小对象（小于 32KB），则将其向上取整到内存分配器的一个类（class）大小。如果是大对象，则将其向上取整到虚拟内存页大小（通常是 4KB）的倍数。

小对象内存分配 对于小对象（小于 32KB），内存分配器使用 class_to_size、size_to_class8 和 size_to_class128 数组来进行内存大小的向上取整。这些数组定义了不同大小类（class）的内存块大小，以便快速分配和减少内存碎片。

  • class_to_size 数组：存储每个大小类（class）对应的内存块大小。
  • size_to_class8 数组：针对小于 128 字节的内存请求，存储每个内存大小对应的大小类（class）。
  • size_to_class128 数组：针对 128 字节到 32KB 的内存请求，存储每个内存大小对应的大小类（class）。

通过这些数组，内存分配器可以快速确定要分配的内存块大小，减少内存碎片。

大对象内存分配 对于大对象（大于等于 32KB），内存分配器使用 alignUp 函数将请求的内存大小向上取整到虚拟内存页大小（通常是 4KB）的倍数。

  • _PageSize：虚拟内存页大小，通常是 4KB。
  • alignUp 函数：将请求的内存大小向上取整到 _PageSize 的倍数。

总结 通过 roundupsize 函数，Go 语言的内存分配器能够根据请求的内存大小返回实际将分配的内存块大小。对于小对象，使用 class_to_size、size_to_class8 和 size_to_class128 数组来快速确定内存块大小；对于大对象，使用 alignUp 函数将请求的内存大小向上取整到虚拟内存页大小的倍数。这些策略有助于提高内存分配效率并减少内存碎片。

  • 内存分配
go
	if overflow || capmem > maxAlloc {
		panic(errorString("growslice: len out of range"))
	}

	var p unsafe.Pointer
	if et.ptrdata == 0 {
		p = mallocgc(capmem, nil, false)
		// The append() that calls growslice is going to overwrite from oldLen to newLen.
		// Only clear the part that will not be overwritten.
		// The reflect_growslice() that calls growslice will manually clear
		// the region not cleared here.
		memclrNoHeapPointers(add(p, newlenmem), capmem-newlenmem)
	} else {
		// Note: can't use rawmem (which avoids zeroing of memory), because then GC can scan uninitialized memory.
		p = mallocgc(capmem, et, true)
		if lenmem > 0 && writeBarrier.enabled {
			// Only shade the pointers in oldPtr since we know the destination slice p
			// only contains nil pointers because it has been cleared during alloc.
			bulkBarrierPreWriteSrcOnly(uintptr(p), uintptr(oldPtr), lenmem-et.size+et.ptrdata)
		}
	}
	//if oldPtr != nil {
	//	println(100)
	//} else {
	//	println(10000)
	//}

	memmove(p, oldPtr, lenmem)

	return slice{p, newLen, newcap}

如果上个环节中，造成了溢出或者期望分配的内存超过最大分配限制，会引起 panic。

mallocgc 函数分配一个大小为之前计算得到的 capmem 对象。如果是小对象，则直接从当前G所在P的缓存空闲列表中分配；如果是大对象，则从堆上进行分配。同时，如果切片中的元素不是指针类型，那么会调用 memclrNoHeapPointers 将超出切片当前长度的位置清空；如果元素是指针类型，且原有切片元素个数不为 0 并可以打开写屏障时，需要调用 bulkBarrierPreWriteSrcOnly 将旧切片指针标记隐藏，在新切片中保存为nil指针。最后使用memmove将原数组内存中的内容拷贝到新申请的内存中，并将新的内存指向指针p 和旧的长度值，新的容量值赋值给新的 slice 并返回。

注意，在 growslice 完成后，只是把旧有数据拷贝到了新的内存中去，计算得到新的 slice 容量大小，此时新的slice已经拷贝了旧的slice数据，并且其底层数组有充足的剩余空间追加数据。后续只需拷贝追加数据至剩余空间，并修改 len 值即可。

性能优化

由于切片在内存管理上的特殊性，在某些情况下（频繁读写切片）可能对性能影响很大。我们通常会采取下面这些的优化措施使程序运行得更加高效。

预分配与扩容

在切片容量不足时，append 操作会导致底层数组的重新分配和复制，这会带来显著的性能开销。所以在创建切片时，预分配足够的容量可以避免多次扩容操作。

slice := make([]int, 0, 100)

避免不必要的切片操作

在处理切片时，不必要的切片操作会增加额外的开销。例如，频繁地创建切片的子集，或者在循环中不断地追加元素，都可能导致性能下降。

每次创建切片的子集都会生成一个新的切片头部（包含指向底层数组的指针、长度和容量），但底层数组不会被复制。如果子切片的生命周期超过原始切片，可能会导致底层数组无法被垃圾回收，从而增加内存使用。

并发安全

切片不支持并发读写，所以并不是线程安全的，使用多个 goroutine 对类型为 slice 的变量进行操作，每次输出的值大概率都不会一样，与预期结果也不一致。

因为当多个 goroutine 并发地对同一个切片执行 append 操作时，如果底层数组的容量不足而导致切片扩容，就会出现数据竞争的问题。这会导致多个 goroutine 的 append 结果被覆盖，从而导致最终切片的长度小于预期的 n。

数据竞争问题

  • 多个 goroutine 同时检查切片的容量，发现容量不足。
  • 多个 goroutine 同时分配新的底层数组，并将旧数组的数据复制到新数组中。
  • 最终只有一个 goroutine 的 append 结果被保留，其他 goroutine 的结果被覆盖。

常见的解决方案包括使用互斥锁（sync.Mutex）或者通道（chan）来同步对切片的访问。

读写锁

在多线程环境中，为了避免数据竞争问题，可以使用互斥锁（mutex）来保护对切片的访问。

go
import (
    "fmt"
    "sync"
)

func main() {
    a := make([]int, 0)
    
    var lock sync.Mutex
    
	var wg sync.WaitGroup
    
	for i := 0; i < 1000; i++ {
		wg.Add(1)
		go func(i int) {
            lock.Lock()
            defer lock.Unlock()
			a = append(a, i)
			wg.Done()
		}(i)
	}
    
	wg.Wait()
	fmt.Println((len(a))) // 1000。如果不加锁，大概率是小于1000的9xx

}

Channle

通过通道来同步对切片的访问，将所有的 append 操作都交给一个专门的 goroutine 来处理。通过通道实现切片线程安全，适合对性能要求高的场景。

go
import (
    "fmt"
)

func main() {
	buffer := make(chan int)
	a := make([]int, 0)
    
	// 消费者
	go func() {
		for v := range buffer {
			a = append(a, v)
		}
	}()
    
	// 生产者
	var wg sync.WaitGroup
	for i := 0; i < 10000; i++ {
		wg.Add(1)
		go func(i int) {
			defer wg.Done()
			buffer <- i
		}(i)
	}
	wg.Wait()
    
	fmt.Println(len(a)) // 10000
}

高级应用

切片还可以用于实现更复杂的数据结构和算法，以下是一些切片的高级应用示例。

队列

切片可以很容易地实现队列（FIFO）的功能。通过在切片的末尾追加元素，并从对首移除元素，我们可以创建一个队列。

go
import "fmt"

type Queue struct {
    slice []int
}

func (q *Queue) Enqueue(value int) {
    q.slice = append(q.slice, value)
}

func (q *Queue) Dequeue() (int, bool) {
    if len(q.slice) == 0 {
        return 0, false
    }
    value := q.slice[0]
    q.slice = q.slice[1:]
    return value, true
}

func main() {
    q := Queue{}
    
    q.Enqueue(1)
    q.Enqueue(2)

    for {
        value, ok := q.Dequeue()
        if !ok {
            break
        }
        fmt.Println(value)
    }
}

栈

在下面这个例子中，我们定义了一个Stack结构体，它包含一个切片items，用于存储栈中的元素。我们实现了 Pus h和 Pop 方法来操作栈。

go
import "fmt"

type Stack struct {
    items []interface{}
}

func (s *Stack) Push(item interface{}) {
    s.items = append(s.items, item)
}

func (s *Stack) Pop() interface{} {
    if len(s.items) == 0 {
        return nil
    }
    item := s.items[len(s.items)-1]
    s.items = s.items[:len(s.items)-1]
    return item
}

func main() {
    stack := Stack{}
    stack.Push(1)
    stack.Push("hello")
    stack.Push(true)

    for {
        item := stack.Pop()
        if item == nil {
            break
        }
        fmt.Println(item)
    }
}

二叉搜索树

在下面这个例子中，我们定义了一个BSTNode结构体来表示二叉搜索树的节点，并实现了插入和搜索功能。

go
type BSTNode struct {
    Value int
    Left *BSTNode
    Right *BSTNode
}

// BSTInsert 用于向BST中插入新值
func BSTInsert(root *BSTNode, value int) {
    if root == nil {
        return &BSTNode{Value: value}
    }
    if value < root.Value {
        root.Left = BSTInsert(root.Left, value)
    } else if value > root.Value {
        root.Right = BSTInsert(root.Right, value)
    }
    return root
}

// BSTSearch 用于在BST中搜索特定值
func BSTSearch(root *BSTNode, value int) bool {
    if root == nil {
        return false
    }
    if root.Value == value {
        return true
    }
    if value < root.Value {
        return BSTSearch(root.Left, value)
    }
    return BSTSearch(root.Right, value)
}

func main() {
    root := &BSTNode{Value: 2}
    
    BSTInsert(root, 1)
    
    BSTInsert(root, 3)
    
    fmt.Println(BSTSearch(root, 1)) // 输出：true
    
    fmt.Println(BSTSearch(root, 3)) // 输出：false
}

迭代器

在处理大型数据集时，使用迭代器可以提高代码的可读性和效率。Go语言的切片没有内置的迭代器，但我们可以通过编写自定义函数来模拟迭代器的行为。以下是一个简单的切片迭代器的示例，它允许我们遍历切片中的每个元素，而不需要直接操作索引。

go
import "fmt"

// SliceIterator 是一个自定义的切片迭代器
type SliceIterator struct {
    slice []int
    index int
}

// NewSliceIterator 创建一个新的切片迭代器
func NewSliceIterator(slice []int) *SliceIterator {
    return &SliceIterator{slice: slice, index: 0}
}

// HasNext 检查迭代器是否还有更多的元素
func (i *SliceIterator) HasNext() bool {
    return i.index < len(i.slice)
}

// Next 返回下一个元素，并更新迭代器的索引
func (i *SliceIterator) Next() int {
    if i.HasNext() {
        value := i.slice[i.index]
        i.index++
        return value
    }
    panic("没有更多元素")
}

func main() {
    slice := []int{1, 2, 3, 4, 5}
    iterator := NewSliceIterator(slice)

    for iterator.HasNext() {
        fmt.Println(iterator.Next())
    }
}

在这个例子中，我们创建了一个SliceIterator结构体，它包含了切片和当前索引。通过HasNext和Next方法，我们可以遍历切片中的所有元素。

数据流

在处理数据流时，切片可以作为一种缓冲机制，帮助我们管理数据的读取和写入。这在文件操作、网络通信等场景中尤为常见。以下是一个使用切片读取文件内容的示例，在读取或写入文件时，我们使用切片来临时存储数据块。

go
import (
    "bufio"
    "fmt"
    "os"
)

func main() {
    file, err := os.Open("test.txt")
    if err != nil {
        panic(err)
    }
    defer file.Close()

    reader := bufio.NewReader(file)

    // 使用切片作为缓冲区读取文件
    buffer := make([]byte, 1024)
    for {
        n, err := reader.Read(buffer)
        if err != nil {
            if err != nil {
                panic(err)
            }
            break
        }

        // 处理读取的数据
        fmt.Print(string(buffer[:n]))
    }
}

在这个例子中，我们使用bufio.Reader来逐块读取文件，每次读取1024字节到切片buffer中，并处理这些数据。

本文作者:sora

本文链接:

版权声明:本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！