Viết code cache-friendly — locality thành kỹ năng

TL;DR: Hai bài trước cho bạn cơ chế (cache line, locality); bài này biến nó thành kỹ năng có hệ thống. Bốn kỹ thuật cốt lõi: (1) duyệt theo thứ tự bộ nhớ (vòng lặp trong cùng đi theo chiều dữ liệu liền nhau), (2) loop blocking/tiling (chia bài toán thành khối vừa cache để tái dùng dữ liệu trước khi nó bị đẩy ra), (3) gói dữ liệu nóng lại gần nhau (để mỗi cache line toàn byte cần), và (4) tránh pointer chasing (ưu tiên cấu trúc liền mạch hơn con trỏ rải rác). Tất cả đều giữ nguyên thuật toán và big-O — chỉ đổi cách dữ liệu được chạm tới — nhưng có thể tăng tốc nhiều lần trên dữ liệu lớn. Đây là kỹ năng "mechanical sympathy" cốt lõi của course.

Bạn đã biết vì sao cache thưởng locality. Câu hỏi giờ là làm thế nào để viết code có locality một cách chủ động — không phải dò dẫm, mà theo vài kỹ thuật lặp lại được. Điểm chung của cả bốn: chúng không đổi bạn tính gì, chỉ đổi bạn chạm bộ nhớ theo thứ tự nào.

Bài này trình bày bốn kỹ thuật kèm code trước/sau, và quy tắc khi nào áp dụng.

1. Kỹ thuật 1 — duyệt theo thứ tự bộ nhớ

Quy tắc nền tảng: vòng lặp trong cùng nên chạy theo chiều dữ liệu nằm liền nhau. Đây là tối ưu rẻ nhất, đáng làm gần như luôn.

Với ma trận row-major, đặt chỉ số hàng ở vòng ngoài, cột ở vòng trong (đã thấy ở bài 02). Nhưng nguyên lý rộng hơn: bất cứ khi nào lồng vòng lặp trên dữ liệu nhiều chiều, sắp thứ tự để bước nhỏ nhất trong bộ nhớ nằm ở vòng trong cùng.

// Cong hai ma tran -- thu tu vong lap dung chieu row-major
for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)        // j chay theo chieu lien nhau
        c[i][j] = a[i][j] + b[i][j];

Phép nhân ma trận ngây thơ là ví dụ kinh điển: thứ tự vòng lặp i-j-k truy cập b[k][j] theo cột (xấu); đổi sang i-k-j khiến cả ba ma trận được duyệt thân thiện hơn:

// Ngay tho i-j-k: b[k][j] duyet theo cot -> nhieu miss
for (int i = 0; i < N; i++)
  for (int j = 0; j < N; j++)
    for (int k = 0; k < N; k++)
      c[i][j] += a[i][k] * b[k][j];

// Doi sang i-k-j: a[i][k] hang so trong vong j (temporal),
// b[k][j] va c[i][j] duyet tuan tu theo j (spatial) -> it miss
for (int i = 0; i < N; i++)
  for (int k = 0; k < N; k++)
    for (int j = 0; j < N; j++)
      c[i][j] += a[i][k] * b[k][j];

Chỉ đổi thứ tự hai vòng lặp — cùng kết quả, cùng số phép nhân — nhưng bản i-k-j thường nhanh hơn nhiều trên ma trận lớn.

2. Kỹ thuật 2 — loop blocking (tiling)

Khi một thuật toán duyệt qua dữ liệu lớn hơn cache nhiều lần (như nhân ma trận), dữ liệu nạp vào cache bị đẩy ra trước khi được dùng lại. Blocking chia bài toán thành các khối (tile) đủ nhỏ để vừa cache, xử lý trọn một khối trước khi sang khối khác — nhờ đó dữ liệu trong khối được tái dùng tối đa khi còn nóng.

// Nhan ma tran co blocking -- xu ly tung khoi B x B vua cache
int B = 64; // tile size, chinh theo cache
for (int ii = 0; ii < N; ii += B)
  for (int kk = 0; kk < N; kk += B)
    for (int jj = 0; jj < N; jj += B)
      // xu ly mot tile B x B -- du lieu trong tile o lai cache
      for (int i = ii; i < min(ii + B, N); i++)
        for (int k = kk; k < min(kk + B, N); k++)
          for (int j = jj; j < min(jj + B, N); j++)
            c[i][j] += a[i][k] * b[k][j];

Ý tưởng: thay vì quét cả một hàng dài rồi quay lại (dữ liệu đã bị đẩy khỏi cache), ta gói công việc thành ô vuông nhỏ. Mỗi ô vừa trong cache nên các phần tử của nó được tái dùng nhiều lần mà không phải nạp lại. Blocking là kỹ thuật chuẩn trong thư viện đại số tuyến tính hiệu năng cao (BLAS).

flowchart LR
  subgraph noblock["Khong blocking"]
    direction TB
    N1["Quet ca hang dai"] --> N2["Du lieu bi day khoi cache"] --> N3["Phai nap lai"]
  end
  subgraph block["Co blocking"]
    direction TB
    B1["Xu ly tile vua cache"] --> B2["Tai dung tron tile"] --> B3["Sang tile ke"]
  end

3. Kỹ thuật 3 — gói dữ liệu nóng lại gần nhau

Mỗi cache line là 64 byte. Nếu dữ liệu bạn thực sự dùng trong vòng lặp nóng nằm rải trong các object lớn, mỗi line kéo về nhiều byte vô ích. Hai cách gói:

Tách field nóng khỏi field nguội. Nếu một vòng lặp chỉ cần id và score của mỗi Player (object 200 byte), tách hai field đó ra một mảng riêng — mỗi line giờ chứa toàn id/score dùng được.

Chọn kiểu nhỏ hơn khi đủ. int (4 byte) thay vì long (8 byte) khi giá trị nhỏ → gấp đôi số phần tử mỗi cache line, gấp đôi mật độ dữ liệu hữu ích. short, byte, hoặc bảng index thay vì con trỏ 8 byte cũng theo nguyên lý này.

// SAI: vong lap chi dung 2 field nhung moi line keo ca object lon
class Player { long id; int score; String name; byte[] avatar; /* ... */ }
Player[] players;
for (Player p : players) leaderboard.add(p.id, p.score); // phi cache

// TOT: tach 2 field nong ra mang rieng -> moi line toan du lieu can
long[] ids;     // lien nhau
int[]  scores;  // lien nhau
for (int i = 0; i < n; i++) leaderboard.add(ids[i], scores[i]);

Đây chính là tiền đề cho AoS vs SoA ở bài 04 — tách field thành mảng riêng là dạng cơ bản của SoA.

4. Kỹ thuật 4 — tránh pointer chasing

"Pointer chasing" là duyệt dữ liệu bằng cách đi theo chuỗi con trỏ tới các địa chỉ rải rác: linked list, cây con trỏ, hash map chaining, đồ thị lưu bằng danh sách kề con trỏ. Mỗi bước là một cache miss khó tránh và vô hiệu hoá prefetcher (bài 02).

Linked list (rai rac tren heap): moi buoc nhay toi dia chi bat ky -> moi node 1 miss
  [node@0x100]--next-->[node@0x9C0]--next-->[node@0x2F0]--next-->[node@0x740]
       miss               miss                miss                miss

Mang (lien mach): phan tu lien nhau -> ~1 miss / 16 phan tu, prefetcher giup
  [a0 a1 a2 a3 ... a15][a16 ...]
   ^miss nap ca line    ^miss

Khi duyệt là thao tác nóng, ưu tiên cấu trúc liền mạch:

• Mảng / ArrayList thay vì LinkedList.
• Cây lưu trong mảng (như binary heap lưu mảng) thay vì cây con trỏ, khi cấu trúc cho phép.
• Hash map open-addressing (lưu entry liền trong mảng) thay vì chaining khi locality quan trọng.
• Đồ thị dạng CSR (compressed sparse row — mảng phẳng) thay vì danh sách kề con trỏ cho thuật toán duyệt nặng.

// CHAM: pointer chasing, moi node mot cache miss
for (Node n = head; n != null; n = n.next) sum += n.value;

// NHANH: mang lien mach, prefetcher giup, ~1 miss / 16 phan tu
for (int i = 0; i < arr.length; i++) sum += arr[i];

5. Áp dụng vào code của bạn

Gộp bốn kỹ thuật thành một quy trình ra quyết định:

1. Đo trước. Dùng profiler hoặc perf stat -e cache-misses,cache-references để xác nhận cache miss thực sự là bottleneck. Nếu hot path bị chặn bởi I/O hay tính toán thuần, tối ưu cache là sai chỗ.
2. Rẻ trước, đắt sau. Đổi thứ tự vòng lặp (kỹ thuật 1) gần như miễn phí về công sức — làm trước. Blocking và viết lại cấu trúc dữ liệu (2, 4) tốn hơn — chỉ khi cần.
3. Dữ liệu lớn hơn cache mới đáng. Mọi kỹ thuật này chỉ tạo khác biệt khi dữ liệu vượt cache (vượt vài MB). Với dữ liệu nhỏ, mọi thứ đã trong cache — đừng phức tạp hoá code.
4. Đo lại sau. Speedup phải chứng minh bằng số trước/sau, kèm số cache-miss giảm. Đây đúng quy trình measure → optimize → re-measure mà capstone sẽ thực hành.

6. Liên hệ các bài khác

• Bài 02 — Cache line và locality: cơ chế nền tảng — bốn kỹ thuật ở đây đều là cách khai thác có hệ thống spatial và temporal locality.
• Bài 04 — AoS vs SoA: kỹ thuật 3 (gói field nóng) được hệ thống hoá thành một quyết định bố cục dữ liệu lớn.
• Course 1 — Branch prediction: locality và branch prediction là hai trụ cột mechanical sympathy; capstone kết hợp cả hai.

7. Tóm tắt

• Bốn kỹ thuật cache-friendly, đều giữ nguyên thuật toán và big-O: duyệt theo thứ tự bộ nhớ, loop blocking, gói dữ liệu nóng, tránh pointer chasing.
• Duyệt theo thứ tự bộ nhớ: vòng lặp trong cùng đi theo chiều dữ liệu liền nhau — tối ưu rẻ nhất, đáng làm gần như luôn.
• Loop blocking: chia bài toán thành tile vừa cache để tái dùng dữ liệu khi còn nóng; chuẩn trong thư viện đại số tuyến tính.
• Gói dữ liệu nóng: tách field nóng ra mảng riêng, chọn kiểu nhỏ hơn khi đủ — tăng tỉ lệ dữ liệu hữu ích mỗi cache line.
• Tránh pointer chasing: ưu tiên cấu trúc liền mạch (mảng) hơn con trỏ rải rác (linked list) khi duyệt là thao tác nóng.
• Quy trình: đo trước → rẻ trước đắt sau → chỉ đáng khi dữ liệu lớn hơn cache → đo lại để chứng minh.

8. Tự kiểm tra

Bài tiếp theo: AoS vs SoA — bố cục dữ liệu theo cache