Mở vòng lặp

Mở vòng lặp (loop unrolling) là một tối ưu nghe rất trực quan: thay vì chạy một thân vòng lặp rồi kiểm tra điều kiện và nhảy lại mỗi lần, trình biên dịch chép thân ra vài lần rồi mới nhảy — bớt được lệnh điều khiển. Sách vở giải thích lợi ích của nó đúng như vậy: giảm nhánh. Bài này bật -funroll-loops và đo xem nó nhanh lên bao nhiêu, tốn thêm bao nhiêu kích thước — và phát hiện cái nhanh thật sự đến từ một nơi hoàn toàn khác với điều tôi (và sách vở) tưởng.

Mở vòng lặp là làm nhiều thân mỗi lần lặp

Một vòng lặp for(i=0;i<n;i++) body; bình thường, mỗi phần tử tốn: thân vòng, một phép tăng i, một phép so sánh, và một lệnh nhảy về đầu. Với body rất nhỏ, phần "điều khiển" (tăng, so, nhảy) có thể chiếm tỷ lệ đáng kể. Nhưng đó là cách nhìn của thời CPU cũ, khi mỗi lệnh chạy tuần tự và một lệnh nhảy tốn nhiều chu kỳ; CPU hiện đại chạy nhiều lệnh song song và đoán nhánh gần như chính xác, nên cái "tiết kiệm nhánh" ấy đã nhỏ đi rất nhiều — một trực giác phần cứng cũ dễ bê nhầm sang phần cứng mới.

Mở vòng lặp chép thân ra nhiều bản — ví dụ làm 4 phần tử liên tiếp rồi mới kiểm tra và nhảy — nên chi phí điều khiển được chia cho 4. -O2 không mở vòng mặc định; -funroll-loops và một phần của -O3 thì có. Cái giá hiển nhiên: mã phình to hơn, gây áp lực lên cache lệnh. Tôi viết một vòng lặp cộng dồn s += i*3 + 1 qua một tỷ vòng, rồi so ba cấu hình.

Đo: nhanh 3.5 lần, nhưng nhánh không đổi

Thời gian (trung vị) và kích thước .text:

Cả ba cho cùng kết quả. -funroll-loops nhanh hơn -O2 3,5 lần (288 xuống 83 ms) và đúng như dự đoán, mã lớn hơn (1648 lên 1916 byte). Nhưng có hai điều không khớp với câu chuyện "giảm nhánh". Thứ nhất, khi đếm số lệnh nhảy trong vòng lặp, cả -O2 lẫn -funroll đều còn một nhánh — việc mở vòng chỉ làm nhánh xảy ra thưa hơn, không xóa nó. Thứ hai, -O3 — mã lớn nhất (2087 B), thậm chí có nhiều nhánh hơn — lại chậm hơn -funroll gần bằng -O2. Nếu "to hơn / ít nhánh hơn = nhanh hơn", những con số này vô lý. Nên tôi đọc assembly.

Một lần tôi đo hớ: cái nhanh nằm ở phá chuỗi phụ thuộc

Tôi vào bài với đúng lời sách vở trong đầu: mở vòng lặp giúp nhờ bớt nhánh, và trên CPU hiện đại thì cái lợi đó nhỏ vì nhánh vòng lặp được bộ dự đoán nhánh đoán gần như hoàn hảo. Với suy nghĩ đó, -funroll nhanh 3,5 lần là điều khó hiểu — bớt một nhánh gần-như-miễn-phí sao lại nhanh gấp mấy lần? Đọc assembly mới lộ ra sự thật, và nó chẳng liên quan gì tới nhánh.

Ở -O2, vòng lặp dùng một ô tích lũy duy nhất:

add x0, x0, x1     ; s = s + (i*3+1), x0 là tổng
add x1, x1, 3      ; chuẩn bị số hạng kế

Mỗi phép add x0, x0, x1 phải chờ kết quả của phép add x0 ở vòng ngay trước — vì cùng ghi vào x0. Đây là một chuỗi phụ thuộc: dù CPU có nhiều đơn vị cộng, chúng phải xếp hàng, mỗi vòng chờ vòng trước. Còn ở -funroll, trình dịch dùng bốn ô tích lũy song song (add x0, add x8, add x11, add x12) — bốn tổng riêng, mỗi cái cộng một phần tư số phần tử, rồi gộp lại ở cuối. Bốn phép cộng này độc lập nhau, nên CPU chạy chúng đồng thời trên các đơn vị thực thi khác nhau (song song mức lệnh, ILP). Đó — chứ không phải bớt nhánh — mới là 3,5 lần tốc độ.

