Atomic fetch_add đúng là nhanh hơn mutex 2,8 lần khi một luồng. Nhưng một biến atomic chung scale ÂM: 627 tụt xuống 34 triệu/giây ở 10 luồng vì cache-line ping-pong, gần bằng mutex. Cách nhanh thật không phải khóa xịn hơn mà là không chia sẻ — đếm riêng nhanh gấp ~180 lần. Tôi đo.
Nhân học sinh O(n²) đáng ra phải thua Karatsuba O(n^1,585) — nhưng đo ra nó thắng tới tận ~1024 hạn (~9.800 chữ số). Ở 64 hạn Karatsuba còn chậm hơn 2,8 lần vì hằng số ẩn của đệ quy. Và mọi phép số lớn chậm hơn nhân 64-bit gốc hàng trăm nghìn lần. Bậc tốt hơn không tự động nhanh hơn. Tôi đo.
rand() % 20000 đo ra lệch đúng 2 lần giữa hai vùng giá trị vì 32768 không chia hết cho 20000. Bit thấp nhất của LCG chỉ đảo 0,1,0,1 — chu kỳ 2, tất định hoàn toàn. Còn xorshift chạy 717 triệu số/giây, nhanh hơn rand() 2,8 lần nhưng tuyệt đối không dùng được cho mật mã. 'Ngẫu nhiên' là tính chất phải đo. Tôi đo.
Cùng zlib, tỉ lệ nén nhảy từ 514 lần (dữ liệu lặp) xuống 2,66 lần (văn bản) xuống dưới 1 với byte ngẫu nhiên — 8 MB phình thành 8.000.316 byte vì không gì nén được hỗn loạn. Mức 9 cho tỉ lệ đúng bằng mức 6, còn lzma chặt hơn nhưng chậm 23 lần. Nén là thuộc tính của dữ liệu, không phải công cụ. Tôi đo.
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.
Kẹp đồng hồ hai đầu vòng lặp rồi đọc số nghe đơn giản, nhưng con số ấy nói dối bốn kiểu: bỏ sink thì compiler xóa vòng và đo ra 0 ns cho việc chưa chạy; lần đầu chậm 27% vì cache lạnh; trên VM một lần vọt 2,7 lần median; và clock_gettime tốn 16 ns nên đo việc vài ns ra rác. Cách đo cho đáng tin.