Rabin-Karp so khớp chuỗi bằng hash, được ghi là O(n+m). Nhưng con số đó đứng trên hai cái chân dễ quên: bỏ hash cuộn (tính lại mỗi cửa sổ) chậm 26 lần, dùng hash xấu trên văn bản lặp cho 999.001 va chạm giả và chậm 33 lần. Cả hai đều tụt về O(n·m) mà không một dòng lỗi. Tôi đo.
Bloom filter trả lời 'phần tử này có trong tập không' một cách không chính xác: dương tính giả 0,81% ở 10 bit/phần tử, 14,7% ở 4 bit, giảm theo hàm mũ khi thêm bit nhưng không bao giờ về 0. Đổi lại nó không bao giờ báo âm tính giả và chỉ tốn 1,2 MB thay vì 25 MB. Có số hàm băm tối ưu. Tôi đo.
Cấp rồi giải 3 triệu object nhỏ tốn 47 ms, còn arena chỉ 6,2 ms (nhanh 8 lần). 1 triệu object 16 byte ngốn 38,6 MB thay vì 16 MB vì metadata và căn lề. Và free sạch rồi RSS vẫn đứng 168 MB. malloc trong vòng nóng là kẻ giết hiệu năng ẩn — gom vào arena chữa cả ba. Tôi đo.
Gói các trường của một object lại thành struct (AoS) là cách tự nhiên nhất. Nhưng khi chỉ cộng một trường của struct rộng, AoS chậm tới 4,7 lần SoA vì mỗi dòng cache kéo cả struct về mà chỉ dùng một trường. Đọc hết mọi trường thì AoS lại ngang. Mẫu truy cập quyết định bố cục, không phải cái nào nghe tự nhiên hơn. Tôi đo.
Cùng một đoạn code, cùng những con số, chỉ khác mảng được sắp trước hay chưa: bản chưa sắp chạy 660 ms, bản đã sắp 379 ms — chênh 1,7 lần. Không phải ít phép tính hơn, không phải cache. Thủ phạm là dự đoán nhánh của CPU, thứ big-O không hề thấy. Viết không nhánh xóa hẳn (183 ms). Tôi đo.
Bật -O3, vòng nhân mảng float nhanh 3,9 lần nhờ NEON làm 4 float mỗi lệnh. Nhưng chỉ thêm một phụ thuộc chuỗi là trình biên dịch lặng lẽ bỏ vector hóa, tụt về scalar chậm 11,6 lần — không một dòng cảnh báo. SIMD không phải phép màu của cờ, mà là phần thưởng cho vòng viết đúng dạng. Tôi đo.