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.
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.
CPU chỉ có ~28 thanh ghi số nguyên dùng được trên AArch64; vượt ngưỡng đó, biến sống cùng lúc bị tràn ra ngăn xếp, và lệnh load/store trong vòng nóng leo từ 1 (4 biến) lên 103 (48 biến). Đây chính là lời giải cho bí ẩn bung vòng x8 chậm hơn x4 — và vì sao biến cục bộ không hề miễn phí.
Định trưng ra một ca -O3 thua -O2, tôi đo bốn kernel trên gcc 13/ARM và không ca nào -O3 chậm hơn — nó thắng đậm hoặc hòa. Nhưng cái giá thật vẫn đo được, chỉ ở chỗ khác: hàm phình từ 15 lên 47 lệnh. -O3 chắc chắn thêm mã, chỉ CÓ THỂ thêm tốc độ.
Hành vi không xác định (UB) chỉ là 'crash hoặc giá trị rác'? Tôi đo và thấy nó là một lời hứa compiler tin tuyệt đối, rồi xóa chính những kiểm tra an toàn tôi viết: if(p==NULL) sau khi deref, if(a+100<a) kiểm tràn — cả hai biến mất ở -O2, để lỗi lọt qua im lặng. Cái tối ưu UB mở khóa nằm ở mã, không phải ở đồng hồ.