Ở bài loại biểu thức con chung ta thấy compiler tính một biểu thức lặp lại chỉ một lần trong một khối. Có một anh em họ của nó làm việc qua các vòng lặp: nếu một biểu thức trong thân vòng cho cùng giá trị ở mọi lần lặp, tính nó một lần trước vòng là đủ. Đó là chuyển mã bất biến ra khỏi vòng (Loop-Invariant Code Motion — LICM). Câu hỏi tôi mang vào: compiler kéo được tới đâu? Tôi tin nó kéo được tất cả, và tin đó gãy đúng chỗ đắt nhất.
Bất biến thì tính một lần
Xét for(int i=0;i<n;i++) a[i] = x*y + i;. Biểu thức x*y cho cùng một giá trị ở mọi vòng lặp — x, y không đổi trong vòng. Tính lại nó n lần là lãng phí; LICM kéo nó ra ngoài, tính một lần rồi dùng lại. Tôi xác nhận trong container gcc:13 (ARM AArch64), biên dịch -O2 và soi mã máy hàm fill:
fill:
cmp w1, 0
ble .L1
mul x2, x2, x3 <- x*y, TRƯỚC nhãn vòng
...
.L3: <- thân vòng bắt đầu
str x2, [x0, x2, lsl 3]
add x2, x2, 1
cmp x2, x1
bne .L3
Lệnh mul (x*y) nằm trước nhãn .L3 — nghĩa là trước vòng lặp. Thân vòng (.L3:) chỉ còn ghi, cộng, so sánh, nhảy — không có phép nhân nào. LICM đã kéo x*y ra ngoài, tính một lần cho cả n vòng. Với biểu thức số học thuần như thế này, LICM hoạt động đúng như mong đợi, và tự tay đưa x*y ra một biến trước vòng không cho bạn gì thêm.
Nhưng tôi vào bài tin rằng compiler kéo được mọi biểu thức bất biến. Đó là chỗ đo hớ.
Đo hớ: một phép ghi chặn cả LICM
Có một cái bẫy hiệu năng kinh điển trong C: viết độ dài chuỗi ngay trong điều kiện vòng.
for(int i=0; i < strlen(s); i++) { ... }
Truyền thuyết nói đây là O(n²) vì strlen (bản thân là O(n)) chạy lại mỗi vòng. Tôi định trưng ra ngay điều đó — nhưng lần đo đầu tiên làm tôi ngạc nhiên. Với thân vòng chỉ đọc (acc += s[i];), tôi đo cả bản strlen-trong-điều-kiện lẫn bản đưa strlen ra ngoài, ở nhiều kích thước n:
thân chỉ đọc: bad ns/phần tử ~ 0,26 (n từ 2.000 tới 32.000, KHÔNG đổi)
good ns/phần tử ~ 0,26 (bằng nhau -> cả hai O(n))
Cả hai đều O(n)! Compiler đã kéo strlen(s) ra ngoài vòng ngay cả trong bản "bad", vì strlen là hàm thuần (chỉ đọc) và thân vòng không ghi vào s, nên nó chứng minh được strlen(s) bất biến. Truyền thuyết O(n²) không hiện ra — trên compiler hiện đại, chỉ viết strlen trong điều kiện chưa đủ để chậm.
Điều gì mới đủ? Khi thân vòng ghi vào chính chuỗi đó. Đổi thân thành s[i] = ... (sửa từng ký tự), rồi đo lại:
n bad (ns/phần tử) good (ns/phần tử)
2.000 19,5 0,29
4.000 44,1 0,28
8.000 80,1 0,27
16.000 142,0 0,26
32.000 257,8 0,26
Giờ thì bad phình đúng bậc hai: ns/phần tử tăng tuyến tính theo n (nghĩa là tổng thời gian tỉ lệ n²). Ở n = 32.000, bản bad mất 8,25 mili giây còn bản good mất 8,3 micro giây — chậm khoảng 990 lần. Lý do: thân vòng ghi s[i], và một phép ghi vào s có thể đổi ký tự kết thúc chuỗi, nên compiler không còn dám chắc strlen(s) bất biến — nó buộc phải gọi strlen lại mỗi vòng. LICM bị chặn, và bẫy O(n²) thành thật.
Vậy đo hớ của tôi có hai lớp. Lớp một: LICM mạnh hơn tôi tưởng ở ca đơn giản (kéo cả strlen khi thân chỉ đọc). Lớp hai: nó yếu hơn tôi tưởng ở ca có ghi bộ nhớ — một phép s[i] = ... là đủ để chặn hoàn toàn, và không có cảnh báo nào. Compiler không "luôn kéo mọi thứ bất biến ra"; nó kéo những gì nó chứng minh được là bất biến, và một phép ghi có thể aliasing xóa sạch chứng minh đó, đúng như strict aliasing đã cho thấy.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên rất cụ thể: đừng đặt lời gọi hàm vào điều kiện vòng nếu thân vòng chạm tới cùng dữ liệu. for(i=0;i<strlen(s);i++) với thân sửa s là bẫy O(n²) kinh điển; tự tay int n = strlen(s); trước vòng biến nó về O(n). Điều này áp cho mọi hàm "đo kích thước" trong điều kiện — v.size() trong C++ khi thân thêm/bớt phần tử, list.count() trong vòng, v.v. Khi thân có thể đổi cái mà điều kiện đo, compiler phải hỏi lại mỗi vòng.
Hệ quả thứ hai: hàm compiler không thấy thân là một bức tường cho LICM. strlen may mắn là builtin nên compiler biết nó thuần; nhưng một hàm của bạn ở file khác (chưa nội tuyến, chưa đánh dấu pure) thì compiler phải giả định nó có thể đổi mọi thứ, và sẽ không kéo lời gọi ra khỏi vòng dù giá trị thực tế bất biến. Đây là một lý do nữa để nội tuyến hoặc đánh dấu __attribute__((pure)) cho hàm không tác dụng phụ. Với strlen tôi đo được cả hai mặt: khi thân chỉ đọc, tính thuần đã biết của builtin đủ để compiler kéo lời gọi ra; khi thân ghi vào s, chính tính thuần đó cũng vô nghĩa vì dữ liệu nó đọc có thể đã đổi — nên đánh dấu pure chỉ giúp khi thân không đụng tới đầu vào của hàm.
Hệ quả thứ ba là bài học đo lường: "compiler tự lo" đúng phần lớn thời gian, nhưng biên giới của nó là aliasing và tính thuần — và ở đó độ phức tạp thuật toán có thể âm thầm nhảy bậc. Một tối ưu bị chặn không làm code sai, chỉ làm nó chậm theo cấp số nhân khi n lớn, và bạn chỉ thấy khi đo đường cong chứ không phải một điểm. Con số mang theo: LICM kéo biểu thức bất biến ra khỏi vòng, tính một lần (x*y kéo ra ngoài, objdump thấy mul trước nhãn vòng), mạnh tới mức hoist cả strlen khi thân chỉ đọc; nhưng một phép ghi vào bộ nhớ mà biểu thức đọc chặn LICM — 'for(i<strlen(s))' với thân sửa chuỗi thành O(n²) thật, n=32.000 chậm 990 lần (8,25 ms so 8,3 µs), và tự tay đưa strlen ra ngoài mới cứu. Đừng tin compiler kéo được mọi thứ; khi nghi ngờ, đo đường cong.
Thử ba mươi giây
Viết hai vòng trên một chuỗi dài chừng 50.000 ký tự: for(int i=0;i<strlen(s);i++) s[i]=(s[i]|1); và bản int n=strlen(s); for(int i=0;i<n;i++) s[i]=(s[i]|1);. Bọc mỗi bản bằng clock_gettime và in thời gian. Bản đầu sẽ chậm hơn bản sau hàng trăm tới hàng nghìn lần — vì thân ghi s[i] khiến compiler gọi strlen lại mỗi vòng. Rồi đổi thân thành chỉ đọc (acc += s[i];) và đo lại: lần này hai bản gần bằng nhau, vì compiler tự kéo strlen ra được. Ba mươi giây đó cho bạn thấy chính xác biên giới của LICM: nó dừng ở phép ghi.
