1. Tai sao nen preallocate dung luong cua slice
Khi nghe den "hieu suat", nhieu nguoi moi bat dau thuong vao che do "toi con chua lam hong may tinh trong vong lap, ma ban da noi den toi uu hoa". Do la phan ung hoan toan binh thuong. Nhung hom nay chung ta se khong do nanosecond va khong tranh luan ve tri hoc cua runtime. Chung ta se tim hieu mot thu thuat rat thuc te va an toan: preallocate dung luong cua slice, de append trong vong lap khong phai copy thua va cap phat bo nho thua.
Hay tuong tuong ban dang gom danh sach cong viec cua nguoi dung (chuoi) hoac mot tap hop so tu dau vao. Cach tu nhien nhat la bat dau voi mot slice rong va goi append trong vong lap. No hoat dong, va dieu do da la tot. Nhung neu ban biet truoc (hoac it nhat doan duoc) se co bao nhieu phan tu, ban co the giup Go lam viec nay du doan duoc hon va re hon.
Quan trong la phai xac dinh ranh gioi ngay: chung ta khong lam "toi uu hoa ma thuat", chung ta chi chon mot dang make phu hop hon. Ma nguon van ro rang, va chuong trinh thuong se bat dau "it rung" hon ve bo nho.
append trong vong lap doi khi tro nen "dat"
Khi ban viet s = append(s, x), no co ve nhu mot thao tac don gian "them vao cuoi". Va thuong thi dung la nhu vay. Nhung doi khi append roi vao tinh huong: "het cho roi". Luc do no se lam mot kich ban gan dung nhu sau (don gian hoa):
- cap phat mot backing array moi (thuong lon hon cai cu),
- sao chep cac phan tu cu sang,
- them phan tu moi,
- tra ve slice moi (voi con tro moi va cap moi).
Dieu nay khong phai "xau" hay "loi", ma la mot phan binh thuong cua phat trien. Trong cac phien ban Go cu, lap trinh vien con viet thu cong, va su xuat hien cua append nhu mot ham builtin da giup moi nguoi khoi phai viet ma nguon lap lai de mo rong danh sach. Tren blog Go con dua ra vi du "append thu cong" tu ngay xua, va chinh no da truyen cam hung cho append tich hop.
Nhung neu ban lam viec nay ben trong mot vong lap lon, se xuat hien mot hieu ung kho chiu: ban tuong minh dang them 100000 phan tu, nhung thuc ra dinh ky lai phai chay mot "chuyen van phong": cap phat mat bang moi va chuyen tat ca ban ghe.
Hinh anh tu duy huu ich:
flowchart TD
A[Co slice: len=8 cap=8] -->|append them 1| B{cap du chua?}
B -->|co| C[Viet vao cung mot backing array]
B -->|khong| D[Cap phat backing array moi]
D --> E[Sao chep 8 phan tu]
E --> F[Them phan tu moi]
F --> G[Tra ve slice header moi]
Y chinh: reallocations khong xay ra sau tung thao tac, nhung moi lan reallocations co the dat hon dang ke so voi append thong thuong. Vi vay neu co co hoi giam so lan do — tai sao khong?
2. Pattern va dang dung cua make
Preallocate dung luong bang make(..., 0, cap)
Preallocation la khi chung ta tao ra mot slice co do dai bang khong, nhung da dat truoc mot dung luong: make([]T, 0, n). Y nghia nghe gan nhu mot cau chuc mung cua lap trinh vien: "Bay gio chung ta chua co gi, nhung cho N phan tu da duoc dat truoc."
Tai sao lai la len = 0? Vi len trong Go la "co bao nhieu phan tu thuc su ton tai va co the dung", khong phai "toi du dinh". Neu ban se them bang append, se tien hon neu bat dau voi danh sach rong, de khong bi "cac so 0 thua"/cac gia tri rong. Chung ta da thay dieu nay roi: make([]int, 5) tao ra nam so 0, va sau do append them phan tu thu sau.
Vi the pattern cho "gom cac phan tu" se la:
- tao s := make([]T, 0, expectedSize)
- trong vong lap, goi s = append(s, ...)
Chi co vay. Khong co goi bi mat nao, khong co cau truc phuc tap nao.
make([]T, n) vs make([]T, 0, n)
Su khac nhau nay co ve nho cho den khi ban gap mot loi kieu "tai sao ket qua lai co nam chuoi rong truoc, roi moi den du lieu cua toi". Vi vay hay cham rai va trung thuc so sanh hai cach. Hay tuong tuong ban dang chuan bi mot cai hop dung do.
- make([]T, n) — ban da dat san ben trong n vat (tam thoi la rong/0), cai hop "day theo do dai".
- make([]T, 0, n) — cai hop rong, nhung co n o trong de them vao nhanh.
Bang tong ket:
| Bieu thuc | len ngay lap tuc | cap ngay lap tuc | Ben trong thuc su co gi | Khi nao thi phu hop |
|---|---|---|---|---|
|
|
|
da co n phan tu voi gia tri 0 | khi ban se dien theo chi so s[i] = ... |
|
|
|
khong co phan tu, nhung co bo nho da cap phat cho viec tang truong | khi ban se them vao bang append |
Vi du nho, de bo nao dung tranh cai voi mat:
package main
import "fmt"
func main() {
a := make([]int, 5) // len=5: da co 5 so 0
b := make([]int, 0, 5) // len=0: rong, nhung cap=5
fmt.Println(a, len(a), cap(a)) // [0 0 0 0 0] 5 5
fmt.Println(b, len(b), cap(b)) // [] 0 5
}
Hay chu y: cach thu hai duoc in ra la [], nhung do khong phai la nil-slice, ma la mot slice rong binh thuong, chi co them du phong ve dung luong.
3. Thuc hanh: TaskBox va su tang cua cap
Vi du: gom danh sach cong viec
Tu day, hay xem nhu chung ta dang viet mot ung dung console nho ten la TaskBox: nguoi dung nhap so luong cong viec, sau do nhap chinh cac cong viec (tam thoi cu mot tu de fmt.Fscan khoi kho), va chuong trinh in ra danh sach da danh so. Dung, day chua phai la mot todo manager hoan chinh, nhung chung ta da lam duoc mot viec huu ich: gom mot tap hop chuoi.
Dau tien hay xem ban naive: bat dau voi nil/rong va cho no lon len. Cach nay van dung.
package main
import (
"bufio"
"fmt"
"os"
)
func main() {
in := bufio.NewReader(os.Stdin)
var n int
fmt.Fscan(in, &n)
var tasks []string // nil-slice
for i := 0; i < n; i++ {
var t string
fmt.Fscan(in, &t)
tasks = append(tasks, t)
}
fmt.Println(tasks) // vi du: [buy_code sleep repeat]
}
Bay gio hay cai tien cung do bang dung mot y tuong: vi n da biet, hay preallocate dung luong.
package main
import (
"bufio"
"fmt"
"os"
)
func main() {
in := bufio.NewReader(os.Stdin)
var n int
fmt.Fscan(in, &n)
tasks := make([]string, 0, n) // len=0, cap=n
for i := 0; i < n; i++ {
var t string
fmt.Fscan(in, &t)
tasks = append(tasks, t)
}
fmt.Println(tasks) // [buy_code sleep repeat]
}
Logic khong doi, do ro rang khong giam, nhung luc nay rat co the chung ta da tranh duoc mot chuoi reallocations khi tang truong, vi backing array da duoc cap phat san dung kich thuoc.
Va hay them mot cach in dep hon (khong lam phuc tap, chi de ket qua trong giong "mot ung dung" hon la "mot bai thi nghiem"):
package main
import "fmt"
func main() {
tasks := []string{"buy_code", "sleep", "repeat"}
for i, t := range tasks {
fmt.Printf("%d) %s\n", i+1, t)
}
// 1) buy_code
// 2) sleep
// 3) repeat
}
Dung, van chi la nhung chuoi don gian. Chung ta se khong dong vao cau truc task phuc tap hon — muc tieu hien tai chinh la pattern lam viec voi slice.
Lam sao nhin thay reallocations bang mat qua cap
Preallocation duoc hieu rat nhanh khi ban mot lan thay "buoc nhay" cua cap trong qua trinh append. Chung ta khong can do thoi gian va khong can viet benchmark — voi nguoi moi bat dau, dieu do thuong bien thanh mot nghia thuc cua nghe thuat than bi. Chung ta se lam mot chan doan don gian: in ra len va cap, va dong thoi dem xem bao nhieu lan cap thay doi.
Day la mot quan sat nho "slice tang truong nhu the nao":
package main
import "fmt"
func main() {
s := make([]int, 0) // khong preallocate
prevCap := cap(s)
for i := 0; i < 10; i++ {
s = append(s, i)
if cap(s) != prevCap {
fmt.Println("cap changed:", prevCap, "->", cap(s))
prevCap = cap(s)
}
}
}
Ban se thay mot vai dong cap changed: ..., va so luong cua chung phu thuoc vao cach runtime quyet dinh tang dung luong. Dieu quan trong khong phai la "nho so", ma la nam duoc nguyen ly: cap thay doi khong thuong xuyen, nhung moi lan nhu vay deu la dau hieu cua viec mo rong/phan cap phat lai.
Bay gio hay so sanh voi preallocation. Chung ta co y dat cap=10 de trong pham vi 10 lan append se khong co mo rong:
package main
import "fmt"
func main() {
s := make([]int, 0, 10) // da preallocate
prevCap := cap(s)
for i := 0; i < 10; i++ {
s = append(s, i)
if cap(s) != prevCap {
fmt.Println("cap changed:", prevCap, "->", cap(s))
prevCap = cap(s)
}
}
fmt.Println("final:", len(s), cap(s)) // final: 10 10
}
Rat co the ban se khong thay dong nao ve cap changed (vi khong con cho de tang nua, va cung khong can tang), con ket qua cuoi se la len=10 va cap=10. Tuc la chung ta da bien su tang truong thanh mot cau chuyen co the du doan: "da danh san cho cho va diền day no mot cach binh yen".
Chon cap nhu the nao neu khong biet kich thuoc chinh xac
Trong thuc te, nhieu luc ban khong biet chinh xac so luong phan tu. Khi do se xuat hien cau hoi: "Nen viet gi vao make(..., 0, cap) — mot con so than bi 42?" (42 thi duoc, nhung tot nhat van nen co y nghia.)
O day hay suy nghi the nay: cap khong phai la "nghia vu", ma la mot loi goi y. Neu ban dat cap nho hon can thiet, chuong trinh khong hong: append chi bat dau mo rong muon hon. Neu ban dat cap lon hon can thiet, chuong trinh cung khong hong, nhung ban da cap phat truoc mot chut bo nho. Tuc la viec chon cap la can bang giua "khong lam reallocations thua" va "khong cap phat du".
Cac tinh huong thuc te thuong gap nhu sau.
Neu kich thuoc duoc biet chinh xac (nhu trong TaskBox cua chung ta, khi dau tien nhap vao n), ban chi can dat cap = n va khong can nghi them. Day la tinh huong ly tuong.
Neu chi biet gioi han tren (vi du, "khong qua 1000 phan tu"), ban co the dat cap bang gioi han do neu bo nho khong lam ban lo lang. Voi []string thi dieu nay co the khong nhe, con voi []int thi thuong van chap nhan duoc, nhung chung ta se khong bien bai giang nay thanh may tinh byte. Y tuong don gian: gioi han tren la mot ung vien tot.
Neu kich thuoc hoan toan khong biet, ban co the khong preallocate, hoac preallocate mot "diem bat dau nho" (vi du 16 hoac 32) de nhung lan mo rong dau tien khong xay ra o moi buoc. No giong nhu luc ban mang theo tui di cho: co the lay tui nho va sau do kho chiu, co the lay tui lon hon mot chut "cho chac", nhung khong mang theo mot cai hop khong lo neu ban chi mua mot cai banh mi.
Hay nho: tinh dung cua thuat toan khong nen phu thuoc vao cap. cap lien quan den hieu suat va tinh du doan, nhung khong lien quan den y nghia cua ket qua.
4. Cac loi thuong gap khi preallocate va dung append trong vong lap
Loi so 1: dung make([]T, n) roi sau do them bang append, dan den "cac so 0 thua".
Day la mot trong nhung cai bay phu bien nhat. make([]int, 5) tao ra nam phan tu da ton tai, va neu ban sau do goi append, ban dang them phan tu vao sau chung. Neu ban muon "mot danh sach rong voi dung luong 5", dang dung la make([]int, 0, 5).
Loi so 2: nham lan cap voi "kich thuoc du lieu" va co gang index den cap.
Ngay ca khi cap(s) == 100, nhung len(s) == 0, bieu thuc s[0] van la loi runtime (panic). Gioi han truy cap luon duoc xac dinh boi len, con cap chi noi rang co the tang them bao nhieu ma chua can mo rong backing array.
Loi so 3: quen gan ket qua cua append trong vong lap (hoac vo tinh lam mat no do :=).
Trong vong lap, gan nhu luc nao ban cung phai viet s = append(s, x). Neu chi viet append(s, x), thi len o ben ngoai se khong doi. Va neu ben trong mot block ban theo tho quen viet s := append(s, x), ban co the vo tinh tao ra mot bien moi roi sau do nga nga vi sao "ben ngoai khong co gi duoc them vao". Dieu nay dac biet kho chiu vi no trong rat dung.
Loi so 4: co gang toi uu hoa hoan hao va phu thuoc vao cac con so tang cap cu the.
Go khong cam ket rang cap se tang dung gap doi hay theo bat ky cong thuc cu the nao. Do la chi tiet implementation, khong phai hop dong cua ngon ngu. Vi the, viec theo doi su tang truong thi huu ich, nhung viet logic "doi cap=64 o buoc thu tam" thi chi dan den cac bug la va nhung cuoc phong van con la.
Loi so 5: preallocate mot dung luong khong lo "cho chac", ma khong co ly do ro rang.
Preallocation la mot cong cu tot, nhung no khong nen tro thanh tho quen "toi se cap phat mot trieu, biet dau mai nay can". Dac biet voi []string, noi moi phan tu khong chi la chuoi ma con co them cau truc du lieu phu tro. Tot hon het la preallocate khi ban co thong tin: kich thuoc chinh xac, gioi han tren, hoac uoc luong hop ly.
GO TO FULL VERSION