Cùng số phép đọc, một cách chậm hơn 405 lần: sức mạnh của cục bộ bộ nhớ

Hình dung bạn đi gom hàng trong một siêu thị khổng lồ với một danh sách mua sắm. Nếu danh sách được sắp theo lối đi — sữa ở lối 1, bánh ở lối 2... — bạn quét một vòng gọn gàng, và siêu thị còn khôn ngoan dọn sẵn hàng lối kế tiếp ra đầu kệ trước khi bạn tới (đó là prefetch); mỗi lần với tay bạn còn bốc luôn cả thùng sáu hộp chứ không phải một hộp (đó là cache line). Nhưng nếu danh sách xáo trộn lung tung — sữa, rồi kem đánh răng tận cuối siêu thị, rồi lại về đầu lấy bánh — bạn phải băng ngang cả cửa hàng cho từng món, mỗi món một chuyến đi dài, và cái thùng sáu hộp bạn mở ra chỉ lấy một hộp rồi bỏ. Cùng chừng ấy món trong giỏ, nhưng cách đi quyết định bạn xong trong mười phút hay ba tiếng. Bộ nhớ máy tính thưởng cho sự "đi theo lối" đúng như vậy — và mức thưởng lớn đến sốc.

Cho tới giờ ta coi bộ nhớ như một khối phẳng ai chạm cũng như nhau. Sự thật phần cứng phức tạp hơn: nơi dữ liệu nằm quyết định bao lâu để lấy nó. Ở quy mô lớn nhất, đó là NUMA (Non-Uniform Memory Access) — máy nhiều socket, mỗi CPU có RAM riêng gần nó, và chạm RAM của socket khác thì chậm hơn. Tôi định đo NUMA — nhưng ngay bước đầu đã đụng một bài học trung thực về đo lường, và rồi đo được thứ thực sự quan trọng: cục bộ bộ nhớ (locality), thứ mà NUMA chỉ là trường hợp cực đoan.

Không có NUMA để đo — và tôi báo thật

Bước đầu tiên khi định đo NUMA: kiểm máy có mấy node bộ nhớ. Tôi chạy trong container gcc:13:

ls /sys/devices/system/node/   -> không có thư mục node nào
lscpu | grep -i numa           -> không có dòng NUMA
nproc                          -> 10

Máy đo này là Apple Silicon ảo hóa (ARM AArch64), và nó chỉ có một node bộ nhớ. Không có hai socket, không có RAM "gần" và "xa" — mọi lõi chạm mọi byte với cùng độ trễ. Nghĩa là tôi không thể đo độ trễ bất đối xứng của NUMA trên máy này, đơn giản vì nó không tồn tại ở đây.

Đây là một điểm rẽ đúng tinh thần cả sê-ri: khi công cụ không quan sát được một hiện tượng, câu trả lời trung thực là "không đo được ở đây", chứ không phải bịa một con số cho có. Tôi có thể viết ra vài con số "độ trễ chéo-node" nghe rất thuyết phục — nhưng chúng sẽ là bịa đặt, và một con số bịa nguy hiểm hơn một lỗ trống thành thật. Vậy nên tôi ghi rõ: NUMA asymmetry không đo được trên máy một node này.

Nhưng câu chuyện chưa hết — vì NUMA không phải một hiện tượng cô lập. Nó là điểm cực đoan của một nguyên lý tổng quát hơn: cục bộ bộ nhớ. Và cục bộ thì đo được, ngay trên một node, và hóa ra ảnh hưởng khổng lồ.

Đo (a): tuần tự nhanh hơn ngẫu nhiên 405 lần

Nguyên lý cục bộ nói: truy cập bộ nhớ gần nhau và theo thứ tự nhanh hơn nhiều truy cập rải rác. Phần cứng có hai cơ chế thưởng cho cục bộ: cache line (mỗi lần chạm RAM kéo về cả một khối 64 byte, nên đọc các byte kế tiếp gần như miễn phí — bốc cả thùng) và prefetch (CPU đoán bạn sắp đọc tuần tự nên nạp trước — dọn sẵn lối kế). Cả hai chỉ giúp nếu bạn truy cập có cục bộ.

Tôi đo trên một mảng 256 MB (lớn hơn mọi cache), một luồng, hai kiểu truy cập:

tuần tự (đọc theo thứ tự, stride 1)  :  0,23 ns / phần tử
ngẫu nhiên (pointer-chase, phá prefetch): 92,3 ns / phần tử
ngẫu nhiên / tuần tự                 :  405× chậm hơn

