Trong đầu nhiều người, các phép số học đều "một phép toán", tốn thời gian như nhau. Phần 11 đã hé lộ điều ngược lại: cộng, nhân, chia có độ trễ rất khác nhau. Phần này soi kỹ vào phép đắt nhất trong số học thường gặp — phép chia — đo xem nó đắt hơn nhân bao nhiêu, và quan trọng hơn, khi nào bạn không phải trả cái giá đó. Tôi đo trong container gcc:13 trên host ARM, và kết quả vừa xác nhận "chia đắt", vừa đính chính một huyền thoại cũ về mức độ đắt.
Vì sao chia đắt hơn nhân
Phép nhân trong CPU làm gần như "một nhát": mạch nhân song song cho ra kết quả sau vài chu kỳ cố định, và thường pipelined (phát một phép mỗi chu kỳ). Phép chia thì khác — thuật toán chia phần cứng về bản chất là lặp, xử lý vài bit thương mỗi bước, nên tốn nhiều chu kỳ hơn và thường không pipelined đầy đủ (bộ chia bận cho tới khi xong). Đó là lý do chia luôn là phép số học tốn nhất trong các phép "cơ bản".
Để đo độ trễ thật của mỗi phép, tôi dựng chuỗi phụ thuộc (mỗi phép ăn kết quả phép trước) như phần 11, quy ra chu kỳ với 1 chu kỳ ≈ 0,214 ns:
Độ trễ (chuỗi phụ thuộc), host ARM, g++ -O2:
add nguyên : 0,227 ns | 1,1 chu kỳ
mul nguyên : 0,683 ns | 3,2 chu kỳ
udiv nguyên: 1,707 ns | 8,0 chu kỳ <- ~2,5x mul, ~7x add
fmul (số thực): 0,704 ns | 3,3 chu kỳ
fdiv (số thực): 2,276 ns | 10,7 chu kỳ <- ~3,2x fmul, ~10x add
Đọc bảng: phép nhân số nguyên tốn 3,2 chu kỳ, còn chia số nguyên (udiv) tốn 8,0 chu kỳ — gấp 2,5 lần nhân và 7 lần một phép cộng. Với số thực, nhân (fmul) 3,3 chu kỳ còn chia (fdiv) 10,7 chu kỳ — gấp 3,2 lần nhân và khoảng 10 lần một phép cộng. Chia đúng là phép số học đắt nhất bạn hay gặp.
Nhưng đây là chỗ đính chính: nhiều tài liệu (và ký ức của tôi) nói "chia đắt gấp hàng chục lần nhân". Trên lõi ARM này, con số thật chỉ ~3 lần — bộ chia của các CPU hiện đại, đặc biệt Apple Silicon, tốt hơn huyền thoại đó nhiều. "20–40 lần" là chuyện của x86 đời cũ; đo máy của bạn mới biết. Dù vậy, chia vẫn là phép đắt nhất và vẫn nên tránh trong vòng lặp nóng.
Đo: cách tránh cái giá của phép chia
Cái hay là phần lớn phép chia trong code không cần trả giá udiv, vì trình biên dịch (hoặc bạn) thay được bằng phép rẻ hơn. Tôi đo thông lượng (nhiều phép độc lập) các cách:
Thông lượng, ns/phép, host ARM:
udiv (chia số BIẾN runtime) : 0,44
div hằng số a/7 (compiler magic): 0,27 <- nhân nghịch đảo + dịch
mod a % biến runtime : 0,44
mod a % 1024 : 0,18
& mask a & 1023 : 0,08 <- rẻ hơn %biến ~5x
Nhìn ba mẹo:
Chia cho hằng số (a/7): trình biên dịch không sinh lệnh chia. Nó dùng một "magic number" — nhân với nghịch đảo cố định rồi dịch bit — cho kết quả y hệt mà chỉ tốn 0,27 ns thay vì 0,44. Bạn viết phép chia, nhưng nếu số chia là hằng số biên dịch, bạn không trả giá chia. Chỉ khi số chia là biến runtime (compiler không biết trước) mới sinh udiv thật.
Lấy dư cho lũy thừa 2 (a % 1024): tương đương a & 1023 (giữ các bit thấp). Trình biên dịch tự thay khi thấy hằng số lũy thừa 2 (0,18 ns), và nếu bạn tự viết & mask thì còn rẻ hơn (0,08 ns) — nhanh gấp ~5 lần so với % số biến. Đây là lý do các bảng băm, vòng đệm (ring buffer) thường chọn kích thước lũy thừa 2: để thay % bằng &.
Nhân nghịch đảo tính sẵn: nếu bạn chia cho cùng một số thực nhiều lần trong vòng (số đó là biến nên compiler không magic được), hãy tính recip = 1.0/d một lần ngoài vòng rồi nhân x * recip bên trong. Bạn đổi nhiều phép fdiv (10,7 ck) thành nhiều phép fmul (3,3 ck) — nhanh ~3 lần (chấp nhận sai số làm tròn cực nhỏ), và các phép nhân độc lập ấy còn được vector hóa tốt hơn chia.
Một lần tôi đo hớ: "nhân với chia tốn như nhau" và "chia luôn đắt hàng chục lần"
Tôi vào đo với mô hình ngây thơ nhất: "nhân, chia đều là một phép toán, tốn như nhau". Đo phá tan: chia đắt hơn nhân rõ rệt — udiv 8 chu kỳ so với mul 3,2; fdiv 10,7 so với fmul 3,3 (~3 lần), và khoảng 10 lần một phép cộng. Chia là phép số học đắt nhất, và một vòng lặp đầy phép chia có thể chậm hơn nhiều lần một vòng đầy phép nhân "cùng số phép toán".
Nhưng đo cũng chỉnh hai niềm tin ngược nhau. Một là huyền thoại "chia đắt hàng chục lần nhân, phải sợ nó": trên ARM này chỉ ~3 lần — con số "20–40 lần" là của x86 đời cũ, bộ chia nay tốt hơn nhiều, nên đừng bóp méo thuật toán chỉ vì nỗi sợ lỗi thời. Hai là niềm tin "chia luôn chậm nên tránh mọi phép chia": sai — chia cho hằng số được compiler biến thành nhân+dịch (gần free), và % 2^k thành & mask (rẻ hơn ~5 lần). Chỉ chia/lấy-dư cho số biến runtime mới thực sự đắt. Sợ sai chỗ khiến ta viết code khó đọc để "tránh chia" ở nơi vốn đã miễn phí.
Bài học đo lường: CHIA là phép số học đắt nhất — đo: udiv 8 ck vs mul 3,2 ck; fdiv 10,7 ck vs fmul 3,3 ck (~3x), ~10x một phép cộng. NHƯNG 'hàng chục lần' là huyền thoại x86 cũ; ARM này ~3x. Và chỉ chia cho số BIẾN mới đắt: chia HẰNG SỐ -> compiler magic (nhân+dịch, 0,27 vs 0,44), % 2^k -> & mask (0,08 vs 0,44, ~5x). Nhân nghịch đảo tính sẵn đổi fdiv thành fmul. 'Nhân chia tốn như nhau' và 'chia luôn đắt hàng chục lần / phải tránh mọi lúc' đều SAI. Nếu tin "tốn như nhau" tôi coi thường vòng lặp đầy chia; nếu tin "đắt hàng chục lần, tránh hết" tôi né cả những phép chia vốn đã free.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: giảm phép chia/lấy-dư cho số BIẾN trong vòng nóng. Nếu bạn chia nhiều lần cho cùng một số thực (chuẩn hóa vector, tính trung bình), tính nghịch đảo một lần rồi nhân — rồi tách nhiều biến tích lũy để chạy song song. Nếu cần % để cuộn chỉ số (ring buffer, hash bucket), chọn kích thước lũy thừa 2 để dùng & (n-1). Đây là những tối ưu tay có thật, đo được vài lần.
Hệ quả thứ hai: để hằng số là hằng số — đừng "giấu" số chia sau một biến. a / 7 được compiler magic hóa; nhưng int d = 7; a / d (nếu d không phải const và compiler không suy ra được) sinh udiv thật. Khai const/constexpr cho các số chia cố định, hoặc dùng literal, để compiler thay bằng nhân+dịch. Một sự khác biệt vô hình trong mã nguồn quyết định bạn trả 0,27 hay 0,44 ns.
Hệ quả thứ ba là tinh thần đo lường: các phép toán không bình đẳng, và cái giá phụ thuộc ngữ cảnh (hằng hay biến), không chỉ tên phép. Con số mang theo: chia là phép đắt nhất (udiv 8 ck, fdiv 10,7 ck, ~3x nhân / ~10x cộng) — nhưng chỉ khi chia số BIẾN; chia hằng số và % 2^k gần miễn phí (magic / & mask). 'Hàng chục lần' là folklore x86. Cùng một dấu / trong mã, tốn 8 chu kỳ hay gần như 0 tùy số chia là biến hay hằng — đo mới thấy ranh giới ấy.
Thử ba mươi giây
Viết ba vòng lặp trên một mảng số nguyên trong cache và bấm giờ ns mỗi phần tử. Một: s += a[i] / d với d là một biến đọc lúc chạy (ví dụ từ argc hay volatile) — bạn được giá udiv thật. Hai: s += a[i] / 7 với 7 là hằng số — nhanh hơn hẳn, vì trình biên dịch thay bằng nhân với "magic number" và dịch bit (xem bằng cách đọc assembly: không có lệnh div nào). Ba: s += a[i] % 1024 so với s += a[i] & 1023 — hai cái cho cùng kết quả nhưng bản & mask nhanh nhất. Cuối cùng, với số thực, so một vòng x[i] / d (d biến) với vòng tính r = 1.0/d một lần rồi x[i] * r: bản nhân nhanh khoảng ba lần. Ba mươi giây đó cho bạn thấy điều mà "nhân chia tốn như nhau" giấu đi: chia là phép đắt nhất, nhưng phần lớn phép chia trong code thật ra không phải trả giá đó — chỉ cần số chia là hằng số hoặc lũy thừa 2, hoặc bạn tự đổi chia thành nhân nghịch đảo.
