Mẹo "nhân 8 thì viết x<<3 cho nhanh" — tôi đo trên ARM đời nay và nó gần như vô nghĩa

Nhớ mấy mẹo nhẩm tính ngày xưa không: nhân với 8 thì cứ nhân đôi ba lần, nhân với 10 thì thêm số 0. Hồi máy tính bỏ túi chưa phổ biến, những mẹo đó quý thật — nhẩm nhanh hơn hẳn đặt tính. Nhưng giờ ai cũng có máy tính bấm cái ra ngay, mẹo nhẩm gần như vô nghĩa, trừ vài phép vẫn thực sự rắc rối. Bên trong CPU cũng đúng câu chuyện đó: có một thời "nhân đắt, dịch bit rẻ" là chân lý, và một mẹo tối ưu ra đời từ đó — nhưng phần cứng đã đổi, và tôi đo để xem mẹo ấy còn giá trị tới đâu.

Có một mẹo mà lập trình viên nào cũng từng nghe: "muốn nhân với 8 thì viết x << 3 cho nhanh". Đằng sau nó là một phép biến đổi thật của trình biên dịch — sức mạnh giảm (strength reduction): thay một phép đắt bằng một dãy phép rẻ tương đương. Câu hỏi tôi mang vào: compiler làm việc đó tới đâu, và trên CPU hiện đại thì "rẻ hơn" còn nhanh hơn được bao nhiêu? Tôi đo trong container gcc:13 (ARM) với hai niềm tin, và cả hai đều phải chỉnh lại.

Đắt thành rẻ, compiler tự làm

Sức mạnh giảm có ba dạng hay gặp. Nhân với hằng số biến thành dịch bit và cộng: x*8 thành x<<3, x*10 thành (x*5)<<1. Chia hoặc lấy dư cho hằng số biến thành một phép nhân với "số ma thuật" rồi dịch — tránh hẳn lệnh chia. Và trong vòng lặp, biểu thức a[i] với địa chỉ base + i*stride được thay bằng một con trỏ cộng dồn p += stride mỗi vòng (biến quy nạp — induction variable), bỏ phép nhân lặp đi lặp lại.

Tôi soi mã máy -O2 để xác nhận. Đúng từng dòng:

x*8   ->  lsl w0, w0, 3                 (một lệnh dịch, không mul)
x*10  ->  add w0, w0, w0, lsl 2         (= x*5)
          lsl w0, w0, 1                 (rồi *2 — vẫn không mul)
x/7   ->  mov w1, 0x92499363            (số ma thuật)
          smull ...; lsr ...; asr ...   (nhân + dịch, KHÔNG có sdiv)
x%10  ->  umull ...; lsr ...; sub ...   (magic, KHÔNG có udiv)
x*y   ->  mul w0, w0, w1                (y là biến -> mul thật, không giảm được)

Chỉ hằng số mới giảm được; x*y với y là biến vẫn phải là lệnh mul thật. Điểm quan trọng đầu tiên: compiler làm hết những thứ này ở -O2. Tự tay viết x<<3 thay x*8 không cho bạn gì ngoài một dòng code khó đọc hơn. Nhưng "giảm" xong thì nhanh hơn bao nhiêu? Đó là chỗ tôi vấp.

Cú vấp: "rẻ hơn" không có nghĩa "nhanh hơn rõ"

Niềm tin thứ nhất của tôi: thay nhân bằng dịch bit thì nhanh hơn hẳn. Tôi đo một chuỗi phụ thuộc — mỗi phép chờ kết quả phép trước, nên đo đúng độ trễ mỗi phép — so a*3 (lệnh mul) với a+(a<<1) (dịch cộng, cũng bằng a*3):

a*3 (mul)      : 0,911 ns / phép
a+(a<<1)       : 0,683 ns / phép

Dịch cộng có nhanh hơn, nhưng chỉ chừng 0,23 ns — không phải trời với vực. Lý do: trên ARM hiện đại (và mọi CPU cao cấp), nhân số nguyên rất rẻ — độ trễ khoảng 3 chu kỳ và bộ nhân có ống lệnh (pipelined), nên một phép nhân gần như không tốn hơn một phép cộng là mấy. Cái hình dung "nhân đắt kinh khủng, dịch bit cứu bạn" là di sản của những CPU cũ hàng chục năm trước — đúng cái mẹo nhẩm thời chưa có máy tính bấm. Hôm nay, x<<3 thay x*8 là tối ưu vi mô gần như vô nghĩa, và compiler đằng nào cũng tự làm.

Niềm tin thứ hai đổ theo cách bất ngờ hơn. Tôi tin chia-cho-hằng-số biến thành magic là luôn thắng phép chia. Đo chuỗi phụ thuộc:

a/7 biến (udiv thật)   : 1,821 ns / phép
a/7 hằng (magic mul)   : 2,047 ns / phép   <- CHẬM hơn!

