Nguyên Lý Hoạt Động Của Lua GC

Luận lý của Lua GC
Lần cuối cùng tôi viết về Lua GC trên blog là vào năm 2011, thời điểm Lua 5.2 chưa chính thức ra mắt. Tôi luôn cho rằng việc nghiên cứu kỹ mã nguồn mở chất lượng cao là hoạt động rất đáng đầu tư, tuy nhiên việc ghi chép lại quá trình nghiên cứu đó lại mang ít giá trị thực tế. Việc thay người khác nhai lại thông tin vừa tốn công mà khó làm vừa lòng tất cả, bởi mỗi người có nền tảng kỹ thuật khác nhau. Nếu viết chi tiết quá sẽ phí thời gian đọc, viết sơ lược lại khiến người đọc khó nắm được mạch. Việc đọc từng dòng mã vốn đã là công việc nặng nhọc, chỉ cần tập trung thì ai cũng làm được. Muốn tiết kiệm thời gian nhờ người khác giải thích thay, thường là không khả thi. Vì vậy cuốn sách “Chiêm ngưỡng mã nguồn Lua” của tôi đến nay vẫn còn nằm trên giấy.

Quá sa đà vào từng chi tiết mã nguồn dễ rơi vào tình trạng “vừa thấy lá chắn tầm nhìn”, ngược lại việc nắm bắt tư tưởng của tác giả lại có cái nhìn toàn cảnh hơn. Tại hội thảo Lua Workshop năm nay, chuyên gia Roberto Ierusalimschy - kiến trúc sư chính của Lua - đã trình bày bài giảng “Garbage collection in Lua”, phân tích rõ tiến trình phát triển các thuật toán thu gom rác qua các phiên bản. Dù tôi không trực tiếp tham dự buổi diễn thuyết này, nhưng qua việc nghiên cứu slide kết hợp mã nguồn là đủ hiểu bản chất. Bài viết hôm nay sẽ chia sẻ góc nhìn của riêng tôi. Xin lưu ý rằng: Tôi đã bổ sung nhiều quan điểm cá nhân, rất có thể đã lệch lạc với nguyên ý ban đầu. Bài viết này hoàn toàn thể hiện góc độ cá nhân.

Hầu như mọi ngôn ngữ lập trình hiện đại ngày nay đều trang bị cơ chế quản lý bộ nhớ tự động. Khi bộ nhớ không còn được sử dụng, hệ thống sẽ tự động giải phóng. Có hai phương pháp chính thực hiện việc này: đếm tham chiếu (reference counting) và thu gom rác (garbage collection). Mặc dù vấn đề vòng tham chiếu khiến đếm tham chiếu không thể tự động giải phóng các đối tượng vô dụng, đây không phải lý do chính khiến Lua chọn lựa cơ chế thu gom rác. Lý do cốt lõi nằm ở chi phí tính toán: với ngôn ngữ động, overhead do đếm tham chiếu gây ra quá lớn, ngay cả khi chương trình không hề cấp phát bộ nhớ mới, hệ thống vẫn phải gánh chi phí này. Một ví dụ tương đồng là Python - ngôn ngữ dựa trên đếm tham chiếu để quản lý bộ nhớ, khiến hiệu suất của trình thông dịch Python bị ảnh hưởng đáng kể.

