Thêm luồng vào một khóa chung làm thông lượng SỤP: 226 xuống 27 triệu ops/giây khi lên 2 luồng — mở rộng âm. Chia nhỏ khóa vẫn tụt sau 2 luồng vì chia sẻ giả (các biến chung dòng cache). Chỉ khi đệm mỗi luồng ra riêng một dòng cache mới scale gấp 6. 'Song song' cần độc lập cả về khóa lẫn dòng cache.
Cứ đo thời gian là biết ngay độ phức tạp? Đo ra: ở n nhỏ hằng số và overhead lấn át nên tỉ số T(2n)/T(n) lung tung (1,0/4,0/1,75), và cache tạo gãy khúc — truy cập ngẫu nhiên nhảy từ 0,9ns (L1) lên 96ns (RAM), khiến vòng O(n) trông siêu tuyến tính. Nhưng đo đúng cách thì tỉ số hội tụ chính xác: O(n)→2,00, O(n log n)→2,07.
Tưởng hàm nóng nhất trong profiler là chỗ cần tối ưu, và CPU bận nghĩa là thiếu CPU? Tôi đo: một chương trình 8 luồng chỉ đạt song song hiệu quả 1,27 lõi vì chờ khóa 81% thời gian — mà hàm 'nóng' nhất lại hoàn toàn vô can. Đọc profiler đa luồng phải nhìn CPU/wall và thời gian chờ.
Lock-free không dùng khóa nên luôn nhanh hơn mutex? Đo ra: với ít luồng thì atomic nhanh hơn hẳn (1 luồng mutex 4,1 ns vs atomic 1,6 ns), nhưng 8 luồng tranh gay gắt một biến thì atomic fetch_add chỉ ngang mutex (20,8 vs 22,1 ns) và CAS-loop tự viết tệ hơn mutex 6,8 lần (141,5 ns) vì thử lại liên tục. Và mutex không tranh chỉ tốn vài ns.
Serialize chỉ là copy dữ liệu ra byte nên nhanh? Đo ra: binary memcpy đúng là gần như chỉ sao chép (0,48 ns/bản ghi, ~38 GB/s), nhưng ghi ra text từng trường chậm hơn 52 lần và parse chậm hơn 29 lần vì phải format/parse mỗi số. Còn binary memcpy nhanh thì lại không di động: endianness, padding, con trỏ đều vô nghĩa qua máy khác.
Giữ nhiều phiên bản của một cấu trúc thì phải copy cả nó mỗi lần sửa, tốn O(n)? Đo ra: một persistent vector kiểu trie nhánh 32 chỉ copy đường dẫn tới phần đổi — update nhanh hơn copy cả mảng 319 lần, và mỗi phiên bản mới tốn 1,76 KB thay vì 4 MB, ít hơn 2345 lần. Còn đọc thì chỉ chậm hơn mảng phẳng 1,1 lần vì nhánh rộng giữ cây nông.