Cùng một mảng, cùng số phép đọc — chỉ khác thứ tự. Đọc tuần tự tốn 0,23 ns mỗi phần tử (cache line và prefetch làm việc trơn tru, phần lớn phần tử đã nằm sẵn trong cache khi cần). Đọc ngẫu nhiên — nhảy tới một vị trí không đoán trước được mỗi lần — tốn 92 ns, gần bằng độ trễ chạm thẳng RAM, vì mỗi truy cập là một cache miss: prefetch vô dụng (không đoán được), và cả cache line 64 byte kéo về chỉ dùng đúng 4 byte rồi vứt (mở thùng lấy một hộp). Chênh lệch 405 lần. Đây là con số làm nhiều người sốc: hai đoạn code đọc cùng lượng dữ liệu, một nhanh hơn cái kia bốn trăm lần, chỉ vì một cái đi theo thứ tự còn một cái nhảy lung tung.

Đo (b): băng thông chung không scale tuyến tính

NUMA nói về độ trễ khác nhau; nhưng ngay trên một node, bộ nhớ còn là một tài nguyên dùng chung có giới hạn về băng thông. Nhiều lõi cùng đọc RAM phải chia nhau một đường tới bộ điều khiển nhớ (một cửa nhập hàng). Tôi đo băng thông đọc (tổng mảng 256 MB) theo số luồng:

NT | thời gian | GB/s | speedup
 1 |   16,6 ms | 16,2 | 1,00×
 2 |    8,8 ms | 30,6 | 1,89×
 4 |    4,5 ms | 59,3 | 3,66×
 8 |    3,4 ms | 79,4 | 4,90×
10 |    3,1 ms | 87,5 | 5,40×

Băng thông có tăng theo số luồng — nhưng dưới tuyến tính: 10 luồng chỉ đạt 5,40× băng thông một luồng, không phải 10×. Và chú ý đoạn cuối: từ 8 lên 10 luồng, băng thông chỉ nhích 79 → 87 GB/s (thêm 25% luồng chỉ được 10% băng thông) — đường cong đang phẳng dần. Đó là dấu hiệu bộ điều khiển nhớ bắt đầu bão hòa: bạn thêm lõi, nhưng đường ống tới RAM có hạn, nên các lõi tranh nhau băng thông thay vì mỗi lõi có phần riêng. Đây khác với việc thuần CPU ta đo ở contention và scaling (workload độc lập scale gần tuyến tính tới ~10 lõi vì mỗi lõi tự tính, không tranh gì): việc nặng bộ nhớ bị chặn bởi băng thông chung, không phải số lõi.

Đo (c): dữ liệu gần luồng vs rải khắp

Điểm cuối, gần gũi nhất với NUMA "giữ dữ liệu gần lõi": khi chia việc cho các luồng, cho mỗi luồng một khối liền (gần nhau) hay để mỗi luồng rải khắp mảng? Tôi so hai cách chia cùng tổng 256 MB, 10 luồng:

gần (mỗi luồng một chunk liền)   :  3,4 ms
rải (cyclic, luồng đọc xen kẽ)   : 11,1 ms  -> chậm 3,31×

Chia gần — mỗi luồng đọc một dải liền — nhanh 3,31 lần so với chia rải. Vì sao? Khi rải (luồng 0 đọc phần tử 0, 10, 20...; luồng 1 đọc 1, 11, 21...), cả 10 luồng cùng cần các phần tử nằm trong cùng một cache line 64 byte — mỗi cache line bị 10 luồng khác nhau kéo về, mỗi luồng chỉ dùng một phần rồi bỏ. Cùng một cache line bị nạp đi nạp lại, băng thông phí phạm gấp nhiều lần. Chia gần thì mỗi luồng "sở hữu" trọn các cache line của mình, dùng hết 64 byte trước khi sang line khác. Đây chính là false sharing ở phiên bản đọc — và là bản chất của lời khuyên NUMA "giữ dữ liệu mỗi luồng cần gần nhau".

(Môi trường đo: container gcc:13 trên host ARM AArch64 (Apple Silicon ảo hóa), 10 lõi, MỘT node bộ nhớ, dòng cache 64B, mảng 256 MB > mọi cache. NUMA asymmetry không tồn tại trên máy này nên không đo; con số cục bộ và băng thông đổi theo máy, nhưng hình dạng bền vững: tuần tự áp đảo ngẫu nhiên, băng thông chung dưới tuyến tính, chia gần thắng chia rải.)

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

Tôi vào với hai niềm tin. Thứ nhất: "NUMA đo được ở mọi máy nhiều lõi". Sai — nhiều lõi không có nghĩa là nhiều node bộ nhớ; máy này 10 lõi nhưng một node, nên không có NUMA asymmetry để đo. Thứ hai: "thêm luồng thì băng thông bộ nhớ tăng tuyến tính". Cũng sai — băng thông là tài nguyên chung, 10 luồng chỉ được 5,4×.

