Một tập các cờ đúng/sai — "số i có phải số nguyên tố không", "phần tử i có trong tập không" — cách thẳng thắn nhất là một mảng bool, mỗi cờ một ô. Nhưng một bool tốn nguyên một byte để giữ đúng một bit thông tin; bảy bit còn lại bỏ không. Nhồi 64 cờ vào một số nguyên 64-bit thì tiết kiệm được 8 lần bộ nhớ — đó là bitset. Câu hỏi đo được: 8 lần bộ nhớ đổi lấy gì về tốc độ, và "thao tác bit" có nhanh hơn như tiếng đồn không? Đáp án có một khúc quanh khiến tôi phải sửa lại điều mình tưởng.
Bitset gói 64 cờ vào một từ
Ý tưởng đơn giản: dùng một mảng số nguyên 64-bit, coi nó như một dãy bit dài. Cờ thứ i nằm ở bit i & 63 của từ i >> 6. Đặt cờ là w[i>>6] |= 1ULL << (i&63); đọc cờ là (w[i>>6] >> (i&63)) & 1. Với 100 triệu cờ, mảng bool tốn 100 MB, còn bitset chỉ tốn 100 triệu / 8 = 12,5 MB. Tôi đo đúng con số ấy: 8 lần nhỏ hơn, không phải ước lượng mà là sizeof thật.
Nhưng cái hay của bitset không dừng ở bộ nhớ. Vì 64 cờ nằm gọn trong một từ, những phép theo từ xử lý 64 cờ cùng một lúc. Giao hai tập là một phép AND; hợp là OR; hiệu là AND NOT; đếm số phần tử của tập là một lệnh popcount (đếm số bit bật) mà CPU làm bằng phần cứng. Một lệnh máy làm việc của 64 — cùng tinh thần "một lệnh, nhiều dữ liệu" của bài SIMD, nhưng ở đây là dữ liệu một-bit.
Đo: giao hai tập nhanh gần 13 lần
Tôi dựng hai tập, mỗi tập 100 triệu phần tử tiềm năng (mật độ khoảng 1/8), rồi tính giao của chúng và đếm kích thước giao — hai cách. Cách bitset: AND từng cặp từ rồi popcount. Cách mảng bool: duyệt từng ô, nhân hai cờ.
Giao hai tập 100 triệu phần tử (đếm kích thước giao):
bitset (AND theo từ, 64 phần tử/lệnh) : 0,4 ms
mảng bool (từng ô một) : 5,8 ms
-> bitset nhanh 12,9 lần
Gần 13 lần. Lợi này đến từ hai nguồn cộng lại: mỗi lệnh AND xử lý 64 cờ thay vì 1, và bitset chỉ phải đọc 12,5 MB thay vì 100 MB (ít hơn 8 lần lưu lượng bộ nhớ, nên cache đỡ hơn nhiều). Đây là chỗ bitset tỏa sáng nhất: các phép trên cả tập cùng lúc.
Còn phép đếm bit thì sao? Tôi so lệnh popcount phần cứng (__builtin_popcountll) với vòng đếm thủ công kiểu Kernighan (x &= x-1 xóa dần bit thấp nhất):
Đếm số bit bật trong bitset (1,56 triệu từ):
popcount phần cứng : 0,4 ms
Kernighan thủ công : 0,7 ms -> phần cứng chỉ nhanh 1,7 lần
Chỉ 1,7 lần — khiêm tốn hơn tôi tưởng. Kiểm mã máy xác nhận -O2 sinh đúng lệnh cnt của ARM (popcount phần cứng, thậm chí còn được vector hóa NEON). Vậy sao chênh lệch nhỏ? Vì cả hai vòng đều nghẽn bộ nhớ, không nghẽn CPU: chúng đọc hết 12,5 MB, và thời gian phần lớn là chờ dữ liệu từ RAM chứ không phải đếm bit. Khi CPU phải chờ bộ nhớ, việc lệnh đếm nhanh hay chậm không còn quyết định. Đây đã là một lời nhắc: "thao tác bit nhanh" chỉ đúng khi nút thắt thật sự là phép tính.
Một lần tôi đo hớ: bit lẻ khi thì chậm, khi thì nhanh
Chỗ tôi tự tin nhất lại là chỗ sai nặng nhất. Tôi biết một điều "kinh điển": đặt một bit lẻ đắt hơn ghi một byte, vì bit phải làm ba việc — dịch để tạo mặt nạ, AND/OR với mặt nạ, và đọc-sửa-ghi cả từ (không ghi thẳng một bit được). Còn ghi một byte chỉ là một lệnh store. Nên tôi đoán chắc: chạm bit lẻ sẽ chậm hơn. Tôi đo, và nó nhanh hơn 6 lần. Ngỡ ngàng, tôi đo lại ở ba quy mô khác nhau, mỗi lần đặt ngẫu nhiên 20 triệu phần tử:
Đặt 1 phần tử ngẫu nhiên, 20 triệu lần:
50 nghìn cờ (bool 50KB, vừa L1/L2) : byte 4,6 ms | bit 6,8 ms -> bit CHẬM 1,46 lần
2 triệu cờ (bool 2MB, cỡ L2) : byte 20 ms | bit 10 ms -> bit NHANH 2,0 lần
100 triệu cờ (bool 100MB, tràn cache): byte 117 ms | bit 18 ms -> bit NHANH 6,3 lần
Đường cong kể toàn bộ câu chuyện. Khi dữ liệu nhỏ, vừa cache (50 nghìn cờ), điều "kinh điển" đúng: bit chậm hơn byte 1,46 lần, đúng vì chi phí dịch + mặt nạ + đọc-sửa-ghi lộ ra khi truy cập bộ nhớ vốn đã rẻ (đều nằm trong L1). Nhưng khi dữ liệu lớn, tràn cache (100 triệu cờ), mọi thứ đảo ngược: bit nhanh hơn 6,3 lần. Lý do là mật độ 8 lần: mảng bool 100 MB khiến gần như mỗi lần chạm ngẫu nhiên là một lần trượt cache phải xuống RAM; bitset 12,5 MB vừa cache tốt hơn hẳn, ít trượt hơn nhiều — và cái lợi cache đó lấn át hoàn toàn chi phí dịch + mặt nạ.
Đo hớ của tôi là đã lấy một sự thật có điều kiện ("bit lẻ đắt hơn byte") và tưởng nó vô điều kiện. Điều kiện là quy mô so với cache: trong cache thì chi phí tính bit thắng, ngoài cache thì mật độ bộ nhớ thắng. Không đo cả đường cong thì tôi đã kết luận sai hẳn một chiều.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: bitset đáng dùng khi tập lớn hoặc khi bạn làm phép trên cả tập. Với vài chục cờ, một mảng bool (hay vài biến) đơn giản và đủ nhanh — thậm chí nhanh hơn nếu chúng vừa cache. Nhưng khi tập lên hàng triệu phần tử, hoặc khi bạn thường xuyên giao/hợp/đếm cả tập (lọc, chỉ mục ngược của công cụ tìm kiếm, bloom filter, sàng số nguyên tố), bitset thắng đậm ở cả bộ nhớ lẫn tốc độ. Cùng bài học của mảng và cache: dữ liệu nhỏ gọn hơn nghĩa là ít trượt cache hơn, và ở quy mô lớn điều đó quan trọng hơn số lệnh.
Hệ quả thứ hai: "thao tác bit nhanh" là một câu cần đo, không phải câu để tin. Các mẹo bit tiết kiệm lệnh, nhưng lệnh chỉ là nút thắt khi CPU không phải chờ bộ nhớ. Đo popcount cho thấy khi vòng nghẽn bộ nhớ, lệnh phần cứng nhanh cũng chỉ hơn 1,7 lần; đo bit-lẻ cho thấy cùng một thao tác có thể chậm hơn hoặc nhanh hơn byte tùy dữ liệu nằm trong hay ngoài cache. Trước khi thay một vòng rõ ràng bằng một mẻ dịch-và-mặt-nạ khó đọc, hãy hỏi: nút thắt của tôi là CPU hay bộ nhớ? Nếu là bộ nhớ, mẹo bit giúp qua mật độ (ít byte hơn) chứ không qua số lệnh.
Hệ quả thứ ba là bài học đo lường bao trùm: lợi thật của bitset là mật độ cache và xử lý theo khối, không phải bản thân "bit". Con số mang theo: bitset nhỏ hơn mảng bool 8 lần; giao hai tập bằng AND nhanh 12,9 lần (64 phần tử mỗi lệnh cộng ít lưu lượng bộ nhớ); nhưng đặt một bit lẻ chậm hơn byte 1,46 lần khi vừa cache rồi nhanh hơn 6,3 lần khi tràn cache — cùng một thao tác, kết quả ngược nhau tùy quy mô. Khi ai đó nói "dùng bit cho nhanh", hãy hỏi "nhanh ở quy mô nào, và nút thắt là gì" — rồi đo đường cong, đừng đo một điểm.
Thử ba mươi giây
Trong C, thử tính nhanh x & (x-1) xóa bit bật thấp nhất, và x & (-x) giữ lại đúng bit bật thấp nhất — hai mẹo bit nền tảng. Rồi thử một phép thực tế: lấy hai unsigned long long bất kỳ, in __builtin_popcountll(a & b) — đó là số phần tử chung của hai tập 64-phần-tử, tính bằng đúng hai lệnh máy. So với việc bạn phải viết một vòng for 64 vòng để làm điều tương tự trên hai mảng bool, bạn sẽ cảm nhận ngay vì sao bitset thắng ở phép-trên-cả-tập. Cuối cùng, nếu tò mò về khúc quanh cache: cấp một mảng bool 200 MB và một bitset 25 MB cho cùng số cờ, đặt ngẫu nhiên vài chục triệu cờ vào mỗi cái, và đo — bạn sẽ thấy chính con số 6 lần mà bài này gặp, và hiểu nó đến từ cache chứ không từ bit.
