Cache locality — Vì sao mảng nhanh hơn linked list 25 lần

TL;DR: Big-O ẩn constant — cùng O(n) nhưng cache miss liên tục khiến danh sách liên kết chậm hơn mảng số nguyên 25 lần vì memory latency không nằm trong ký hiệu Big-O. CPU memory hierarchy có nhiều cấp: L1 cache ~1ns, L2 ~10ns, L3 ~30ns, DRAM ~100ns. Mỗi cache miss khi duyệt danh sách liên kết phải đợi 100ns đọc từ RAM. Mảng số nguyên layout liên tiếp: CPU đọc một cache line 64 byte nạp 16 phần tử, hardware prefetcher dự đoán và nạp trước. Danh sách liên kết dùng con trỏ nhảy ngẫu nhiên: 1 cache miss mỗi node, prefetcher vô hiệu. Nguyên tắc thực tế: data-oriented thinking — layout liền kề trong bộ nhớ quan trọng hơn abstract structure.

Bạn cần tính tổng 10 triệu phần tử. Hai đoạn thuật toán bên dưới có cùng logic, cùng độ phức tạp O(n), chạy trên cùng máy:

-- Tính tổng qua mảng số nguyên liên tiếp
-- Thời gian đo được: ~8ms
sumArray(A):
    total <- 0
    for each x trong A: total <- total + x
    return total

-- Tính tổng qua danh sách liên kết với giá trị được đóng gói (boxed)
-- Thời gian đo được: ~200ms
sumLinkedList(L):
    total <- 0
    node <- L.head
    while node != NIL:
        total <- total + node.value
        node <- node.next         -- theo con trỏ đến node tiếp theo
    return total

Cùng O(n). Cùng số phép cộng. Cách nhau 25 lần. Big-O không giải thích được điều này.

Bài này giải thích cache locality từ bản chất — vì sao memory layout quan trọng hơn thuật toán chọn khi input vừa, và lúc nào Big-O lừa bạn ở production.

1. Analogy — Thư viện và bàn đọc sách

Hình dung bạn đang đọc 10 cuốn sách theo thứ tự.

Mảng giống kệ sách liên tiếp: tất cả cuốn xếp cạnh nhau trên cùng một kệ. Lấy xong cuốn 1, với tay lấy ngay cuốn 2 — không đứng dậy, không đi đâu cả.

Danh sách liên kết giống hệ thống mục lục phân tán: mỗi cuốn sách có ghi chú "đọc tiếp ở kệ 7, tầng 3, phòng B". Đọc xong cuốn 1 phải đi bộ 5 phút đến kệ đó mới lấy được cuốn 2. CPU cache giống cái bàn đọc nhỏ chỉ chứa được vài cuốn sách gần nhất — nếu cuốn tiếp theo không trên bàn, phải đứng dậy đi lấy.

2. CPU memory hierarchy — Bậc thang latency

CPU không đọc RAM trực tiếp theo từng byte. Giữa CPU và RAM có một chuỗi bộ nhớ đệm nhỏ nhưng nhanh hơn:

Để dễ so sánh — nếu L1 cache là 1 giây:

• L2 tương đương 3–10 giây
• L3 tương đương 10–30 giây
• DRAM tương đương 100 giây — gần 2 phút
• SSD tương đương vài ngày
• HDD tương đương vài tháng

DRAM chậm hơn L1 khoảng 100 lần. Mỗi cache miss khi duyệt danh sách liên kết buộc CPU đợi 100ns — nghe nhỏ nhưng nhân với 10 triệu phần tử là 1 giây đợi thuần túy.

graph TD
    CPU["CPU\n(xử lý)"]
    L1["L1 Cache\n~1ns / 32-64KB"]
    L2["L2 Cache\n~10ns / 256KB-1MB"]
    L3["L3 Cache\n~30ns / 4-64MB"]
    DRAM["DRAM\n~100ns / GB"]
    SSD["SSD\n~10-100µs / TB"]

    CPU --> L1
    L1 --> L2
    L2 --> L3
    L3 --> DRAM
    DRAM --> SSD

3. Cache line và prefetch — Cơ chế bên dưới

3.1 Cache line là gì

CPU không đọc từng byte riêng lẻ. Mỗi lần cần dữ liệu từ RAM, nó đọc cả một cache line — khối 64 byte liên tiếp (chuẩn trên x86 và ARM hiện đại).

Nghĩa thực tế: khi bạn đọc A[0] trong mảng số nguyên 4-byte, CPU tự động nạp cả A[0] đến A[15] vào cache (16 phần tử × 4 byte = 64 byte). Lần đọc A[1], A[2], ..., A[15] kế tiếp đều là cache hit — gần như miễn phí.

3.2 Hardware prefetcher

CPU hiện đại có hardware prefetcher — mạch điện chuyên dự đoán dữ liệu sẽ cần và nạp trước vào cache.

Khi thấy pattern truy cập tuần tự A[0], A[1], A[2], ..., prefetcher nhận ra pattern và bắt đầu nạp A[16], A[17], ... trước khi code đến đó. Kết quả: mỗi phần tử trong mảng sequential traversal gần như không tốn thời gian chờ.

