CPU chạy nhanh nhất khi dữ liệu nằm trong thanh ghi — vài chục ô nhớ tí hon ngay trong lõi. Nhưng số thanh ghi là cố định (aarch64 có 31, dùng được khoảng 28), còn chương trình thì có bao nhiêu biến tùy ý. Khi cần giữ nhiều giá trị hơn số thanh ghi, trình biên dịch buộc phải đổ bớt ra stack — gọi là spill (tràn) — rồi nạp lại khi cần. Bài này đo khi nào xảy ra tràn, và tôi vấp một cái bẫy đo lường kinh điển khi cố định lượng "tràn tốn bao nhiêu".
Tràn xảy ra khi giá trị sống nhiều hơn thanh ghi
Việc trình biên dịch quyết định giá trị nào nằm ở thanh ghi nào gọi là cấp phát thanh ghi (register allocation). Nó cố giữ các giá trị đang dùng trong thanh ghi. Nhưng nếu tại một điểm trong chương trình có nhiều giá trị cần sống cùng lúc hơn số thanh ghi sẵn có, không còn cách nào khác: nó phải đẩy một số giá trị ra bộ nhớ stack (str), rồi khi cần lại nạp về (ldr). Mỗi lần tràn biến một truy cập thanh ghi (gần như tức thì) thành một cặp ghi/đọc bộ nhớ — chậm hơn.
Điều tôi tưởng ban đầu: càng khai báo nhiều biến, càng dễ tràn. Đo ra không phải vậy. Tôi viết một hàm dùng 40 biến nhưng theo kiểu tuần tự (t = t*C + D lặp 40 lần — mỗi bước dùng kết quả bước trước), rồi đếm lệnh tràn (str/ldr vào vùng [sp]) ở -O2:
seq (40 biến, dùng tuần tự): 0 lệnh tràn
wide (24 giá trị đọc từ mảng): 0 lệnh tràn
Cả hai đều 0 tràn. Hàm seq có 40 phép gán nhưng tại mỗi thời điểm chỉ một giá trị sống (biến t), nên một thanh ghi dùng đi dùng lại là đủ. Hàm wide đọc 24 phần tử mảng, nhưng trình dịch không cần giữ cả 24 trong thanh ghi — nó nạp lại từ mảng khi cần (rẻ). Vậy áp lực thanh ghi không đến từ số biến khai báo mà từ số giá trị phải sống đồng thời. Để thực sự ép tràn, tôi cần nhiều giá trị buộc phải sống cùng lúc và không nạp lại được.
Đo: 40 ô tích lũy song song thì tràn
Tôi viết một hàm với 40 ô tích lũy (s0..s39), tất cả được cập nhật trong mỗi vòng lặp và cộng lại ở cuối — nên cả 40 phải sống suốt vòng lặp cùng lúc:
acc4 (4 ô tích lũy): 0 lệnh tràn
acc40 (40 ô tích lũy): 52 lệnh tràn (> 31 thanh ghi)
Với 4 ô, mọi thứ nằm gọn trong thanh ghi. Với 40 ô — vượt xa 31 thanh ghi vật lý — trình dịch buộc phải tràn, sinh 52 lệnh str/ldr vào stack ngay trong thân vòng lặp nóng. Đây đúng là hiện tượng tràn: số giá trị sống đồng thời (40) vượt số thanh ghi. Giờ tôi muốn biết cái tràn đó tốn bao nhiêu, và tôi đã đo hớ.
Một lần tôi đo hớ: 12 lần chậm hơn, nhưng không phải do tràn
Để đo chi phí tràn, tôi so thời gian chạy hai hàm: acc4 (0 tràn) và acc40 (52 tràn), mỗi cái chạy 300 nghìn lượt:
acc4 (0 tràn): 135 ms
acc40 (52 tràn): 1640 ms
Chênh 12 lần. Suýt nữa tôi viết "tràn thanh ghi làm chậm 12 lần". Nhưng con số quá lớn khiến tôi khựng lại — và nhận ra mình đã thay đổi hai biến cùng lúc. acc40 không chỉ tràn; nó còn có 40 ô tích lũy thay vì 4, tức làm gấp 10 lần số phép tính so với acc4. Phần lớn cái "12 lần" kia là nhiều việc hơn, không phải tràn. Tôi đang đo "tràn + khối lượng tính" gộp lại rồi gán hết cho tràn.
Để tách biến, tôi giữ nguyên một hàm (acc12, cùng khối lượng tính) và chỉ thay đổi số thanh ghi được dùng — bằng cờ -ffixed reserve bớt 10 thanh ghi để ép tràn:
acc12, đủ thanh ghi: 0 lệnh tràn, 314 ms
acc12, thiếu 10 tghi: 2 lệnh tràn, 324 ms (+3%)
Cùng công việc, chỉ khác số thanh ghi: 2 lệnh tràn làm chậm khoảng 3%. Chi phí tràn thật sự — khi cô lập đúng — nhỏ hơn nhiều con số 12 lần tôi suýt tin. Lý do một phần: các ô tràn nằm trên stack, mà đỉnh stack gần như luôn nóng trong cache L1, nên đọc/ghi nó khá rẻ; và CPU thường có băng thông load/store dư để chồng lấp việc tràn với việc tính. Bài học đo lường, đúng linh hồn sê-ri: muốn đo chi phí của một thứ, phải giữ nguyên mọi thứ khác — hai số 135 và 1640 trông như đo chi phí tràn, thực ra đo cả lượng tính. Đổi hai biến cùng lúc thì con số nói dối về nguyên nhân.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên là giảm áp lực thanh ghi bằng cách rút ngắn tầm sống của giá trị, không phải bằng cách khai ít biến. Khai bao nhiêu biến địa phương cũng được — nếu chúng dùng tuần tự (tính xong dùng ngay rồi bỏ), chỉ một thanh ghi luân phiên là đủ, như hàm seq cho thấy. Áp lực chỉ tăng khi bạn buộc nhiều giá trị sống song song qua một vùng dài — ví dụ nhiều biến tích lũy, hay một biểu thức khổng lồ với hàng chục kết quả trung gian cùng cần. Muốn nhẹ, hãy tính theo cụm nhỏ, dùng xong thả sớm.
Hệ quả thứ hai là đừng hoảng vì tràn, nhưng cũng đừng bỏ qua nó trong vòng lặp nóng nhất. Một vài lệnh tràn trên stack L1 gần như miễn phí, như phép đo cô lập cho thấy. Nhưng trong một vòng lặp cực nóng chạy hàng tỉ lần, hàng chục lệnh tràn mỗi vòng (như acc40) cộng dồn thành chi phí thật, và tệ hơn nếu vùng tràn bị đẩy khỏi L1. Khi tối ưu một hàm nóng, đọc assembly tìm str/ldr vào [sp] trong thân vòng lặp là cách phát hiện áp lực thanh ghi — thứ không nhìn thấy trong mã nguồn.
Hệ quả thứ ba là bài học đo lường cốt lõi: tách biến khi so sánh. Con số mang theo: tràn xảy ra khi số giá trị sống đồng thời vượt số thanh ghi (acc40: 40 ô → 52 lệnh tràn), chứ không phải khi bạn khai nhiều biến (seq: 40 biến tuần tự → 0 tràn); và chi phí tràn thật, khi cô lập đúng, khá nhỏ (2 tràn ≈ +3%) — con số 12 lần ban đầu phần lớn là do làm nhiều việc hơn, không phải do tràn. Mỗi khi hai phép đo chênh nhau lớn, hãy hỏi mình đã đổi mấy biến; nếu nhiều hơn một, con số đang trộn nhiều nguyên nhân, và gán hết cho một cái là đo hớ.
Thử ba mươi giây
Viết một hàm với khoảng 40 biến long s0=0,...,s39=0;, cập nhật tất cả trong một vòng lặp rồi cộng lại trả về, dịch gcc -O2 -S file.c -o file.s, và tìm trong thân vòng lặp các lệnh str/ldr có [sp — đó là các lần tràn. Giờ giảm xuống 4 biến, dịch lại: các lệnh tràn biến mất. Bạn vừa thấy áp lực thanh ghi bằng mắt. Và nhớ: đừng đo "tràn tốn bao nhiêu" bằng cách so 4 biến với 40 biến — cái đó đổi cả khối lượng tính; muốn đo đúng, giữ nguyên hàm và chỉ đổi số thanh ghi khả dụng.
