Vòng lặp for(i<strlen(s)) — huyền thoại O(n²): compiler cứu, cho tới khi tôi thêm một phép ghi

Hình dung bạn đếm số người trong một căn phòng ở đầu mỗi lượt việc. Nếu cửa đóng, không ai ra vào, thì đếm một lần rồi dùng lại con số đó suốt — đếm lại mỗi lượt là phí. Nhưng nếu chính công việc của bạn lại cho người ra vào qua cửa, thì con số cũ không còn tin được: bạn buộc phải đếm lại mỗi lượt. Trình biên dịch đối xử với những biểu thức "bất biến" trong vòng lặp đúng theo logic đó — và cái ranh giới "công việc có đụng tới cái đang đếm không" hóa ra là chỗ một vòng lặp trông vô hại âm thầm nhảy lên O(n²).

Ở 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. Đo trong container gcc:13 (ARM).

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 bằng cách 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ỗ tôi vấp.

Cú vấp: 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. Cửa đóng thì đếm một lần là xong.

Điều gì mới đủ? Khi thân vòng ghi vào chính chuỗi đó — tức mở cửa cho người ra vào. Đổ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 cú vấp 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ề đến code hằng ngày

Điều đầ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.

Điều 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ụ — nhưng nhớ: đánh dấu pure chỉ giúp khi thân vòng không ghi vào chính dữ liệu hàm đọc.

Và đây là chỗ đáng nhớ nhất, vì cái bẫy "đo lại cái không đổi trong mỗi vòng" này phổ biến hơn nhiều ở tầng cao — chỉ có điều compiler/runtime ít khi cứu được, nên nó cắn thật. Java: for (int i=0; i<list.size(); i++) thường ổn vì size() rẻ, nhưng gọi một hàm nặng (query DB, Pattern.compile, đọc file) trong điều kiện hay thân vòng là lỗi hiệu năng kinh điển mà JIT không kéo ra được vì nó có tác dụng phụ. Chỗ đau nhất là CSDL: một truy vấn lồng trong vòng ứng dụng (N+1 query) chính là strlen-trong-điều-kiện phóng đại — mỗi vòng một chuyến khứ hồi mạng, và không tầng nào tự gộp giúp bạn; phải tự kéo ra thành một truy vấn IN (...) hay JOIN. Mẫu số chung: tính một lần cái không đổi trong vòng là tối ưu compiler làm giúp bạn ở phạm vi hẹp (biểu thức thuần, dữ liệu nó chứng minh được bất biến), nhưng ở mọi ranh giới có tác dụng phụ — ghi bộ nhớ, gọi hàm mờ đục, truy vấn mạng — bạn phải tự tay kéo ra, vì máy không dám giả định thay bạn.

Muốn tự thấy thì 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.