Module 2 — Tổng kết & cheat sheet

TL;DR: Module 2 bóc tách vì sao truy cập dữ liệu nhanh hay chậm quyết định hiệu năng nhiều khi hơn cả thuật toán. CPU nhanh hơn RAM ~100 lần, nên có memory hierarchy; cache lấy dữ liệu theo cache line 64 byte, thưởng code có locality; bố cục dữ liệu (AoS vs SoA) và sắp xếp field (false sharing) ảnh hưởng lớn tới số cache miss. Đây là một trang để bookmark.

Đã đi qua những gì

Bạn bắt đầu từ bức tranh lớn: CPU và RAM lệch tốc độ hàng trăm lần, nên máy tính xếp tầng bộ nhớ và bạn cần thuộc thang độ trễ để ước lượng. Rồi vào cơ chế: cache không lấy từng byte mà cả cache line 64 byte, nên code truy cập gần nhau (locality) được thưởng — đây là lý do mảng đánh bại linked list và duyệt theo hàng nhanh hơn theo cột. Bạn biến nó thành kỹ năng qua bốn kỹ thuật cache-friendly, rồi nâng lên mức thiết kế dữ liệu với AoS vs SoA. Cuối cùng, mặt trái trong đa luồng: false sharing — hai luồng vô tình tranh một cache line. Toàn bộ module là một sự thật vật lý (cache line 64 byte) nhìn từ nhiều góc.

mindmap
  root(("Cache va<br/>hierarchy"))
    Hierarchy
      CPU nhanh hon RAM ~100 lan
      Thang do tre L1 L2 L3 RAM SSD
      Big-O bo qua tang bo nho
    Cache line
      Nap 64 byte moi lan
      Spatial va temporal locality
      Mang thang linked list
    Cache-friendly
      Duyet theo thu tu bo nho
      Loop blocking
      Tranh pointer chasing
    Bo cuc du lieu
      AoS vs SoA
      SoA mo duong SIMD
      False sharing da luong

🗺️ Cheat sheet

📖 Glossary module

⚠️ Pitfall tổng hợp

1. Tin big-O, quên tầng bộ nhớ:

O(n) truy cap ngau nhien (moi buoc ~100ns RAM)
co the cham hon O(n log n) truy cap tuan tu (~1ns L1)

2. Duyệt ma trận sai chiều:

for (col...) for (row...) sum += m[row][col];  // SAI: theo cot
for (row...) for (col...) sum += m[row][col];  // DUNG: theo hang

3. Dùng cấu trúc con trỏ rải rác ở hot loop:

for (Node n = head; n != null; n = n.next) ... // SAI: pointer chasing
for (int i = 0; i < arr.length; i++) ...        // DUNG: lien mach

4. AoS khi vòng lặp chỉ dùng vài field:

for (Player p : players) leaderboard.add(p.id, p.score); // phi cache
// DUNG: SoA -> long[] ids; int[] scores;

5. Biến per-thread liền nhau → false sharing:

long[] counters = new long[8];   // SAI: 8 counter trong 1 line
// DUNG: tich luy cuc bo roi gop, hoac padding ra 64 byte

✅ Self-assessment

Bạn đã đạt module này nếu trả lời được:

• Explain được vì sao có memory hierarchy và ghi nhớ thang độ trễ L1/L2/L3/RAM/SSD/mạng.
  • Nếu chưa: đọc lại bài 01 mục 2–3.
• Explain được cache line và locality (temporal, spatial), dự đoán khi nào code gây cache miss.
  • Nếu chưa: đọc lại bài 02 mục 2–3.
• Refactor được một vòng lặp hoặc cấu trúc dữ liệu để tăng locality và giảm cache miss.
  • Nếu chưa: đọc lại bài 03 mục 1–4.
• Compare được bố cục AoS vs SoA và chẩn đoán false sharing trong code đa luồng.
  • Nếu chưa: đọc lại bài 04 và bài 05.

🚀 What's next

Module 3 — Bộ nhớ ảo — trả lời câu hỏi bạn có thể đã thắc mắc suốt module này: khi nói "địa chỉ", đó là địa chỉ thật trên thanh RAM, hay một thứ khác? Hoá ra mỗi tiến trình thấy một không gian địa chỉ ảo của riêng nó, và phần cứng cùng OS dịch nó sang địa chỉ vật lý sau lưng. Bạn sẽ học paging, page table, TLB, page fault — cơ chế cho phép nhiều chương trình chạy cách ly, dùng nhiều bộ nhớ hơn RAM thật, và là nền của swap, mmap, copy-on-write.

Bài tiếp theo: Module 3 — Bộ nhớ ảo: tổng quan

📚 Tài liệu mở rộng

• Tài liệu: What Every Programmer Should Know About Memory (Ulrich Drepper) — chương về cache và NUMA là kinh điển cho cả module này.
• Bài viết: Latency Numbers Every Programmer Should Know (Jeff Dean) — nguồn gốc của thang độ trễ ở bài 01.
• Talk: "Data-Oriented Design and C++" (Mike Acton, CppCon 2014) — bài nói nền tảng về DOD và AoS/SoA, đặc biệt cho game/hệ thống hiệu năng cao.
• Thực hành: chạy một benchmark duyệt mảng vs linked list, và row-major vs column-major, đo bằng perf stat -e cache-misses để thấy tận mắt mọi điều module này mô tả.