Chiếc Heap Lisp Đơn Lẻ: Hành trình tối ưu hóa bộ nhớ từ con số không

Chiếc Heap Lisp Đơn Lẻ: Hành trình tối ưu hóa bộ nhớ từ con số không

Giống như nhiều ngôn ngữ động khác, Lone - một dự án trình thông dịch Lisp - ban đầu bắt đầu rất đơn giản. Về bản chất, nó là một tập hợp các cấu trúc dữ liệu được viết bằng C, bao gồm các union, cấu trúc giá trị có kiểu (typed value structure) và một ngôn ngữ tùy chỉnh nhằm mục đích kết hợp các giá trị này thành các chương trình hoạt động.

Tuy nhiên, ngôn ngữ này dường như chỉ là phụ phẩm cho công việc xây dựng máy ảo (virtual machine). Lone thực tế không được thiết kế trước, mà được xây dựng trong thời gian thực và phát triển theo độ hiểu biết của người tạo ra nó.

Tự viết bộ cấp phát bộ nhớ (Memory Allocator)

Lone là một trình thông dịch Lisp được viết bằng Freestanding C (môi trường C không có thư viện chuẩn). Điều này đồng nghĩa với việc không có malloc, không có libc, chỉ có mã nguồn. Nếu muốn cấp phát bộ nhớ động, tác giả phải tự viết nó.

Bộ cấp phát đầu tiên hoạt động dựa trên nguyên tắc đơn giản: duyệt qua danh sách liên kết các khối bộ nhớ và tìm khối trống đầu tiên vừa đủ (first-fit).

for (block = system->memory; block; block = block->next)
    if (block->free && block->size >= size)
        break;

Cách tiếp cận này hoạt động nhưng rất lãng phí. Nó có thể trả về một khối 16 KiB cho một yêu cầu chỉ 64 byte. Để cải thiện, tác giả đã thêm cơ chế chia nhỏ (split) khối bộ nhớ khi cấp phát và gộp (coalesce) các khối liền kề khi giải phóng.

Mặc dù bộ cấp phát này "thô sơ" và gây phân mảnh bộ nhớ nghiêm trọng, nhưng nó đã phục vụ Lone được khoảng ba năm. Đó là lúc tác giả nhận ra cần một giải pháp tốt hơn để hỗ trợ bộ thu gom rác (Garbage Collector).

Thách thức với bộ thu gom rác (GC)

Bộ thu gom rác của Lone hoạt động theo kiểu bảo thủ (conservative): nó quét ngăn xếp (stack) và kiểm tra mọi giá trị xem có phải là con trỏ trỏ đến đối tượng Lisp hay không.

Việc so sánh từng từ trong ngăn xếp với mọi con trỏ Lisp sẽ dẫn đến độ phức tạp bậc hai (quadratic time) - một thảm họa về hiệu suất. Giải pháp là tạo ra một "heap" riêng cho các giá trị Lisp.

Thay vì cấp phát từng đối tượng riêng lẻ, Lone mua sắm theo số lượng lớn. Các khối bộ nhớ chứa mảng các giá trị Lisp được đặt cạnh nhau. Điều này giúp GC dễ dàng kiểm tra xem một con trỏ có nằm trong phạm vi hợp lệ hay không chỉ bằng cách so sánh địa chỉ.

Sự "độc tài" của con trỏ

Mảng mang lại hiệu suất cao (thân thiện với cache), nhưng lại có một nhược điểm lớn: khó thay đổi kích thước. Trong thực tế, việc "resize" một mảng thực chất là cấp phát mảng mới, sao chép dữ liệu và hủy mảng cũ.

Vấn đề là tất cả các đối tượng Lisp đều là con trỏ trỏ đến các giá trị bên trong các mảng này. Nếu di chuyển mảng, tất cả các con trỏ đó sẽ trở nên vô hiệu (dangling pointers). Con trỏ lười biếng và cố định tại chỗ, buộc thế giới xung quanh phải thích nghi với chúng.

Giải pháp: Từ con trỏ sang chỉ số (Index)

Để giải quyết vấn đề, tác giả đã thực hiện một thay đổi mang tính nền tảng: Thay vì sử dụng con trỏ, các giá trị Lisp bây giờ là các chỉ số (index) trong mảng heap.

struct lone_lisp_heap_value *
lone_lisp_heap_value_of(struct lone_lisp *lone, struct lone_lisp_value value)
{
    size_t index = /* lấy index từ giá trị */;
    return &lone->heap.values[index];
}

Nhờ đó, các giá trị không còn phụ thuộc vào vị trí vật lý của chúng trong bộ nhớ. Heap bây giờ chỉ là một mảng phẳng lớn (flat array). Lone có thể tự do di chuyển, thay đổi kích thước heap mà không làm hỏng các tham chiếu, vì các chỉ số vẫn giữ nguyên.

Tối ưu hóa với mremap và Cache Line

Với kiến trúc mới, Lone có thể tận dụng các tính năng nâng cao của Linux. Thay vì cấp phát bộ nhớ thông thường, Lone sử dụng mmap để ánh xạ các trang bộ nhớ (pages).

Các giá trị trong heap được căn chỉnh (align) để kích thước là 64 byte - tương đương với một dòng cache (cache line) của CPU. Điều này đảm bảo các giá trị không bao giờ vượt qua ranh giới trang bộ nhớ và tối ưu hóa việc truy cập cache.

Đặc biệt, Linux cung cấp hệ thống gọi mremap, cho phép thay đổi kích thước vùng bộ nhớ đã ánh xạ mà không cần sao chép dữ liệu. Kernel có thể cấu trúc lại bảng trang bộ nhớ (page tables) và di chuyển toàn bộ heap đến một vị trí mới trong bộ nhớ ảo một cách minh bạch.

lone->heap.values = linux_mremap(lone->heap.values,
                                 old_size, new_size,
                                 MREMAP_MAYMOVE);

Kết quả là một chiếc heap Lisp hiệu quả, thân thiện với cache và có thể mở rộng động mà không gây ra sự hỗn loạn của con trỏ hay chi phí sao chép dữ liệu lớn. Từ một bộ cấp phát thô sơ, Lone đã tiến hóa thành một hệ thống quản lý bộ nhớ tinh vi, tận dụng tối đa khả năng của hệ điều hành.