Fibonacci đệ quy khớp y hệt định nghĩa toán học, nhưng đo ra nó nổ theo hàm mũ: fib(43) gọi 1,4 tỉ lần, mất 447 ms, vì tính lại bài con chồng lấn. Quy hoạch động chỉ là 'nhớ để khỏi tính lại': memo đưa về 85 lời gọi, dưới 1 micro giây. Tabulation nhanh hơn memo 28 lần và không tràn ngăn xếp. Tôi đo.
BFS và DFS được dạy như cặp sinh đôi cùng O(V+E), nên tưởng thay thế được. Nhưng trên lưới 1000×1000 chúng tìm thứ khác hẳn: BFS ra đường ngắn nhất 1998 cạnh, DFS ra đường 499.500 cạnh — dài gấp 250 lần. Bộ nhớ cũng phình theo hai chiều khác nhau. 'Cùng độ phức tạp' không có nghĩa 'cùng việc'. Tôi đo.
Dijkstra là thuật toán tham lam nhưng đúng — nhờ đúng một điều kiện: trọng số không âm. Cho nó một cạnh âm (2→1 = -3), nó chốt dist[1]=4 sai trong khi đáp án thật là 2, mà không một cảnh báo. Và cấu trúc bên trong quyết định quy mô: heap nhanh hơn mảng 36 lần trên đồ thị thưa. Tôi đo.
Gói các trường của một object lại thành struct (AoS) là cách tự nhiên nhất. Nhưng khi chỉ cộng một trường của struct rộng, AoS chậm tới 4,7 lần SoA vì mỗi dòng cache kéo cả struct về mà chỉ dùng một trường. Đọc hết mọi trường thì AoS lại ngang. Mẫu truy cập quyết định bố cục, không phải cái nào nghe tự nhiên hơn. Tôi đo.
Bloom filter trả lời 'phần tử này có trong tập không' một cách không chính xác: dương tính giả 0,81% ở 10 bit/phần tử, 14,7% ở 4 bit, giảm theo hàm mũ khi thêm bit nhưng không bao giờ về 0. Đổi lại nó không bao giờ báo âm tính giả và chỉ tốn 1,2 MB thay vì 25 MB. Có số hàm băm tối ưu. Tôi đo.
Cấp rồi giải 3 triệu object nhỏ tốn 47 ms, còn arena chỉ 6,2 ms (nhanh 8 lần). 1 triệu object 16 byte ngốn 38,6 MB thay vì 16 MB vì metadata và căn lề. Và free sạch rồi RSS vẫn đứng 168 MB. malloc trong vòng nóng là kẻ giết hiệu năng ẩn — gom vào arena chữa cả ba. Tôi đo.