"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 trên một lõi CPU hiện đại và rộng như phần 10 đã đo, câu chuyện khác hẳn. 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.
Một lần tôi đo hớ: "unroll luôn nhanh hơn" và "unroll là việc tay phải tự làm"
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". Đo phá tan: 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 đo cũng phá một niềm tin ngược: "unroll là kỹ thuật tay quan trọng, phải tự bung vòng cho khéo". 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.
Bài học đo lường: unroll MỘT MÌNH hiếm khi giúp trên lõi rộng hiện đại — đo: L1 1 accumulator bung 1/2/4/8 cho ns/phần tử Y HỆT (0,2136) vì lõi out-of-order đã giấu chi phí vòng và nút cổ chai là chuỗi phụ thuộc. Cái GIÚP là phá chuỗi bằng nhiều accumulator độc lập: L1 3,5x (0,061), RAM 2,1x (0,116, mở MLP). Memory-bound thì unroll thuần vô ích. Và -O3 TỰ vector hóa tổng -> 0,041 ns, compiler lo hộ. 'Unroll luôn nhanh hơn' và 'unroll phải tự làm tay' đều SAI. Nếu tin "unroll luôn nhanh" tôi bung mù mà không nhanh; nếu tin "phải tự làm tay" tôi bỏ qua chuyện compiler đã làm tốt hơn.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầ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.
Hệ quả 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).
Hệ quả thứ ba là tinh thần đo lường: một tối ưu chỉ "giúp" khi nó chạm đúng nút cổ chai — unroll thường không. Con số mang theo: unroll 1 accumulator: 0 lợi ích (0,2136 bất kể 1/2/4/8); phá chuỗi (nhiều acc): 3,5x (L1), 2,1x (RAM/MLP); memory-bound: unroll vô ích; -O3 tự vector hóa: 0,041 ns. Hỏi nút cổ chai trước, để compiler lo phần cơ khí. Cùng một vòng lặp, bung ra hay không, tốc độ không đổi — cho tới khi bạn chạm đúng thứ đang giới hạn nó.
Thử ba mươi giây
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 bạn 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.
