std::set hay bitset? Cùng một tập, chênh nhau tới 10.000 lần

Hình dung hai cách ghi lại "hôm nay ai có mặt" trong một hội trường đánh số ghế. Cách thứ nhất: một tờ điểm danh in sẵn mọi số ghế, ai có mặt thì tích một ô — muốn biết ghế 500 có người không thì liếc đúng một ô, muốn so hai buổi thì đặt hai tờ chồng lên nhau nhìn cái là ra. Cách thứ hai: một xấp danh thiếp, mỗi người có mặt một tấm — gọn khi cả sân vận động chỉ có dăm người, nhưng muốn biết một ghế cụ thể có ai không thì phải lật cả xấp. Cách thứ nhất là bitset, cách thứ hai là std::set / hash set — và chọn nhầm có thể phí cả nghìn lần.

Bạn cần một tập hợp các số nguyên — theo dõi những id đã thấy, những trạng thái đã bật, những phần tử được chọn. Phản xạ mặc định là std::set<int> hoặc std::unordered_set<int>, gõ một dòng là xong. Nhưng nếu miền giá trị nhỏ và biết trước (ví dụ id trong khoảng 0..1 triệu), bitset nén hơn hàng trăm lần và nhanh hơn hàng nghìn lần. Tôi đo cả ba lựa chọn trong container gcc:13, và con số cho thấy "chọn set cho tiện" có thể phí cả RAM lẫn tốc độ một cách khủng khiếp — hoặc ngược lại, bitset có thể là lựa chọn sai nếu dùng nhầm chỗ.

Một bit cho một phần tử

Bitset là một mảng bit: bit thứ i bằng 1 nghĩa là i thuộc tập — đúng cái tờ điểm danh tích ô. Lưu bằng một mảng uint64 — mỗi word 64 bit chứa 64 phần tử của miền. Thêm phần tử i là bật bit (A[i/64] |= 1<<(i%64)), kiểm tra là đọc bit. So với std::set — một cây đỏ-đen mà mỗi node tốn ~48 byte (ba con trỏ, một byte màu, giá trị, đệm) — hay unordered_set (~40 byte/phần tử gồm node và bucket), bitset chỉ tốn 1 bit cho mỗi vị trí của miền.

Điều này cho bitset ba lợi thế khi miền nhỏ và dày đặc: (1) bộ nhớ — nén hàng trăm lần; (2) phép tập hợp — hợp/giao/hiệu là OR/AND/XOR trên uint64, xử lý 64 phần tử mỗi lệnh CPU; (3) kiểm tra thành viên — một phép dịch và AND, O(1), không cache miss theo con trỏ. Tôi đo cả ba.

Đo: nén 192 lần, giao nhanh 10.000 lần

Tôi dựng một tập ~501 nghìn phần tử (~50%) trên miền 0..1 triệu, bằng cả ba cấu trúc:

Miền 0..1 triệu, tập ~501k phần tử (~50%), g++ -O2:

A. BỘ NHỚ:
   bitset (mảng uint64)  :    122 KB   (1 bit/phần tử của miền)
   std::set<int>         : ~23.000 KB  (~48 B/node × 501k)
   unordered_set<int>    : ~19.000 KB  (~40 B/phần tử × 501k)
   -> bitset nén ~192 lần so với std::set

B. GIAO (intersect) A & B:
   bitset AND            :      4,8 µs   (AND 64 phần tử/lệnh + popcount)
   std::set lặp + count  : 47.851,2 µs   (lặp qua A, tra B: O(n log n))
   -> bitset nhanh hơn ~10.000 lần

C. KIỂM TRA THÀNH VIÊN (1 triệu lần test):
   bitset test bit       :   0,39 ns/test  (O(1), 1 lệnh dịch+and)
   std::set count        : 338,91 ns/test  (O(log n), cache miss mỗi bước)
   unordered_set count   :  19,83 ns/test  (O(1) tb, nhưng hash + cache miss)

Nhìn A: cùng tập ~501 nghìn phần tử, bitset chỉ tốn 122 KB, còn std::set tốn ~23 MB — bitset nén ~192 lần. Vì set trả ~48 byte cho mỗi phần tử (node cây), còn bitset trả 1 bit. B còn ấn tượng hơn: phép giao hai tập bằng bitset chỉ mất 4,8 µs (AND từng cặp word — 64 phần tử mỗi lệnh — rồi popcount), trong khi std::set phải lặp qua từng phần tử của A và tra trong B, mất 47,9 mili-giây — bitset nhanh hơn ~10.000 lần. Và C: kiểm tra thành viên, bitset 0,39 ns so với std::set 338,9 ns (nhanh 870 lần — set phải đi ~20 bước cây, mỗi bước cache miss) và unordered_set 19,8 ns (nhanh 50 lần — hash vẫn có một cache miss). Với tập số nguyên miền nhỏ dày đặc, bitset thắng ở mọi mặt, và không phải chút ít — mà hàng trăm tới hàng nghìn lần.