Nhưng bài học đo lường lớn nhất ở phần này không phải một con số — mà là điều tôi không làm: tôi không bịa con số NUMA. Rất dễ để viết "độ trễ node xa gấp 1,8 lần node gần" cho khớp kỳ vọng người đọc — sách giáo khoa nói vậy, và không ai kiểm được. Nhưng tôi không đo được nó trên máy này, nên ghi ra là nói dối. Đúng tinh thần đo lường vi mô đúng cách: một phép đo chỉ đáng tin khi nó thật sự chạy trên phần cứng trước mặt; khi phần cứng không có hiện tượng đó, câu trả lời trung thực là "không quan sát được ở đây", và ta đo cái đo được — cục bộ — vốn là nền tảng mà NUMA chỉ khuếch đại. Con số bịa mượt mà hơn lỗ trống thành thật, nhưng nó phá hỏng đúng thứ khiến cả sê-ri này đáng đọc: rằng mọi con số đều từ đồng hồ thật.

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

Điều đầu tiên: cục bộ bộ nhớ thường quan trọng hơn cả số phép tính. Một vòng lặp đọc tuần tự nhanh hơn cùng vòng đó đọc ngẫu nhiên hàng trăm lần — nên bố trí dữ liệu để duyệt tuần tự (mảng thay vì danh sách liên kết rải rác), tránh nhảy con trỏ khắp heap. Đây là cả một trường phái: data-oriented design và cấu trúc "struct-of-arrays" (gom mỗi trường vào một mảng liền, duyệt trường nào chỉ đụng mảng đó) đánh bại "array-of-structs" đúng vì locality; và đó là lý do ArrayList của Java thường thắng LinkedList khi duyệt dù cùng độ phức tạp O(n) trên giấy — mảng liền, còn list là các node rải khắp heap, mỗi node một cache miss.

Điều thứ hai: với việc nặng bộ nhớ, đừng kỳ vọng scale theo số lõi. Nếu vòng lặp của bạn chủ yếu đọc/ghi bộ nhớ (ít tính), băng thông chung sẽ chặn nó — thêm luồng chỉ giúp tới điểm bão hòa (ở đây ~5×) rồi phẳng. Đo đường cong băng thông của bạn; nếu nó phẳng sớm, giải pháp là giảm lượng dữ liệu chạm (cache tốt hơn, nén, xử lý tại chỗ), không phải thêm luồng.

Chỗ này cái nguyên lý "đọc theo thứ tự, giữ dữ liệu gần" leo lên tận kiến trúc hệ thống lớn. Cơ sở dữ liệu cột (columnar — ClickHouse, Parquet, DuckDB) ra đời chính vì locality: một truy vấn phân tích chỉ đọc vài cột thì lưu mỗi cột liền một khối cho phép quét tuần tự tốc độ băng thông, thay vì kiểu row-store phải nhảy qua mọi hàng nhặt từng ô — đúng cái 405× tôi đo, ở quy mô terabyte. Cũng vì thế mà index scan tuần tự trên khóa clustered nhanh hơn nhiều random seek, và DB rất ngại truy vấn buộc nhảy ngẫu nhiên khắp đĩa. Trên máy NUMA thật (server nhiều socket), nguyên lý này thành lời khuyên vận hành cụ thể: numactl --membind ghim bộ nhớ vào node của lõi chạy, JVM có cờ -XX:+UseNUMA để cấp phát heap theo node, và các database lớn (Oracle, SQL Server, Postgres) đều có tùy chọn NUMA-aware — tất cả để tránh đúng cái "đi lấy hàng ở kho xa" mà tôi không đo được ở đây nhưng có thật trên phần cứng đó. Mẫu số chung: từ dòng cache 64 byte tới node NUMA tới file cột trên đĩa, câu hỏi luôn là "dữ liệu tôi sắp cần có nằm gần và theo thứ tự không".

Muốn tự soi thì lấy một vòng lặp duyệt dữ liệu của bạn và hỏi: nó chạm bộ nhớ theo thứ tự hay nhảy lung tung? Nếu bạn duyệt một mảng từ đầu tới cuối, cache và prefetch giúp bạn — nhanh. Nếu bạn theo con trỏ trong một danh sách liên kết, hay tra một bảng băm với khóa ngẫu nhiên, mỗi bước là một cú nhảy có thể cache miss — và như đo được, một cache miss đắt gấp hàng trăm lần một lần đọc tuần tự. Thử một thí nghiệm: tính tổng một mảng lớn theo thứ tự, rồi tính tổng đúng mảng đó theo một hoán vị ngẫu nhiên các chỉ số — bấm giờ cả hai. Bạn sẽ thấy bản ngẫu nhiên chậm hơn nhiều lần dù làm y hệt số phép cộng. Vài phút đó dạy bạn vì sao "giữ dữ liệu gần và đọc tuần tự" là một trong những đòn tối ưu mạnh nhất — và vì sao NUMA, cache, prefetch đều là cùng một câu chuyện: nơi dữ liệu nằm quan trọng ngang bạn làm gì với nó.