Ở bài mức tối ưu, ta thấy -O0 chậm gấp mấy lần -O2 vì nó để mọi biến trên ngăn xếp thay vì trong thanh ghi CPU. Bài này đo sâu vào chính cơ chế đó — cấp phát thanh ghi — và cái xảy ra khi nó không đủ chỗ: biến bị tràn ra ngăn xếp. Và tôi tìm thấy lời giải cho một bí ẩn từ bài trước: vì sao bung vòng lặp với tám biến tích lũy lại chậm hơn với bốn.
Thanh ghi có hạn, và tràn khi hết chỗ
CPU tính toán trên thanh ghi — những ô nhớ cực nhanh nằm ngay trong lõi, đọc/ghi trong chưa tới một chu kỳ. Nhưng số thanh ghi rất hữu hạn: trên AArch64 (ARM 64-bit) có 31 thanh ghi số nguyên (x0–x30), trừ vài cái dành riêng (con trỏ ngăn xếp, địa chỉ trả về...) còn khoảng 28 dùng được. Trên x86-64 còn ít hơn — chỉ 16.
Cấp phát thanh ghi (register allocation) là bài toán trình biên dịch xếp các biến của bạn vào số thanh ghi ít ỏi đó, giữ những biến đang sống (đang được dùng, chưa tính xong) trong thanh ghi càng nhiều càng tốt. Nó làm việc này rất giỏi. Nhưng có một giới hạn cứng nó không vượt được: khi số biến sống cùng lúc vượt số thanh ghi, nó buộc phải TRÀN (spill) — lưu tạm một biến xuống ngăn xếp (một lệnh str), giải phóng thanh ghi cho việc khác, rồi nạp lại (ldr) khi cần biến đó. Mỗi lần spill thêm một cặp store/load chạm bộ nhớ, và trong một vòng nóng, chúng cộng dồn.
Đo: qua ngưỡng, load/store leo dốc
Tôi viết các hàm với số biến tích lũy sống cùng lúc tăng dần — 4, 8, 16, 24, 32, 48 biến, mỗi biến một chuỗi độc lập cập nhật mỗi vòng lặp — rồi đếm số lệnh load/store trong vòng nóng của mỗi hàm (bằng objdump):
Số biến sống cùng lúc | lệnh ldr/str trong vòng nóng
4 biến | 1
8 biến | 7
16 biến | 19
24 biến | 30
32 biến | 55
48 biến | 103 <- tràn stack nặng
Với 4 biến, vòng nóng chỉ có 1 lệnh chạm bộ nhớ (đọc mảng đầu vào) — bốn biến tích lũy nằm gọn trong bốn thanh ghi, không spill. Nhưng số load/store leo dốc khi thêm biến: 7, rồi 19, rồi 30, và bùng lên 103 ở 48 biến. Đó là spill: khi số biến sống vượt ~28 thanh ghi, trình biên dịch phải liên tục đẩy biến xuống ngăn xếp và kéo lại trong mỗi vòng lặp. 48 biến sống chéo nhau tạo ra 103 lần chạm bộ nhớ mỗi vòng, thay vì 1.
Về thời gian, hiệu ứng tinh tế hơn: thời gian mỗi biến-mỗi-phần-tử đạt tốt nhất (~0,11 ns) quanh 16–32 biến, rồi nhích lên ở 48 (0,114 ns). Trên con chip này, các lần spill rơi vào cache L1 (rất nhanh), nên phạt thời gian nhẹ (~3%); nhưng số lệnh thì phình rõ, và trên một máy có áp lực thanh ghi cao hơn hay khi spill trượt khỏi L1, cái phạt đó sẽ cắn mạnh hơn nhiều.
Một lần tôi đo hớ: biến cục bộ không "miễn phí", và bí ẩn x8
Định kiến của tôi: "biến cục bộ chỉ là tên gọi, khai bao nhiêu tùy thích, trình biên dịch lo hết". Con số bác bỏ: biến cục bộ không miễn phí — mỗi biến sống chiếm một thanh ghi, và thanh ghi thì đếm được. Viết một vòng nóng với hàng chục giá trị sống chéo nhau là tự ép trình biên dịch spill, và mã chậm đi (hoặc ít nhất phình lệnh) đo được.
Và đây là lúc bí ẩn từ bài bung vòng lặp sáng tỏ. Ở đó, bung vòng với 4 biến tích lũy nhanh 3,72 lần, nhưng bung với 8 biến lại chậm hơn với 4 — tôi đã ghi nhận "vượt sức song song của CPU" mà chưa chỉ ra cơ chế. Giờ thì rõ: một phần của sự thoái lui đó chính là áp lực thanh ghi. Tám (hay hơn) biến tích lũy độc lập, cộng các biến điều khiển vòng và con trỏ, bắt đầu chạm trần thanh ghi, và trình biên dịch spill — thêm load/store nuốt mất cái lợi ILP. Điểm ngọt của bung vòng không phải ngẫu nhiên ở ~4: nó là nơi số chuỗi song song vừa đủ lấp đơn vị thực thi mà chưa vượt số thanh ghi. Đây cũng là mặt kia của bài mức -O: -O0 chậm vì nó không cấp phát thanh ghi chút nào — mọi biến spill, cho ra 72 lệnh load/store thay vì 26.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: giữ số giá trị sống cùng lúc trong vòng nóng ở mức nhỏ. Bạn hiếm khi khai báo biến với ý thức về thanh ghi, nhưng khi tối ưu một vòng nóng, để ý: nếu bạn có hàng chục biến tạm cùng sống, hay bung vòng quá tay tạo ra nhiều biến tích lũy, bạn đang ép spill. Chia vòng thành các phần nhỏ hơn với ít biến sống mỗi phần đôi khi nhanh hơn một vòng "làm hết mọi thứ cùng lúc". Đây cũng liên quan tới độ phức tạp không gian ở tầng vi mô nhất: thanh ghi là bộ nhớ nhanh nhất và ít nhất, và tràn nó là một dạng "hết chỗ".
Hệ quả thứ hai: tin trình biên dịch cấp phát thanh ghi, nhưng đừng làm khó nó. Register allocation là một trong những phần tinh vi nhất của trình biên dịch, và nó làm tốt hơn con người trong hầu hết trường hợp — đừng cố "giúp" bằng cách viết mã máy trong đầu. Nhưng nó bị chặn bởi số thanh ghi vật lý, nên hãy giúp nó bằng cách giảm số giá trị sống đồng thời, không phải bằng thủ thuật. Và biết rằng x86 (16 thanh ghi) dễ spill hơn ARM (31), nên cùng một code có thể spill trên máy này mà không trên máy kia.
Hệ quả thứ ba là bài học đo lường: một "tài nguyên vô hình" — thanh ghi CPU — có giới hạn cứng đo được. Con số mang theo: CPU chỉ có ~28 thanh ghi số nguyên dùng được (AArch64); vượt ngưỡng đó biến sống cùng lúc bị tràn ra ngăn xếp, và lệnh load/store trong vòng nóng leo từ 1 (4 biến) lên 103 (48 biến); đây chính là lý do bung vòng x8 chậm hơn x4 (quá nhiều accumulator → tràn), và -O0 chậm vì không cấp phát thanh ghi (mọi biến spill). Thanh ghi là tài nguyên khan hiếm nhất và nhanh nhất trong máy; biết nó có hạn, và giữ vòng nóng của bạn gọn trong số thanh ghi, là một tầng tối ưu mà "big-O" không bao giờ chạm tới — nhưng đồng hồ và objdump thì thấy rõ.
Thử ba mươi giây
Viết một hàm với, chẳng hạn, tám biến long tích lũy độc lập trong một vòng nóng, biên dịch gcc -O2 -S -o out.s file.c, và đếm số lệnh str/ldr (x86: mov với [rsp...] hay [rbp...]) trong vòng. Rồi tăng lên bốn mươi biến tích lũy và đếm lại: bạn sẽ thấy số lệnh chạm ngăn xếp tăng vọt — đó là spill, biến bị đẩy ra bộ nhớ vì hết thanh ghi. Đối chiếu với số thanh ghi của kiến trúc (x0–x30 trên ARM, 16 thanh ghi đa dụng trên x86-64) và bạn sẽ thấy ngưỡng khớp. Ba mươi giây đó cho bạn cảm nhận trực tiếp rằng thanh ghi là hữu hạn, và biến cục bộ, ở tầng sâu nhất, không hề miễn phí.
