Lập trình Go 22/09/2026 11 phút

Allocator ba tầng của Go: mcache, mcentral, mheap và vì sao cấp phát nhỏ không cần khoá

Go cấp phát bộ nhớ qua ba tầng như tcmalloc: mcache mỗi P không khoá, mcentral có khoá, mheap khoá heap. Đo thật: cấp đối tượng nhỏ song song còn nhanh hơn một luồng (mcache per-P), cấp lớn song song chậm gấp 3 vì tranh khoá mheap. Và tiny allocator gộp đối tượng nhỏ. Go 1.23.

Lập trình 22/09/2026 7 phút

Heap và bài toán top-k: vì sao lấy 10 phần tử lớn nhất lại nhanh hơn sắp xếp 247 lần

Cần 10 phần tử lớn nhất từ 8 triệu? Sắp xếp cả mảng rồi lấy 10 đầu là cách ai cũng nghĩ tới — và là cách sai. Bài này đo thật trong go-lab: min-heap size k lấy top-10 trong 4,3 ms, còn full sort mất hơn 1 giây — nhanh hơn 247 lần. Kèm cơ chế heap làm hàng đợi ưu tiên với Push/Pop O(log n), nền tảng của Dijkstra và lập lịch.

Lập trình 22/09/2026 8 phút

Dijkstra với heap: vì sao đổi cách tìm đỉnh gần nhất biến 3,5 giây thành 17 mili giây

Dijkstra tìm đường đi ngắn nhất, nhưng tốc độ của nó phụ thuộc vào một chi tiết: tìm đỉnh gần nguồn nhất bằng cách nào. Bài này đo thật trong go-lab: bản quét mảng O(V²) mất 3,55 giây trên đồ thị thưa 50.000 đỉnh, còn bản dùng heap O((V+E)log V) chỉ 16,9 ms — nhanh hơn 210 lần, cùng kết quả. Nhưng trên đồ thị dày, bản mảng lại cạnh tranh.