Sách bảo linked list chèn O(1) thắng mảng O(n), nên tải chèn nhiều thì chọn linked list. Nhưng đo ra list chậm hơn vector 31 lần ngay ở chèn — vì O(1) splice bị nuốt bởi O(n) đi tìm vị trí đầy cache-miss; và duyệt chậm 395 lần. Big-O một thao tác bỏ qua chi phí tìm và locality. Tôi đo bằng C.
Đệ quy đuôi được đồn là liều thuốc chống tràn ngăn xếp. Nhưng cùng một hàm: gcc -O0 tràn ở 1 triệu tầng, gcc -O2 chạy 100 triệu vì biến thành vòng lặp, còn CPython không bao giờ tối ưu đuôi — vẫn tràn ở 1000 khung. 'Đệ quy đuôi an toàn' chỉ đúng khi trình biên dịch thật sự làm TCO. Tôi đo.
Sách bảo naive O(n·m) chậm, phải dùng KMP. Nhưng trên văn bản ngẫu nhiên naive chỉ 1,04 so sánh mỗi ký tự — gần O(n), còn nhỉnh hơn KMP. O(n·m) là trường hợp xấu nhất, chỉ bật ra trên văn bản lặp (T='aaaa', P='aa..b') nơi KMP nhanh 194 lần. Nhãn xấu nhất không phải bản án cho mọi đầu vào. Tôi đo.
Tưởng barrier rẻ, cứ thêm cho chắc? Tôi đo: mỗi rào tốn 8 tới 41 micro giây, tăng theo số luồng vì phải đánh thức cả N luồng; và rào chờ luồng chậm nhất mỗi pha — một luồng nặng gấp 4 trong tám làm cả tính toán 500 pha chậm 1,75 lần. Barrier khuếch đại mọi mất cân bằng tải.
Ai cũng bảo muốn compiler tự vector hóa SIMD thì phải bật -O3. Tôi đo trên gcc 13: -O2 đã sinh 26 lệnh NEON và nhanh gấp 2 lần -O1 scalar, còn -O3 cho mã y hệt. Và cách biết chắc vòng nào được vector hóa không phải đoán theo mức -O, mà là đọc -fopt-info-vec — compiler tự khai.
Tưởng tạo luồng mỗi việc là ổn cho việc nhỏ, hoặc thread pool là kỹ thuật rườm rà thừa? Tôi đo: 20.000 việc nhỏ kiểu thread-per-task mất 989ms vì chi phí tạo luồng ~47µs lấn át việc thật, còn thread pool nhanh 125 lần với số worker quanh số lõi — quá nhiều worker lại chậm đi. Một chi phí nhỏ nhân số lần lớn thành nút thắt khổng lồ.