Trong chuỗi phụ thuộc, bản magic chậm hơn cả phép chia thật một chút. Vì phép udiv hiện đại không còn quá đắt, còn dãy magic (nhân + dịch + cộng + trừ) là một chuỗi lệnh dài hơn về độ trễ. Bất ngờ này buộc tôi hỏi: vậy khi nào magic thắng? Câu trả lời là thông lượng — khi có nhiều phép chia độc lập chạy song song trong ống lệnh, không phép nào chờ phép nào:

chia mảng, mỗi phần tử độc lập:
a[i]/7 biến (udiv)     : 0,483 ns / phần tử
a[i]/7 hằng (magic)    : 0,347 ns / phần tử   -> nhanh 1,39 lần

Ở đây magic thắng rõ, vì hai lý do: bộ chia của CPU có thông lượng thấp (ít phép chia mỗi chu kỳ) trong khi bộ nhân chạy song song tốt; và quan trọng hơn, phép nhân magic vector hóa được trên NEON còn udiv thì không (ARM không có lệnh chia vector số nguyên). Nên lợi của sức mạnh giảm không phải một hằng số cố định — nó phụ thuộc phép nào (chia lợi nhiều hơn nhân) và hình dạng tải (thông lượng lợi, chuỗi phụ thuộc có khi không).

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

Điều đầu tiên: đừng tự tay làm sức mạnh giảm. Viết x<<3 thay x*8, hay tự chế công thức magic để chia, chỉ khiến code khó đọc mà không nhanh hơn bản compiler tự sinh — nó đã làm, và làm đúng hơn bạn (xử lý cả số âm, tràn). Cái bạn đổi đi là sự rõ ràng; cái bạn nhận về thường là số không. Viết x*8 hay x/7 cho người đọc hiểu; để -O2 lo phần mã máy.

Điều thứ hai: "phép đắt" là khái niệm phụ thuộc CPU và ngữ cảnh. Trên phần cứng hôm nay, nhân số nguyên đã rẻ ngang cộng, nên khoảng cách nhân–dịch gần như biến mất. Phép chia vẫn là phép đắt nhất trong nhóm số học, nên đó là chỗ sức mạnh giảm còn đáng giá — nhưng ngay cả nó cũng chỉ thắng ở thông lượng. Nếu bạn từng nghe "tránh nhân/chia bằng mọi giá", hãy đo trước: quy tắc đó đến từ một thế hệ CPU khác.

Điều thứ ba nối sang tối ưu vòng lặp: trong vòng nóng, chi phí thật thường không phải một phép nhân lẻ mà là phép nhân lặp lại triệu lần. Đó là lý do biến quy nạp (đổi base + i*stride thành p += stride) đáng giá — nó xóa phép nhân khỏi mỗi vòng, kết hợp với bung vòng lặp và vector hóa thành phần lớn tốc độ của một vòng chặt.

Và cái ý "một thao tác từng đắt nay đã rẻ, mẹo né nó thành lỗi thời" là bài học vượt xa mã máy — nó lặp lại ở mọi tầng, và bỏ quên nó khiến người ta tối ưu nhầm chỗ. Java: bao thế hệ được dạy x << 1 thay x * 2, nhưng JIT đã strength-reduce từ lâu, và mã "tối ưu tay" kiểu đó chỉ làm bytecode khó đọc; thứ thật sự đắt trên JVM giờ là cấp phát đối tượng và cache miss, không phải một phép nhân. Ở tầng hệ thống, "join trong CSDL đắt nên tránh bằng mọi giá" là một huyền thoại tương tự — với index đúng, join thường rẻ, còn cái đắt thật là N+1 query hay full scan. Mẫu số chung, và là một quy tắc vàng chống tối ưu-theo-tin-đồn: "thao tác X đắt" luôn có một dấu-thời-gian ẩn — đắt trên phần cứng/hệ thống nào, năm nào; trước khi bẻ cong code để né một phép, hãy đo xem trên máy của bạn, hôm nay nó có còn đắt không, vì rất thường là không.

Muốn tự thấy thì viết int f(int x){ return x*8; } và int g(int x){ return x/7; }, rồi chạy gcc -O2 -S t.c -o - và tìm hai hàm. Bạn sẽ thấy f chỉ có một lsl (không hề có mul), và g không có sdiv nào cả — thay vào đó là một mov số ma thuật (kiểu 0x92499363) rồi smull. Thử đổi x*8 thành x*9, x*7, x*15 xem compiler chọn bao nhiêu lệnh dịch-cộng; rồi đổi x/7 thành x/8 (lũy thừa 2) và xem nó rút về một phép dịch duy nhất. Ba mươi giây đó cho bạn thấy trình biên dịch đã làm sẵn mọi mẹo bit mà người ta hay khuyên bạn tự viết.