Một Bộ Phân Bổ Con Trỏ Bump
Một Bump Pointer Allocator mới mẻ
Gần đây tôi tranh thủ thời gian rảnh để đọc bản dịch cuốn sách “Game Engine Architecture” của Milo Yip. Quyển sách này hiện vẫn chưa xuất bản chính thức, nhưng do được mời viết lời giới thiệu cho bản dịch tiếng Việt nên tôi đã sớm tiếp cận được phiên bản điện tử. Với độ dày gần 800 trang, tôi đã đọc được khoảng 600 trang và hy vọng sẽ hoàn thành nốt trong cuối tuần này.
Tác phẩm được viết bởi Jason Gregory - một trong những kỹ sư trưởng của đội ngũ Naughty Dog. Nội dung sách cực kỳ phong phú, bản dịch của Milo Yip cũng rất trôi chảy và chuẩn xác. Đọc từng chương, tôi liên tục cảm thấy đồng cảm sâu sắc, do đó muốn chia sẻ một số điểm ấn tượng ngay lập tức.
Vì nền tảng chuyên môn của tác giả chủ yếu nằm ở mảng phát triển game console, nơi mà giới hạn bộ nhớ luôn rất ngặt nghèo (đặc biệt là thiếu vắng cơ chế bộ nhớ ảo), nên các kỹ thuật quản lý bộ nhớ trong sách được trình bày rất tỉ mỉ. Nhiều vấn đề mà các nền tảng PC thường bỏ qua, khi chuyển sang môi trường console lại trở thành thách thức lớn. Điều này khiến tôi nhớ lại hơn mười năm trước, khi phát triển game Đại Thoại Tây Du, chúng tôi cũng phải vận hành hệ thống trong giới hạn 64MB bộ nhớ. Tôi đã từng viết hàng loạt công cụ quản lý bộ nhớ đặc biệt để đáp ứng yêu cầu khắt khe đó.
Ví dụ như kỹ thuật quản lý bộ nhớ mô phỏng stack - tức là cấp phát bộ nhớ theo cấu trúc ngăn xếp trên heap, chỉ cần ghi nhớ một mốc đánh dấu để giải phóng hàng loạt sau này. Hay như thiết kế bộ phân phối hai đầu (dual-end allocator), trong đó tự quản lý một vùng nhớ lớn và phân bổ từ hai đầu hướng vào giữa theo nhu cầu khác nhau. Thậm chí có thể kết hợp đồng thời nhiều kỹ thuật với nhau để tối ưu hiệu quả.
Một kỹ thuật nữa là ràng buộc vòng đời đối tượng với từng khung hình render. Sau mỗi frame, toàn bộ bộ nhớ tạm thời của khung hình đó sẽ được giải phóng. Tinh vi hơn, chúng tôi từng xây dựng cơ chế “ping-pong” để giữ lại vùng nhớ tạm sang đến cuối frame kế tiếp. Những kỹ thuật này đều đã được tôi áp dụng thực tế trong giai đoạn phát triển game.
Đặc biệt vào năm 2004, tại NetEase đã tổ chức một cuộc thi nội bộ nhằm xây dựng trình quản lý bộ nhớ tối ưu trên một vùng nhớ cố định. Dữ liệu thi đấu được lấy trực tiếp từ các dự án Đại Thoại Tây Du và Mộng Hoàn Tây Du. Các bài dự thi được chấm điểm dựa trên tốc độ xử lý và tỷ lệ phân mảnh. Dù không trực tiếp tham gia, tôi đã thử viết một chương trình và đạt điểm cao nhất thời điểm đó. Ba thí sinh đạt giải cao nhất sau này đều trở thành kỹ sư trưởng của các dự án lớn tại NetEase hoặc các công ty mới rời ra.
Ngày nay, khi phát triển game trên nền tảng PC, phần lớn chúng ta đều sử dụng trực tiếp các thư viện trưởng thành như jemalloc mà ít quan tâm đến tối ưu cấp thấp này. Chỉ đến khi chuyển sang phát triển iOS gần đây, tôi mới cùng đồng nghiệp thảo luận lại các vấn đề quản lý bộ nhớ trên thiết bị giới hạn. Chúng tôi đã thiết kế một trình phân bổ đặc biệt dành riêng cho Lua trên iOS, kết hợp dữ liệu thực tế từ dự án để tối ưu hiệu quả, kết quả đạt được rất khả quan.
Trong sách, tác giả tiết lộ Naughty Dog áp dụng kỹ thuật sử dụng “handle” thay vì con trỏ địa chỉ vật lý để truy xuất đối tượng trong hệ thống quản lý tài nguyên. Nhờ đó, mọi khối nhớ có thể được di chuyển tự do mà không ảnh hưởng đến tham chiếu. Cơ chế handle giúp giải quyết triệt để vấn đề định vị lại con trỏ khi có sự thay đổi địa chỉ.
Hệ thống còn tích hợp tính năng dọn dẹp bộ nhớ thông minh, tận dụng khoảng trống xử lý khi máy rảnh để nén các khối nhớ đã giải phóng, tiến tới mục tiêu tỷ lệ phân mảnh bằng 0. Hiệu suất cache đạt mức tối ưu đáng kinh ngạc.
Nếu tất cả module trong engine đều do nhóm phát triển tự xây dựng, thì giải pháp này thực sự hoàn hảo. Được biết engine của Naughty Dog đã đạt được điều này. Ngay cả khi sử dụng library bên thứ ba, việc lựa chọn kỹ lưỡng và tùy chỉnh trình phân bổ phù hợp cũng giúp hệ thống vận hành mượt mà.
Tôi từng nghĩ đến giải pháp này nhưng chưa bao giờ thử nghiệm thực tế. Ngay khi đọc đến phần này trong sách, tôi cảm thấy hứng thú tột độ. “Talk is cheap, show me the code” - theo đúng tinh thần này, tôi đã dành thời gian viết một đoạn mã đơn giản để hiện thực hóa Bump Pointer Allocator như mơ tả.
Thư viện này có thể quản lý một vùng nhớ đã định trước, chia nhỏ theo nhu cầu sử dụng. Mỗi khối nhớ được đánh dấu bằng ID duy nhất (không tái sử dụng cho đến khi vòng 32-bit lặp lại), giúp người dùng dễ dàng nhận biết một ID đã vô hiệu hay chưa - tương đương cơ chế tham chiếu yếu (weak reference). Việc ánh xạ từ ID sang địa chỉ chỉ tốn O(1), cực kỳ hiệu quả mà không cần dịch chuyển bộ nhớ trừ khi có yêu cầu rõ ràng về phân tích lại.
Thời gian cấp phát và giải phóng bộ nhớ đều đạt độ phức tạp O(1), chỉ trong một số trường hợp đặc biệt mới suy biến thành O(n). Toàn bộ quá trình phân tích lại bộ nhớ có thể được điều chỉnh để thực hiện theo từng frame cố định. Mặc dù cần tạm dừng toàn bộ hệ thống (stop the world), nhưng đảm bảo hoàn thành ít nhất một bước trong thời gian giới hạn (trừ trường hợp có khối nhớ đơn lẻ quá lớn).
Mỗi khối nhớ hỗ trợ đếm tham chiếu, kết hợp cùng cơ chế tham chiếu yếu giúp lập trình viên dễ dàng tránh được các vấn đề vòng lặp tham chiếu.
Dự án vẫn còn nhiều điểm có thể cải tiến: hỗ trợ đa luồng, thiết lập một