Bạn có hai vòng lặp duyệt cùng một mảng, mỗi vòng làm một việc. Trực giác nói: gộp chúng thành một vòng — ghép vòng (loop fusion) — sẽ nhanh hơn, vì bớt được một lần đếm biến và một lần duyệt, và dữ liệu vào cache một lần dùng cho cả hai việc. Ngược lại có tách vòng (loop fission), chia một vòng làm nhiều việc thành nhiều vòng. Tôi vào đo, tin rằng ghép luôn thắng — và đo được rằng chiều nào thắng phụ thuộc một thứ tôi không ngờ: số luồng bộ nhớ.
Ghép và tách: hai chiều ngược nhau
Ghép gộp hai vòng thành một để dữ liệu chỉ phải vào cache một lần, và bớt chi phí quản lý vòng (tăng biến, so sánh, nhảy). Tách làm ngược lại: chia một vòng nặng làm nhiều việc thành nhiều vòng gọn, mỗi vòng đụng ít luồng dữ liệu hơn, đơn giản hơn nên dễ vector hóa và ít áp lực thanh ghi/cache.
Sách thường dạy ghép là tốt (locality) và ít nhắc tách. Tôi kiểm cả hai chiều trong container gcc:13 (ARM AArch64), với mảng lớn hơn cache. Lưu ý: cả hai bản đều không vector hóa vì compiler không biết các con trỏ có chồng lấn không (không có restrict), nên đây là so sánh scalar thuần — càng làm rõ tác động bộ nhớ.
Đo: ghép thắng khi tái dùng, thua khi thêm luồng
Ca ghép có lợi. Hai phép rút gọn (reduction) cùng chỉ đọc một mảng a (320MB): s1 = Σa[i] và s2 = Σa[i]². Bản hai vòng đọc a hai lần từ RAM; bản ghép đọc một lần:
hai vòng riêng (đọc a 2 lần) : 0,523 ns/phần tử
ghép một vòng (đọc a 1 lần) : 0,291 ns/phần tử -> ghép nhanh 1,8 lần
Đúng như sách: ghép cắt một nửa lưu lượng đọc (đọc a một lần thay hai), và vì cả hai việc chỉ đọc a — không thêm luồng bộ nhớ nào — nên ghép thắng rõ. Đây là fusion đúng nghĩa.
Ca ghép có hại. Giờ hai vòng mỗi vòng ghi một mảng khác: b[i] = a[i]+1 rồi c[i] = a[i]*2. Bản ghép làm cả hai trong một thân:
hai vòng riêng : 0,49 ns/phần tử
ghép một vòng : 1,36 ns/phần tử -> ghép CHẬM 2,75 lần
Ngược hẳn trực giác! Ghép chậm gần ba lần. Lý do: thân vòng ghép giờ đụng ba luồng bộ nhớ đồng thời — đọc a, ghi b, ghi c đan xen từng phần tử. Bản hai vòng thì mỗi vòng chỉ có hai luồng (đọc a, ghi một mảng), đơn giản hơn cho hệ thống bộ nhớ (bộ đệm ghi, băng thông). Dù bản ghép về lý thuyết đọc a ít hơn, cái giá của việc nhồi hai luồng ghi vào một thân lớn hơn nhiều. Và tôi đo lại với mảng nhỏ vừa cache (192KB) — ghép vẫn chậm 2,3 lần, nên đây không phải chuyện a có ở cache hay không, mà là số luồng đồng thời.
Đây là đo hớ của tôi. Tôi tin "ghép luôn nhanh vì ít overhead vòng". Đo ra chi phí quản lý vòng (mà ghép tiết kiệm) nhỏ xíu so với chi phí bộ nhớ; và ghép hay tách là bài toán về số luồng bộ nhớ đồng thời, không phải đếm số vòng. Khi thân đụng quá nhiều luồng, tách (fission) mới là cái nhanh.
Tách còn mở đường vector hóa
Một lý do nữa khiến tách vòng đáng giá mà phép đo scalar trên chỉ chạm nhẹ: mỗi vòng con đơn giản hơn thì vector hóa dễ hơn. Một vòng nặng làm năm việc, đụng năm mảng, có nhánh rẽ, thường khiến compiler bỏ cuộc không vector hóa được — quá nhiều ràng buộc. Tách nó thành năm vòng, mỗi vòng một phép đơn giản trên một mảng, và compiler có thể vector hóa từng cái. Ở đây tách không chỉ giảm số luồng đồng thời mà còn mở khóa một tối ưu khác hẳn.
Điều này cũng nối với chuyện aliasing: khi thân vòng ghi nhiều mảng, compiler càng khó chứng minh chúng không chồng lấn, nên càng dè dặt vector hóa. Vòng con một-mảng thì ít con trỏ để lo hơn. Nên khi một vòng nóng phức tạp không chịu vector hóa, thử tách nó ra — vừa giảm áp lực luồng bộ nhớ, vừa cho compiler cơ hội SIMD hóa từng phần. Đó là lý do các thư viện tính toán số thường viết nhiều vòng nhỏ chuyên biệt thay vì một vòng đa năng đồ sộ.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: ghép khi tái dùng dữ liệu, tách khi thân quá nhiều luồng. Nếu hai vòng cùng đọc một mảng lớn và không thêm mảng ghi nào, ghép chúng để đọc một lần — thắng thật (1,8 lần). Nhưng nếu ghép làm thân vòng đọc/ghi nhiều mảng lớn cùng lúc, hệ thống bộ nhớ nghẽn ở số luồng, và giữ chúng thành các vòng riêng (mỗi vòng ít luồng) lại nhanh hơn. Đừng gộp vòng theo phản xạ "ít vòng = nhanh".
Hệ quả thứ hai: compiler dè dặt với cả hai phép, nên đây là việc của bạn. gcc có các cờ -floop-* nhưng rất thận trọng tự ghép/tách vì chúng đổi thứ tự truy cập bộ nhớ (rủi ro nếu có aliasing) và tác động khó đoán. Trong thực tế, chính bạn cấu trúc vòng theo mẫu truy cập — và cách duy nhất biết chiều nào thắng là đo trên dữ liệu thật, vì nó phụ thuộc kích thước mảng, số luồng, và cache của máy đích.
Hệ quả thứ ba là bài học đo lường của cả sê-ri: "ít vòng hơn thì nhanh hơn" là đếm sai thứ. Cái tốn không phải số lần lặp hay số vòng, mà là lưu lượng và số luồng bộ nhớ. Con số mang theo: ghép/tách vòng quyết định bởi SỐ LUỒNG bộ nhớ đồng thời trong thân, không phải số vòng — ghép hai reduction cùng đọc một mảng (không thêm luồng ghi) nhanh 1,8 lần (0,291 so 0,523 ns) nhờ đọc một lần; nhưng ghép hai vòng mỗi vòng ghi một mảng (thêm 2 luồng ghi đan xen) CHẬM 2,75 lần (1,36 so 0,49 ns), kể cả khi mảng vừa cache — nên ghép để tái dùng dữ liệu, tách khi thân đụng quá nhiều luồng. Đo mẫu truy cập của bạn, đừng đếm số vòng.
Thử ba mươi giây
Viết hai vòng ghi hai mảng: for(i) b[i]=a[i]+1; rồi for(i) c[i]=a[i]*2;, với a,b,c là ba mảng lớn (vài trăm MB). Đo thời gian. Rồi gộp thành một vòng làm cả hai và đo lại. Trên nhiều máy bạn sẽ thấy bản ghép chậm hơn, vì thân vòng giờ đan xen ba luồng bộ nhớ. Rồi thử ca ngược: hai vòng chỉ đọc cùng mảng a để tính hai tổng khác nhau — ghép chúng lại và đo: lần này ghép nhanh hơn, vì đọc a một lần thay hai mà không thêm luồng. Ba mươi giây đó cho bạn thấy quy tắc thật không phải "ghép hay tách", mà là "đếm số luồng bộ nhớ trong thân vòng".