(Môi trường đo: container gcc:13 trên host ARM AArch64, g++ -O2, miền 0..1tr, mỗi số lấy MIN sau warmup. Con số đổi theo máy và mật độ; cái cần nhìn là lợi thế khổng lồ của bit + phép AND/OR song song khi miền nhỏ dày đặc.)

Hai niềm tin đối nghịch, cùng sai

Tôi vào đo với niềm tin lười: "cần tập thì std::set, chọn cái nào cũng như nhau, tiện là được". Con số bác thẳng: với miền nhỏ dày đặc, bitset nén RAM 192 lần, giao tập nhanh 10.000 lần, kiểm tra thành viên nhanh 870 lần. "Set cho tiện" có thể phí hàng chục MB và làm chậm hàng nghìn lần.

Nhưng tôi suýt rơi vào một đo hớ ngược: "vậy bitset luôn tốt hơn vì nó nhỏ và nhanh". Cũng sai — bitset tốn M bit cho cả miền, bất kể tập có bao nhiêu phần tử. Nếu miền rộng mà tập thưa — ví dụ 100 phần tử nằm rải trong 0..1 tỷ — bitset cần 1 tỷ bit = 125 MB dù chỉ có 100 phần tử, trong khi std::set/hash chỉ tốn ~100 node. Lúc đó bitset là lựa chọn tệ, đúng cái tờ điểm danh in sẵn cả triệu ghế cho một hội trường chỉ có vài người. Chọn đúng phụ thuộc miền và mật độ.

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

Điều đầu tiên: khi tập số nguyên có miền nhỏ, biết trước, và dày — dùng bitset. Cờ trạng thái (0..số-trạng-thái), tập id trong một khoảng, sàng nguyên tố, đánh dấu "đã thăm" trong đồ thị với đỉnh đánh số liên tục — tất cả là ứng viên hoàn hảo. std::bitset<N> (kích thước cố định) hay std::vector<uint64_t> (động) cho bạn nén và tốc độ. Và nếu bạn làm nhiều phép hợp/giao/hiệu các tập, bitset gần như luôn thắng vì phép bit song song.

Điều thứ hai: khi tập thưa trên miền rộng — dùng hash set (hoặc set nếu cần thứ tự). unordered_set tốn bộ nhớ theo số phần tử, không theo miền, nên nó là lựa chọn đúng khi bạn có ít phần tử rải trên một không gian lớn (id 64-bit, khóa chuỗi băm ra số lớn). Đừng ép bitset vào đây — bạn sẽ cấp phát một biển bit rỗng.

Chỗ này thú vị là các hệ thống thật đã sinh ra cấu trúc lai để khỏi phải chọn. Roaring bitmap (dùng trong Elasticsearch, Lucene, ClickHouse, Druid) chia miền thành các khối 64k và tự chọn cách lưu mỗi khối — bitset cho khối dày, mảng số cho khối thưa — nên nó nén tốt ở cả hai chế độ; đây là lý do các engine tìm kiếm và phân tích dựa vào nó để giao/hợp các tập tài liệu triệu phần tử cực nhanh. Java có BitSet và EnumSet (một bitset cho enum, cực gọn), Python có bitset qua số nguyên lớn hoặc thư viện. Còn ở tầng database, chỉ mục bitmap là đúng ý tưởng này áp cho các cột ít giá trị phân biệt (giới tính, trạng thái) — truy vấn WHERE status=A AND type=B biến thành phép AND hai bitmap, đúng cái 10.000x trong đo B. Nhận ra "tập của mình có miền nhỏ và dày không" là lúc với tay tới bitset thay vì set.

Muốn tự thấy thì dựng một tập vài trăm nghìn số nguyên trong khoảng 0..1 triệu bằng hai cách: một std::set<int> và một mảng uint64 làm bitset (bật bit thứ i). So bộ nhớ ước tính (số phần tử × ~48 byte cho set, số phần tử của miền / 8 cho bitset) — bitset nhỏ hơn cả trăm lần. Rồi tạo hai tập và tính giao của chúng: với bitset là một vòng A[i] & B[i] chạy vèo, với set là lặp và tra cứu, chậm hơn hàng nghìn lần. Cuối cùng, thử tưởng tượng (hoặc đo) trường hợp ngược: một tập chỉ 100 phần tử nhưng giá trị tới hàng tỷ — bitset lúc này phải cấp cả trăm MB, còn set chỉ 100 node. Vài phút đó cho bạn thấy điều mà "cứ dùng set cho tiện" giấu đi: cấu trúc tập đúng phụ thuộc miền giá trị nhỏ hay rộng và tập dày hay thưa — chọn khớp thì nhanh và gọn hàng nghìn lần, chọn nhầm thì phí RAM hoặc phí thời gian.