Bố cục struct chỉ là cách tổ chức, không đổi tốc độ? Tôi đo thử: duyệt một trường trên 15 triệu phần tử, SoA nhanh hơn AoS 3,6 lần vì cache line không bị lãng phí. Nhưng truy cập ngẫu nhiên mọi trường thì AoS lại nhanh gấp đôi. Không có bố cục nào luôn thắng — chọn theo mẫu truy cập.
Hai luồng, mỗi luồng tăng bộ đếm riêng — độc lập hoàn toàn, phải chạy song song? Tôi đo thử: nếu hai bộ đếm nằm cùng một cache line, chúng chậm hơn 3,8–4,9 lần vì dòng cache ping-pong giữa hai lõi (false sharing). Tách sang cache line riêng (padding) là khắc phục. Không chia sẻ một byte dữ liệu nào vẫn bị phạt vì chung dòng.
Thứ tự khai báo trường trong struct chỉ là chuyện phong cách? Tôi đo thử: đảo thứ tự cùng ba trường làm struct từ 24 byte xuống 16 byte — phí 33% RAM chỉ vì đệm căn lề, và duyệt mảng bản 16B nhanh hơn 1,35 lần vì nhét gấp đôi số struct mỗi cache line. Sắp trường lớn tới nhỏ.
Cần một tập số nguyên, cứ dùng std::set cho tiện? Tôi đo thử: với miền nhỏ dày đặc, bitset nén RAM 192 lần, phép giao nhanh 10.000 lần (AND 64 phần tử mỗi lệnh), kiểm tra thành viên nhanh 870 lần. Nhưng miền rộng tập thưa thì bitset lại phí RAM — chọn theo miền nhỏ/rộng, dày/thưa.
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).
Nối chuỗi trong vòng lặp s = s + phần trông vô hại? Tôi đo thử: với chuỗi bất biến (tạo chuỗi mới mỗi lần), nối 200 nghìn ký tự đã copy 20 tỷ byte — O(N²), 2151 ns/ký tự; nếu 20 triệu thì mất 72 phút. Buffer/StringBuilder append tại chỗ chỉ 2,18 ns/ký tự, O(N) — nhanh hơn 1000 lần mỗi ký tự.