Module 2 — Cache & memory hierarchy: tổng quan

TL;DR: CPU hiện đại chạy vài tỉ lệnh mỗi giây, nhưng đọc một byte từ RAM tốn ~100 nanosecond — đủ lâu để CPU lẽ ra làm được vài trăm lệnh. Nếu CPU phải chờ RAM cho mỗi lần truy cập, nó sẽ nghỉ phần lớn thời gian. Cache là các lớp bộ nhớ nhỏ, cực nhanh, nằm sát CPU, giữ bản sao dữ liệu hay dùng. Hiệu quả của cache phụ thuộc vào locality — code truy cập dữ liệu gần nhau và lặp lại. Module này dạy bạn vì sao có nhiều lớp bộ nhớ (memory hierarchy), những con số độ trễ nên nhớ, cache hoạt động theo cache line thế nào, và làm sao bố trí dữ liệu để code nhanh gấp nhiều lần mà không đổi độ phức tạp big-O.

Vì sao module này tồn tại

Bạn có hai vòng lặp làm cùng một việc — cộng tất cả phần tử của một ma trận — chỉ khác thứ tự duyệt (theo hàng vs theo cột). Cùng số phép tính, cùng O(n²), nhưng một bản chạy nhanh gấp 5–10 lần. Bạn có hai cách lưu danh sách điểm 3D — một mảng các struct vs ba mảng toạ độ — và một cách xử lý nhanh gấp đôi. Khác biệt không nằm ở thuật toán, mà ở cách dữ liệu nằm trong bộ nhớ và cách CPU lấy nó qua cache.

Module 1 dạy dữ liệu sống ở đâu (stack/heap/static). Module này dạy việc truy cập dữ liệu nhanh hay chậm — và đó thường là yếu tố quyết định hiệu năng thực tế hơn cả thuật toán, một khi big-O đã hợp lý.

Sau module này bạn sẽ

• Explain vì sao tồn tại memory hierarchy (thanh ghi → L1 → L2 → L3 → RAM → SSD → mạng) và ghi nhớ thang độ trễ tương đối giữa các lớp.
• Explain cache line và hai loại locality (temporal, spatial), và dự đoán khi nào một đoạn code gây nhiều cache miss.
• Refactor một vòng lặp hoặc cấu trúc dữ liệu để tăng locality và giảm cache miss, đo cải thiện.
• Compare bố cục AoS (array of structs) vs SoA (struct of arrays) và chẩn đoán false sharing trong code đa luồng.

Lộ trình module

Bài 01 đặt bức tranh lớn: vì sao một máy tính cần nhiều lớp bộ nhớ với tốc độ và dung lượng khác nhau, kèm "những con số độ trễ mọi lập trình viên nên nhớ". Bài 02 đi vào cơ chế: cache làm việc theo cache line (khối 64 byte), và vì sao locality quyết định cache hit hay miss. Bài 03 biến lý thuyết thành kỹ năng: cách viết vòng lặp và bố trí dữ liệu thân thiện cache. Bài 04 áp dụng vào thiết kế dữ liệu: AoS vs SoA, một quyết định bố cục ảnh hưởng lớn tới throughput. Bài 05 chạm tới đa luồng: false sharing — khi hai luồng vô tình tranh cùng một cache line — và liên hệ cache coherence. Bài 06 là cheat sheet tổng kết.

flowchart LR
  A["01 Hierarchy + do tre"] --> B["02 Cache line + locality"]
  B --> C["03 Code cache-friendly"]
  C --> D["04 AoS vs SoA"]
  D --> E["05 False sharing"]

Yêu cầu trước khi bắt đầu

• Hoàn thành Module 1 của course này (stack/heap, con trỏ, bố cục bộ nhớ) — module này xây trực tiếp trên đó.
• Nắm cơ bản về CPU và bộ nhớ từ Course 1 (RAM, lệnh máy, pipeline) sẽ giúp hiểu sâu hơn nhưng không bắt buộc.

Time budget

• Module: ~1.6 giờ đọc.

Cách học module này hiệu quả

• Đo, đừng tin lời. Mỗi kỹ thuật trong module đều kiểm chứng được bằng một benchmark nhỏ. Tự chạy hai phiên bản (cache-friendly vs không) và xem số — cảm giác "nhanh hơn" sẽ thành con số cụ thể.
• Nhớ thang độ trễ tương đối, không phải số tuyệt đối. "L1 nhanh hơn RAM ~100 lần" hữu ích để ước lượng nhanh; con số nanosecond chính xác thay đổi theo chip.
• Đừng bỏ qua khối "Áp dụng vào code của bạn" — đây là module mà mechanical sympathy cho lợi ích đo được rõ nhất.

Bài tiếp theo: Vì sao có cache & những con số độ trễ