"Bung vòng lặp" (loop unrolling) là một trong những tối ưu tay được dạy sớm nhất: lặp lại thân vòng vài lần trong mỗi vòng để làm nhiều phần tử một lượt, nhờ đó giảm chi phí vòng — số lần tăng biến đếm, so sánh điều kiện, và nhảy. Nghe rất hợp lý: ít lệnh điều khiển hơn thì nhanh hơn.

Nhưng hãy nghĩ tới một dây chuyền đóng gói. "Chi phí vòng" giống động tác với tay lấy hộp rỗng tiếp theo giữa mỗi lần đóng gói. Bung vòng là gộp bốn món vào một lần với tay. Hợp lý — nếu việc với tay là nút thắt. Nhưng nếu công nhân của bạn có nhiều tay và làm động tác với-tay song song với việc đóng gói (lõi out-of-order), thì gộp lại chẳng tiết kiệm gì. Và nếu nút thắt thật là băng chuyền chở hàng tới quá chậm (băng thông bộ nhớ), thì thao tác tay nhanh cỡ nào cũng vô nghĩa. Tôi bung cùng một vòng cộng mảng theo các mức 1x/2x/4x/8x và đo trong container gcc:13 trên host ARM — kết quả cho thấy unroll một mình thường chẳng giúp gì, và cái thực sự tạo khác biệt là một thứ khác.

Unroll cắt chi phí vòng — nhưng chi phí đó có còn không?

Ý tưởng unroll: một vòng for(i=0;i<n;i++) s+=a[i]; mỗi phần tử phải trả thêm phần điều khiển vòng (tăng i, so i<n, nhảy về đầu). Bung 4x — s+=a[i]; s+=a[i+1]; s+=a[i+2]; s+=a[i+3]; mỗi vòng — chia phần điều khiển đó cho 4 phần tử, giảm chi phí mỗi phần tử.

Nhưng có hai lý do khiến điều này không còn đúng trên lõi hiện đại. Thứ nhất, lõi out-of-order (thực thi ngoài thứ tự) chạy phần điều khiển vòng song song với công việc thật — bộ dự đoán nhánh đoán đúng vòng lặp, và việc tăng/so/nhảy lấp vào những khe phát trống, gần như miễn phí (xem bề rộng phát lệnh, phần 10). Thứ hai, nếu nút cổ chai thật của vòng nằm ở chỗ khác — một chuỗi phụ thuộc hay băng thông bộ nhớ — thì cắt chi phí vòng chẳng chạm tới nút cổ chai đó. Đo mới biết.

Đo: unroll một mình không nhúc nhích

Tôi cộng một mảng int64 bằng một biến tích lũy, bung 1x/2x/4x/8x, đo ns mỗi phần tử — trong hai tình huống: mảng nhỏ nằm trong L1, và mảng lớn phải đọc từ RAM (-O2, tắt vector hóa để cô lập tác dụng của unroll):

Tổng mảng, ns/phần tử, host ARM, g++ -O2 (không vector hóa):

   A. L1 (32 KB), 1 accumulator (chuỗi phụ thuộc trên s)
      unroll 1 : 0,2136       unroll 4 : 0,2136
      unroll 2 : 0,2136       unroll 8 : 0,2136   <- Y HỆT nhau
      unroll 4 + 4 accumulator ĐỘC LẬP : 0,061   <- 3,5x

   C. RAM (512 MB, memory-bound), 1 accumulator
      unroll 1 : 0,249        unroll 8 : 0,229    <- gần phẳng
      unroll 4 + 4 accumulator : 0,116            <- 2,1x

Nhìn tình huống A: bung 1, 2, 4, 8 lần đều cho đúng 0,2136 ns mỗi phần tử — không đổi một chút nào. Unroll ở đây hoàn toàn vô ích, vì hai lý do vừa nói: lõi out-of-order đã giấu chi phí vòng (nên chẳng có gì để cắt), và nút cổ chai thật là chuỗi phụ thuộc trên biến s — mỗi s += a[i] phải đợi giá trị s trước, chạy đúng 1 phép cộng mỗi chu kỳ (0,2136 ns ≈ 1 chu kỳ, như phần 11). Unroll không đụng tới chuỗi đó.

Cái thực sự giúp: bung 4x nhưng dùng 4 biến tích lũy độc lập (s0+=a[i]; s1+=a[i+1]; ... rồi gộp cuối) — 0,061 ns, nhanh 3,5 lần. Đây không phải nhờ "cắt chi phí vòng" mà nhờ phá chuỗi phụ thuộc, cho lõi rộng chạy nhiều phép cộng độc lập song song (ILP, phần 3). Unroll chỉ là phương tiện để bày ra song song ấy — bản thân nó không tạo ra tốc độ.

Nhìn tình huống C (RAM): unroll 1 acc gần phẳng (0,249 → 0,229) — vòng memory-bound, băng thông và độ trễ bộ nhớ mới là trần, unroll chẳng phá được. Nhưng 4 accumulator độc lập lại nhanh 2,1 lần (0,116) — vì nhiều biến cho phép nhiều lần nạp bộ nhớ chạy song song (memory-level parallelism), rút được nhiều băng thông hơn. Lại là phá chuỗi, không phải unroll thuần.

