Bật -funroll-loops phình mã gấp 2,6 lần mà không nhanh hơn một giây — lợi thật của bung vòng nằm ở chỗ khác

Hình dung một dây chuyền chỉ có một người: mỗi món phải làm xong hoàn toàn rồi mới bắt đầu món kế, vì bước sau cần kết quả bước trước. Bạn có thể xếp việc gọn hơn, bớt thời gian đi lại giữa các bước — nhưng chừng nào vẫn một người làm tuần tự, tốc độ bị chặn ở chỗ mỗi món phải chờ món trước. Cách thật sự nhanh là mở bốn dây chuyền song song, mỗi cái xử lý phần việc độc lập của mình. Vòng lặp có chuỗi phụ thuộc trong CPU vấp đúng thế bí đó, và "bung vòng" — nếu hiểu sai — chỉ là xếp lại việc cho một người, chứ không mở thêm dây chuyền.

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ử". Đúng, nhưng lời giải thích đó bỏ lỡ nơi phần lớn tốc độ thật sự đến từ. Tôi đo cả hai mặt trong container gcc:13 (ARM), 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 — đúng cái dây chuyền một người. 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, như mở bốn dây chuyền. 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ỗ tôi vấp đầ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. Đúng cảnh mở tám dây chuyền khi chỉ có bốn bàn. Có một điểm ngọt, ở đây quanh x4, và vượt qua nó là hại.

Cú vấp: 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ì. Vẫn là một người làm tuần tự, chỉ bớt vài bước đi lại. 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.

Đâ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ề đến code hằng ngày

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

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

Và đây là chỗ đáng nhớ, vì "phá chuỗi phụ thuộc để chạy song song" là một trong những ý tưởng hiệu năng sâu nhất, vượt xa vòng lặp C. Đây chính là lý do các phép rút gọn song song (parallel reduction) trên GPU và trong java.util.stream phải cộng theo cây nhiều nhánh độc lập chứ không tuần tự — cùng nguyên lý nhiều-biến-tích-lũy, phóng lên hàng nghìn lõi. Ở tầng hệ thống, đây là vì sao một pipeline xử lý bất đồng bộ (nhiều request "in-flight" cùng lúc) đạt throughput cao hơn hẳn kiểu gửi-một-chờ-một, dù mỗi request vẫn mất từng ấy thời gian: bạn phá chuỗi phụ thuộc giữa các request. Và nó soi rõ một sự thật đo lường: độ trễ (một việc mất bao lâu) và thông lượng (làm được bao nhiêu việc mỗi giây) là hai trục khác nhau — chuỗi phụ thuộc khóa bạn vào độ trễ, và cách thoát là tìm việc độc lập để chồng lên nhau. Mẫu số chung: khi một tính toán bị nghẽn vì mỗi bước chờ bước trước, tốc độ không đến từ làm mỗi bước nhanh hơn mà từ việc tìm ra các chuỗi độc lập để chạy song song — ở CPU là nhiều biến tích lũy, ở hệ thống là nhiều request in-flight, cùng một ý tưởng.

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