3.3 Đuổi theo con trỏ phá vỡ prefetch

Node của danh sách liên kết chứa con trỏ next trỏ đến node tiếp theo — node đó có thể nằm ở bất kỳ đâu trên heap. Pattern truy cập trông như:

Node A tại 0x1000 → Node B tại 0x8F20 → Node C tại 0x3A40 → ...

Địa chỉ nhảy ngẫu nhiên. Prefetcher không thể dự đoán — mỗi bước duyệt là một cache miss buộc CPU đợi 100ns để fetch từ RAM. Với 10 triệu node: 10 triệu cache miss × 100ns = 1 giây chờ thuần túy.

Sơ đồ cache hit/miss khi duyệt:

Mảng truy cập tuần tự:
[0x1000: 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]
  ^-- nạp một cache line, prefetch dòng tiếp theo
  đọc phần tử 1: HIT (vừa nạp)
  đọc phần tử 2: HIT
  đọc phần tử 3: HIT
  ... 16 lần đọc từ 1 cache line

Danh sách liên kết đuổi theo con trỏ:
Node@0x1000 -> next=0x8F20 -> MISS (đọc từ RAM, đợi 100ns)
Node@0x8F20 -> next=0x3A40 -> MISS (đọc từ RAM, đợi 100ns)
Node@0x3A40 -> next=0xC510 -> MISS (đọc từ RAM, đợi 100ns)
  ... 1 cache miss mỗi node

4. Overhead object — Vì sao danh sách liên kết thật sự tệ

Vấn đề không chỉ là đuổi theo con trỏ. Danh sách liên kết với giá trị được đóng gói (boxed) còn chịu gánh nặng object overhead rất nặng so với mảng số nguyên.

4.1 Kích thước mỗi phần tử

Số nguyên 4-byte trong mảng primitive: 4 byte. Chỉ vậy thôi.

Số nguyên được đóng gói (boxed Integer): 12 byte object header (compressed OOPs trên JVM 64-bit) + 4 byte giá trị int = 16 byte — 4 lần số nguyên primitive.

Node của danh sách liên kết: 12 byte header + 4 byte tham chiếu item + 4 byte tham chiếu prev + 4 byte tham chiếu next = 24 byte (tổng đã là bội số của 8 nên không cần padding, với compressed OOPs).

Tổng cho 1 phần tử trong danh sách liên kết boxed:

• Integer object: 16 byte
• Node: 24 byte
• Tổng: 40 byte — so với 4 byte của mảng số nguyên

Gấp 10 lần về RAM. 10 triệu phần tử: mảng số nguyên chiếm 40 MB; danh sách liên kết boxed chiếm khoảng 400 MB — chưa kể fragmentation của GC heap.

4.2 Đo bằng công cụ phân tích layout object (JOL)

JOL là tool chính thức để đo object size trên JVM thực tế. Với compressed OOPs bật (mặc định khi heap dưới 32 GB), Integer object = 16 byte. Tắt bằng cờ -XX:-UseCompressedOops sẽ tăng object header lên 16 byte và reference lên 8 byte.

5. Benchmark — Con số thực tế

Số đo xấp xỉ trên JVM hiện đại (Java 21, warmup đủ, JMH):

ArrayList boxed chậm hơn mảng primitive vì boxing — mỗi phần tử là Integer object 16 byte thay vì 4 byte, L1 cache chứa ít phần tử hơn, nhưng layout vẫn liền kề nên prefetcher còn hoạt động được. Danh sách liên kết boxed chịu cả hai vấn đề: boxing và đuổi theo con trỏ.

6. Pitfall tổng hợp

Pitfall 1: Dùng danh sách liên kết vì "O(1) insert" nhưng quên traverse cost.

-- Nhầm: add tại index i -- phải duyệt đến i trước
list.add(50000, newElement)
-- O(n) duyệt + O(1) cập nhật con trỏ = O(n) tổng
-- Còn chậm hơn mảng động trong thực đo vì cache miss khi duyệt

add(index, value) trên danh sách liên kết phải tìm vị trí index trước — duyệt từ đầu hoặc cuối đến index, tốn O(n/2). Chỉ thao tác cập nhật con trỏ sau khi tìm vị trí mới là O(1). Tổng vẫn O(n) — và còn chậm hơn mảng động trong thực đo vì cache miss khi duyệt.

Pitfall 2: Object header size thay đổi theo JVM config.

Với -XX:-UseCompressedOops (heap vượt 32 GB hoặc tắt tường minh), object header tăng từ 12 lên 16 byte, reference từ 4 lên 8 byte. Không hardcode những con số này trong code production — dùng JOL để đo khi cần.

Pitfall 3: Tin Big-O quá, chọn cây tìm kiếm cho 100 phần tử.

-- Quá mức cần thiết cho n nhỏ: TreeMap O(log n) với cache miss overhead
-- Với 100 entry: dùng mảng linear scan thường nhanh hơn trong thực đo
-- Vì toàn bộ 100 phần tử vừa trong L1 cache (100 × 8 byte = 800 byte, nhỏ hơn 32KB L1)
-- TreeMap duyệt qua cây đỏ-đen -- nhiều cache miss mỗi bước

