Memory model & cache locality — Vì sao LinkedList chậm hơn int[] 25 lần

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

// Sum using primitive int array
int[] arr = new int[10_000_000];
// ... fill arr ...
long sum = 0;
for (int x : arr) sum += x;
// Elapsed: ~8 ms

// Sum using LinkedList of boxed Integer
LinkedList<Integer> list = new LinkedList<>();
// ... fill list ...
long sum = 0;
for (int x : list) sum += x;
// Elapsed: ~200 ms

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 algorithm 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ự.

int[] 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ả.

LinkedList<Integer> 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 traverse LinkedList 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.

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 arr[0] trong int[], CPU tự động nạp cả arr[0] đến arr[15] vào cache (mỗi int 4 byte, 16 phần tử tổng cộng 64 byte). Lần đọc arr[1], arr[2], ..., arr[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 — circuit 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ự arr[0], arr[1], arr[2], ..., prefetcher nhận ra pattern và bắt đầu nạp arr[16], arr[17], ... trước khi code đến đó. Kết quả: mỗi phần tử trong int[] sequential traversal gần như không tốn thời gian chờ.

3.3 Pointer chasing phá vỡ prefetch

LinkedList.Node 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 traverse 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.

Diagram cache hit/miss khi traverse:

int[] sequential access:
[0x1000: 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]
  ^-- load one cache line, prefetch next line
  read 1: HIT (just loaded)
  read 2: HIT
  read 3: HIT
  ... 16 reads from 1 cache line fetch

LinkedList pointer chase:
Node@0x1000 -> next=0x8F20 -> MISS (fetch from RAM, wait 100ns)
Node@0x8F20 -> next=0x3A40 -> MISS (fetch from RAM, wait 100ns)
Node@0x3A40 -> next=0xC510 -> MISS (fetch from RAM, wait 100ns)
  ... 1 cache miss per node

4. Java object overhead — Vì sao LinkedList thật sự tệ

Vấn đề không chỉ là pointer chasing. LinkedList<Integer> còn chịu gánh nặng object overhead rất nặng so với int[].

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

int primitive trong int[]: 4 byte. Chỉ vậy thôi.

Integer boxed object: 12 byte object header (compressed OOPs trên 64-bit JVM) + 4 byte giá trị int + 0 byte padding (tổng vừa đúng 16 byte, aligned). Tổng: 16 byte — 4 lần int primitive.

LinkedList.Node: object header 12 byte + trường item (reference 4 byte với compressed OOPs) + trường prev (4 byte ref) + trường next (4 byte ref) + 4 byte padding = 28–32 byte tùy JVM và alignment.

Tổng cho 1 phần tử trong LinkedList<Integer>:

• Integer object: 16 byte
• LinkedList.Node: 32 byte
• Tổng: 48 byte — so với 4 byte của int[]

Gấp 12 lần về RAM. 10 triệu phần tử: int[] chiếm 40 MB; LinkedList<Integer> chiếm khoảng 480 MB — chưa kể fragmentation của GC heap.

4.2 Đo bằng Java Object Layout (JOL)

JOL là tool chính thức để đo object size trên JVM thực tế:

// Add dependency: org.openjdk.jol:jol-core:0.17
import org.openjdk.jol.info.ClassLayout;

System.out.println(ClassLayout.parseClass(Integer.class).toPrintable());
// Output (64-bit JVM, compressed OOPs):
// java.lang.Integer object internals:
//  OFFSET  SIZE   TYPE DESCRIPTION
//       0    12        (object header)
//      12     4    int Integer.value
// Instance size: 16 bytes

Số liệu JOL là source of truth — kết quả thực tế tùy JVM flag và version. Compressed OOPs bật mặc định khi heap dưới 32 GB; tắt bằng -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<Integer> chậm hơn int[] 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. LinkedList<Integer> chịu cả hai vấn đề: boxing và pointer chasing.

6. Pitfall tổng hợp

Pitfall 1: Dùng LinkedList vì "O(1) insert" nhưng quên traverse cost.

// Mistaken: add at index i -- must traverse to i first
list.add(50_000, newElement); // O(n) traverse + O(1) pointer update = O(n) total

LinkedList.add(index, value) phải gọi node(index) để tìm vị trí — traverse từ đầu hoặc cuối đến index, tốn O(n/2). Chỉ thao tác pointer update sau khi tìm vị trí mới là O(1). Tổng vẫn O(n) — và còn chậm hơn ArrayList.add(index, value) trong thực đo vì cache miss khi traverse.

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. Integer object: 24 byte thay vì 16. Node: có thể lên 48 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 TreeMap cho 100 phần tử.

// Overkill for small n: TreeMap O(log n) with pointer chase overhead
Map<String, Integer> scores = new TreeMap<>(); // 100 entries

// Often faster in practice for small n: ArrayList linear scan, cache friendly
List<Map.Entry<String, Integer>> entries = new ArrayList<>(100);
// linear scan O(n) but n=100, data fits entirely in L1 cache

TreeMap traversal là pointer chasing qua red-black tree nodes — nhiều cache miss. ArrayList linear scan qua 100 phần tử nằm liên tiếp trong bộ nhớ — toàn bộ fit trong L1 cache (100 × 8 byte reference = 800 byte, ít hơn 32 KB L1). Thực đo nhiều trường hợp n dưới 500: ArrayList scan nhanh hơn TreeMap. Đo trước khi kết luận từ asymptotic complexity.

7. Cache locality trong thực tế

Effective Java khuyến nghị ArrayDeque thay LinkedList/Stack: ArrayDeque dùng mảng liên tiếp với circular buffer — cache-friendly cho cả push/pop ở cả hai đầu. LinkedList tốn thêm 2 pointer 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 single contiguous array (ring buffer) thay vì queue với linked nodes. Mỗi slot trong ring buffer cố định, thread ghi và đọc không cần allocate 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 pad thêm byte để mỗi slot chiếm đúng 1 cache line, tránh false sharing (xem self-check). Module 2 sẽ phân tích chi tiết case study LMAX.

Database row store vs column store: Row store (PostgreSQL, MySQL) lưu tất cả cột của một row liền kề — cache-friendly cho SELECT * trên ít row (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 row (OLAP/analytics). Chọn storage layout dựa trên query pattern là cache locality ở cấp database.

HashMap vs LinkedHashMap iteration: LinkedHashMap maintain insertion order qua doubly-linked list nối các entry với nhau. Khi iterate, traversal theo linked list — mỗi entry ở địa chỉ ngẫu nhiên trên heap, cache miss liên tục tương tự LinkedList. Nếu chỉ cần iterate theo insertion order một lần cuối, copy vào ArrayList và iterate mảng sẽ nhanh hơn đáng kể.

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 array liên tiếp trong bộ nhớ. Physics system chỉ đọc positions[] và velocities[] — cache utilization gần 100%. Unity DOTS và Bevy (Rust) đều dùng ECS vì lý do này.

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 LinkedList chậm hơn int[] 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 traverse LinkedList 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; int[] sequential traverse = 1 cache miss cho 16 phần tử; LinkedList pointer chase = 1 cache miss cho mỗi node.
• Hardware prefetcher dự đoán sequential access và nạp trước — int[] tận dụng hoàn toàn; pointer chasing vô hiệu hóa prefetcher.
• LinkedList<Integer> 12x RAM: 1 phần tử = 16 byte Integer + 32 byte Node = 48 byte, so với 4 byte int trong int[].
• Khi LinkedList thực sự thắng: insert/delete tại vị trí đã biết (có iterator), không cần traverse — O(1) pointer update. Khi phải traverse trước thì tổng vẫn O(n) và cache miss còn tệ hơn ArrayList.
• Nguyên tắc thực tế: data-oriented thinking — layout liền kề trong bộ nhớ quan trọng hơn abstract structure. Array, ArrayDeque, column store, ECS đều dựa trên cùng nguyên lý này.
• Đo trước: TreeMap cho 100 phần tử thường chậm hơn ArrayList linear scan vì cache miss nhiều hơn, dù O(log n) thấp hơn O(n).

10. Tự kiểm tra

class Counter {
  volatile long countA; // thread A writes here
  volatile long countB; // thread B writes here
  // Both are 8 bytes, adjacent in memory -> same cache line
  // Every write by A invalidates B's cache and vice versa
}

// Version A: sequential access
int sumSequential(int[] arr) {
  int s = 0;
  for (int i = 0; i < arr.length; i++) s += arr[i];
  return s;
}

// Version B: jump by stride 16
int sumStrided(int[] arr) {
  int s = 0;
  for (int i = 0; i < arr.length; i += 16) s += arr[i];
  return s;
}

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