Bỏ con trỏ, dùng chỉ số: cây nhỏ hơn 33% và nhanh hơn 1,86 lần

Có hai cách chỉ cho ai đó biết một căn phòng. Cách thứ nhất: đưa địa chỉ đầy đủ tuyệt đối — "số nhà, tên đường, quận, thành phố" — dài, và nếu tòa nhà bị dời đi thì địa chỉ ấy sai hết. Cách thứ hai: nói "phòng 305 trong khách sạn này" — ngắn gọn, và dù cả khách sạn có được nhấc lên chở đi nơi khác, "phòng 305" vẫn đúng. Khi cài một cây hay danh sách liên kết, con trỏ chính là kiểu địa chỉ tuyệt đối, còn chỉ số vào một arena là kiểu số phòng trong khách sạn — và cái khác biệt tưởng nhỏ đó hóa ra đổi cả kích thước lẫn tốc độ.

Phản xạ mặc định của mọi sách giáo khoa 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. 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) — cái khách sạn — 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, int16 2 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. Đây đúng là "nhấc cả khách sạn đi mà số phòng vẫn đúng". 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à chỗ tôi thấy bất ngờ nhất: 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ôi trường đo: container gcc:13 trên host ARM AArch64, g++ -O2, cây 10 triệu node, mỗi số lấy MIN sau warmup. Con số tuyệt đối đổi theo máy; cái cần nhìn là node gọn hơn 33%, và lợi thế tốc độ đến từ tính liền mạch của arena so với malloc rải rác.)

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

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". Con số 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.

Nhưng có một niềm tin ngược, tinh vi hơn, cũng sai: "con trỏ và chỉ số chỉ là hai kiểu biểu diễn, tốc độ như nhau, chọn gì cũng thế". Con số bác lại — 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 độ. Cái giá duy nhất của chỉ số là bạn phải biết trước trần số node.

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

Điều đầ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).

Điều 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ỏ": mỗi byte tiết kiệm được nhân lên hàng triệu node.

Chỗ này nếu bạn từng làm với các định dạng dữ liệu hiện đại thì thấy đúng ý tưởng "số phòng thay địa chỉ" lặp lại khắp nơi, chỉ đổi tên. Các định dạng serialize như FlatBuffers và Cap'n Proto cố tình dùng offset (một dạng chỉ số) thay con trỏ, đúng vì thế mà đọc chúng khỏi cần bước "giải mã và fixup con trỏ" — ánh xạ file vào bộ nhớ là dùng được ngay. Trong Java, dùng int index vào các mảng nguyên thủy song song thay cho một mảng object là mẹo kinh điển để né overhead con trỏ và cache miss (chính là tinh thần của các thư viện primitive-collection). Còn ở tầng database, con trỏ trong một cây B trên đĩa bắt buộc phải là số hiệu trang chứ không thể là địa chỉ RAM — vì trang được nạp vào các vị trí khác nhau mỗi lần, y hệt "khách sạn bị dời chỗ". Cùng một bài học: khi dữ liệu phải sống ngoài một lần chạy chương trình, chỉ số bền hơn con trỏ.

Muốn tự thấy thì 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. Vài phút đó 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.