Bài trước kết thúc bằng một phát hiện khó chịu: hai cây nhị phân cùng chiều cao, cùng O(log n), mà tra chênh nhau 6 lần chỉ vì cách các node nằm trong bộ nhớ. Thủ phạm là trượt cache — cây nhị phân con trỏ rải rác bắt CPU nhảy tới một node ở địa chỉ ngẫu nhiên ở mỗi tầng, và khi cây vượt cache thì mỗi cú nhảy là một lần chờ RAM. B-tree là câu trả lời trực diện cho vấn đề đó. Bài này cài B-tree thật, đo nó ở nhiều bậc, và bắt gặp một trong những bài học đo lường sạch sẽ nhất của sê-ri: số so sánh và đồng hồ nói hai điều trái ngược, và chỉ một trong hai nói thật.
B-tree đổi cách bố trí, không đổi ý tưởng tìm kiếm
Ý tưởng tìm kiếm của B-tree vẫn là chia để trị như cây nhị phân, nhưng cách xếp dữ liệu vào bộ nhớ thì đảo ngược. Thay vì mỗi node giữ một khóa và hai con trỏ, một node B-tree giữ nhiều khóa — bậc B của cây — nằm liền nhau trong một khối, cùng B con trỏ tới các cây con. Vì mỗi node "nuốt" được nhiều khóa, cây thấp hẳn xuống: chiều cao là log theo cơ số B chứ không phải cơ số 2. Với hai triệu khóa, một cây nhị phân cao 22 tầng, còn B-tree bậc 64 chỉ cao 4 tầng.
Vì sao chiều cao lại đáng giá đến thế? Vì cái đắt không phải phép so sánh, mà là mỗi lần bước xuống một tầng — đó là lúc CPU phải nạp một node mới từ bộ nhớ, và nếu node không có trong cache thì phải chờ RAM (hàng trăm chu kỳ). Một node B-tree được gói trong một khối liền cỡ một dòng cache, nên nạp cả node chỉ tốn một lần chờ. Ít tầng nghĩa là ít lần chờ. Bên trong một node thì CPU quét tuyến tính qua các khóa đã nằm sẵn trong cache — rẻ như không. Đây chính là lý do B-tree là cấu trúc của mọi chỉ mục cơ sở dữ liệu và hệ thống tệp: ở đó "một lần nạp" là một lần đọc đĩa, đắt gấp vạn lần, nên ép cây thật thấp là thắng lớn. Tôi đo xem lý thuyết này đúng tới đâu, và ở bậc B nào.
Đo: quét đường cong theo bậc B
Tôi cài B-tree trong C (gcc -O2), nạp hai triệu khóa, rồi đo với các bậc B từ 2 tới 256: số tầng, số phép so sánh trung bình mỗi lần tra, và thời gian tra thực tế. Kèm một mốc so sánh: tìm nhị phân trên mảng phẳng đã sắp.
bậc B tầng so sánh/tra thời gian tra
2 22 22 437 ns (chính là cây nhị phân con trỏ)
8 8 31 92 ns
16 6 43 71 ns
32 5 66 70 ns *
64 4 100 70 ns *
128 3 190 81 ns
256 3 271 100 ns
tìm nhị phân mảng phẳng: 20 so sánh, 98 ns
Đường cong kể một câu chuyện rõ ràng. Khi B tăng, số tầng giảm đều (22 xuống 3), số so sánh mỗi lần tra tăng (22 lên 271), còn thời gian thì đi theo hình chữ U: giảm mạnh từ 437 xuống chạm đáy khoảng 70 nano giây ở bậc 32-64, rồi lại nhích lên. B=2 — vốn chính là một cây nhị phân con trỏ — chậm nhất, 437 nano giây, vì 22 tầng là 22 lần trượt cache. Bậc tối ưu nằm ở 32-64, nơi node vừa cỡ một dòng cache. Và hai con số ở đáy chữ U với ở mốc nhị phân là chỗ tôi suýt kết luận sai.
Một lần tôi đo hớ: số so sánh nói dối, đồng hồ nói thật
Nếu tôi đo B-tree bằng thước quen thuộc nhất của phân tích thuật toán — đếm số phép so sánh — thì tôi đã kết luận B-tree tệ hơn. Nhìn thẳng vào số: tìm nhị phân trên mảng làm 20 phép so sánh mỗi lần tra; B-tree bậc 64 làm 100 — gấp năm lần. Theo cách đếm cổ điển, năm lần nhiều việc hơn thì phải năm lần chậm hơn. Tôi đã vào bài nửa tin rằng B-tree chỉ đáng cho đĩa, còn trong RAM thì tìm nhị phân gọn nhẹ sẽ thắng.
Đồng hồ nói ngược lại. B-tree bậc 64 tra mất 70 nano giây; tìm nhị phân mất 98. B-tree làm gấp năm lần số so sánh mà vẫn nhanh hơn. Lý do là số so sánh đo nhầm đại lượng: cái quyết định thời gian không phải số phép so sánh, mà là số lần trượt cache. Tìm nhị phân trên mảng hai triệu phần tử nhảy tới 20 vị trí cách xa nhau, phần lớn là trượt cache — khoảng 20 lần chờ RAM. B-tree bậc 64 chỉ đi xuống 4 tầng, tức 4 lần nạp node; 100 phép so sánh của nó nằm gọn trong 4 khối đã ở trong cache, chạy gần như miễn phí. Bốn lần chờ RAM đánh bại hai mươi lần, dù kèm theo nhiều phép so sánh gấp bội. Đây là bài học đo lường cốt lõi: số phép so sánh là một mô hình chi phí lỗi thời; trên phần cứng thật, đơn vị đắt tiền là một lần chạm bộ nhớ, và chỉ đồng hồ mới đếm đúng nó. Ai tối ưu theo số so sánh sẽ chọn sai cấu trúc.
Cú hớ thứ hai nằm ngay cạnh: nếu ít tầng là tốt, thì cứ chọn B thật lớn cho ít tầng nhất, phải không? Đo ra không. Bậc 256 có ít tầng nhất (3) nhưng lại chậm hơn bậc 64 (100 so với 70 nano giây), vì mỗi node giờ to tới mức quét tuyến tính qua 255 khóa trong nó bắt đầu tốn — và một node 2KB tràn khỏi một dòng cache, nên "một lần nạp" thành nhiều lần. Có một bậc B tối ưu, ở đây quanh 32-64, đúng chỗ một node vừa khít cỡ một dòng cache. Không đo cả đường cong thì không thấy được cái đỉnh này — đúng như kỷ luật của sê-ri: đo đường cong, đừng đo một điểm.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: bỏ thói quen đếm số phép so sánh khi cần biết cái gì nhanh trên phần cứng thật. Số so sánh (và big-O đếm thao tác nói chung) là mô hình từ thời bộ nhớ phẳng, mọi truy cập tốn như nhau. Máy thật không như vậy — một lần trúng cache và một lần trượt cache chênh nhau cả trăm lần. Khi hai cấu trúc cùng độ phức tạp mà một cái chạm bộ nhớ ít lần hơn, cái đó thắng, dù nó làm nhiều "thao tác" hơn trên giấy. Cách duy nhất để biết là bấm đồng hồ.
Hệ quả thứ hai: thiết kế cấu trúc theo cấp bộ nhớ mà nó sống trên đó. B-tree tỏa sáng vì nó khớp với thực tế phần cứng: dữ liệu di chuyển theo khối (dòng cache 64 byte, trang đĩa vài KB), không theo từng byte. Gói nhiều khóa vào một khối để mỗi lần nạp làm được nhiều việc là nguyên lý chung — nó là lý do CSDL dùng B-tree với node cỡ trang đĩa, và cũng là lý do trong RAM người ta dùng B-tree bậc nhỏ (hay cây gói mảng) thay cho cây nhị phân con trỏ. Chọn bậc B khớp cấp bộ nhớ đang nghẽn: cỡ dòng cache nếu ở RAM, cỡ trang nếu ở đĩa.
Hệ quả thứ ba là bài học đo lường mang theo. Con số cần nhớ: B-tree bậc 64 làm 100 phép so sánh mỗi lần tra, gấp 5 lần tìm nhị phân (20), nhưng tra 70ns so với 98ns vì chỉ 4 lần nạp bộ nhớ thay vì 22 — số so sánh nói dối, đồng hồ nói thật; và có bậc B tối ưu quanh cỡ dòng cache (32-64), không phải càng lớn càng nhanh. Khi một cấu trúc "làm nhiều việc hơn" mà vẫn nhanh hơn, đừng cãi lại đồng hồ — hãy hỏi nó đang đếm đúng cái gì mà cách đếm cũ của bạn bỏ sót.
Thử ba mươi giây
Lần tới khi bạn định chọn cấu trúc tra cứu "ít thao tác nhất", dừng lại hỏi: mỗi thao tác của nó chạm bộ nhớ ở đâu? Một cây nhị phân đẹp trên giấy (log n so sánh) nhưng con trỏ rải khắp bộ nhớ sẽ trả giá một lần trượt cache cho mỗi tầng; một cấu trúc gói dữ liệu thành khối liền làm nhiều so sánh hơn nhưng ít lần chạm RAM hơn, và thường thắng. Cách thử nhanh nhất là đừng suy luận mà đo: lấy cấu trúc của bạn, đếm số lần nó nhảy tới một địa chỉ xa (đó là các lần trượt cache tiềm tàng), rồi so với số lần nó đọc dữ liệu liền kề. Nếu bạn thấy nhiều cú nhảy xa, đó là chỗ để cải thiện — gói dữ liệu lại gần nhau, giảm số tầng, tăng số việc làm trên mỗi lần nạp. Và luôn xác nhận bằng đồng hồ: nếu số so sánh giảm mà thời gian không giảm, bạn vừa tối ưu nhầm đại lượng.
