Khi bạn có một bản ghi với nhiều trường nhỏ — vài cờ bool, một loại 0–7, một mức 0–15, một đếm 0–255 — cách viết tự nhiên là cho mỗi trường một int riêng. Đơn giản, nhưng lãng phí: một int giữ 4 byte để chứa một giá trị chỉ cần vài bit. Với hàng chục triệu bản ghi, những byte thừa đó cộng thành hàng trăm megabyte. Bit packing (gói bit) là kỹ thuật gói nhiều trường nhỏ vào chung một từ (word), dùng shift và mask để đọc/ghi từng trường. Nhiều người ngại nó: "gói bit tiết kiệm bộ nhớ thật, nhưng shift/mask làm chậm CPU". Tôi đo cả hai trong container gcc:13, và con số cho thấy nỗi lo đó phần lớn không có cơ sở — nhưng cũng cho thấy lợi ích thật nằm ở đâu.
Bốn int rời rạc so với bốn trường trong một từ
Lấy một bản ghi ví dụ: type (0–7), active (một cờ), level (0–15), count (0–255). Hai cách biểu diễn:
- Thô (ngây thơ): mỗi trường một
int. Bốnint= 16 byte. Mỗi giá trị nhỏ nằm gọn trong 4 byte đầy đủ, phần lớn bit là 0 lãng phí. (Đây là nơi padding và kích thước trường quyết định sizeof.) - Nén: gói cả bốn trường vào một
uint32(32 bit):type3 bit,active1 bit,level4 bit,count8 bit = 16 bit, còn thừa chỗ.sizeof= 4 byte.
Đọc một trường nén là shift + mask: count = (w >> 8) & 0xFF — vài lệnh ALU. Ghi một trường nén tốn hơn: phải đọc-sửa-ghi (xóa các bit cũ bằng mask rồi OR bit mới vào), vì bạn không thể ghi đè một phần của từ mà không đụng phần còn lại.
Đánh đổi trên lý thuyết: nén nhỏ hơn 4 lần → nhiều bản ghi trên mỗi cache line hơn → duyệt khối lớn ít cache miss hơn. Đổi lại là chi phí shift/mask mỗi lần chạm trường. Câu hỏi đo lường: chi phí đó có ăn hết lợi ích cache không?
Đo: nhỏ 4 lần, đọc gần như miễn phí, throughput nhanh vừa phải
Tôi tạo 40 triệu bản ghi ở cả hai dạng, đo bộ nhớ (RSS thật), duyệt tuần tự, và truy cập khi dữ liệu đã nằm trong cache:
N=40 triệu bản ghi, g++ -O2:
sizeof: thô = 16 byte, nén = 4 byte (uint32)
A. BỘ NHỚ (mảng 40 triệu):
thô : 610,4 MB
nén : 152,6 MB -> nhỏ hơn ~4 lần
B. DUYỆT tuần tự, tính tổng một trường (ns/phần tử):
thô : 0,257 ns (đọc 16 byte/phần tử)
nén : 0,226 ns (đọc 4 byte/phần tử + shift/mask) -> nén nhanh ~1,1 lần
C. MẢNG NHỎ NÓNG (nằm gọn trong cache), đọc một trường lặp lại:
thô : 0,228 ns
nén : 0,227 ns -> HÒA (shift/mask gần như miễn phí)
Nhìn A — bộ nhớ: đúng như sizeof hứa, mảng nén dùng 152,6 MB so với 610,4 MB của mảng thô — nhỏ hơn 4 lần. Đây là lợi ích chắc chắn và lớn nhất của bit packing: bạn nhét cùng dữ liệu vào 1/4 không gian.
Nhìn B — duyệt tuần tự: nén (0,226 ns) nhanh hơn thô (0,257 ns), nhưng chỉ ~1,1 lần, không phải 4 lần như tỷ lệ bộ nhớ. Lý do trung thực: bản thô đọc 16 byte × 40 triệu ≈ 640 MB trong ~10 ms, tức đã sát băng thông bộ nhớ của máy; còn bản nén chỉ đọc 160 MB nên không còn bị giới hạn băng thông — lúc này nó bị giới hạn bởi tốc độ vòng lặp (shift/mask + cộng), nên không nhanh thêm được nữa. Density giúp, nhưng lợi ích throughput bị chặn ở mức khiêm tốn khi bản nén đã đủ nhỏ để không còn nghẽn ở RAM.
Nhìn C — chỗ phá tan nỗi lo "shift/mask làm chậm CPU": khi mảng đủ nhỏ để nằm trong cache và ta đọc một trường lặp đi lặp lại, thô (0,228 ns) và nén (0,227 ns) hòa nhau. Nghĩa là phép shift + mask để rút một trường ra khỏi từ gần như miễn phí — nó là một hai lệnh ALU được ẩn trong pipeline của CPU, không thêm thời gian đo được. Cái "chậm vì shift/mask" mà người ta sợ đơn giản không xuất hiện khi đọc.
(Một trung thực nữa: ghi một trường nén thì có tốn hơn — phải đọc-sửa-ghi. Nhưng với các trường được đọc nhiều hơn ghi — cờ trạng thái, thuộc tính — điều đó hiếm khi thành nút cổ chai.)
Một lần tôi đo hớ: "gói bit làm chậm CPU" và "gói bit nhanh hơn tỉ lệ với tiết kiệm bộ nhớ"
Tôi vào đo với một nỗi ngại quen thuộc: "gói bit tiết kiệm bộ nhớ thật, nhưng mỗi lần đọc trường phải shift/mask — thêm lệnh, làm chậm CPU, nên chỉ đáng dùng khi rất thiếu RAM". Đo phá tan phần đó: shift/mask khi đọc gần như miễn phí — khi dữ liệu đã trong cache, bản nén hòa với bản thô (0,227 vs 0,228 ns), và khi duyệt khối lớn bản nén còn nhanh hơn 1,1 lần nhờ đọc ít byte hơn. Chi phí ALU của một phép (w >> 8) & 0xFF bị ẩn hoàn toàn trong pipeline. Bit packing không làm chậm việc đọc.
Nhưng đo cũng phá luôn niềm tin ngược mà tôi suýt rơi vào sau khi thấy nén nhỏ 4 lần: "vậy nén nhỏ 4 lần thì chắc cũng nhanh 4 lần vì đọc ít bộ nhớ hơn". Sai: tiết kiệm bộ nhớ là 4 lần, nhưng throughput duyệt chỉ nhanh 1,1 lần. Vì một khi bản nén đủ nhỏ (4 byte/phần tử), việc duyệt không còn bị giới hạn bởi băng thông bộ nhớ nữa — nó chuyển sang bị giới hạn bởi tốc độ vòng lặp, nên đọc ít hơn không giúp nhanh thêm. Và khi dữ liệu đã nằm trong cache, không có lợi ích cache nào để hưởng, nên hai bên hòa. Lợi ích của bit packing là bộ nhớ, không phải tốc độ — nhầm hai cái là kỳ vọng sai về hiệu năng.
Bài học đo lường: bit packing gói nhiều trường nhỏ vào một từ (4 int 16B -> 1 uint32 4B = nhỏ 4x); đọc trường = shift/mask GẦN NHƯ MIỄN PHÍ (mảng nóng trong cache hòa 0,227 vs 0,228 ns), duyệt khối lớn còn nhanh ~1,1x nhờ cache — KHÔNG làm chậm CPU. NHƯNG throughput chỉ nhanh ~1,1x chứ KHÔNG tỉ lệ với mức nén 4x (ở 4B/phần tử hết bị giới hạn băng thông); ghi một trường tốn hơn (đọc-sửa-ghi). Lợi ích chính là BỘ NHỚ. Nếu tôi tin "shift/mask làm chậm" tôi né bit packing vô ích; nếu tôi tin "nén 4x thì nhanh 4x" tôi kỳ vọng sai về tốc độ.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: khi có dữ liệu lớn gồm nhiều trường nhỏ, gói bit để tiết kiệm bộ nhớ — đừng ngại shift/mask. Cờ trạng thái, chỉ số nhỏ, enum, mức độ, đếm giới hạn — gói chúng vào một từ cắt bộ nhớ nhiều lần, và với việc đọc thì chi phí shift/mask không đáng kể. Đây là lý do bit packing có mặt khắp nơi: cờ trong struct của kernel, định dạng nhị phân, Redis (encoding của các kiểu dữ liệu), địa chỉ/thẻ trong CPU. C/C++ còn có bit-field (unsigned type : 3;) để trình biên dịch tự sinh shift/mask giùm.
Hệ quả thứ hai: kỳ vọng đúng lợi ích — bộ nhớ là chắc chắn, tốc độ chỉ là phụ. Đừng gói bit chỉ để mong duyệt nhanh hơn nhiều: throughput thường chỉ nhích lên (như 1,1 lần đo được) vì một khi đủ nhỏ, workload hết bị nghẽn băng thông. Lợi ích tốc độ thật của việc nhỏ gọn xuất hiện gián tiếp: nhiều dữ liệu vừa trong cache hơn, ít áp lực bộ nhớ hơn cho phần còn lại của chương trình. Nếu trường bị ghi rất nhiều (đọc-sửa-ghi), hoặc bạn cần con trỏ/tham chiếu tới từng trường, thì cân nhắc lại.
Hệ quả thứ ba là tinh thần đo lường: một tối ưu có thể thắng lớn ở một trục (bộ nhớ) mà chỉ hòa hoặc nhỉnh ở trục khác (tốc độ) — đừng gộp chúng làm một. Con số mang theo: bit packing gói trường nhỏ vào một từ: bộ nhớ nhỏ ~4x (16→4 byte, 610→153 MB), đọc gần như miễn phí (shift/mask ẩn trong pipeline: mảng nóng hòa, duyệt lớn nhanh ~1,1x); nhưng throughput KHÔNG tỉ lệ với mức nén (chỉ 1,1x vì hết nghẽn băng thông), ghi một trường tốn đọc-sửa-ghi. Dùng cho dữ liệu lớn, đọc nhiều, cần gọn. Đo từng trục riêng, đừng để "nhỏ hơn" tự động nghĩa là "nhanh hơn cùng tỷ lệ".
Thử ba mươi giây
Định nghĩa một struct với vài trường nhỏ theo hai cách: một bản mỗi trường một int (thô), và một bản gói tất cả vào một uint32_t với shift/mask (hoặc dùng bit-field unsigned x : 3;). In sizeof hai bản — bạn sẽ thấy bản nén nhỏ hơn nhiều lần. Rồi cấp một mảng vài chục triệu phần tử mỗi loại và đọc RSS: mảng nén chiếm ít RAM hơn đúng tỷ lệ sizeof. Bấm giờ một vòng duyệt tính tổng một trường: bản nén nhanh hơn một chút nhờ đọc ít byte, nhưng đừng ngạc nhiên nếu chỉ nhanh ~10% chứ không phải mấy lần — một khi đủ nhỏ, vòng lặp hết bị nghẽn bộ nhớ. Cuối cùng, làm với một mảng nhỏ nằm gọn trong cache và đọc lặp lại: hai bản gần như hòa, cho thấy shift/mask gần như miễn phí. Ba mươi giây đó cho bạn thấy điều mà "gói bit làm chậm CPU" giấu đi: rút một trường ra khỏi một từ chỉ là một hai lệnh ẩn trong pipeline, còn bộ nhớ tiết kiệm được là thật và lớn — miễn là bạn kỳ vọng đúng: bit packing thắng ở dung lượng, không phải ở tốc độ.