Hai niềm tin đối nghịch, cùng sai

Tôi vào đo với niềm tin kinh điển: "unroll cắt chi phí vòng nên luôn làm nhanh hơn, cứ bung là được". Con số bác ngay: bung một biến tích lũy 1/2/4/8 lần cho ns mỗi phần tử y hệt (0,2136) — không nhanh hơn một tí nào. Lõi out-of-order hiện đại đã giấu chi phí vòng từ trước, nên không còn gì để unroll cắt; và nếu nút cổ chai là chuỗi phụ thuộc hay bộ nhớ, unroll cũng không chạm tới. Cái tạo khác biệt (3,5 lần ở L1, 2,1 lần ở RAM) là phá chuỗi bằng nhiều biến độc lập — unroll chỉ hữu ích khi nó đi kèm việc đó. "Unroll = nhanh hơn" là một phản xạ sai; phải hỏi nút cổ chai là gì trước.

Nhưng nếu vì thế mà nghĩ "unroll là kỹ thuật tay quan trọng, phải tự bung vòng cho khéo" thì cũng sai theo hướng khác. Khi tôi bật -O3, trình biên dịch tự vector hóa vòng cộng (tổng số nguyên kết hợp được nên nó được phép gom vào SIMD), và bản bung 8x tụt xuống 0,041 ns — nhanh hơn mọi phiên bản tôi bung tay ở -O2. Cái "khéo" thật sự là vector hóa do compiler làm, không phải mấy dòng unroll tay. Trên thực tế, bung tay quá nhiều còn hại: phình mã, tăng áp lực icache và thanh ghi. Việc của bạn thường chỉ là viết vòng sạch, cho phép compiler tối ưu, rồi để nó lo.

Về đến code hằng ngày

Việc đầu tiên: trước khi unroll, hỏi nút cổ chai là gì. Nếu vòng bị trói bởi chuỗi phụ thuộc, cách chữa là nhiều biến tích lũy độc lập (unroll + tách biến), không phải unroll suông. Nếu bị trói bởi bộ nhớ, cách chữa là cải thiện bố cục/truy cập tuần tự, chứ unroll không giúp. Unroll suông chỉ đáng khi vòng thật sự bị chi phối bởi chi phí điều khiển — hiếm hơn ta tưởng trên lõi rộng.

Việc thứ hai: để trình biên dịch làm phần cơ khí, bạn lo phần thuật toán và bố cục. Bật -O2/-O3, viết vòng đơn giản để nó vector hóa/unroll được (phần tử độc lập, truy cập liền, không aliasing) — nó thường bung và vector hóa tốt hơn tay. Bung tay chỉ khi bạn đo thấy nó thắng và hiểu vì sao (thường là để lộ ILP mà compiler không tự thấy, ví dụ với số thực không kết hợp — xem phần 3).

Cái bài học "tối ưu chỉ giúp khi chạm đúng nút cổ chai" này lên tầng cao còn đắt giá hơn, vì ở đó người ta hay unroll-nhầm bằng tiền và công sức. JIT của JVM và của Go tự unroll và vector hóa vòng nóng, nên viết vòng Java/Go "khéo" bằng tay hiếm khi thắng — thứ đáng làm là giúp JIT (vòng đơn giản, tránh nhánh khó đoán). Rộng hơn, cả nguyên tắc "hỏi nút cổ chai trước khi tối ưu" là kim chỉ nam ở mọi quy mô: thêm cache trước một service đang CPU-bound chẳng giúp gì; tối ưu một truy vấn chạy 1% thời gian là lãng phí; mua thêm server khi nút thắt là một cái khóa dùng chung (như tranh chấp atomic) thì tiền đổ sông. Profiler tồn tại chính để trả lời câu "nút cổ chai ở đâu" trước khi bạn ra tay — y hệt việc đo ns mỗi phần tử ở đây. Tối ưu mà không đo nút thắt là bung vòng trong bóng tối.

Muốn tự thấy thì viết một vòng cộng mảng int64 vừa trong cache bằng một biến tích lũy, rồi bung tay 2x, 4x, 8x (vẫn một biến), biên dịch -O2 -fno-tree-vectorize và bấm giờ ns mỗi phần tử (nhớ volatile sink, min nhiều lần). Bạn sẽ thấy bốn con số gần như y hệt — unroll một mình không giúp, vì lõi đã giấu chi phí vòng và bạn đang bị chuỗi phụ thuộc trói. Giờ đổi sang bốn biến tích lũy độc lập cộng bốn phần tử mỗi vòng rồi gộp cuối: nhanh vài lần, vì bạn vừa phá chuỗi. Cuối cùng, biên dịch lại bản gốc với -O3 (bật vector hóa) và đo: trình biên dịch tự gom phép cộng vào SIMD và nhanh hơn cả bản bung tay của bạn. Ba mươi giây đó cho thấy điều mà "unroll luôn làm nhanh hơn" giấu đi: bung vòng chỉ là hình thức; thứ quyết định tốc độ là bạn có chạm đúng nút cổ chai — chuỗi phụ thuộc, bộ nhớ, hay bề rộng lõi — hay không, và thường thì trình biên dịch làm phần cơ khí ấy giỏi hơn tay bạn.