slice

TIP

Đọc bài viết này cần kiến thức về thư viện chuẩn unsafe.

Slice có lẽ là cấu trúc dữ liệu được sử dụng phổ biến nhất trong ngôn ngữ Go, hầu như có thể thấy nó ở khắp mọi nơi. Về cách sử dụng cơ bản của nó đã được trình bày trong phần nhập môn ngôn ngữ, dưới đây hãy xem xem bên trong nó trông như thế nào và nó hoạt động ra sao.

Cấu trúc

Về việc triển khai slice, mã nguồn của nó nằm trong file runtime/slice.go. Trong runtime, slice tồn tại dưới dạng một cấu trúc, kiểu là runtime.slice, như dưới đây.

type slice struct {
  array unsafe.Pointer
  len   int
  cap   int
}

Cấu trúc này chỉ có ba trường:

array, con trỏ trỏ đến mảng底层
len, độ dài của slice, chỉ số lượng phần tử đã có trong mảng
cap, dung lượng của slice, chỉ tổng số phần tử mà mảng có thể chứa

Từ thông tin trên có thể biết rằng, việc triển khai底层 của slice vẫn phụ thuộc vào mảng, thông thường nó chỉ là một cấu trúc, chỉ giữ tham chiếu đến mảng, và ghi lại dung lượng và độ dài. Như vậy chi phí truyền slice sẽ rất thấp, chỉ cần sao chép tham chiếu của dữ liệu, không cần sao chép tất cả dữ liệu, và khi sử dụng len và cap để lấy độ dài và dung lượng của slice,就等于 là đang lấy giá trị trường của nó, không cần phải duyệt mảng.

Tuy nhiên điều này cũng mang lại một số vấn đề khó phát hiện, xem ví dụ sau:

package main

import "fmt"

func main() {
  s := make([]int, 0, 10)
  s = append(s, 1, 2, 3, 4, 5)
  s1 := s[:]
  s1[0] = 2
  fmt.Println(s)
}

[2 2 3 4 5]

Trong code trên, s1 được tạo ra một slice mới thông qua cách cắt, nhưng nó và slice nguồn đều tham chiếu đến cùng một mảng底层, việc sửa đổi dữ liệu trong s1 cũng khiến s thay đổi. Vì vậy khi sao chép slice nên sử dụng hàm copy, slice được sao chép bởi hàm này không liên quan gì đến slice trước. Hãy xem thêm một ví dụ:

