Trình Thu Gom Rác Plush Tăng Tốc Ấn Tượng: Từ 117ms Xuống 7ms Nhờ Thuật Toán Cheney Cổ Điển

Plush, một ngôn ngữ lập trình dạng Lox do tác giả tự phát triển, vừa có một bước nhảy vọt về hiệu năng thu gom rác (GC) nhờ việc thay thế HashMap bằng thuật toán Cheney với forwarding pointer. Kết quả là thời gian thu gom 1 triệu đối tượng sống giảm từ 117ms xuống còn 7ms, vượt xa mục tiêu 20ms ban đầu. Ngoài ra, tác giả còn áp dụng kỹ thuật mmap để tối ưu bộ nhớ và loại bỏ giới hạn kích thước message.

Vấn Đề Hiệu Năng và Sự Thay Đổi Đơn Giản Nhưng Hiệu Quả

Khi phát triển trình thu gom rác cho Plush, một ngôn ngữ có kiến trúc song song dựa trên actor, tác giả ban đầu triển khai theo cách sử dụng HashMap để theo dõi mối quan hệ giữa các đối tượng và bản sao của chúng. Điều này nhằm mục đích tái sử dụng thuật toán cho cả việc gửi message giữa các actor mà không làm thay đổi dữ liệu của sender.

Tuy nhiên, hiệu năng không như mong đợi: thời gian thu gom cho 1 triệu đối tượng là khoảng 117ms trên MacBook Air M5. Nguyên nhân chính được đồng nghiệp Laurent Huberdeau chỉ ra là Rust HashMap mặc định sử dụng hàm băm bảo mật (để chống tấn công HashDoS), điều này làm giảm hiệu suất đáng kể.

"Tôi đã không nhận ra rằng HashMap của Rust mặc định dùng secure hashing function, và điều này đã ảnh hưởng đến hiệu suất."

Việc thay thế bằng FxHashMap từ crate rustc_hash (một bản thay thế trực tiếp) cùng với việc loại bỏ một lần tra cứu dư thừa đã giúp GC nhanh hơn gấp đôi, đạt 43ms.

Giới Hạn Của HashMap và Quyết Định Quay Lại Với Cheney

Dù đã cải thiện, nhưng bản thân HashMap vẫn là một cấu trúc dữ liệu không phù hợp cho GC bởi vì:

• Bảng băm chiếm nhiều dung lượng hơn dữ liệu sống cần sao chép
• Hàm băm tạo ra phân bố ngẫu nhiên, gây cache miss nghiêm trọng do truy cập bộ nhớ không theo trật tự
• Cần duyệt lại toàn bộ bảng băm để cập nhật con trỏ, khiến mọi thứ chậm hơn

Tác giả nhận ra rằng việc sử dụng forwarding pointer (theo thuật toán Cheney truyền thống) là giải pháp tối ưu hơn, đặc biệt khi kết hợp với một danh sách để hoàn tác các thay đổi trong trường hợp gửi message. Kết quả là thời gian GC giảm xuống còn 7ms, nhanh gấp 16.7 lần so với ban đầu và thấp hơn nhiều so với mục tiêu 20ms.

Kỹ Thuật mmap Thông Minh: Quản Lý Bộ Nhớ Linh Hoạt

Ngoài việc tăng tốc GC, tác giả còn giải quyết vấn đề giới hạn 16MB cho message allocator bằng kỹ thuật mmap. Thay vì cấp phát bộ nhớ vật lý ngay lập tức, kỹ thuật này sử dụng MAP_PRIVATE | MAP_ANONYMOUS với PROT_NONE để dự trữ một vùng địa chỉ ảo lớn (có thể lên tới 512GB), sau đó dùng mprotect để mở quyền truy cập khi cần.

Điều này cho phép:

• Thay đổi kích thước bộ nhớ linh hoạt mà không làm mất hiệu lực con trỏ
• Không cần phối hợp giữa các actor khi gửi message lớn
• Giảm RSS vì các trang chưa được sử dụng không chiếm RAM vật lý

Một chương trình đơn giản với 2000 actor chỉ tiêu tốn 224MB RSS và khởi động trong 0.23 giây, và chương trình không có actor nào chỉ mất 9.6MB RSS.

Kết Luận và Hướng Phát Triển Tiếp Theo

Bài viết nhấn mạnh rằng thuật toán Cheney từ năm 1970 vẫn là lựa chọn tối ưu cho bộ nhớ và hiệu suất khi so sánh với cấu trúc dữ liệu phụ trợ như HashMap. Điều này cho thấy tầm quan trọng của cache efficiency và các mẫu truy cập bộ nhớ có thể dự đoán được.

Trong tương lai, tác giả dự định tiếp tục cải thiện Plush bằng cách:

• Chuyển sang tagging scheme để giảm kích thước Value type từ 16 byte xuống còn 8 byte
• Thử nghiệm với register-based interpreter thay vì stack-based
• Khám phá khả năng dùng LLM để viết JIT compiler cho Plush

Tác giả cũng đặt ra câu hỏi thú vị về việc so sánh GC copying với mark-and-sweep GC — một thử nghiệm mà độc giả có thể tự thực hiện bằng cách chạy các benchmark đã được thêm vào repository của dự án.

Plush GC benchmark