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. Giống như đếm số người trong một khán phòng: bạn có thể chỉ tay đếm từng ghế một, hoặc — nếu có một cái bảng điện tử ở cửa đã đếm sẵn lúc mọi người vào — chỉ việc liếc con số. Đếm số bit 1 trong một số (popcount) đúng là ca đó. 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, như cái bảng điện tử ở cửa. Phần 17 cho thấy mỗi lệnh có giá của nó; phần này tôi đo xem chọn đúng lệnh thắng code khéo bao nhiêu, trong container gcc:13 trên host ARM, kèm 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 trá hình.

Chỗ tôi hớ: compiler không tự làm hộ

Đây là chỗ tôi đã đoán sai. Tôi tin chắc: "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". Con số dập tắt: 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 ý.

Ba niềm tin bị đo cho gãy

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". Con số cho thấy 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.

Rồi hai niềm tin ngược cũng gãy nốt. 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 đều khiến ta bỏ lại hiệu năng trên bàn: một vì trông chờ compiler, một vì tự tin vào code khéo. Mà lệnh phần cứng vừa nhanh nhất vừa dễ đọc nhất — thật sự không có lý do gì để không dùng.

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

Việc đầ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à 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).

Việc 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ó.

Đáng mừng là bài học này leo lên tầng cao gần như miễn phí, vì các ngôn ngữ lớn đều đã bọc sẵn đúng lệnh phần cứng đó — chỉ cần bạn biết mà gọi. Java có Integer.bitCount() / Long.bitCount(), và HotSpot JIT biên dịch chúng thẳng thành lệnh POPCNT trên CPU hỗ trợ; Integer.numberOfLeadingZeros ra lệnh CLZ. Go có math/bits.OnesCount, LeadingZeros — cùng ý. Điểm chung là: viết tay một vòng đếm bit trong Java hay Go cũng chậm y như trong C, và JIT cũng không chắc nhận ra để thay hộ — nên gọi đúng hàm chuẩn mới là cách lấy được lệnh phần cứng. Ở tầng cao hơn nữa, đây là bí mật đằng sau tốc độ của các bitmap index (Roaring Bitmap trong nhiều database, search engine): những phép AND/OR/đếm trên hàng triệu bit dựa hết vào popcount phần cứng. Độ phức tạp thuật toán không nhìn thấy mấy lệnh này; chỉ khi đo, hoặc khi biết chúng tồn tại, bạn mới tận dụng được.

Muốn tự thấy thì viết ba hàm đếm số bit 1 của mỗi phần tử trong một mảng 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 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 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 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 còn ngắn hơn.