Có những việc trông như phải "làm từng bước" mà CPU thật ra làm một nhát. Đếm số bit 1 trong một số (popcount) là ví dụ kinh điển: cách nghĩ tự nhiên là lặp qua 32 bit và cộng dồn, tốn thời gian tỉ lệ số bit. Nhưng phần cứng có hẳn một lệnh (CNT trên ARM, POPCNT trên x86) làm việc đó trong một nhịp. Phần 17 cho thấy mỗi lệnh có giá của nó; phần này đo xem chọn đúng lệnh thắng code khéo bao nhiêu — trong container gcc:13 trên host ARM — và một điều bất ngờ về việc trình biên dịch không tự làm hộ.
Một lệnh cho việc trông như cả vòng lặp
CPU hiện đại có sẵn nhiều lệnh thao tác bit làm trong ~1 nhịp những việc mà viết tay tốn cả vòng: popcount (CNT — đếm số bit 1), CLZ/CTZ (đếm số bit 0 ở đầu/cuối một số — hữu ích cho log2, tìm bit cao nhất), đảo bit, tìm bit thấp nhất... Chúng có mặt vì rất nhiều thuật toán cần: bitset, bộ lọc Bloom, mã hóa, đồ họa, cơ sở dữ liệu cột.
Để đếm số bit 1, có bốn cách quen thuộc, từ ngây thơ tới phần cứng: (A) lặp 32 lần dịch từng bit; (B) mẹo Kernighan x &= x-1 xóa bit thấp nhất mỗi vòng (lặp theo số bit set, nhanh hơn khi ít bit); (C) bảng tra 8-bit (tra 4 lần cho số 32-bit); (D) __builtin_popcount — trình biên dịch sinh thẳng lệnh CNT phần cứng. Tôi đo cả bốn trên cùng một mảng.
Đo: phần cứng thắng 31 lần
Popcount mảng uint32 (trong L1), host ARM, g++ -O2 -fno-tree-vectorize:
naive (lặp 32 lần dịch bit) : 7,83 ns/phần tử <- 31x chậm
Kernighan (x &= x-1) : 0,46 ns <- ~1,8x chậm
bảng tra 8-bit (LUT) : 0,48 ns <- ~1,9x chậm
__builtin_popcount -> lệnh CNT : 0,25 ns <- nhanh nhất
Đếm bit 0 ở đầu (leading zeros):
thủ công (vòng) : 0,58 ns
__builtin_clz -> CLZ : 0,24 ns <- ~2,4x
Đọc bảng: cách naive — lặp 32 lần, mỗi lần dịch một bit và cộng — tốn 7,83 ns mỗi số. Lệnh phần cứng __builtin_popcount chỉ 0,25 ns — nhanh hơn 31 lần. Thú vị hơn, hai cách "khéo" mà lập trình viên hay tự hào — mẹo Kernighan (0,46 ns) và bảng tra (0,48 ns) — tuy nhanh hơn naive cả chục lần, vẫn chậm hơn lệnh phần cứng khoảng hai lần. Bao nhiêu khéo léo trong phần mềm cũng không bằng một lệnh phần cứng chuyên dụng. CLZ cũng vậy: đếm bit 0 đầu bằng vòng tốn 0,58 ns, __builtin_clz chỉ 0,24 ns.
Tôi xem assembly để chắc: __builtin_popcount sinh đúng lệnh cnt, __builtin_clz sinh clz. Chúng thật sự là lệnh phần cứng, không phải hàm thư viện.
Đo hớ: compiler không tự làm hộ
Đây là chỗ tôi hớ. Tôi tin: "trình biên dịch hiện đại đủ thông minh để nhận ra vòng đếm bit naive và tự thay bằng lệnh CNT". Đo phá tan: bản naive vẫn tốn 7,83 ns — chậm 31 lần — nghĩa là -O2 không nhận ra mẫu đó, nó giữ nguyên vòng 32 lần. (Một số trình biên dịch nhận ra một số mẫu popcount nhất định, nhưng không đáng tin; ở đây GCC 13 -O2 bỏ qua.) Muốn dùng phần cứng, bạn phải gọi __builtin_popcount (hoặc std::popcount trong C++20) — không thể trông chờ compiler tự đoán ý.
Một lần tôi đo hớ: "đếm bit phải lặp từng bit" và "compiler tự thay / mẹo tay là đủ"
Tôi vào đo với mô hình thuật toán thuần: "đếm bit là O(số bit), phải duyệt qua chúng". Đo phá tan: CPU làm popcount trong ~1 nhịp bằng lệnh CNT — __builtin_popcount 0,25 ns so với vòng naive 7,83 ns, nhanh 31 lần. Rất nhiều "phép trên bit" trông như vòng lặp thực ra là một lệnh: popcount, đếm zero đầu/cuối, đảo bit. Nghĩ theo "độ phức tạp thuật toán" mà quên phần cứng có lệnh sẵn khiến ta viết vòng chậm gấp chục lần cho việc CPU làm một nhát.
Nhưng đo cũng phá hai niềm tin ngược. Một: "trình biên dịch tự nhận ra và thay bằng lệnh phần cứng" — sai, -O2 giữ nguyên vòng naive 7,83 ns; phải gọi builtin rõ ràng. Hai: "mẹo bit khéo (Kernighan, bảng tra) là đủ nhanh, khỏi cần builtin" — sai, chúng vẫn chậm hơn lệnh CNT ~2 lần. Cả hai sai lầm khiến ta bỏ lại hiệu năng trên bàn: một cái vì trông chờ compiler, một cái vì tự tin vào code khéo. Lệnh phần cứng vừa nhanh nhất vừa dễ đọc nhất — không có lý do không dùng.
Bài học đo lường: CPU có LỆNH BIT một nhịp cho việc trông như cả vòng: popcount (CNT), clz/ctz. Đo: __builtin_popcount 0,25 ns vs vòng naive 7,83 ns = 31x, và vẫn nhanh ~2x mẹo tay Kernighan/LUT (0,46-0,48). __builtin_clz 0,24 vs vòng 0,58. NHƯNG -O2 KHÔNG tự thay vòng naive bằng CNT (vẫn 7,83) — phải GỌI builtin/std::popcount. 'Đếm bit phải lặp từng bit' và 'compiler tự thay / mẹo tay đủ nhanh' đều SAI. Nếu tin "phải lặp" tôi viết vòng chậm 31x; nếu tin "compiler tự lo" tôi để nguyên vòng naive mà tưởng đã nhanh.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: dùng builtin/hàm chuẩn cho các phép bit, đừng viết tay. __builtin_popcount/__builtin_popcountll, __builtin_clz/ctz, hoặc std::popcount, std::countl_zero (C++20) — chúng sinh lệnh phần cứng, nhanh nhất và rõ ràng nhất. Đây là các nền tảng của bitset nhanh, chỉ mục cột, union of sets, rank/select trong cấu trúc dữ liệu súc tích (succinct).
Hệ quả thứ hai: biết những gì CPU có lệnh sẵn. Ngoài popcount và clz/ctz: byte swap (__builtin_bswap), tìm bit thấp nhất, nhân cao (high-mul), và với SIMD còn popcount cả vector cùng lúc. Khi thấy mình sắp viết một vòng lặp trên bit, hãy hỏi "CPU có lệnh cho việc này không?" — thường là có.
Hệ quả thứ ba là tinh thần đo lường: độ phức tạp thuật toán không thấy lệnh phần cứng — đo mới thấy một lệnh thay cả vòng. Con số mang theo: popcount phần cứng (CNT) 0,25 ns vs vòng naive 7,83 ns = 31x, vs mẹo tay ~2x; clz phần cứng 0,24 vs vòng 0,58. Compiler KHÔNG tự thay vòng — gọi __builtin_popcount / std::popcount. Cùng bài toán "đếm bit", một vòng lặp hay một lệnh chênh nhau ba chục lần — và cái nhanh nhất lại là cái ngắn nhất để viết.
Thử ba mươi giây
Viết ba hàm đếm số bit 1 của mỗi phần tử trong một mảng số nguyên và bấm giờ ns mỗi phần tử. Một: vòng lặp 32 lần, for(b=0;b<32;b++) c += (x>>b)&1. Hai: mẹo Kernighan, while(x){ x &= x-1; c++; }. Ba: c = __builtin_popcount(x). Bạn sẽ thấy bản vòng naive chậm hàng chục lần bản builtin, và ngay cả Kernighan (dù khéo) vẫn thua builtin khoảng hai lần. Rồi xem assembly (g++ -O2 -S): chỉ bản gọi builtin có lệnh cnt; bản naive vẫn là một vòng lặp đầy đủ — trình biên dịch không tự thay. Thử thêm __builtin_clz so với một vòng đếm bit 0 ở đầu: lại một lệnh thắng cả vòng. Ba mươi giây đó cho bạn thấy điều mà "đếm bit phải lặp từng bit" giấu đi: rất nhiều thao tác trên bit mà ta quen viết thành vòng lặp thật ra là một lệnh phần cứng — chỉ cần gọi đúng tên, bạn được tốc độ gấp chục lần và code ngắn hơn.
