Mỗi Byte đều Quan trọng: Tối ưu hóa hiệu năng nhờ hiểu rõ Cache CPU

Tôi đã dành phần lớn sự nghiệp của mình để làm việc với Java. Trong khoảng thời gian đó, bạn sẽ quen với những lớp (class) khổng lồ. Cần thêm chức năng mới? Chỉ cần thêm một phương thức và trường mới vào lớp đó.

Chi phí của mỗi trường mới hiếm khi được xem xét. Hiệu năng thường được xem xét từ góc độ khoa học máy tính cổ điển thông qua việc phân tích tiệm cận của các thuật toán và cấu trúc dữ liệu đang sử dụng.

Nhưng thực tế là, ngay cả trong cùng một mức tăng trưởng của thuật toán, chẳng hạn như một vòng lặp đơn giản O(N), thời gian thực thi vẫn có thể thay đổi mạnh mẽ nếu chúng ta hiểu sâu hơn một chút về phần cứng bên dưới.

Trước hết, hãy hiểu về máy tính hiện tại của chúng ta. Hãy cùng nhìn vào kích thước dòng cache (cache line) và kích thước trang.

$ lscpu | grep -i cache
L1d cache:    352 KiB (10 instances)
L1i cache:    640 KiB (10 instances)
L2 cache:     10 MiB (5 instances)
L3 cache:     12 MiB (1 instance)
$ getconf LEVEL1_DCACHE_LINESIZE
64

Số lượng instances phản ánh cách các cache được chia sẻ giữa các CPU. Nếu tôi có 10 CPU, mỗi CPU có cache L1d riêng, trong khi hai trong số đó sẽ chia sẻ cache L2.

Kích thước dòng cache của chúng ta là 64 byte.

┌─────────────────────────────────────────────┐
│                 64 bytes                    │
│  byte 0   byte 1   byte 2   ...  byte 63    │
└─────────────────────────────────────────────┘

Khi bạn đọc một byte duy nhất từ bộ nhớ, phần cứng sẽ lấp đầy 64 byte xung quanh vào dòng cache. Ý tưởng là dữ liệu thường có tính cục bộ về không gian và thời gian, nghĩa là dữ liệu thường được truy cập gần nhau và gần nhau về thời gian.

Chúng ta có thể tham khảo bảng "Latency numbers every programmer should know" (Các con số độ trễ mọi lập trình viên nên biết) nổi tiếng của Jeff Dean, nhưng dưới đây là tóm tắt nhanh với các giá trị từ máy cụ thể của chúng ta:

• Registers (Thanh ghi): < 1 ns
• L1d Cache: ~35 KiB/core, ~4-5 chu kỳ, ~1-2 ns (~560 dòng cache)
• L2 Cache: ~2 MiB/core-pair, ~12-15 chu kỳ, ~4-5 ns (~32.000 dòng cache)
• L3 Cache: 12 MiB chia sẻ, ~30-40 chu kỳ, ~10-15 ns (~196.000 dòng cache)
• DRAM: ~100-200 chu kỳ, ~60-100 ns

Kích thước của mỗi cache là con số trả về bởi lscpu chia cho số lượng core hoặc instances; ví dụ: 352 KiB ÷ 10 instances = ~35 KiB. Sau đó, chúng ta xác định số lượng dòng cache bằng cách chia con số này cho 64; ví dụ: 35 KiB ÷ 64 bytes = 560 dòng cache.

Vậy điều này có ý nghĩa gì?

Hãy xem xét một ví dụ nơi chúng ta muốn lặp qua một cấu trúc Monster duy nhất và lấy ra giá trị boolean is_alive để lọc chúng.

Chúng ta tạo cấu trúc của mình, và trong ví dụ cụ thể này, chúng ta cần 64 byte để đại diện cho một Monster.

struct Monster {
    uint32_t id;          // 4 bytes
    float    x, y, z;     // 12 bytes
    float    vx, vy, vz;  // 12 bytes
    int32_t  hp;          // 4 bytes
    int32_t  attack;      // 4 bytes
    int32_t  defense;     // 4 bytes
    uint8_t  is_alive;    // 1 byte
    uint8_t  team;        // 1 byte
    char     name[22];    // 22 bytes
};                        // tổng: 64 bytes

