Gộp hai vòng làm một tưởng nhanh hơn — tôi đo, nó chậm đi 2,75 lần

Hình dung một đầu bếp có bốn cái bếp. Gộp nhiều món vào nấu một lượt nghe là tiết kiệm — đỡ phải lấy nguyên liệu ra hai lần. Nhưng nếu "gộp" nghĩa là bắc năm cái nồi lên cùng lúc trong khi chỉ có bốn bếp, anh ta phải luân phiên, đảo qua đảo lại, và mọi món cùng chậm. Đôi khi nấu thành hai đợt, mỗi đợt vài nồi, lại nhanh hơn — vì số bếp mới là giới hạn, không phải số lần vào bếp. Vòng lặp đụng bộ nhớ có đúng cái giới hạn "số bếp" đó, và tôi đã quên mất nó khi tin rằng gộp vòng luôn thắng.

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 — ghép vòng (loop fusion) — sẽ nhanh hơn, vì bớt một lần đếm biến, 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 đo trong container gcc:13 (ARM), 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 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. Một cái bếp, hai món cùng dùng.

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 — đúng cảnh năm nồi trên bốn bếp. 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à chỗ tôi nhầm. 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ề đến code hằng ngày

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

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

Và cái căng thẳng "gộp một lượt hay chia nhiều đợt" này chính là một trong những quyết định lớn nhất ở tầng cao, chỉ đổi tên. Java Streams: một chuỗi .map().filter().map() được ghép (loop fusion) trong một lần duyệt lazy — tốt khi các bước nhẹ, nhưng nếu mỗi bước sinh một collection trung gian đồ sộ thì bạn đang trả giá đúng như ghép-quá-nhiều-luồng. Spark và các engine dữ liệu lớn có hẳn khái niệm pipelining vs shuffle: gộp các phép vào một stage để dữ liệu chảy qua một lần, nhưng khi phải vật chất hóa nhiều luồng thì tách stage lại rẻ hơn. CSDL còn rõ hơn: bộ tối ưu chọn giữa một plan pipeline (một lần quét, ít bộ nhớ) và materialize kết quả trung gian, cân đúng cái đánh đổi băng thông vs số luồng này. Mẫu số chung: "làm tất cả trong một lượt" chỉ thắng khi lượt đó không bị quá tải tài nguyên đồng thời (bếp, luồng bộ nhớ, bộ đệm) — quá ngưỡng thì chia nhỏ ra lại nhanh hơn, và chỉ đo mới biết ngưỡng nằm đâu.

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