func main() {
  s := make([]int, 0, 10)
  s = append(s, 1, 2, 3, 4, 5)
  s1 := s[:]
  s1 = append(s1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
  s1[0] = 10
  fmt.Println(s)
  fmt.Println(s1)
}

[1 2 3 4 5]
[10 2 3 4 5 1 2 3 4 5 6 7 8 9 10]

Cũng là sử dụng cách cắt để sao chép slice, nhưng lần này không gây ảnh hưởng đến slice nguồn. Ban đầu s1 và s确实 hướng đến cùng một mảng, nhưng sau đó thêm quá nhiều phần tử vào s1 vượt quá số lượng mà mảng có thể chứa, nên đã phân phối một mảng mới lớn hơn để chứa phần tử, vì vậy cuối cùng chúng hướng đến hai mảng khác nhau rồi. Bạn có nghĩ là không có vấn đề gì nữa không, vậy hãy xem thêm một ví dụ:

package main

import "fmt"

func main() {
  s := make([]int, 0, 10)
  appendData(s, 1, 2, 3, 4, 5, 6)
  fmt.Println(s)
}

func appendData[T comparable](s []T, data ...T) {
  s = append(s, data...)
}

[]

Rõ ràng đã thêm phần tử, nhưng in ra lại là slice rỗng, thực tế dữ liệu确实 đã được thêm vào slice, chỉ là được ghi vào mảng底层. Trong Go tham số hàm là truyền theo giá trị, nên tham số s thực tế là bản sao của cấu trúc slice nguồn, và thao tác append sau khi thêm phần tử sẽ trả về một cấu trúc slice đã cập nhật độ dài, chỉ là gán cho tham số s chứ không phải slice nguồn s, hai cái其实 không có liên hệ gì.

Đối với một slice而言, vị trí bắt đầu mà nó có thể truy cập và sửa đổi phụ thuộc vào vị trí tham chiếu đến mảng, độ lệch phụ thuộc vào độ dài được ghi lại trong cấu trúc. Con trỏ trong cấu trúc ngoài có thể hướng đến đầu cũng có thể hướng đến giữa mảng, như hình dưới đây.

Một mảng底层 có thể được nhiều slice tham chiếu, và vị trí và phạm vi tham chiếu có thể khác nhau, như hình trên, tình huống này thường xuất hiện khi cắt slice, tương tự như code dưới đây:

s := make([]int, 0, 10)
s1 := s[:4]
s2 := s[4:6]
s3 := s[7:]

Khi cắt, dung lượng của slice mới được tạo bằng độ dài mảng trừ đi vị trí bắt đầu mà slice mới tham chiếu. Ví dụ dung lượng của slice được tạo bởi s[4:6] là 6 = 10 - 4. Đương nhiên, phạm vi tham chiếu của slice cũng không nhất thiết phải liền kề, cũng có thể đan xen nhau, nhưng điều này sẽ gây ra rắc rối rất lớn, có thể dữ liệu của slice hiện tại bị slice khác sửa đổi mà không hay biết, như slice màu tím trong hình trên, nếu sử dụng append để thêm phần tử sau này, có thể sẽ ghi đè lên dữ liệu của slice màu xanh lá và slice màu xanh dương. Để tránh tình huống này, Go cho phép thiết lập phạm vi dung lượng khi cắt, cú pháp như sau:

s4 = s[4:6:6]

Trong trường hợp này, dung lượng của nó bị giới hạn ở 2, thì thêm phần tử sẽ kích hoạt mở rộng, sau khi mở rộng sẽ là một mảng mới, không liên quan đến mảng nguồn, sẽ không có ảnh hưởng. Bạn nghĩ vấn đề về slice đến đây là hết sao,其实 không, hãy xem thêm một ví dụ:

package main

import "fmt"

func main() {
  s := make([]int, 0, 10)
  // Số lượng phần tử thêm vào vừa lớn hơn dung lượng
  appendData(s, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
  fmt.Println(s)
}

func appendData[T comparable](s []T, data ...T) {
  s = append(s, data...)
}

[]

Code không khác gì ví dụ trước, chỉ sửa đổi tham số đầu vào, để số lượng phần tử thêm vào vừa lớn hơn dung lượng của slice, như vậy khi thêm sẽ kích hoạt mở rộng, như vậy dữ liệu không những không được thêm vào slice nguồn s, mà ngay cả mảng底层 mà nó hướng đến cũng không được ghi dữ liệu, chúng ta có thể xác nhận điều này thông qua con trỏ unsafe, code như sau:

package main

import (
  "fmt"
  "unsafe"
)

func main() {
  s := make([]int, 0, 10)

  // Số lượng phần tử thêm vào vừa lớn hơn dung lượng
  appendData(s, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
  fmt.Println("ori slice", unsafe.SliceData(s))
  unsafeIterator(unsafe.Pointer(unsafe.SliceData(s)), cap(s))
}

func appendData[T comparable](s []T, data ...T) {
  s = append(s, data...)
  fmt.Println("new slice", unsafe.SliceData(s))
  unsafeIterator(unsafe.Pointer(unsafe.SliceData(s)), cap(s))
}

func unsafeIterator(ptr unsafe.Pointer, offset int) {
  for ptr, i := ptr, 0; i < offset; ptr, i = unsafe.Add(ptr, unsafe.Sizeof(int(0))), i+1 {
    elem := *(*int)(ptr)
    fmt.Printf("%d, ", elem)
  }
  fmt.Println()
}

new slice 0xc0000200a0
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 0, 0, 0, 0, 0, 0, 0, 0, 0,
ori slice 0xc000018190
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

Có thể thấy rằng, mảng底层 của slice nguồn trống rỗng, không có gì cả, dữ liệu đều được ghi vào mảng mới, nhưng không liên quan gì đến slice nguồn, vì cho dù append trả về tham chiếu mới, thì sửa đổi cũng chỉ là giá trị của tham số hình thức s, không ảnh hưởng đến slice nguồn s. Slice với tư cách là cấu trúc确实 có thể khiến nó rất nhẹ, nhưng vấn đề như trên cũng không thể bỏ qua, đặc biệt là trong code thực tế những vấn đề này thường ẩn rất sâu, khó bị phát hiện.

Tạo

Trong runtime, việc tạo slice bằng hàm make được thực hiện bởi runtime.makeslice, logic của nó khá đơn giản, chữ ký hàm như sau:

func makeslice(et *_type, len, cap int) unsafe.Pointer

Nó nhận ba tham số: kiểu phần tử, độ dài, dung lượng, sau đó trả về một con trỏ trỏ đến mảng底层, code của nó như sau:

func makeslice(et *_type, len, cap int) unsafe.Pointer {
    // Tính toán tổng bộ nhớ cần thiết, nếu quá lớn sẽ dẫn đến tràn số
    // mem = sizeof(et) * cap
  mem, overflow := math.MulUintptr(et.Size_, uintptr(cap))
  if overflow || mem > maxAlloc || len < 0 || len > cap {
        // mem = sizeof(et) * len
    mem, overflow := math.MulUintptr(et.Size_, uintptr(len))
    if overflow || mem > maxAlloc || len < 0 {
      panicmakeslicelen()
    }
    panicmakeslicecap()
  }

    // Nếu không có vấn đề thì phân phối bộ nhớ
  return mallocgc(mem, et, true)
}

Có thể thấy logic rất đơn giản, tổng cộng chỉ làm hai việc:

Tính toán bộ nhớ cần thiết
Phân phối không gian bộ nhớ

Nếu kiểm tra điều kiện thất bại, sẽ panic trực tiếp:

Khi tính toán bộ nhớ bị tràn số
Kết quả tính toán lớn hơn bộ nhớ tối đa có thể phân phối
Độ dài và dung lượng không hợp lệ

Nếu bộ nhớ tính được lớn hơn 32KB, sẽ phân phối nó lên heap, sau đó sẽ trả về một con trỏ trỏ đến mảng底层, việc xây dựng cấu trúc runtime.slice không do hàm makeslice hoàn thành. Thực tế, việc xây dựng cấu trúc được hoàn thành trong thời gian biên dịch, hàm makeslice trong runtime chỉ负责 phân phối bộ nhớ, tương tự như code dưới đây:

var s runtime.slice
s.array = runtime.makeslice(type,len,cap)
s.len = len
s.cap = cap

Nếu感兴趣的话可以去看看生成的中间代码，跟这个类似。

name s.ptr[*int]: v11
name s.len[int]: v7
name s.cap[int]: v8

Nếu sử dụng mảng để tạo slice, ví dụ như dưới đây:

var arr [5]int
s := arr[:]

Quá trình này tương tự như code dưới đây:

var arr [5]int
var s runtime.slice
s.array = &arr
s.len = len
s.cap = cap

Go sẽ trực tiếp sử dụng mảng đó làm mảng底层 của slice, nên việc sửa đổi dữ liệu trong slice cũng sẽ ảnh hưởng đến dữ liệu của mảng. Khi sử dụng mảng để tạo slice, độ dài bằng hight-low, dung lượng bằng max-low, trong đó max mặc định là độ dài mảng, hoặc cũng có thể chỉ định dung lượng thủ công khi cắt, ví dụ:

var arr [5]int
s := arr[2:3:4]

Truy cập

Truy cập slice cũng sử dụng chỉ số dưới giống như truy cập mảng:

elem := s[i]

Thao tác truy cập slice đã được hoàn thành trong thời gian biên dịch, thông qua cách生成 mã trung gian để truy cập, code cuối cùng được生成 có thể hiểu là code giả sau:

p := s.ptr
e := *(p + sizeof(elem(s)) * i)

Thực tế là thông qua thao tác di chuyển con trỏ để truy cập phần tử có chỉ số tương ứng, tương ứng với phần code sau trong hàm cmd/compile/internal/ssagen.exprCheckPtr:

case ir.OINDEX:
    n := n.(*ir.IndexExpr)
    switch {
    case n.X.Type().IsSlice():
        // Dịch chuyển con trỏ
        p := s.addr(n)
        return s.load(n.X.Type().Elem(), p)

Khi sử dụng hàm len và cap để truy cập độ dài và dung lượng của slice, cũng là đạo lý tương tự, cũng là phần code trong hàm cmd/compile/internal/ssagen.exprCheckPtr:

case ir.OLEN, ir.OCAP:
    n := n.(*ir.UnaryExpr)
    switch {
    case n.X.Type().IsSlice():
        op := ssa.OpSliceLen
        if n.Op() == ir.OCAP {
            op = ssa.OpSliceCap
        }
        return s.newValue1(op, types.Types[types.TINT], s.expr(n.X))

Trong code thực tế được生成, thông qua di chuyển con trỏ để truy cập trường len trong cấu trúc slice, có thể hiểu là code giả sau:

p := &s
len := *(p + 8)
cap := *(p + 16)

Giả sử hiện có code như sau:

func lenAndCap(s []int) (int, int) {
  l := len(s)
  c := cap(s)
  return l, c
}

Thì trong một giai đoạn nào đó của code trung gian được生成 rất có thể dài như thế này:

v9 (+9) = ArgIntReg <int> {s+8} [1] : BX (l[int], s+8[int])
v10 (+10) = ArgIntReg <int> {s+16} [2] : CX (c[int], s+16[int])
v1 (?) = InitMem <mem>
v3 (11) = Copy <int> v9 : AX
v4 (11) = Copy <int> v10 : BX
v11 (+11) = MakeResult <int,int,mem> v3 v4 v1 : <>
Ret v11 (+11)
name l[int]: v9
name c[int]: v10
name s+16[int]: v10
name s+8[int]: v9

Từ trên có thể nhìn ra, một cái cộng 8, một cái cộng 16, rất rõ ràng là thông qua dịch chuyển con trỏ để truy cập trường slice.

Nếu có thể suy đoán ra độ dài và dung lượng của nó trong thời gian biên dịch, thì sẽ không cần dịch chuyển con trỏ để lấy giá trị trong runtime, ví dụ tình huống dưới đây就不 cần di chuyển con trỏ:

s := make([]int, 10, 20)
l := len(s)
c := cap(s)

Giá trị của biến l và s sẽ được trực tiếp thay thế thành 10 và 20.

Ghi

Sửa đổi

s := make([]int, 10)
s[0] = 100

Khi sửa đổi giá trị của slice thông qua chỉ số dưới, trong thời gian biên dịch sẽ生成 code giả tương tự như sau thông qua thao tác OpStore:

p := &s
l := *(p + 8)
if !IsInBounds(l,i) {
    panic()
}
ptr := (s.ptr + i * sizeof(elem) * i)
*ptr = val

Trong một giai đoạn nào đó của code trung gian được生成 rất có thể dài như thế này:

v1 (?) = InitMem <mem>
v5 (8) = Arg <[]int> {s} (s[[]int])
v6 (?) = Const64 <int> [100]
v7 (?) = Const64 <int> [0]
v8 (+9) = SliceLen <int> v5
v9 (9) = IsInBounds <bool> v7 v8
v14 (?) = Const64 <int64> [0]
v12 (9) = SlicePtr <*int> v5
v15 (9) = Store <mem> {int} v12 v6 v1
v11 (9) = PanicBounds <mem> [0] v7 v7 v1
Exit v11 (9)

name s[[]int]: v5
name s[*int]:
name s+8[int]:

Có thể thấy code truy cập độ dài slice để kiểm tra chỉ số có hợp lệ không, cuối cùng thông qua di chuyển con trỏ để lưu trữ phần tử.

Thêm

Thông qua hàm append có thể thêm phần tử vào slice:

var s []int
s = append(s, 1, 2, 3)

Sau khi thêm phần tử, nó sẽ trả về một cấu trúc slice mới, nếu không mở rộng thì so với slice nguồn chỉ cập nhật độ dài, nếu không sẽ hướng đến một mảng mới. Về vấn đề sử dụng append đã được trình bày rất chi tiết trong phần Cấu trúc, không trình bày lại nữa, dưới đây sẽ tập trung vào append hoạt động như thế nào.

Trong runtime, không có hàm tương tự như runtime.appendslice tương ứng với nó, việc thêm phần tử thực tế đã được thực hiện trong thời gian biên dịch, hàm append sẽ được triển khai thành code trung gian tương ứng, code phán đoán nằm trong hàm cmd/compile/internal/walk/assign.go walkassign:

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

Có thể thấy chia thành ba tình huống:

Thêm một số phần tử
Thêm một slice
Thêm một slice được tạo tạm thời

Dưới đây sẽ nói xem code được生成 trông như thế nào, để hiểu append thực tế hoạt động ra sao, nếu感兴趣 về quá trình生成 code có thể tự tìm hiểu.

Thêm phần tử

s = append(s, x, y, z)

Nếu chỉ thêm một số lượng hữu hạn phần tử, sẽ được hàm walkAppend triển khai thành code sau:

// Số lượng phần tử cần thêm
const argc = len(args) - 1
newLen := s.len + argc

// Có cần mở rộng không
if uint(newLen) <= uint(s.cap) {
  s = s[:newLen]
} else {
  s = growslice(s.ptr, newLen, s.cap, argc, elemType)
}

s[s.len - argc] = x
s[s.len - argc + 1] = y
s[s.len - argc + 2] = z

Đầu tiên tính toán số lượng phần tử cần thêm, sau đó phán đoán có cần mở rộng không, cuối cùng gán giá trị từng cái một.

Thêm slice

s = append(s, s1...)

Nếu trực tiếp thêm một slice, sẽ được hàm appendSlice triển khai thành code sau:

newLen := s.len + s1.len
// Compare as uint so growslice can panic on overflow.
if uint(newLen) <= uint(s.cap) {
  s = s[:newLen]
} else {
  s = growslice(s.ptr, s.len, s.cap, s1.len, T)
}
memmove(&s[s.len-s1.len], &s1[0], s1.len*sizeof(T))

Vẫn như trước, tính toán độ dài mới, phán đoán có cần mở rộng không, khác biệt là Go không thêm từng phần tử của slice nguồn, mà chọn cách trực tiếp sao chép bộ nhớ.

Thêm slice tạm thời

s = append(s, make([]T, l2)...)

Nếu thêm một slice được tạo tạm thời, sẽ được hàm extendslice triển khai thành code sau:

if l2 >= 0 {
// Empty if block here for more meaningful node.SetLikely(true)
} else {
  panicmakeslicelen()
}
s := l1
n := len(s) + l2

if uint(n) <= uint(cap(s)) {
  s = s[:n]
} else {
  s = growslice(T, s.ptr, n, s.cap, l2, T)
}
// clear the new portion of the underlying array.
hp := &s[len(s)-l2]
hn := l2 * sizeof(T)
memclr(hp, hn)

Đối với slice được thêm tạm thời, Go sẽ lấy độ dài của slice tạm thời, nếu dung lượng của slice hiện tại không đủ để chứa, sẽ thử mở rộng, sau đó còn xóa bộ nhớ tương ứng.

Mở rộng

Từ nội dung phần cấu trúc có thể biết rằng,底层 của slice vẫn là một mảng, mảng là cấu trúc dữ liệu có độ dài cố định, nhưng độ dài slice có thể thay đổi. Khi dung lượng mảng không đủ, slice sẽ xin một vùng bộ nhớ lớn hơn để chứa dữ liệu,也就是 một mảng mới, sau đó sao chép dữ liệu cũ sang, rồi tham chiếu của slice sẽ hướng đến mảng mới, quá trình này được gọi là mở rộng. Việc mở rộng được hoàn thành bởi hàm runtime.growslice trong runtime, chữ ký hàm như sau:

func growslice(oldPtr unsafe.Pointer, newLen, oldCap, num int, et *_type) slice

Giải thích đơn giản các tham số:

oldPtr, con trỏ trỏ đến mảng cũ
newLen, độ dài của mảng mới, newLen = oldLen + num
oldCap, dung lượng của slice cũ,也就是 bằng độ dài của mảng cũ
et, kiểu phần tử

Giá trị trả về của nó trả về một slice mới, slice mới này không liên quan gì đến slice ban đầu, điểm chung duy nhất là dữ liệu lưu giữ giống nhau.

var s []int
s = append(s, elems...)

Khi sử dụng append để thêm phần tử, sẽ yêu cầu giá trị trả về của nó ghi đè slice ban đầu, nếu xảy ra mở rộng thì trả về là một slice mới.

Khi mở rộng, đầu tiên cần xác định độ dài và dung lượng mới, tương ứng với code dưới đây:

oldLen := newLen - num
if newLen < 0 {
    panic(errorString("growslice: len out of range"))
}

if et.Size_ == 0 {
    return slice{unsafe.Pointer(&zerobase), newLen, newLen}
}

newcap := oldCap
// Gấp đôi dung lượng
doublecap := newcap + newcap
if newLen > doublecap {
    newcap = newLen
} else {
    const threshold = 256
    if oldCap < threshold {
        newcap = doublecap
    } else {
        for 0 < newcap && newcap < newLen {
            // newcap += 0.25 * newcap + 192
            newcap += (newcap + 3*threshold) / 4
        }
        // Tràn số
        if newcap <= 0 {
            newcap = newLen
        }
    }
}

Từ code trên có thể biết, đối với slice có dung lượng nhỏ hơn 256, dung lượng tăng gấp đôi, còn slice có dung lượng lớn hơn hoặc bằng 256, thì ít nhất sẽ là 1.25 lần dung lượng ban đầu, khi slice hiện tại nhỏ, mỗi lần đều trực tiếp tăng gấp đôi, có thể tránh mở rộng thường xuyên, khi slice lớn, tỷ lệ mở rộng sẽ giảm, tránh xin quá nhiều bộ nhớ gây lãng phí.

Sau khi có được độ dài và dung lượng mới,再 tính toán bộ nhớ cần thiết, tương ứng với code sau:

var overflow bool
var lenmem, newlenmem, capmem uintptr
switch {
    ...
    ...
  default:
    lenmem = uintptr(oldLen) * et.Size_
    newlenmem = uintptr(newLen) * et.Size_
    capmem, overflow = math.MulUintptr(et.Size_, uintptr(newcap))
    capmem = roundupsize(capmem)
    // Dung lượng cuối cùng
    newcap = int(capmem / et.Size_)
    capmem = uintptr(newcap) * et.Size_
}

if overflow || capmem > maxAlloc {
    panic(errorString("growslice: len out of range"))
}

Công thức tính bộ nhớ là mem = cap * sizeof(et), để tiện cho việc căn chỉnh bộ nhớ, trong quá trình sẽ lấy bộ nhớ tính được làm tròn lên thành lũy thừa nguyên của 2, và tính toán lại dung lượng mới. Nếu dung lượng mới quá lớn导致 tính toán bị tràn số, hoặc bộ nhớ mới vượt quá bộ nhớ tối đa có thể phân phối, sẽ panic.

var p unsafe.Pointer
// Phân phối bộ nhớ
p = mallocgc(capmem, nil, false)
memclrNoHeapPointers(add(p, newlenmem), capmem-newlenmem)

memmove(p, oldPtr, lenmem)
return slice{p, newLen, newcap}

Sau khi tính toán ra kết quả cần thiết, sẽ phân phối bộ nhớ có kích thước chỉ định, sau đó xóa bộ nhớ trong khoảng từ newLen đến newCap, rồi sao chép dữ liệu của mảng cũ sang slice mới, cuối cùng xây dựng cấu trúc slice.

Sao chép

src := make([]int, 10)
dst := make([]int, 20)
copy(dst, src)

Khi sử dụng hàm copy để sao chép slice, sẽ do cmd/compile/internal/walk.walkcopy quyết định sao chép bằng cách nào trong thời gian biên dịch, nếu gọi trong runtime, sẽ dùng đến hàm runtime.slicecopy, hàm này负责 sao chép slice, chữ ký hàm như sau:

func slicecopy(toPtr unsafe.Pointer, toLen int, fromPtr unsafe.Pointer, fromLen int, width uintptr) int

Nó nhận con trỏ và độ dài của slice nguồn và slice đích,以及 độ dài cần sao chép width. Logic của hàm này rất đơn giản, như sau:

func slicecopy(toPtr unsafe.Pointer, toLen int, fromPtr unsafe.Pointer, fromLen int, width uintptr) int {
  if fromLen == 0 || toLen == 0 {
    return 0
  }

  n := fromLen
  if toLen < n {
    n = toLen
  }

  if width == 0 {
    return n
  }

  // Tính toán số byte cần sao chép
  size := uintptr(n) * width

  if size == 1 {
    *(*byte)(toPtr) = *(*byte)(fromPtr)
  } else {
    memmove(toPtr, fromPtr, size)
  }
  return n
}

Giá trị của width phụ thuộc vào giá trị nhỏ nhất của độ dài hai slice. Có thể thấy rằng, khi sao chép slice không phải duyệt từng phần tử để sao chép, mà chọn cách trực tiếp sao chép nguyên khối bộ nhớ của mảng底层, khi slice rất lớn thì việc sao chép bộ nhớ mang lại ảnh hưởng hiệu suất không nhỏ.

Nếu không gọi trong runtime, sẽ triển khai thành code dạng sau:

n := len(a)
if n > len(b) {
  n = len(b)
}
if a.ptr != b.ptr {
  memmove(a.ptr, b.ptr, n*sizeof(elem(a)))
}

Nguyên lý của hai cách đều giống nhau, đều là sao chép slice thông qua cách sao chép bộ nhớ. Hàm memmove được triển khai bằng assembly, nếu感兴趣 có thể xem chi tiết trong runtime/memmove_amd64.s.

Xóa

package main

func main() {
  s := make([]int, 0, 10)
  s = append(s, 1, 2, 3, 4, 5)
  clear(s)
}

Trong phiên bản go1.21, đã thêm hàm built-in mới clear có thể dùng để xóa nội dung của slice, hoặc nói là đặt tất cả phần tử về giá trị零. Khi hàm clear tác dụng lên slice, compiler sẽ do hàm cmd/compile/internal/walk.arrayClear triển khai thành dạng sau trong thời gian biên dịch:

if len(s) != 0 {
  hp = &s[0]
  hn = len(s)*sizeof(elem(s))
    if elem(s).hasPointer() {
        memclrHasPointers(hp, hn)
    }else {
        memclrNoHeapPointers(hp, hn)
    }
}

Đầu tiên phán đoán độ dài slice có bằng 0 không, sau đó tính toán số byte cần xóa, rồi dựa vào phần tử có phải là con trỏ hay không để xử lý theo hai tình huống, nhưng cuối cùng đều sẽ dùng đến hàm memclrNoHeapPointers, chữ ký như sau:

func memclrNoHeapPointers(ptr unsafe.Pointer, n uintptr)

Nó nhận hai tham số, một là con trỏ trỏ đến địa chỉ bắt đầu, hai là độ lệch,也就是 số byte cần xóa. Địa chỉ bắt đầu bộ nhớ là địa chỉ tham chiếu mà slice giữ, độ lệch n = sizeof(et) * len, hàm này được triển khai bằng assembly, nếu感兴趣 có thể xem chi tiết trong runtime/memclr_amd64.s.

Đáng đề cập là, nếu trong code nguồn cố gắng sử dụng vòng lặp để xóa mảng, ví dụ như thế này:

for i := range s {
  s[i] = ZERO_val
}

Trước khi có hàm clear, thường đều xóa slice bằng cách này. Trong thời gian biên dịch, hiện tại đoạn code này sẽ được hàm cmd/compile/internal/walk.arrayRangeClear tối ưu hóa thành dạng này:

for i, v := range s {
    if len(s) != 0 {
        hp = &s[0]
        hn = len(s)*sizeof(elem(s))
        if elem(s).hasPointer() {
            memclrHasPointers(hp, hn)
        }else {
            memclrNoHeapPointers(hp, hn)
        }
        // Dừng vòng lặp
        i = len(s) - 1
    }
}

Logic vẫn giống như trên, trong đó có thêm một dòng i = len(s)-1, tác dụng của nó là để dừng vòng lặp sau khi xóa bộ nhớ.

Duyệt

for i, e := range s {
  fmt.Println(i, e)
}

Khi sử dụng for range để duyệt slice, sẽ được hàm walkRange trong cmd/compile/internal/walk/range.go triển khai thành dạng sau:

// Sao chép cấu trúc
hs := s
// Lấy con trỏ mảng底层
hu = uintptr(unsafe.Pointer(hs.ptr))
v1 := 0
v2 := zero
for i := 0; i < hs.len; i++ {
    hp = (*T)(unsafe.Pointer(hu))
    v1, v2 = i, *hp
    ... body of loop ...
    hu = uintptr(unsafe.Pointer(hp)) + elemsize
}

Có thể thấy rằng, việc triển khai for range vẫn là thông qua di chuyển con trỏ để duyệt phần tử. Để tránh slice bị cập nhật trong khi duyệt,事先 sao chép một bản cấu trúc hs, để tránh con trỏ hướng đến bộ nhớ vượt giới hạn sau khi duyệt kết thúc, hu sử dụng kiểu uintptr để lưu trữ địa chỉ, khi cần truy cập phần tử mới chuyển đổi thành unsafe.Pointer.

Biến v2也就是 e trong for range, trong toàn bộ quá trình duyệt trước sau đều là một biến, nó chỉ bị ghi đè, không được tạo lại. Điểm này gây ra vấn đề biến vòng lặp困扰 nhà phát triển Go trong mười năm, đến phiên bản go1.21官方 mới quyết định giải quyết, dự kiến trong cập nhật phiên bản sau, cách tạo v2 có thể sẽ变成 dạng sau:

v2 := *hp

Quá trình tạo code trung gian ở đây bỏ qua, đây không thuộc kiến thức phạm vi slice, nếu感兴趣 có thể tự tìm hiểu.

slice ​

Cấu trúc ​

Tạo ​

Truy cập ​

Ghi ​

Sửa đổi ​

Thêm ​

Mở rộng ​

Sao chép ​

Xóa ​

Duyệt ​