Duyệt cây tìm kiếm là đuổi theo con trỏ qua các node cây — nhiều cache miss. Mảng linear scan qua 100 phần tử nằm liên tiếp trong bộ nhớ — toàn bộ fit trong L1 cache. Thực đo nhiều trường hợp n dưới 500: mảng scan nhanh hơn cây tìm kiếm. Đo trước khi kết luận từ asymptotic complexity.

7. Cache locality trong thực tế

Deque dùng mảng thay danh sách liên kết: Nhiều thư viện khuyến nghị Deque dựa trên mảng thay vì danh sách liên kết/Stack truyền thống. Mảng circular dùng vùng nhớ liên tiếp — cache-friendly cho cả push/pop ở cả hai đầu. Danh sách liên kết tốn thêm 2 con trỏ và 1 object header mỗi node, cộng với cache miss mỗi bước.

LMAX Disruptor — ring buffer zero pointer overhead: Disruptor pattern dùng mảng liên tiếp đơn (ring buffer) thay vì queue với các node liên kết. Mỗi slot trong ring buffer cố định, thread ghi và đọc không cần cấp phát object mới — gần như loại bỏ hoàn toàn cache miss và GC pressure. Ngoài ra, các slot trong buffer được padding thêm byte để mỗi slot chiếm đúng 1 cache line, tránh false sharing (xem self-check).

Database row store vs column store: Row store (PostgreSQL, MySQL) lưu tất cả cột của một hàng liền kề — cache-friendly cho SELECT * trên ít hàng (OLTP). Column store (Parquet, ClickHouse, Apache Arrow) lưu tất cả giá trị của một cột liền kề — cache-friendly cho SUM(revenue), AVG(price) trên nhiều hàng (OLAP/analytics). Chọn storage layout dựa trên query pattern là cache locality ở cấp database.

Game engine — Data-Oriented Design: Game engine truyền thống dùng OOP: mỗi Entity là object chứa position, velocity, health, renderer. Khi update physics cho 10.000 entity, phải load toàn bộ object (vài trăm byte) dù chỉ cần position và velocity (16 byte). Entity-Component-System (ECS) tách ra: positions[], velocities[] — mỗi mảng liên tiếp trong bộ nhớ. Physics system chỉ đọc positions[] và velocities[] — cache utilization gần 100%.

8. 📚 Deep Dive tài liệu gốc

9. Tóm tắt

• Big-O ẩn constant — cùng O(n) nhưng cache miss liên tục khiến danh sách liên kết chậm hơn mảng số nguyên 25 lần vì memory latency không nằm trong ký hiệu Big-O.
• CPU memory hierarchy: L1 ~1ns, L2 ~10ns, L3 ~30ns, DRAM ~100ns — mỗi cache miss khi duyệt danh sách liên kết phải đợi 100 lần lâu hơn so với cache hit.
• Cache line 64 byte: CPU đọc theo khối 64 byte liên tiếp; mảng sequential traverse = 1 cache miss cho 16 phần tử int; danh sách liên kết đuổi theo con trỏ = 1 cache miss mỗi node.
• Hardware prefetcher dự đoán sequential access và nạp trước — mảng tận dụng hoàn toàn; đuổi theo con trỏ vô hiệu hóa prefetcher.
• Danh sách liên kết boxed 10x RAM: 1 phần tử = 16 byte Integer + 24 byte Node = 40 byte, so với 4 byte int trong mảng.
• Khi danh sách liên kết thực sự thắng: insert/delete tại vị trí đã biết (có iterator), không cần duyệt — O(1) cập nhật con trỏ. Khi phải duyệt trước thì tổng vẫn O(n) và cache miss còn tệ hơn mảng động.
• Nguyên tắc thực tế: data-oriented thinking — layout liền kề trong bộ nhớ quan trọng hơn abstract structure. Mảng, Deque vòng tròn, column store, ECS đều dựa trên cùng nguyên lý này.
• Đo trước: cây tìm kiếm cho 100 phần tử thường chậm hơn mảng linear scan vì cache miss nhiều hơn, dù O(log n) thấp hơn O(n).

10. Tự kiểm tra

-- Hai bộ đếm nằm liền kề trong bộ nhớ -> cùng cache line
Counter:
  countA: long    -- thread A ghi vào đây
  countB: long    -- thread B ghi vào đây
  -- Cả hai cách nhau 8 byte, nằm trong cùng cache line 64 byte
  -- Mỗi lần A ghi countA: invalidate cache line của B và ngược lại

-- Phiên bản A: truy cập tuần tự
sumSequential(A):
  s <- 0
  for i <- 0 đến n-1: s <- s + A[i]
  return s

-- Phiên bản B: nhảy theo stride 16
sumStrided(A):
  s <- 0
  for i <- 0 đến n-1 bước 16: s <- s + A[i]
  return s

Bài tiếp theo: Problem-solving framework