Sắp mảng trước khi chạy, cùng code lại nhanh gấp 1,7 lần — vì sao?

Một người pha chế lành nghề, khi hàng dài khách gọi y hệt nhau — "đen đá, đen đá, đen đá" — làm nhoay nhoáy vì đoán trước được ly kế tiếp, tay đã với sẵn. Nhưng nếu mỗi khách gọi một kiểu ngẫu nhiên, không đoán được gì, anh ta khựng lại một nhịp mỗi lần để nghe cho rõ. Cùng số ly pha ra, cùng những món ấy — nhưng thứ tự đoán được hay không quyết định tốc độ. CPU của bạn cũng y hệt. Suốt sê-ri ta đã thấy đồng hồ nói khác big-O vì cache, cấp phát, bố cục. Bài này đo một hiệu ứng còn kỳ lạ hơn: cùng một đoạn code, chạy trên cùng tập dữ liệu với cùng các giá trị, có thể nhanh gần gấp đôi chỉ vì dữ liệu được sắp xếp trước. Thủ phạm là một cơ chế phần cứng mà không phân tích thuật toán nào nhắc tới: dự đoán nhánh.

CPU đoán nhánh để không phải chờ

CPU hiện đại không chạy từng lệnh xong mới sang lệnh sau; nó chạy theo dây chuyền (pipeline), bắt đầu lệnh tiếp theo trước khi lệnh trước hoàn tất, như một dây chuyền lắp ráp. Vấn đề nảy sinh ở một câu if: để tiếp tục dây chuyền, CPU phải biết nhánh sẽ rẽ hướng nào — nhưng nó chưa tính xong điều kiện. Giải pháp: nó đoán hướng rẽ và cứ thế chạy tiếp theo hướng đoán. Nếu đoán đúng, dây chuyền trôi liền mạch, gần như không tốn gì. Nếu đoán sai, mọi lệnh đã lỡ chạy theo hướng sai phải bị xả bỏ và làm lại từ đúng nhánh — mất khoảng 10–20 chu kỳ, một cái giá lớn.

Bộ dự đoán nhánh rất giỏi với các mẫu ổn định: một nhánh luôn đúng, luôn sai, hay lặp đều đặn, nó học được và đoán gần như hoàn hảo. Nhưng với một nhánh 50/50 ngẫu nhiên — lúc đúng lúc sai không theo quy luật — nó đoán sai khoảng một nửa số lần, và mỗi lần sai là một lần xả dây chuyền. Đây là chỗ thứ tự dữ liệu bước vào.

Sắp mảng làm code nhanh gấp 1,7 lần

Thí nghiệm kinh điển: cộng các phần tử lớn hơn hoặc bằng một ngưỡng trong một mảng số. Nhánh quyết định là if (a[i] >= 128). Tôi để mảng vừa trong cache (để loại cache khỏi phương trình) và chạy lặp lại nhiều lần trên cùng dữ liệu, chỉ khác: một lần mảng chưa sắp (ngẫu nhiên), một lần đã sắp.

mảng chưa sắp (nhánh 50/50)     : 660 ms
mảng đã sắp   (nhánh đoán được)  : 379 ms   -> chưa sắp chậm hơn 1,7 lần

Cùng đoạn code, cùng những con số (tổng ra y hệt: 3.145.346), cùng số phép cộng — chỉ khác thứ tự các phần tử trong mảng — mà bản chưa sắp chậm hơn 1,7 lần. Lý do: khi mảng đã sắp, mọi phần tử nhỏ nằm trước, mọi phần tử lớn nằm sau, nên nhánh a[i] >= 128 là "sai, sai, sai, ..., rồi đúng, đúng, đúng" — một mẫu cực dễ đoán, bộ dự đoán gần như không sai lần nào. Khi mảng chưa sắp, nhánh nhảy loạn true/false theo dữ liệu ngẫu nhiên — 50/50 — và bộ dự đoán sai liên tục, mỗi lần xả dây chuyền. Điều rút ra: thời gian chạy không chỉ phụ thuộc số phép tính; nó phụ thuộc cả việc các nhánh có đoán được không — một chi phí phần cứng mà big-O và "đếm phép" hoàn toàn không thấy.

Trình biên dịch đã âm thầm xóa nhánh

Ở đây có một cú hớ đo lường mà tôi phải thành thật kể, vì nó dạy nhiều hơn cả kết quả chính. Khi tôi viết đúng vòng lặp kinh điển if (a[i] >= 128) sum += a[i]; và đo, mảng sắp và chưa sắp chạy bằng nhau — hiệu ứng biến mất. Tôi tưởng mình đo sai. Nhìn kỹ ra: trình biên dịch (gcc -O2) đã tự chuyển câu if đó thành code không nhánh — dùng lệnh "chọn có điều kiện" (conditional select / cmov) tính cả hai khả năng rồi chọn, thay vì rẽ nhánh thật. Không còn nhánh thì không có gì để đoán sai, nên thứ tự dữ liệu chẳng ảnh hưởng gì.

