Tưởng thread-local storage miễn phí như biến toàn cục, hoặc chậm không đáng dùng? Tôi đo ra ở giữa: truy cập TLS chỉ đắt hơn global 4% (một lệnh đọc con trỏ luồng), nhưng dùng TLS làm bộ đếm cục bộ nhanh hơn atomic chung 385 lần vì xóa sạch tranh chấp. Và chính phép đo TLS suýt cho tôi một con số rác 13.000 lần.
Tưởng shared memory tự nó là IPC nhanh nhất vì zero-copy? Tôi đo: shm một-buffer lockstep chỉ 14 GB/s, THUA cả Unix socket 21 GB/s (phải copy nhưng chồng lấn được); chỉ khi dùng ring buffer lock-free (24 GB/s) shm mới thắng. Zero-copy là cần, chưa đủ.
Tưởng cứ thêm #pragma omp parallel for là tự động nhanh? Tôi đo: OpenMP tiện thật, speedup ngang pthread mà chỉ một dòng — nhưng bọc quanh vòng quá nhỏ thì chậm hơn tuần tự 105 lần, chọn sai schedule chậm 1,38 lần, và vẫn dính trần Amdahl. Pragma là công cụ phải đo, không phải nút bấm là nhanh.
Cây tìm kiếm nhị phân được dạy là O(log n). Nhưng đổ khóa đã sắp (id tăng, timestamp — rất thường gặp) vào thì nó thoái hóa thành xâu: chiều cao 40000 thay vì 34, tra 32672 ns thay vì 51 ns, chậm 640 lần đúng bằng quét tuyến tính. Và một mảng nhị phân đẹp cache cũng không nhanh hơn cây cân bằng. Tôi đo.
Union-find chỉ là đi lên gốc cây parent, đơn giản mà? Tôi đo thử: thiếu nén đường và union by rank, cây suy biến thành chuỗi và find thành O(n) — 28.368 ns/find. Thêm hai tối ưu, mỗi thao tác còn 3,8 ns, gần O(1) (α(n) — Ackermann ngược), nhanh hơn cả O(log n).
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.