Go: Slice Grow
Thường thì, việc mở rộng slice xảy ra sau khi thêm các phần tử vào slice bằng cách sử dụng hàm append
.
Trước tiên, hãy xem nguyên mẫu của hàm append
:
Hàm append
có số lượng tham số biến đổi, do đó có thể thêm nhiều giá trị vào slice, hoặc thêm một slice bằng cách sử dụng …
.
Hàm append
trả về một slice mới, và trình biên dịch Go không cho phép gọi hàm append
mà không sử dụng giá trị trả về.
Vì vậy, cách sử dụng trên là không đúng và sẽ không biên dịch được.
Sử dụng hàm append
có thể thêm phần tử vào slice, thực tế là thêm phần tử vào mảng gốc. Tuy nhiên, độ dài của mảng gốc là cố định, nếu chỉ số len-1
trỏ đến phần tử cuối cùng của mảng, không thể thêm phần tử nữa.
Khi đó, slice sẽ được di chuyển đến vị trí bộ nhớ mới, đồng thời độ dài của mảng gốc cũng sẽ tăng lên để chứa các phần tử mới. Đồng thời, để đối phó với việc thêm phần tử trong tương lai, độ dài của mảng gốc mới, tức là sức chứa của slice mới, sẽ có một số buffer
dư thừa. Nếu không có buffer
, việc thêm phần tử sẽ gây ra việc di chuyển mảng liên tục, gây tốn kém.
Kích thước buffer
được dự đoán theo một quy tắc nhất định. Trước phiên bản Go 1.18, hầu hết các bài viết trên mạng mô tả quy tắc mở rộng slice như sau:
Khi sức chứa của slice gốc nhỏ hơn
1024
, sức chứa của slice mới là gấp đôi sức chứa cũ; khi sức chứa của slice gốc vượt quá1024
, sức chứa của slice mới là1.25
lần sức chứa cũ.
Tuy nhiên, sau phiên bản Go 1.18, quy tắc mở rộng slice đã thay đổi thành:
Khi sức chứa của slice gốc (oldcap) nhỏ hơn 256, sức chứa của slice mới (newcap) là gấp đôi sức chứa cũ; khi sức chứa của slice gốc vượt quá 256, sức chứa của slice mới được tính theo công thức
newcap = oldcap + (oldcap + 3 * 256) / 4
.
Để minh họa quy tắc trên, tôi đã viết một đoạn mã đơn giản:
Tôi tạo một slice rỗng ban đầu, sau đó trong một vòng lặp, tôi liên tục thêm phần tử vào slice. Tôi ghi lại sự thay đổi về sức chứa và mỗi khi sức chứa thay đổi, tôi ghi lại sức chứa cũ, sức chứa sau khi thêm phần tử và các phần tử trong slice tại thời điểm đó. Như vậy, tôi có thể quan sát được sự thay đổi về sức chứa của slice cũ và slice mới, từ đó tìm ra quy tắc.
Kết quả chạy (trước phiên bản 1.18):
Kết quả chạy (phiên bản 1.18):
Dựa vào kết quả trên, chúng ta có thể thấy các quy tắc như sau (trước phiên bản 1.18):
- Khi sức chứa của slice gốc (oldcap) nhỏ hơn 1024, sức chứa của slice mới (newcap) là gấp đôi sức chứa cũ.
- Khi sức chứa của slice gốc (oldcap) lớn hơn hoặc bằng 1024, sức chứa của slice mới (newcap) là 1.25 lần sức chứa cũ.
Tuy nhiên, sau phiên bản 1.18, quy tắc đã thay đổi như sau:
- Khi sức chứa của slice gốc (oldcap) nhỏ hơn 256, sức chứa của slice mới (newcap) là gấp đôi sức chứa cũ.
- Khi sức chứa của slice gốc (oldcap) lớn hơn hoặc bằng 256, sức chứa của slice mới (newcap) được tính theo công thức newcap = oldcap + (oldcap + 3 * 256) / 4.
Cần lưu ý rằng quy tắc này chỉ áp dụng cho việc mở rộng slice khi thêm phần tử vào. Quy tắc này giúp chúng ta hiểu rõ hơn về cách slice mở rộng và sử dụng slice một cách hiệu quả.
Bằng cách xem mã nguồn, chúng ta có thể xem rõ quy tắc mở rộng slice.
Trong phiên bản Go 1.9.5:
Trong phiên bản Go 1.18:
Như bạn đã thấy, nếu chỉ xem nửa đầu của mã nguồn, thì những quy tắc về newcap
mà các bài viết trên mạng đề cập là đúng. Tuy nhiên, nửa sau của mã nguồn cũng thực hiện một quá trình “căn chỉnh bộ nhớ” cho newcap
, điều này liên quan đến chiến lược phân bổ bộ nhớ. Sau khi hoàn tất quá trình căn chỉnh bộ nhớ, sức chứa của slice mới sẽ lớn hơn hoặc bằng newcap
được tạo ra từ nửa đầu của mã nguồn.
Sau đó, mã nguồn yêu cầu bộ quản lý bộ nhớ Go cấp phát bộ nhớ, sao chép dữ liệu từ slice cũ sang và thêm các phần tử append vào mảng cơ sở mới.
Cuối cùng, growslice
trả về một slice mới cho người gọi hàm, với độ dài không thay đổi nhưng sức chứa đã tăng lên.
【Mở rộng 1】
Hãy xem ví dụ:
Code | Mô tả trạng thái slice |
---|---|
s := []int{5} | s chỉ có một phần tử, [5] |
s = append(s, 7) | s mở rộng, sức chứa tăng lên 2, [5, 7] |
s = append(s, 9) | s mở rộng, sức chứa tăng lên 4, [5, 7, 9] . Lưu ý, lúc này s có độ dài là 3, chỉ có 3 phần tử |
x := append(s, 11) | Vì mảng cơ sở của s vẫn còn chỗ trống, nên không cần mở rộng. Như vậy, mảng cơ sở trở thành [5, 7, 9, 11] . Lưu ý, lúc này s = [5, 7, 9] , sức chứa là 4; x = [5, 7, 9, 11] , sức chứa là 4. Ở đây, s không thay đổi |
y := append(s, 12) | Ở đây vẫn là thêm phần tử vào cuối của s, vì độ dài của s là 3, sức chứa là 4, nên chỉ cần điền số 12 vào vị trí chỉ số 3 của mảng cơ sở. Kết quả: s = [5, 7, 9] , y = [5, 7, 9, 12] , x = [5, 7, 9, 12] , cả x và y đều có độ dài là 4, sức chứa cũng là 4 |
Vì vậy, kết quả thực thi chương trình là:
Cần lưu ý rằng, sau khi thực hiện hàm append, một slice hoàn toàn mới được trả về và không ảnh hưởng đến slice được truyền vào.
【Mở rộng 2】
Chúng ta hãy xem một ví dụ cuối:
Kết quả chạy là:
Nếu theo như các bài viết trên mạng đã tổng kết: khi độ dài của slice gốc nhỏ hơn 1024, sức chứa tăng gấp đôi mỗi lần. Khi thêm phần tử 4, sức chứa tăng lên 4; khi thêm phần tử 5, sức chứa không thay đổi; khi thêm phần tử 6, sức chứa tăng gấp đôi, trở thành 8.
Vậy kết quả chạy của đoạn mã trên sẽ là:
Điều này là sai! Hãy xem xét kỹ hơn, tại sao lại như vậy, và xem lại mã nguồn:
Hàm này có các tham số lần lượt là kiểu phần tử, slice cũ, sức chứa tối thiểu của slice mới
.
Trong ví dụ, s
ban đầu chỉ có 2 phần tử, len
và cap
đều là 2. Sau khi append
ba phần tử, độ dài trở thành 5, sức chứa tối thiểu cần là 5, tức là khi gọi hàm growslice
, tham số thứ ba được truyền là 5, tức là cap=5
. Một mặt, doublecap
là gấp đôi sức chứa của slice gốc, bằng 4. Thỏa mãn điều kiện if
đầu tiên, vì vậy newcap
trở thành 5.
Tiếp theo, gọi hàm roundupsize
, truyền vào giá trị 40. (Trong mã nguồn, ptrSize
đại diện cho kích thước của một con trỏ, trên máy 64-bit là 8 byte).
Chúng ta tiếp tục xem xét về việc căn chỉnh bộ nhớ, và trích xuất mã của hàm roundupsize
:
Rõ ràng, chúng ta sẽ trả về kết quả của biểu thức này:
Đây là hai slice
liên quan đến việc phân bổ bộ nhớ trong mã nguồn Go. class_to_size
được sử dụng để lấy kích thước của object
được phân vùng thông qua spanClass
. Còn size_to_class8
biểu thị spanClass
tương ứng với kích thước size
.
Chúng ta truyền vào size
có giá trị là 40. Vì vậy, (size+smallSizeDiv-1)/smallSizeDiv = 5
; phần tử có chỉ số 5
của mảng size_to_class8
là 5
; phần tử có chỉ số 5
của mảng class_to_size
là 48
.
Cuối cùng, sức chứa mới của slice là 6
:
Còn về hai mảng ma thuật
trên, chúng ta sẽ không đi vào chi tiết.
【Mở rộng 2】
Thêm phần tử vào một nil slice
sẽ xảy ra gì? Tại sao?
Thực tế, nil slice
hoặc empty slice
đều có thể mở rộng bằng cách gọi hàm append để có được một mảng cơ sở mới. Cuối cùng, cả hai đều gọi hàm mallocgc
để yêu cầu bộ nhớ từ bộ quản lý bộ nhớ của Go, sau đó gán cho nil slice
hoặc empty slice
ban đầu, và biến thành một real slice
.