Đảo byte tôi tự viết bằng shift/mask nhanh ngang builtin — vì gcc nhận ra tôi đang làm gì

Hình dung gian bếp có đủ dụng cụ chuyên dụng. Cái máy ép tỏi biến việc băm một tép tỏi — vốn phải bằm lách cách một hồi — thành đúng một cú bóp: ở đây dụng cụ thắng rõ, vì băm tay chậm và lích kích. Nhưng với việc thái hành, một đầu bếp lành nghề cầm con dao tốt cũng nhanh ngang bất cứ cái máy thái nào — mua thêm máy chẳng để làm gì. Cái khéo là người đầu bếp tự biết khi nào việc bạn đang làm xứng đáng lôi dụng cụ chuyên dụng ra. Trình biên dịch đúng là người đầu bếp đó, và nó thay đổi hẳn câu "muốn nhanh phải dùng builtin".

CPU hiện đại có những lệnh chuyên dụng làm trong một nhịp thứ mà mã C ngây thơ phải làm bằng cả một vòng lặp: đếm số bit 1 (CNT), đếm số bit 0 đầu chuỗi (CLZ), đảo thứ tự byte (REV). Trình biên dịch phơi chúng ra qua các hàm builtin (__builtin_popcount, __builtin_clz, __builtin_bswap), và qua intrinsics cho lệnh SIMD. Lời khuyên thường gặp: "muốn nhanh thì dùng builtin/intrinsics, đừng viết C tay". Tôi đo xem lời khuyên đó đúng tới đâu trong container gcc:13 (ARM) — và thấy nó đúng một nửa, sai một nửa, tùy phép.

Builtin ánh xạ thẳng sang một lệnh

Một builtin không phải hàm thư viện; nó là một ký hiệu mà compiler thay thẳng bằng lệnh máy tương ứng. objdump xác nhận:

__builtin_popcountll(x)  ->  cnt   (đếm bit 1, qua thanh ghi NEON)
__builtin_clzll(x)       ->  clz   (đếm bit 0 đầu chuỗi)
__builtin_bswap64(x)     ->  rev   (đảo byte)

Mỗi builtin gói một khả năng phần cứng vào một cái tên dễ đọc, thay cho một đoạn mẹo bit khó hiểu. Câu hỏi thực tế: nếu tôi không dùng builtin mà viết tay logic tương đương, compiler có sinh ra cùng lệnh không? Đây là chỗ tôi vấp.

Đo: popcount thắng lớn, bswap thì hòa

Popcount viết tay. Cách kinh điển đếm bit 1 là vòng Kernighan: while(x){ x &= x-1; c++; } — mỗi vòng xóa bit 1 thấp nhất, lặp đúng bằng số bit 1. Đây là một vòng lặp phụ thuộc dữ liệu: với số 64-bit ngẫu nhiên (khoảng 32 bit 1), nó chạy ~32 vòng. So với __builtin_popcountll (một lệnh cnt):

popcount viết tay (Kernighan) : 0,502 ns/số
__builtin_popcountll          : 0,283 ns/số   -> builtin nhanh 1,8 lần

Builtin nhanh gần gấp đôi. Không có gì lạ: một lệnh cnt cố định thắng một vòng lặp phải quay 32 lần và phụ thuộc dữ liệu. Đây là ca builtin đáng dùng — phép mà C không có cách viết tự nhiên nào ánh xạ thẳng sang lệnh, đúng như băm tỏi cần cái máy ép.

Byte-swap viết tay. Giờ thử đảo byte bằng shift và mask, cách ai cũng từng viết:

uint32_t bswap(uint32_t x){
  return ((x>>24)&0xff) | ((x>>8)&0xff00) | ((x<<8)&0xff0000) | ((x<<24)&0xff000000);
}

Tôi đoán nó sẽ chậm hơn __builtin_bswap32 (một lệnh rev). Đo ra:

bswap viết tay (shift/mask) : 0,257 ns/số
__builtin_bswap32           : 0,262 ns/số   -> BẰNG nhau

Bằng nhau! Và objdump giải thích vì sao: bản viết tay bằng shift/mask cũng biên dịch thành đúng một lệnh rev. gcc nhận ra cái mẫu — nó thấy chuỗi shift/mask đó chính là một byte-swap và thay bằng lệnh chuyên dụng, y hệt như builtin. Đây gọi là nhận mẫu (idiom recognition): compiler hiện đại có cả một thư viện mẫu mã thông dụng và tự thay chúng bằng lệnh tối ưu. Đúng anh đầu bếp thấy bạn thái hành thì tự lấy đúng con dao.

Vậy cú vấp của tôi được sửa: "phải dùng builtin mới nhanh" chỉ đúng khi phép không có mẫu C tự nhiên để compiler nhận (popcount). Với những phép có mẫu quen (byte-swap, và nhiều phép bit khác), viết C rõ ràng đã cho đúng lệnh tối ưu — builtin không nhanh hơn, chỉ ngắn gọn và rõ ý hơn.

