Memory allocator showdown

Jane Street · 2020 · 3. Quy mô lớn · Độ khó: Khó — bài gốc

Bối cảnh

OCaml 4.10 thêm allocator best-fit bên cạnh allocator mặc định next-fit. Jane Street chuyển sang best-fit và thấy cải thiện lớn, nhưng bài kể cái khó là chứng minh điều đó.

Một benchmark chạy chậm đi khi đổi allocator (34,3 s → 36,1 s). Đo thêm bộ nhớ thì thấy best-fit chậm hơn chút nhưng dùng ít bộ nhớ hơn.
Trong ngôn ngữ có GC, GC chọn lúc giải phóng, nên hiệu năng không phải một điểm (bộ nhớ, thời gian) mà là một đường cong. Họ quét tham số space_overhead từ 20 tới 320 (1/4 tới 4 lần mặc định 80): với mỗi điểm next-fit đều có một điểm best-fit vừa nhanh hơn vừa nhỏ hơn, kể cả trên benchmark tệ nhất của best-fit.
Ở cấu hình mặc định, best-fit đứng ở điểm thiên về tiết kiệm bộ nhớ hơn, vì space_overhead không tính phân mảnh.
Đo bộ nhớ bằng RSS chứ không bằng top_heap_size: số sau bị lượng tử hoá (heap tăng theo khối lớn) và đếm cả phần heap chưa dùng. Next-fit bám khối trống cuối heap và dùng hết nó; best-fit lấp lỗ trước nên RAM thật dùng ít hơn mức heap cho thấy.
Đường cong lấy từ một mô hình 3 tham số H = b/(t−a) + c: a là thời gian tối thiểu nếu không GC (best-fit cấp phát nhanh hơn), c là bộ nhớ tối thiểu nếu GC liên tục (best-fit phân mảnh ít hơn), b là hình dạng ở giữa.

So một điểm mặc định với một điểm mặc định có thể cho kết luận ngược (best-fit "chậm hơn") vì hai allocator chọn điểm khác nhau trên đường đánh đổi.

Với runtime có GC, so sánh thay đổi hiệu năng phải quét tham số GC và so đường cong, không so một cặp số.
Chọn thước đo bộ nhớ cẩn thận: số do runtime báo có thể che phần cải thiện thật.