Nếu chúng ta có một mảng các Monster và lặp qua chúng, dòng cache sẽ được lấp đầy như sau. Mỗi dòng cache sẽ chứa một con quái vật duy nhất, và chúng ta chỉ lấy ra byte is_alive.

Đây thường được gọi là "Array of Structs" (Mảng của Cấu trúc).

So sánh Array of Structs và Struct of Arrays

Nếu thay vào đó, chúng ta chuẩn hóa dữ liệu sao cho mỗi trường nằm trong danh sách riêng của nó, chúng ta có thể đóng gói các dòng cache chặt chẽ hơn nhiều.

// Bố cục SoA
struct Monsters {
    uint32_t *ids;
    float    *xs, *ys, *zs;
    float    *vxs, *vys, *vzs;
    int32_t  *hps;
    int32_t  *attacks;
    int32_t  *defenses;
    uint8_t  *is_alives;    // đóng gói liên tục
    uint8_t  *teams;
    char     (*names)[22];
};

Loại bố cục này được gọi là "Struct of Arrays" (Cấu trúc của Mảng). Trong một lần lấy dữ liệu (fetch), chúng ta có thể lấy được trạng thái của 64 con quái vật.

Việc này có tác động lớn như thế nào?

Chúng ta có thể quan sát thấy sự cải thiện lên tới 30 lần khi cấu trúc Monster là 1KiB. Sự chênh lệch này ít quan sát thấy hơn khi cấu trúc nhỏ vì nhiều cấu trúc Monster vẫn có thể được lấy trong một dòng cache duy nhất.

Tuy nhiên, mô hình truy cập dữ liệu này cực kỳ nóng. Bộ nạp trước (prefetcher) của CPU biết rằng nó đang đi tuần tự và sẽ lấy dòng cache tiếp theo trước khi bạn cần nó. Bạn thực sự không bao giờ phải đợi bộ nhớ được lấy.

Vậy còn các mẫu truy cập ngẫu nhiên thì sao?

Không phải tất cả các mẫu truy cập đều tuần tự. Bản đồ băm (hash maps), cây, duyệt đồ thị và các cấu trúc dữ liệu nặng về con trỏ sẽ nhảy đến các vị trí không thể đoán trước. CPU không thể nạp trước những gì nó không thể dự đoán. Với truy cập ngẫu nhiên, CPU cần toàn bộ mảng phải có mặt trong cache để tránh các độ trễ do tra cứu bộ nhớ.

Điều này có nghĩa là tổng kích thước của bộ dữ liệu làm việc (working set) của bạn sẽ quyết định tầng hiệu năng của bạn.

Việc tăng gấp đôi cấu trúc từ 64B lên 128B sẽ làm tăng gấp đôi bộ dữ liệu làm việc cho cùng số lượng quái vật, đẩy dữ liệu vào các cấp độ cache chậm hơn. Chỉ với 512 con quái vật, cấu trúc 64B vừa khít trong L1d với độ trễ ~3 ns — nhưng cấu trúc 128B đã tràn sang L2 với độ trễ ~11 ns.

Chúng ta có thể quan sát điều này thông qua điểm chuẩn truy cập con trỏ (pointer-chasing). Chúng ta cấp phát N nút kích thước quái vật, nối chúng theo một thứ tự ngẫu nhiên và truy theo các con trỏ. Mỗi bước nhảy sẽ rơi vào một địa chỉ không thể đoán trước, đánh bại hoàn toàn bộ nạp trước của CPU.

Thay vì vẽ biểu đồ theo tỷ lệ log, mà tôi thấy đôi khi dễ bỏ sót, tôi đã bao gồm một biểu đồ phóng to. Chúng ta có thể thấy rằng tất cả các kích thước cấu trúc đều đạt cùng một mẫu hình dạng cầu thang khi chúng đi qua các cấp độ cache khác nhau, tuy nhiên các kích thước cấu trúc lớn hơn bị dịch sang trái, nghĩa là chúng gặp sự tăng độ trễ sớm hơn.

Điều này có nghĩa là với các mẫu truy cập ngẫu nhiên, nếu bạn có thể kiểm soát chặt chẽ tổng kích thước bộ dữ liệu làm việc, bạn có thể ảnh hưởng đáng kể đến thời gian xử lý.

Biểu đồ độ trễ theo kích thước bộ dữ liệu

Việc biết kích thước cấu trúc và bộ dữ liệu làm việc của mình có thể tạo ra sự khác biệt rất lớn.