Một builtin còn để đúng, không chỉ để nhanh

Có một loại builtin đáng nói riêng, vì nó không chỉ nhanh mà còn đúng: __builtin_add_overflow (và các anh em sub/mul). Ở bài hành vi không xác định ta đã đo cảnh: viết kiểm tra tràn thủ công if(a+100 < a) bị compiler xóa sạch, vì tràn số nguyên có dấu là hành vi không xác định nên compiler giả định nó không xảy ra. Cách kiểm tràn đúng là dùng builtin:

int s;
if(__builtin_add_overflow(a, b, &s)) { /* đã tràn — xử lý an toàn */ }

Builtin này biên dịch thành một phép cộng rồi đọc thẳng cờ tràn của CPU — luôn đúng, không dựa vào hành vi không xác định nào để compiler có cớ xóa. Đây là điểm khác biệt quan trọng: một số builtin tồn tại không phải để đổi một vòng lấy một lệnh cho nhanh, mà để diễn đạt một phép mà C thuần không có cách viết an toàn. Với chúng, builtin là lựa chọn đúng đắn chứ không phải tối ưu vi mô.

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

Điều đầu tiên: dùng builtin khi phép khó nhận, để chắc chắn và rõ ý. __builtin_popcount, __builtin_clz, __builtin_ctz là những phép mà cách viết tay hoặc là vòng lặp chậm, hoặc là mẹo bit khó đọc mà compiler không phải lúc nào cũng nhận. Ở đó, builtin vừa đảm bảo ra một lệnh, vừa nói rõ ý định — __builtin_popcountll(mask) dễ hiểu hơn một vòng while xóa bit. Đây cũng là nơi thao tác bit và bitset hưởng lợi nhiều nhất.

Điều thứ hai: đừng rắc intrinsics thủ công khắp nơi theo phản xạ. Với nhiều phép, compiler tự nhận mẫu và sinh cùng lệnh, nên viết C rõ ràng là đủ. Viết bằng intrinsics NEON tay đổi lại nhiều cái mất: kém di động (mã chỉ chạy trên ARM), khó đọc, và đôi khi còn chặn tối ưu của compiler — một chuỗi intrinsics viết cứng khiến compiler không dám sắp lại hay vector hóa theo cách nó muốn. Một quy tắc thực dụng: viết C rõ ràng trước, kiểm objdump xem compiler đã sinh lệnh mong muốn chưa; chỉ khi nó không nhận ra mẫu và bạn đã đo thấy chậm thật, mới chạm tới builtin hay intrinsics — và ngay cả khi đó, ưu tiên builtin (di động qua nhiều kiến trúc) hơn intrinsics gắn cứng vào một tập lệnh.

Và cái ranh giới "để trình biên dịch tự nhận hay tự tay gọi lệnh chuyên dụng" này lặp lại ở mọi tầng, thường theo chiều bất ngờ. JVM đi xa hơn C: rất nhiều hàm Integer.bitCount, Long.numberOfLeadingZeros, Math.max, thậm chí Integer.reverseBytes được JIT nhận ra là intrinsic và thay bằng đúng lệnh popcnt/lzcnt/bswap lúc chạy — bạn viết một lời gọi thư viện trông bình thường, JIT biến nó thành một lệnh máy. Go phơi ra qua gói math/bits (bits.OnesCount, bits.LeadingZeros) mà compiler map thẳng sang lệnh CPU. Ngay cả CSDL cũng có tinh thần này: một hàm cửa sổ hay tập hợp bạn viết bằng SQL thường được engine thực thi bằng đường tối ưu sẵn, nhanh hơn tự cuộn vòng lặp thủ công trong stored procedure. Mẫu số chung: các phép cấp thấp phổ biến hầu như luôn đã có đường tắt phần cứng, và tầng bên dưới (compiler, JIT, engine) ngày càng giỏi tự nhận ra ý định của bạn — nên hãy viết rõ ràng, dùng hàm chuẩn/builtin cho phép khó, và chỉ hạ xuống mã gắn cứng phần cứng khi đã đo thấy tầng dưới thật sự bỏ lỡ.

Muốn tự thấy thì viết hai hàm đếm bit 1: một bản vòng Kernighan (while(x){x&=x-1;c++;}) và một bản __builtin_popcountll(x). Biên dịch gcc -O2 -S -o - t.c và so: bản builtin có một lệnh cnt (hoặc chuỗi NEON ngắn), bản viết tay là một vòng lặp có nhãn và nhánh. Rồi viết một byte-swap bằng shift/mask và so với __builtin_bswap32 — lần này cả hai đều rút về một lệnh rev, vì gcc nhận ra mẫu. Ba mươi giây đó cho bạn thấy ranh giới: builtin cần cho phép compiler không tự nhận ra, và thừa cho phép nó đã nhận.