Cùng một lần đọc RAM tốn 156 ns hoặc 5 ns — chênh 28 lần chỉ tuỳ vào việc CPU có đoán được địa chỉ tiếp theo hay không; tối ưu bộ nhớ đệm không phải đọc ít đi

Hình dung bạn cần lấy ba mươi cuốn sách từ một thư viện lớn. Cách thứ nhất: bạn đưa cả danh sách ba mươi tên một lúc, nhân viên đi gom hết rồi mang ra trong một chuyến — bạn chỉ chờ đúng một lần dù có ba mươi cuốn. Cách thứ hai: mỗi cuốn sách chứa mẩu giấy ghi tên cuốn tiếp theo, nên bạn phải đọc xong cuốn này mới biết đi tìm cuốn nào — ba mươi chuyến đi, ba mươi lần chờ nối tiếp. Cùng ba mươi cuốn, cùng quãng đường mỗi chuyến, nhưng tổng thời gian chênh nhau một trời một vực. CPU truy cập bộ nhớ đúng theo hai cách đó, và bài này đo xem khác biệt lớn tới mức nào — cùng lý do vì sao "tối ưu cache" không phải là đọc ít đi.

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. Ở đây tôi đ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:

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:

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. Đó là đưa cả danh sách sách một lúc. Khi mỗi địa chỉ phụ thuộc lần đọc trước, nó buộc phải xếp hàng dọc — đọc từng cuốn mới biết cuốn kế. Đâ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 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:

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.

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.

Mẫu số chung: hình dạng dữ liệu quyết định hiệu năng nhiều hơn số phép tính

Bài học lớn nhất ở đây — độ độc lập giữa các lần truy cập quan trọng hơn số lượng truy cập — quy về một sự thật rộng hơn: ở phần cứng có song song ẩn (CPU, đĩa, mạng), hình dạng và cách bố trí dữ liệu quyết định hiệu năng nhiều hơn số phép tính bạn thực hiện. Và trình tối ưu không sửa được hình dạng đó cho bạn.

Trong thế giới Java, đây đúng là lý do một int[] duyệt nhanh hơn hẳn một ArrayList<Integer> hay LinkedList<Integer> chứa cùng số phần tử: mảng nguyên thuỷ nằm liền khối, còn danh sách các Integer là mảng con trỏ tới object rải rác trên heap — mỗi bước là một cú nhảy con trỏ, đúng "đọc từng cuốn mới biết cuốn kế". Đây cũng là điều Project Valhalla (value types) sinh ra để chữa, và là lý do người ta chọn mảng cột (columnar) cho tính toán nóng.

Trong Go, cùng chuyện với []Item so với []*Item: slice của struct giá trị nằm liền nhau và duyệt tuần tự, slice của con trỏ thì mỗi phần tử là một lần nhảy vào heap; chọn kiểu phần tử là chọn cách bố trí bộ nhớ, và nó cân nặng hơn nhiều tinh chỉnh thuật toán.

Còn ở cơ sở dữ liệu, đây là toàn bộ lý do tồn tại của kho cột (columnar): quét một cột trong bảng row-store phải nhảy qua từng hàng (phụ thuộc, rải rác), còn column-store đặt cả cột liền khối nên quét tuần tự và song song hoá được — cùng số dòng, chênh một bậc độ lớn; và index clustered so với non-clustered là đúng đánh đổi "liền khối vs nhảy con trỏ" ở tầng đĩa.

Mẫu số chung: trên phần cứng có song song ẩn, cái quyết định tốc độ không phải bạn làm bao nhiêu phép mà là các phép đó có độc lập và liền kề để chạy song song hay buộc phụ thuộc và rải rác thành xếp hàng dọc — và điều đó do cách bố trí dữ liệu quyết định, không do thuật toán; trình biên dịch/tối ưu gần như không sửa được. Nên khi một vòng lặp nóng chậm bất ngờ mà số phép tính đã tối thiểu, câu hỏi đúng không phải "làm sao tính ít đi" mà là "dữ liệu của tôi nằm liền khối hay là một rừng con trỏ, và các lần truy cập có phụ thuộc nhau bắt phần cứng xếp hàng dọc không".

Muốn tự 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.