Dấu chia tốn 8 chu kỳ hay gần như 0? Tùy bạn viết

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.

Nghĩ về chuyện làm tính bằng tay. Cộng hai số thì nhẩm ngay. Nhân cũng nhanh nếu thuộc bảng cửu chương. Nhưng chia dài — kiểu 4728 ÷ 37 — thì bạn phải làm từng bước: ước lượng, nhân ngược, trừ, hạ chữ số, lặp lại. Không có cách nào "chia một nhát"; bản chất nó là một quy trình lặp. CPU cũng y hệt: mạch chia phần cứng phải lặp qua từng bit thương, nên chia luôn là phép số học tốn nhất. Phần này tôi soi kỹ vào nó, đo xem đắ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á đó. Đo trong container gcc:13 trên host ARM, 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 mỗi chu kỳ). Phép chia thì như phép chia dài ở trên — thuật toán 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 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ỗ cần đính chính: nhiều tài liệu (và ký ức của chính 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 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

Ba mẹo hiện ra từ bảng:

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.

Hai thái cực đều sai

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". Con số bác ngay: 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 nếu vì thế mà nhảy sang cực kia thì cũng sai theo hai cách. Cực thứ nhấ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ì một nỗi sợ lỗi thời. Cực thứ hai là "chia luôn chậm nên tránh mọi phép chia": cũng 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í.

Về đến code hằng ngày

Việc đầ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.

Việc 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 khác biệt vô hình trong mã nguồn quyết định bạn trả 0,27 hay 0,44 ns.

Và điều làm tôi thấy hay là mẹo "chia hằng số thành nhân" không phải đặc sản của C — nó có mặt ở mọi nơi có JIT hay tối ưu, chỉ là bạn không thấy. JIT của JVM và của Go đều làm đúng magic-number đó cho x / 7 hay x % 8; viết HashMap với dung lượng lũy thừa 2 (Java làm mặc định) chính là để băm bằng & thay vì %. Còn ở tầng cao hơn, "chia là phép đắt nhất, tránh nếu được" biến thành các quyết định kiến trúc: sharding theo hash % N với N lũy thừa 2, hay tránh phép chia trong vòng nóng của một game engine / bộ mã hóa video. Ngay cả trong SQL, một biểu thức chia trên hàng triệu hàng cũng đáng để ý — dù ở quy mô đó chi phí I/O thường lấn át. Nguyên tắc chung: 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) chứ không chỉ tên phép.

Muốn tự thấy thì 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 (đọc assembly sẽ thấy 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 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.