Khi cài một cây hay danh sách liên kết, phản xạ mặc định là dùng con trỏ: mỗi node được malloc riêng, mỗi liên kết là một con trỏ 8 byte trỏ tuyệt đối tới node con. Đây là "cách chuẩn" trong mọi sách giáo khoa. Nhưng có một lựa chọn khác ít được dạy mà các engine hiệu năng cao dùng thường xuyên: chỉ số (index) vào một arena. Thay vì con trỏ, mỗi liên kết là một chỉ số nhỏ vào một mảng chứa mọi node. Tôi đo cả hai cách trong container gcc:13, và con số cho thấy "cách chuẩn" không phải cách tốt nhất — chỉ số nhỏ hơn, nhanh hơn, và dễ lưu hơn.
Chỉ số vào arena thay cho con trỏ tuyệt đối
Ý tưởng đơn giản: giữ mọi node trong một mảng duy nhất (arena), và mỗi liên kết là chỉ số vào mảng đó (int32, 4 byte) thay vì con trỏ (8 byte). Dùng -1 thay cho null. Node con của node i là arena[node.left_index].
Ba lợi thế:
- Nhỏ hơn: chỉ số 4 byte thay con trỏ 8 byte. Một node cây có 2 con: hai con trỏ = 16 byte, hai chỉ số = 8 byte. Struct gọn hơn thì nhiều node vừa trong một cache line hơn (và với <65 nghìn node,
int162 byte còn nhỏ hơn nữa). - Cache tốt hơn: mọi node nằm liền mạch trong arena, không rải rác như malloc từng cái. Duyệt ít cache miss hơn.
- Serialize/lưu dễ: muốn ghi cấu trúc ra file, chỉ cần ghi cả mảng — chỉ số vẫn đúng khi nạp lại. Con trỏ thì phải sửa (fixup) toàn bộ vì địa chỉ đổi mỗi lần nạp. So sánh, hoán vị, copy cả cấu trúc cũng rẻ hơn (chỉ là copy mảng).
Đo: nhỏ hơn 33%, nhanh hơn 1,86 lần
Tôi dựng một cây nhị phân 10 triệu node theo cả hai cách:
Cây nhị phân 10 triệu node (key + 2 con), g++ -O2:
A. KÍCH THƯỚC NODE:
con trỏ (long + 2 con trỏ 8B) : 24 byte
chỉ số (long + 2 index 4B) : 16 byte
-> index nhỏ hơn 33%
B. BỘ NHỚ (10 triệu node):
arena (index 16B) : 160 MB
con trỏ (24B) : 240 MB (+ overhead malloc mỗi node)
-> index tiết kiệm ~33% RAM
C. TRA CỨU (2 triệu lần, đi từ gốc theo con):
arena/INDEX : 456 ns/tra cứu (node liền mạch trong arena)
CON TRỎ : 847 ns/tra cứu (node malloc rải rác, cache miss)
-> index nhanh hơn ~1,86 lần
Nhìn A: node dùng con trỏ tốn 24 byte (một long + hai con trỏ 8B), node dùng chỉ số chỉ 16 byte (một long + hai int32) — nhỏ hơn 33%. B: với 10 triệu node, đó là 240 MB so với 160 MB, và con số con trỏ còn chưa tính overhead của malloc mỗi node (mỗi lần cấp phát riêng có header quản lý riêng). Nhưng C mới là bất ngờ: tra cứu trên arena (chỉ số) chỉ 456 ns, còn con trỏ tốn 847 ns — arena nhanh hơn 1,86 lần. Vì các node trong arena nằm liền mạch trong một khối 160 MB, nên khi đi xuống cây, phần cứng prefetch và cache làm việc tốt hơn; còn node malloc rải rác khắp bộ nhớ khiến mỗi bước là một cú nhảy tới địa chỉ ngẫu nhiên — cache miss. Chỉ số không chỉ tiết kiệm RAM, nó còn nhanh hơn nhờ bố cục.
Một lần tôi đo hớ: "phải dùng con trỏ" và "con trỏ với index như nhau"
Tôi vào đo với niềm tin sách vở: "cây/list thì dùng con trỏ, đó là cách chuẩn, đúng đắn". Đo cho thấy chỉ số vào arena tốt hơn về mọi mặt đo được: nhỏ hơn 33%, nhanh hơn 1,86 lần, và còn dễ serialize (chỉ ghi mảng, không fixup con trỏ). "Cách chuẩn" không phải cách tối ưu. Còn niềm tin ngược, tinh vi hơn: "con trỏ và chỉ số chỉ là hai kiểu biểu diễn, tốc độ như nhau". Sai — con trỏ 8 byte to gấp đôi chỉ số 4 byte (nên node lớn hơn, cache kém hơn), và node malloc rải rác gây cache miss mỗi bước trong khi arena liền mạch thì không. Chúng không như nhau; khác biệt là 33% RAM và gần 2 lần tốc độ.
Bài học đo lường: dùng CHỈ SỐ (4B, hoặc 2B) vào một arena (mảng node) thay cho CON TRỎ (8B, malloc mỗi node) làm node nhỏ hơn (16 vs 24B = 33%), RAM ít hơn (160 vs 240 MB), tra cứu nhanh hơn (456 vs 847 ns = 1,86x — node liền mạch vs malloc rải rác gây cache miss), và serialize dễ hơn (ghi cả mảng, không fixup con trỏ); đổi lại cần biết trần số node (4B = tối đa ~4 tỷ). Nếu tôi tin "phải dùng con trỏ" tôi bỏ lỡ một tối ưu 33% RAM + 2x tốc độ; nếu tôi tin "con trỏ với index như nhau" tôi coi thường một khác biệt bố cục lớn.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: với cấu trúc node-based lớn, cân nhắc arena + chỉ số thay vì con trỏ + malloc. Cây, đồ thị, danh sách với hàng triệu node là ứng viên hoàn hảo: giữ node trong một std::vector, dùng int32/int16 làm liên kết. Bạn được node nhỏ hơn, cache tốt hơn, và cấp phát nhanh hơn (chỉ push_back, không malloc từng cái). Đây là kỹ thuật cốt lõi của data-oriented design trong game engine và trình biên dịch (AST/IR thường dùng chỉ số vào một pool).
Hệ quả thứ hai: chọn độ rộng chỉ số theo số node tối đa. int32 (4 byte) đủ cho ~4 tỷ node — thừa cho hầu hết trường hợp, và bằng nửa con trỏ. Nếu bạn chắc chắn dưới 65 nghìn node, int16 (2 byte) làm node còn nhỏ hơn nữa. Đây là cùng bài học "chọn kiểu vừa đủ nhỏ" của phần 14: mỗi byte tiết kiệm được nhân lên hàng triệu node.
Hệ quả thứ ba là tinh thần đo lường: "cách chuẩn" trong sách không phải luôn là cách tối ưu — biểu diễn liên kết là một quyết định hiệu năng. Con số mang theo: chỉ số (4B) vào arena vs con trỏ (8B) + malloc: index làm node nhỏ hơn 33% (16 vs 24B), RAM ít hơn 33% (160 vs 240 MB + overhead malloc), tra cứu nhanh 1,86x (456 vs 847 ns) vì arena liền mạch (cache) thay malloc rải rác (cache miss), và serialize dễ (ghi mảng, không fixup con trỏ). Đổi lại cần trần số node (4B ~4 tỷ, 2B ~65k). Cây/graph lớn -> cân nhắc arena+index. Con trỏ không phải lựa chọn duy nhất, và thường không phải lựa chọn tốt nhất.
Thử ba mươi giây
Cài một cây nhị phân hai cách với vài triệu node. Cách một: mỗi node malloc riêng, con trỏ left/right 8 byte. Cách hai: mọi node trong một std::vector, left/right là int32 (chỉ số, -1 cho null). In sizeof node — bản chỉ số nhỏ hơn (16 vs 24 byte). Rồi tra cứu vài triệu lần trên cả hai và bấm giờ — bản arena nhanh hơn, vì node nằm liền mạch thay vì rải rác khắp bộ nhớ. Cuối cùng, thử "lưu cây ra file": bản chỉ số chỉ cần ghi cả vector và nạp lại là xong; bản con trỏ thì mọi con trỏ đều sai sau khi nạp (địa chỉ đổi), phải dựng lại. Ba mươi giây đó cho bạn thấy điều mà "cây thì dùng con trỏ" giấu đi: liên kết không nhất thiết phải là địa chỉ tuyệt đối — một chỉ số vào mảng nhỏ hơn một nửa, thân thiện cache hơn, và lưu được thẳng ra đĩa. Cách chuẩn không phải lúc nào cũng là cách nhanh nhất.
