Một vòng 2 tỉ phép tính mà kết quả không ai dùng đo ra đúng 0,00 ns — gcc -O2 xóa cả vòng, hàm chỉ còn ret. Thêm một volatile sink là số nhảy lên 1,37 ns thật. Khử mã chết còn xóa dead store và mã sau return, và đây chính là lý do mọi benchmark cần 'quan sát' kết quả.
Mọi sắp xếp dựa trên so sánh bị chặn ở O(n log n). Nhưng radix và counting sort chạy O(n): radix thắng introsort 5–11 lần trên số 32-bit ở mọi cỡ, counting sort nhanh 15,6 lần với khóa nhỏ. Giới hạn thật không ở n nhỏ mà ở bề rộng khóa (32-bit 4 lượt, 64-bit 8 lượt) và scatter phá cache. Tôi đo.
Cùng một code C, -O0 chậm 4,6 lần -O2 — không phải vì làm nhiều phép tính hơn, mà vì giữ mọi biến trên ngăn xếp (72 lệnh load/store so với 26 khi lên -O1). Cú nhảy tốc độ lớn nhất nằm ở -O0 → -O1; còn -O2 và -O3 cho mã gần như y hệt. Số cao hơn không đảm bảo nhanh hơn.
Ma trận kề ngốn 1.527 MB ở V=40.000 và OOM quanh V~90.000, còn danh sách kề chỉ 2,6 MB. Bảng DP đầy đủ dùng 382 MB, bản cuộn hai biến dùng 1 MB cùng thời gian. Merge sort tốn gấp đôi RAM nhưng nhanh hơn heapsort 3,7 lần. Không gian là bức tường cứng, không phải tài nguyên miễn phí — tôi đọc VmHWM để đo.
Bung vòng để 'giảm nhánh' là lời giải thích bỏ lỡ điều quan trọng. Tôi đo: bung với nhiều biến tích lũy độc lập nhanh 3,72 lần vì phá chuỗi phụ thuộc, nhưng bung cơ học của -funroll-loops phình mã 121→314 lệnh mà 0 tăng tốc — và bung x8 còn chậm hơn x4. Cái đáng làm không phải chép thân vòng.
Tưởng CPU luôn chạy theo thứ tự mình viết, còn reorder bộ nhớ chỉ là lý thuyết trong sách? Tôi đo litmus store-buffer trên ARM: reorder xảy ra thật (11 ca trong 60 triệu vòng), rào dmb ish dập được về 0. Nhưng nó hiếm tới ~1 trên 5,5 triệu vòng — nên code sai vẫn qua sạch mọi test rồi nổ ở production.