Giải thuật 03/09/2026 10 phút

Free lẻ mà vẫn nhanh 5,7 lần malloc: mẹo free list

Arena nhanh nhưng không free lẻ được — muốn free từng cái thì đành quay lại malloc? Tôi đo thử: một pool free list cấp và free từng ô O(1) bằng cách xâu các ô trống vào một danh sách liên kết, churn nhanh gấp 5,7 lần malloc/free. Hay nhất là con trỏ next nhúng ngay trong ô trống nên tốn 0 byte thừa.

Giải thuật 03/09/2026 7 phút

shared_ptr không miễn phí: cái giá atomic mỗi lần copy

shared_ptr tiện nên cứ dùng khắp nơi? Tôi đo thử: mỗi lần copy shared_ptr là một phép đếm tham chiếu atomic, chậm gấp 2,3 lần gán con trỏ thô — và tệ hơn nữa khi nhiều luồng tranh cùng bộ đếm. Trong khi unique_ptr thì gần như miễn phí, nhanh bằng con trỏ thô. Chọn theo có cần chia sẻ sở hữu hay không.

Giải thuật 03/09/2026 8 phút

Cấp phát nhanh gấp 10 lần malloc bằng một mẹo cũ: arena

malloc/free có phải cách cấp phát duy nhất, chi phí không tránh được? Tôi đo thử: một arena allocator cấp phát bằng cách chỉ tăng một con trỏ — nhanh gấp 10 lần malloc — và giải phóng cả lô 10 triệu đối tượng chỉ bằng một phép reset O(1) thay vì free 44 ms. Đổi lại nó không free lẻ được, chỉ hợp khi các đối tượng chết cùng lúc.

Giải thuật 03/09/2026 10 phút

free() rồi mà RAM không trả về: sự thật về phân mảnh heap

free() xong là bộ nhớ trả về hệ điều hành ngay? Tôi đo thử: sau khi free 90% của 4 triệu ô nhỏ, RSS vẫn giữ 655 MB trong khi dữ liệu sống chỉ 55 MB — gấp 12 lần. Tệ hơn, những hố nhỏ rời rạc không lấp được request lớn hơn: cấp lại các ô 512B làm heap phình thêm 563 MB, còn cùng cỡ thì tái dùng đúng hố, +0 MB.

Giải thuật 03/09/2026 9 phút

CPU sắp lại thứ tự bộ nhớ thật — 11 lần trong 60 triệu vòng, hiếm tới mức test không bao giờ bắt được

Tưởng CPU luôn chạy theo thứ tự mình viết, còn reorder bộ nhớ chỉ là lý thuyết trong sách? Tôi đo litmus store-buffer trên ARM: reorder xảy ra thật (11 ca trong 60 triệu vòng), rào dmb ish dập được về 0. Nhưng nó hiếm tới ~1 trên 5,5 triệu vòng — nên code sai vẫn qua sạch mọi test rồi nổ ở production.