Phần 8 cho thấy nhảy nhân làm chậm gấp đôi khi tập làm việc vừa bộ nhớ đệm. Bài này đo thẳng cái đang bị mất: một lần trượt bộ nhớ đệm tốn bao nhiêu.
Cầu thang
Chương trình đo dùng con trỏ nối đuôi: mỗi ô nhớ chứa địa chỉ ô tiếp theo, xáo trộn ngẫu nhiên. Đọc ô sau bắt buộc phải đọc xong ô trước — CPU không có cách nào chạy trước.
for (i = 0; i < steps; i++) p = a[p];
Ghim vào nhân 3, quét kích thước mảng:
| Tập làm việc | ns mỗi truy cập | Nằm ở đâu |
|---|---|---|
| 16 KB | 1,46 | L1 |
| 32 KB | 1,44 | L1 |
| 64 KB | 1,44 | L1 |
| 256 KB | 5,64 | L2 |
| 1 MB | 8,06 | L3 |
| 4 MB | 9,55 | L3 |
| 16 MB | 25,81 | rìa L3 |
| 64 MB | 115,41 | RAM |
| 256 MB | 156,27 | RAM |
108 lần giữa hai đầu bảng. Không đổi dòng mã nào, chỉ đổi kích thước mảng.
Bậc thang cho biết cấu hình phần cứng mà không cần tra tài liệu: L1 khoảng 64 KB (bậc đầu tiên gãy sau 64 KB), L2 vài trăm KB, L3 vài megabyte.
Rồi con số 156 ns hoá ra là con số của trường hợp xấu nhất
Tôi tưởng 156 ns là "giá của RAM". Phép đo thứ hai cho thấy không phải.
Chương trình thứ hai quét 256 MB với bước nhảy 4096 byte — vẫn trượt bộ nhớ đệm ở mọi lần đọc, nhưng các lần đọc độc lập với nhau: địa chỉ tính được ngay, không cần chờ kết quả lần trước.
for (i = 0; i < n; i += 4096) sum += a[i];
Đo ba lần, cạnh nhau:
| Lần | Nối đuôi (phụ thuộc) | Bước nhảy (độc lập) |
|---|---|---|
| 1 | 154,39 ns | 5,14 ns |
| 2 | 151,38 ns | 5,68 ns |
| 3 | 149,97 ns | 5,05 ns |
Cùng dung lượng, cùng kiểu trượt, chênh 28 lần.
Lý do: CPU hiện đại giữ được hàng chục yêu cầu bộ nhớ cùng lúc. Khi biết trước các địa chỉ, nó phát hết một lượt và chờ chung — 30 lần chờ 150 ns chồng lên nhau thành 150 ns, không phải 4500 ns. Khi mỗi địa chỉ phụ thuộc lần đọc trước, nó buộc phải xếp hàng dọc.
Đây mới là bài học đáng nhớ, không phải con số 156 ns.
Nghĩa là tối ưu bộ nhớ đệm không phải chuyện đọc ít đi
Nói lại lần thứ hai, vì nó ngược với trực giác: giảm số lần đọc không giúp gì mấy; làm cho các lần đọc độc lập với nhau giúp tới 28 lần.
Cụ thể trong mã nguồn thật:
| Chậm | Nhanh |
|---|---|
| Danh sách liên kết, cây con trỏ | Mảng liên tục |
| Mảng con trỏ tới đối tượng rời rạc | Mảng đối tượng đặt liền nhau |
for (n = head; n; n = n->next) |
for (i = 0; i < len; i++) |
| Băm rồi nhảy theo con trỏ | Băm mở địa chỉ, dò tuyến tính |
Một std::vector<Item> và một std::vector<Item*> chứa cùng dữ liệu có thể chênh nhau một bậc độ lớn khi duyệt, và không profiler nào chỉ thẳng vào dòng khai báo đó.
Dòng bộ nhớ đệm là 64 byte
Phép đo thứ ba: cùng 256 MB, đổi bước nhảy.
| Bước nhảy | Ô chạm | ns mỗi ô |
|---|---|---|
| 4 B | 268.435.456 | 1,37 |
| 8 B | 134.217.728 | 1,41 |
| 16 B | 67.108.864 | 1,45 |
| 32 B | 33.554.432 | 1,45 |
| 64 B | 16.777.216 | 1,56 |
| 128 B | 8.388.608 | 4,36 |
| 256 B | 4.194.304 | 4,53 |
| 4096 B | 262.144 | 4,95 |
Từ bước 4 tới bước 64, giá mỗi ô gần như không đổi. Nghĩa là 16 lần đọc trong cùng một dòng 64 byte rẻ gần bằng một lần: dòng đã được nạp về, 15 lần sau chỉ là đọc từ L1.
Từ bước 128 trở đi giá mỗi ô nhảy gấp ba, vì mỗi lần chạm là một dòng mới và bộ nạp trước không còn bám kịp.
Hệ quả thực dụng: nhét các trường hay dùng chung vào cùng 64 byte là miễn phí. Ngược lại, tách chúng ra xa nhau là trả tiền thật.
Một sai lầm tôi mắc khi đo
Bảng bước nhảy ở lần chạy đầu ra thế này:
4 B | 268435456 | 0.063 s | 0.24
4096 B | 262144 | 0.000 s | 0.22
0,063 giây cho 1 GB đọc từ RAM là 63 GB/s — nhanh hơn băng thông bộ nhớ của máy. Con số không thể đúng, và đó là dấu hiệu duy nhất.
Nguyên nhân: biến sum cộng dồn rồi không dùng tới, nên trình biên dịch bỏ luôn vòng lặp. Sửa bằng cách khai volatile long sum để mỗi phép cộng buộc phải xảy ra. Con số nhảy từ 0,24 lên 1,37 ns — gấp gần 6 lần.
Bài học: mọi phép đo hiệu năng viết bằng C ở mức -O2 phải có một cách buộc kết quả được dùng. Và cách phát hiện tốt nhất vẫn là so với giới hạn vật lý.
Xem cấu hình bộ nhớ đệm thật
lscpu | grep -i cache
cat /sys/devices/system/cpu/cpu0/cache/index*/size
Trong container tôi đo, các tệp size này rỗng — nhân của Docker Desktop không phơi ra. Nên bảng cầu thang ở trên là cách duy nhất tôi biết được ranh giới, và nó cũng là cách đáng tin hơn: nó đo cái CPU thực sự làm, không đọc cái nó khai.
Thử ba mươi giây
Chạy đúng phép đo đơn giản nhất trên máy bạn:
cat > /tmp/c.c <<'EOF'
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int main(int c,char**v){
size_t kb=atol(v[1]), n=kb*1024/8, st=8, m=n/st;
size_t *a=malloc(n*8), *ix=malloc(m*8);
for(size_t i=0;i<m;i++) ix[i]=i;
srandom(1);
for(size_t i=m-1;i>0;i--){size_t j=random()%(i+1),t=ix[i];ix[i]=ix[j];ix[j]=t;}
for(size_t i=0;i<m;i++) a[ix[i]*st]=ix[(i+1)%m]*st;
size_t p=0; struct timespec t0,t1;
for(size_t i=0;i<m*4;i++) p=a[p];
clock_gettime(CLOCK_MONOTONIC,&t0);
for(size_t i=0;i<20000000;i++) p=a[p];
clock_gettime(CLOCK_MONOTONIC,&t1);
printf("%6zu KB %6.2f ns (p=%zu)\n",kb,
((t1.tv_sec-t0.tv_sec)+(t1.tv_nsec-t0.tv_nsec)/1e9)/20000000*1e9,p);
return 0;
}
EOF
cc -O2 -o /tmp/c /tmp/c.c
for k in 16 256 4096 262144; do taskset -c 1 /tmp/c $k; done
Bốn dòng ra sẽ cho bạn L1, L2, L3 và RAM của chính máy mình. Nếu dòng cuối không lớn hơn dòng đầu ít nhất 50 lần, hãy kiểm lại xem trình biên dịch có bỏ vòng lặp không.
Phần sau: bộ nhớ ảo và trang — đo page fault nhẹ và page fault nặng.
