Bung vòng lặp (loop unrolling) là một trong những tối ưu được dạy sớm nhất, với một lời giải thích gọn: "mỗi vòng lặp tốn vài lệnh điều khiển — tăng biến đếm, kiểm điều kiện, nhảy về đầu; chép thân vòng bốn lần thì trả cái chi phí đó một lần cho bốn phần tử thay vì cho mỗi phần tử". Đúng, nhưng lời giải thích đó bỏ lỡ nơi phần lớn tốc độ thật sự đến từ. Bài này đo cả hai mặt, và tìm ra rằng bung vòng "cơ học" mà trình biên dịch làm gần như vô dụng — cái đáng giá là một thứ khác hẳn.
Hai lý do để bung, và lý do lớn hơn
Lý do "sách vở" của bung vòng là giảm chi phí điều khiển: mỗi lần lặp có phần tính toán thật (thân vòng) cộng phần quản lý vòng (tăng biến đếm, so điều kiện, nhánh quay lại). Bung x4 gộp bốn thân vòng lại, trả chi phí quản lý một lần cho bốn phần tử. Với thân vòng nhỏ, phần quản lý chiếm tỉ lệ đáng kể, nên bung giúp.
Nhưng lý do lớn hơn nằm ở kiến trúc CPU: phá chuỗi phụ thuộc để tăng ILP (instruction-level parallelism, song song mức lệnh). Xét một vòng cộng dồn acc = acc*C + a[i]: mỗi lần tính acc mới cần giá trị acc cũ, nên phép nhân của bước sau phải chờ phép nhân bước trước xong. Phép nhân mất vài chu kỳ (độ trễ), và CPU — dù có nhiều đơn vị nhân — không thể chạy song song vì chúng phụ thuộc nhau. Vòng bị nghẽn ở độ trễ, không phải thông lượng. Bung vòng với nhiều biến tích lũy độc lập phá thế nghẽn đó: bốn biến s0, s1, s2, s3, mỗi biến một chuỗi riêng, cho CPU chạy bốn phép nhân cùng lúc. Tôi đo cả hai hiệu ứng.
Đo: nhiều biến tích lũy, nhanh gần bốn lần
Tôi lấy vòng acc = acc*C + a[i] (mảng nằm gọn trong cache để đo độ trễ, không đo băng thông) và bung tay với 1, 2, 4, 8 biến tích lũy độc lập:
Chuỗi acc=acc*C+a[i], ns mỗi phần tử:
x1 (1 chuỗi, phụ thuộc) : 0,911 ns (1,00x)
x2 (2 chuỗi độc lập) : 0,463 ns (1,97x)
x4 (4 chuỗi độc lập) : 0,245 ns (3,72x)
x8 (8 chuỗi độc lập) : 0,378 ns (2,41x) <- chậm hơn x4!
Từ x1 lên x4, tăng tốc gần tuyến tính: 1,97x rồi 3,72x. Mỗi biến tích lũy thêm cho CPU một chuỗi độc lập để chạy song song, và ở x4 nó lấp đầy khả năng thực thi. Nhưng nhìn x8: chậm hơn x4 (2,41x so với 3,72x). Đây là chỗ đo hớ đầu tiên: "càng bung càng tốt" là sai. Quá điểm bão hòa — khi số chuỗi song song vượt số đơn vị thực thi (hay số thanh ghi khả dụng, gây tràn ra ngăn xếp) — bung thêm chỉ tạo áp lực mà không thêm song song, và tốc độ thoái lui. Có một điểm ngọt, ở đây quanh x4, và vượt qua nó là hại.
Một lần tôi đo hớ: bung cơ học của compiler gần như vô dụng
Định kiến lớn hơn của tôi: "bung vòng là chép thân vòng, và trình biên dịch làm điều đó với cờ -funroll-loops, nên bật cờ là được tăng tốc". Tôi đo vòng acc = acc*C + a[i] (bản một biến, chuỗi phụ thuộc) qua các cờ:
Cùng vòng chuỗi phụ thuộc:
-O2 : 0,911 ns
-O3 : 0,912 ns
-O2 -funroll-loops : 0,911 ns (không nhanh hơn!)
-O3 -funroll-loops : 0,918 ns
Số lệnh trong hàm:
-O2 : 121 lệnh
-O2 -funroll-loops : 314 lệnh (phình 2,6 lần)
-funroll-loops thật sự bung vòng — mã máy phình từ 121 lên 314 lệnh, gấp 2,6 lần. Nhưng thời gian không đổi một chút nào: 0,911 ns cả có lẫn không. Vì sao bung mà không nhanh hơn? Vì trình biên dịch bung cơ học — nó chép thân vòng nhiều lần nhưng vẫn dùng một biến tích lũy, giữ nguyên chuỗi phụ thuộc. Nó giảm được chi phí điều khiển (ít nhánh hơn), nhưng chi phí đó vốn đã bị che khuất hoàn toàn bởi độ trễ của phép nhân — nên giảm nó chẳng đổi gì. Cái tăng tốc 3,72x ở phần trước không đến từ việc chép thân vòng; nó đến từ việc tách chuỗi phụ thuộc thành nhiều biến tích lũy — một biến đổi ngữ nghĩa mà trình biên dịch không tự làm cho phép cộng số nguyên (hay float, trừ khi bật -ffast-math), vì nó đổi thứ tự phép tính. Bung cơ học của compiler ở đây chỉ để lại mã phình và không lợi ích.
Đây cũng là lý do GCC không tự bung vòng ngay cả ở -O3 — phải bật -funroll-loops thủ công. Không phải vì các nhà làm GCC lười, mà vì đo đạc cho thấy bung cơ học thường chỉ phình mã (ép cache lệnh) mà không tăng tốc, trừ những trường hợp hẹp.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: đừng bung vòng bằng tay chỉ để "giảm nhánh" — CPU hiện đại đoán nhánh vòng lặp gần như hoàn hảo, nên chi phí điều khiển đã rất nhỏ. Cái đáng làm, khi bạn có một vòng nóng nghẽn ở độ trễ (một chuỗi cộng/nhân dồn), là dùng nhiều biến tích lũy để phá chuỗi phụ thuộc — đó mới là nguồn của tăng tốc mấy lần. Và đo để tìm điểm ngọt: thường 2-4 biến, hiếm khi hơn 8, vì vượt qua là thoái lui.
Hệ quả thứ hai: -funroll-loops không phải nút tăng tốc, và nên đo trước khi bật. Nó phình mã và chỉ giúp trong vài trường hợp (vòng thân nhỏ, số lần lặp biết trước, không nghẽn độ trễ). Với vòng đã vector hóa hay nghẽn băng thông bộ nhớ, bung không giúp gì. Việc GCC để nó tắt mặc định là một tín hiệu: nếu bung cơ học đáng giá phổ quát, nó đã được bật ở -O2.
Hệ quả thứ ba là bài học đo lường của bài: hiểu vì sao một tối ưu giúp quan trọng hơn cái tên của nó. Con số mang theo: bung vòng với nhiều biến tích lũy độc lập nhanh 3,72 lần (phá chuỗi phụ thuộc, tăng ILP), nhưng x8 lại chậm hơn x4 (2,41x, vượt sức song song CPU); và bung cơ học của -funroll-loops phình mã 2,6 lần mà 0 tăng tốc vì giữ nguyên một biến tích lũy. "Bung vòng" gộp hai thứ rất khác nhau — chép thân vòng (compiler làm, ít giá trị) và tách chuỗi phụ thuộc (bạn làm, giá trị lớn). Biết mình cần cái nào, và đo để tìm điểm bão hòa, mới là tối ưu đúng.
Thử ba mươi giây
Viết một vòng cộng dồn có phụ thuộc, for(i) sum = sum*3 + a[i];, đo thời gian. Rồi viết bản "bung tay bốn biến": bốn biến s0..s3, mỗi biến nhận a[i], a[i+1], a[i+2], a[i+3], cuối cùng cộng lại. Đo lại — bạn sẽ thấy bản bốn biến nhanh hẳn (2-4 lần), dù cùng số phép tính. Rồi thử tám biến: rất có thể nó không nhanh hơn bốn, thậm chí chậm hơn. Ba mươi giây đó cho bạn thấy lợi thật của bung vòng là phá chuỗi phụ thuộc cho CPU chạy song song, và cái điểm ngọt mà vượt qua là hại — hai điều mà "chép thân vòng cho ít nhánh" không hề nói tới.