Bằng chứng ngược chốt lại: -O3 mã lớn nhất, nhiều nhánh hơn, nhưng nó giữ nguyên chuỗi phụ thuộc một ô (không tách thành nhiều tổng), nên vẫn chậm ngang -O2. Mã to hơn mà không phá được chuỗi phụ thuộc thì không nhanh hơn. Bài học đo lường: đừng gán tốc độ cho nguyên nhân hiển nhiên (nhánh) — đọc assembly để tìm nguyên nhân thật (chuỗi phụ thuộc). Cả câu mô tả trong sách ("mở vòng lặp giảm nhánh") lẫn trực giác của tôi ("giảm nhánh thì lợi ít") đều đúng về chi tiết mà sai về nguyên nhân chính. Chỉ có việc đọc bốn thanh ghi tích lũy khác nhau mới cho tôi câu trả lời.

Vì sao điều này quan trọng khi lập trình

Hệ quả đầu tiên là hiểu chuỗi phụ thuộc mới là nút thắt của vòng lặp số học, không phải nhánh. Khi một vòng lặp cộng/nhân dồn vào một biến, mỗi phép phải chờ phép trước, và tốc độ bị chặn bởi độ trễ của một phép toán chứ không phải thông lượng của CPU. Muốn nhanh, phải phá chuỗi: dùng nhiều biến tích lũy độc lập rồi gộp cuối (chính cái -funroll làm tự động). Bạn có thể tự tay làm điều này khi trình dịch không làm — đó là kỹ thuật "nhiều accumulator" quen thuộc trong tối ưu số học. Ví dụ khi tính tổng hay tích vô hướng của một mảng lớn, chia thành bốn tổng riêng chạy song song rồi cộng lại thường nhanh gấp mấy lần một tổng đơn — đúng cái trình dịch vừa làm hộ khi ta bật -funroll-loops.

Hệ quả thứ hai là -funroll-loops không phải nút thần kỳ, và cũng không phải vô dụng. Nó giúp lớn khi vòng lặp bị chặn bởi chuỗi phụ thuộc và trình dịch tách được thành nhiều luồng; nhưng với vòng lặp đã bị chặn bởi bộ nhớ (đọc/ghi mảng lớn) hoặc đã vector hóa, mở vòng chỉ làm mã to ra mà không nhanh thêm — thậm chí chậm đi vì cache lệnh. Đừng bật nó khắp nơi theo niềm tin; hãy đo, và nhớ rằng cái lợi phụ thuộc vào bản chất nút thắt của từng vòng.

Hệ quả thứ ba là bài học đo lường tổng quát của cả sê-ri: một tối ưu có thể mang lại lợi ích lớn qua một cơ chế hoàn toàn khác với cái tên gọi của nó gợi ra. "Mở vòng lặp" nghe như chuyện nhánh, nhưng ở đây nó là chuyện song song hóa. Con số mang theo: -funroll-loops làm vòng lặp cộng dồn nhanh 3,5 lần bằng cách dùng nhiều ô tích lũy song song để phá chuỗi phụ thuộc (ILP), chứ không phải bằng cách bớt nhánh — và mã to hơn (-O3) không bảo đảm nhanh hơn nếu chuỗi phụ thuộc còn nguyên. Muốn biết một tối ưu thật sự làm gì, đừng đọc tên nó — đọc assembly nó sinh ra.

Thử ba mươi giây

Viết một vòng lặp for(i=0;i<n;i++) s += a[i]; cộng dồn vào một biến s, dịch gcc -O2 -S file.c -o o2.s rồi gcc -O2 -funroll-loops -S file.c -o u.s, và so hai file. Trong o2.s bạn sẽ thấy một thanh ghi tích lũy duy nhất được cộng lặp lại; trong u.s bạn sẽ thấy nhiều thanh ghi khác nhau được cộng song song rồi gộp cuối. Đó chính là chuỗi phụ thuộc bị phá thành nhiều luồng — cái làm nên tốc độ. Chỉ hai lần đọc .s là bạn thấy vì sao "mở vòng lặp" thật ra là chuyện song song, không phải chuyện nhánh.