Khi một vòng lặp chậm bất thường, câu hỏi vàng là "chậm vì sao?" — nghẽn ở bộ nhớ (cache miss) hay ở đoán nhánh (branch misprediction)? CPU có sẵn các bộ đếm hiệu năng phần cứng (PMU) đếm chính xác những sự kiện đó, và perf stat đọc chúng ra. Bài này định dùng perf để đo cache-miss và branch-miss của hai vòng lặp — nhưng chính phép đo lại vấp một bức tường môi trường, biến nó thành gương lật hoàn hảo của bài chi phí strace.
PMU và perf
Mỗi CPU hiện đại có một PMU (Performance Monitoring Unit) — một bộ đếm phần cứng đếm các sự kiện vi kiến trúc: số lệnh thực thi, số chu kỳ, số lần trượt cache (cache-miss), số lần đoán nhánh sai (branch-miss), và nhiều nữa. Đây là cửa sổ duy nhất nhìn thấy được vì sao một đoạn code chậm ở tầng phần cứng — thời gian nói "chậm", nhưng chỉ bộ đếm mới nói "chậm vì trượt cache" hay "chậm vì đoán nhánh sai".
perf stat <lệnh> chạy chương trình rồi in ra các bộ đếm đó. Nghe hoàn hảo. Nhưng có một điều kiện tiên quyết mà tôi đã bỏ qua: PMU là phần cứng vật lý, và trong môi trường ảo hóa, hypervisor phải lộ nó ra máy khách thì guest mới đọc được. Nhiều máy ảo — kể cả máy ảo Docker chạy trên chip Apple — không lộ PMU. Đó là lúc phép đo của tôi vỡ.
Đo: bộ đếm phần cứng "không hỗ trợ", phải quay về đồng hồ
Việc đầu tiên tôi làm là thử perf với các sự kiện phần cứng:
perf stat -e cache-misses,branch-misses,instructions <lệnh>
<not supported> cache-misses
<not supported> branch-misses
<not supported> instructions
Mọi bộ đếm phần cứng đều báo <not supported>. Máy ảo này không lộ PMU, nên perf không đọc được gì. May là các bộ đếm phần mềm (do nhân tự đếm, không cần PMU) vẫn chạy: task-clock, page-faults, context-switches đều cho số thật. Nhưng đúng hai thứ tôi cần — cache-miss và branch-miss — thì không.
Không đo trực tiếp được nguyên nhân, tôi quay về thứ luôn hoạt động: đồng hồ. Tôi dựng hai thí nghiệm mà hiệu ứng lộ ra qua thời gian. Thứ nhất, cache: duyệt một mảng 64 MB (lớn hơn cache) theo hai kiểu — tuần tự (thân thiện prefetch) và ngẫu nhiên (pointer-chase, trượt cache liên tục):
tuần tự: 0,4 ns / mỗi truy cập
ngẫu nhiên: 82,9 ns / mỗi truy cập (chậm hơn ~200 lần)
Cùng số lần truy cập, cùng dữ liệu, chỉ khác thứ tự — và chậm gấp 200 lần. Tôi không cần bộ đếm cache-miss để biết đây là hiệu ứng cache; đồng hồ nói quá rõ.
Thí nghiệm thứ hai, đoán nhánh, là demo kinh điển "mảng sắp xếp chạy nhanh hơn": một vòng lặp if (a[i] >= 128) sum += a[i] chạy trên mảng đã sắp xếp so với mảng ngẫu nhiên. Nhưng kết quả làm tôi ngớ ra.
Một lần tôi đo hớ: bộ đếm không có, và cả demo cũng biến mất
Kết quả demo đoán nhánh với -O2 thông thường:
sắp xếp: 0,187 s ngẫu nhiên: 0,189 s (KHÔNG khác gì!)
Demo nổi tiếng — được cho là chênh 3-6 lần — ở đây không chênh chút nào. Và đây là lúc sự vắng mặt của bộ đếm phần cứng cắn tôi: nếu perf đo được branch-miss, tôi đã thấy ngay "cả hai đều ít mispredict" và hiểu chuyện. Nhưng branch-miss <not supported>, nên tôi mù. Phải phân rã assembly ra mới thấy: trình biên dịch -O2 trên ARM đã biến câu if thành một lệnh chọn có điều kiện (csel) — branchless, không còn nhánh nào để mà đoán sai (đếm được: csel=1, b.cond=0 trong hàm). Không có nhánh thì không có mispredict, nên sắp xếp hay không cũng như nhau.
Khi tôi ép trình biên dịch giữ nhánh thật (-fno-if-conversion), demo mới hiện:
ngẫu nhiên: 0,745 s sắp xếp: 0,527 s (~1,4× — đoán nhánh có thật)
Bài học đo lường có hai tầng, và cả hai đều là chủ đề của sê-ri. Tầng một, đây là gương lật của bài chi phí strace: ở đó tôi nói "tin bộ đếm, đừng tin đồng hồ" (vì strace bóp méo thời gian); ở đây thì ngược lại — bộ đếm phần cứng không tồn tại trong môi trường ảo, nên phải quay về đồng hồ, và may là đồng hồ vẫn lộ rõ hiệu ứng cache. Bộ đếm phần cứng là một năng lực phần cứng, không phải lúc nào cũng có — một biến môi trường khổng lồ mà nhiều người không lường. Tầng hai: trình biên dịch và kiến trúc có thể xóa mất chính hiện tượng bạn định đo. Demo "mảng sắp xếp nhanh hơn" là chuyện của một thời và một kiến trúc; trên ARM với -O2, nó bốc hơi vì compiler dùng branchless. Đừng bê demo x86 sang ARM, và luôn kiểm assembly khi một hiệu ứng "biến mất".
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên là muốn tối ưu vi kiến trúc thì phải đo được PMU — kiểm môi trường trước. Nếu bạn định dùng perf để săn cache-miss hay branch-miss, hãy chạy perf stat -e cache-misses true trước xem có ra số hay <not supported>. Trong container/VM (cloud, Docker Desktop, nhiều CI), PMU thường bị khóa; muốn đo thật phải chạy trên máy vật lý (bare metal) hoặc bật PMU pass-through cho máy ảo. Đo hiệu năng vi kiến trúc trên một VM không có PMU là đo một thứ không tồn tại.
Hệ quả thứ hai là cache và đoán nhánh là hai nguồn chậm lớn mà thời gian tính toán "trên giấy" không thấy. Hai vòng lặp cùng số phép tính có thể chênh nhau hàng trăm lần chỉ vì kiểu truy cập bộ nhớ (như đo được: 0,4 so với 82,9 ns). Khi tối ưu đường nóng, bố cục dữ liệu để truy cập tuần tự (thân thiện cache) thường quan trọng hơn giảm số phép tính. Còn đoán nhánh thì thường để compiler lo (nó tự branchless hóa khi có lợi), nhưng biết nó tồn tại giúp hiểu vì sao code "nhánh khó đoán" đôi khi chậm.
Hệ quả thứ ba, khép lại mạch đo lường: mỗi công cụ đo có điều kiện để hoạt động, và khi nó câm, đồng hồ là chỗ dựa cuối. Con số mang theo: perf đọc bộ đếm PMU phần cứng (cache-miss, branch-miss) để biết VÌ SAO code chậm — nhưng máy ảo thường không lộ PMU nên trả (bộ đếm phần mềm như page-faults vẫn chạy); khi đó phải quay về đồng hồ, và nó vẫn lộ hiệu ứng cache (tuần tự 0,4 ns vs ngẫu nhiên 82,9 ns, ~200×); còn demo đoán nhánh sắp-xếp-nhanh-hơn không tái hiện với -O2 vì compiler biến nhánh thành branchless. Bộ đếm cho biết tại sao, đồng hồ cho biết bao nhiêu — và khi không có bộ đếm, ít nhất đồng hồ vẫn nói được điều gì đó.
Thử ba mươi giây
Kiểm PMU trên máy bạn: perf stat -e cache-misses,branch-misses true — nếu ra số thật, bạn có PMU; nếu <not supported>, môi trường không lộ nó (thường là VM/container). Muốn thấy hiệu ứng cache bằng đồng hồ, so perf stat (hay time) một vòng cộng mảng tuần tự với một vòng pointer-chase ngẫu nhiên trên mảng lớn hơn cache — bản ngẫu nhiên chậm hơn cả trăm lần. Và nếu định thử demo "mảng sắp xếp nhanh hơn", nhớ nó phụ thuộc compiler và kiến trúc: xem assembly bằng objdump -d | grep -iE 'csel|b\.' — nếu thấy csel mà không thấy nhánh điều kiện, compiler đã branchless hóa và demo sẽ không chênh, đúng cái bài này vấp phải.