Lấy Lua làm ví dụ, các đối tượng runtime hoặc tồn tại trong bảng (table) được gián tiếp tham chiếu từ registry, hoặc nằm trên stack thực thi (về mặt cấu trúc, registry tham chiếu đến thread chính, stack nằm trong cấu trúc thread). Khi một đối tượng được tham chiếu từ table, với cơ chế thu gom rác tăng dần (incremental GC), cần có hàng rào Barrier để duy trì trạng thái khả kiến (visibility) của đối tượng - chi phí tương đương với việc tăng đếm tham chiếu. Tuy nhiên khi loại bỏ đối tượng khỏi table, không cần thực hiện thao tác giảm đếm tham chiếu như trước. Có thể coi trong trường hợp này, chi phí đếm tham chiếu chỉ gấp đôi chi phí của thu gom rác. Vấn đề hiệu năng thực sự nằm ở thao tác với các đối tượng trên stack. Không chỉ các lời gọi và trả về hàm truyền đối tượng qua các frame stack, mà mọi đoạn mã đều liên tục di chuyển đối tượng trên stack. Với phần lớn ngôn ngữ tĩnh, có thể thông qua phân tích tĩnh để chèn các thao tác tăng/giảm tham chiếu ở vị trí cần thiết, sau đó dùng trình biên dịch tối ưu bỏ những thao tác không cần thiết. Ví dụ như cơ chế RAII của C++ hay ARC của Objective-C đều áp dụng phương pháp này. Tuy nhiên với Lua, việc này làm tăng đáng kể độ phức tạp của trình thông dịch, ngay cả khi có thể sinh mã tương tự, chi phí vận hành vẫn không thể bỏ qua. C++ có thể loại bỏ hầu hết overhead RAII thông qua inline function, nhưng kỹ thuật này không khả thi với ngôn ngữ động như Lua.

Chính vì lý do overhead này, Lua chọn thu gom rác thay vì đếm tham chiếu. Bộ thu gom rác không trực tiếp xử lý việc cấp phát/giải phóng bộ nhớ, chức năng底层 này được thực hiện qua bộ phân bổ (allocator) do người dùng cung cấp khi khởi tạo máy ảo Lua. Trong quá trình vận hành, mọi đối tượng được tạo ra đều được liên kết thành danh sách, các đối tượng còn được tham chiếu gián tiếp từ tập gốc (root set) sẽ được giữ lại, những đối tượng không còn khả năng truy cập sẽ được thu hồi vào thời điểm thích hợp. Tập gốc của máy ảo bao gồm registry, các metatable của kiểu dữ liệu nguyên sinh, bảng toàn cục, thread chính, mã thư viện chuẩn… đều được registry tham chiếu.

Trước Lua 5.0, thuật toán thu gom rác sử dụng rất đơn giản: đánh dấu và quét. Quá trình bắt đầu từ tập gốc, đánh dấu các đối tượng có thể truy cập được là đối tượng sống, sau đó duyệt toàn bộ danh sách đối tượng đã cấp phát qua allocator, xóa bỏ những đối tượng không được đánh dấu.

Tuy nhiên từ Lua 5.0 trở đi, khi hỗ trợ userdata với phương thức __gc, đơn giản quét một lượt không còn khả thi. Nếu không xử lý đúng cách, các userdata chết sẽ bị loại bỏ ngay, không kịp chạy __gc. Thuật toán đánh dấu do đó phải thực hiện làm hai giai đoạn: đầu tiên loại bỏ các đối tượng chết (kể cả userdata), sau đó tìm lại các userdata có phương thức __gc trong số này, tiến hành đánh dấu lại các đối tượng liên quan để đảm bảo userdata có thể chạy __gc đúng lúc. Các userdata sau khi xử lý __gc sẽ được giải phóng ở chu kỳ GC tiếp theo (nếu không được “hồi sinh” trong __gc). Mỗi userdata có một cờ đơn hướng xác định __gc đã được thực thi hay chưa, đảm bảo phương thức này chỉ chạy duy nhất một lần, dù userdata có được hồi sinh (tham chiếu lại từ tập gốc). Nói cách khác, userdata đã chạy finalizer sẽ vĩnh viễn trở thành userdata không còn finalizer.

Hiệu năng của GC ảnh hưởng trực tiếp đến toàn bộ hệ thống. Ví dụ như Go trong giai đoạn đầu từng bị chỉ trích gay gắt vì vấn đề của GC. Nếu tắt GC hoàn toàn, CPU không tốn overhead nhưng bộ nhớ sẽ tăng không kiểm soát; nếu mỗi lần cấp phát lại chạy GC, bộ nhớ không tốn nhưng hiệu năng CPU sẽ tụt thảm hại (hiện Lua vẫn giữ macro kiểm thử GC bằng cách chạy liên tục full GC). Lua 5.0 dùng giải pháp trung hòa: cứ khi bộ nhớ cấp phát vượt