Để thấy hiệu ứng dự đoán nhánh, tôi phải ép một nhánh thật mà trình biên dịch không thể xóa — cụ thể là gọi một hàm có điều kiện (không thể "chọn có điều kiện" một lời gọi hàm). Lúc đó con số 1,7 lần mới hiện ra. Đây chính là điều đáng nhớ thứ hai, và nó lạc quan: với những nhánh đơn giản, trình biên dịch hiện đại thường tự động biến chúng thành code không nhánh (branchless) — nên trong nhiều trường hợp bạn được hưởng lợi mà không cần làm gì. Và khi tôi tự viết bản branchless (thay if bằng số học: sum += a[i] & mask), nó chạy 183 ms bất kể mảng sắp hay chưa — nhanh nhất, và hoàn toàn miễn nhiễm với thứ tự dữ liệu, vì đơn giản là không có nhánh nào để đoán.

Về đến code hằng ngày

Điều đầu tiên, hơi ngược đời: đôi khi sắp xếp dữ liệu trước khi xử lý lại làm tổng thể nhanh hơn, dù sắp xếp tốn công. Nếu bạn có một vòng lặp nóng với một nhánh phụ thuộc dữ liệu, và dữ liệu có thể được sắp để nhánh trở nên đoán được (ví dụ gom các phần tử "qua điều kiện" lại một chỗ), khoản tiết kiệm từ việc bớt đoán sai có thể lớn hơn chi phí sắp. Đây là một cân nhắc mà chỉ đo mới quyết được — nhưng biết nó tồn tại đã là một lợi thế.

Điều thứ hai: khi một nhánh nóng khó đoán, cân nhắc viết nó không nhánh (branchless). Thay if bằng số học — nhân với 0/1, dùng mặt nạ bit, hay lệnh chọn-có-điều-kiện — loại bỏ hoàn toàn khả năng đoán sai, đổi lại luôn tính cả hai đường. Với nhánh 50/50 khó đoán, đánh đổi này thường thắng (đo được 183 so với 660 ms). Nhưng đừng làm bừa: với nhánh dễ đoán, bộ dự đoán đã gần như miễn phí, và branchless (luôn tính cả hai) có thể còn chậm hơn. Và nhớ rằng trình biên dịch thường đã tự làm điều này cho các nhánh đơn giản.

Và hiệu ứng này không riêng gì C — nó nằm ở tầng CPU nên mọi ngôn ngữ đều chạm. JIT của JVM cũng tự sinh cmov cho nhánh đơn giản, và một vòng Java lọc-theo-ngưỡng trên dữ liệu ngẫu nhiên cũng chậm y như vậy; đây là lý do đằng sau lời khuyên quen thuộc "sắp dữ liệu trước rồi xử lý theo lô". Go tương tự. Nhưng chỗ bài học này đắt giá nhất lại là cơ sở dữ liệu phân tích: các engine cột hiện đại (ClickHouse, DuckDB) cố tình viết bộ lọc không nhánh — thay vì if từng dòng, chúng tính một mặt nạ bit cho cả lô rồi áp một lượt — chính để tránh cơn bão đoán-sai khi lọc hàng triệu dòng với tỉ lệ chọn ~50%; đó là một phần lý do quét-cột nhanh hơn quét-hàng nhiều lần. Mẫu số chung: thời gian chạy không chỉ là số phép tính, nó còn là hình dạng các quyết định rẽ nhánh — một tầng thực tại nằm dưới cả cache, nơi cùng một thuật toán trên cùng dữ liệu nhanh chậm khác nhau chỉ vì thứ tự.

Muốn tự thấy thì nhìn vòng lặp nóng nhất của bạn và tìm các câu if bên trong. Hỏi: điều kiện này đúng/sai theo một mẫu ổn định, hay nhảy loạn theo dữ liệu? Nếu nó khó đoán (so sánh với một ngưỡng trên dữ liệu ngẫu nhiên, 50/50), bạn có thể đang trả một khoản đoán-sai âm thầm mà không hồ sơ hiệu năng nào theo dòng lệnh chỉ ra rõ. Cách thử nhanh: lấy một mảng lớn giá trị ngẫu nhiên, chạy một vòng lọc-theo-ngưỡng và bấm giờ; rồi sắp mảng đó và chạy lại đúng vòng ấy. Nếu bản đã sắp nhanh hơn hẳn, bạn vừa tận mắt thấy dự đoán nhánh — và biết rằng đôi khi cách tăng tốc một vòng lặp không nằm ở thuật toán, mà ở việc làm cho các nhánh của nó dễ đoán hơn, hoặc bỏ chúng đi.