Một Vài Nỗ Lực Cải Thiện Hiệu Năng Xử Lý Phép Toán Vector Trong Lua

Anonymous trong Thực Hiện và Phát Triển Web

2018-01-01 Khoảng 1100 từ 5 phút

Khi thực hiện các phép toán vector/matrix thuần túy bằng Lua trong các tình huống đòi hỏi hiệu năng cao thường không thể đáp ứng yêu cầu. Ngay cả khi đóng gói thành thư viện C, phương pháp truyền thống vẫn còn nhiều bất cập. Nếu mỗi đối tượng vector đều được bao bọc dưới dạng userdata, tỷ lệ dữ liệu hữu ích so với chi phí quản lý rất thấp. Một vector float 4 chiều chỉ chiếm 16 byte bộ nhớ, trong khi userdata lại yêu cầu thêm 40 byte phụ trợ. Đối với ma trận float 4x4 cũng chỉ lớn hơn chút đỉnh với 64 byte. Chưa kể gánh nặng GC do hàng loạt đối tượng tạm thời sinh ra trong quá trình tính toán.

Việc sử dụng lightuserdata giúp giảm tiêu hao bộ nhớ, nhưng lại gây khó khăn nghiêm trọng trong quản lý vòng đời đối tượng. Khác với khả năng sử dụng bộ nhớ stack trong C hoặc cơ chế RAII của C++, việc API trở nên rườm rà khi tích hợp với Lua là điều khó tránh.

Tôi từng băn khoăn về độ phân giải khi cung cấp các phép toán vector ở tầng Lua liệu có quá mịn. Qua thời gian suy nghĩ và thử nghiệm phương án mới đây, tôi đã đạt được kết quả khả quan. Ứng dụng của tôi là một engine game 3D xây dựng theo kiến trúc ECS (Entity-Component-System), tạo nền tảng vững chắc cho tối ưu hóa phép toán vector. Nhờ cơ chế quản lý thành phần và hệ thống xử lý theo chu kỳ, việc kiểm soát vòng đời đối tượng trở nên đơn giản hơn nhiều.

Trong engine game, các phép toán vector chủ yếu phục vụ hai mục đích:

Đối tượng tạm thời - Thường xuất hiện khi xử lý logic như ma trận 3x3, vector3/vector4
Trạng thái không gian - Các đối tượng cần lưu trữ ma trận transform (vị trí, góc quay, tỷ lệ)

Mặc dù kích thước vector/matrix vượt quá độ rộng từ dữ liệu hệ thống, chúng vẫn nên được xem như kiểu giá trị chứ không phải kiểu tham chiếu. Điều này tương tự như việc Lua xử lý chuỗi: ngữ nghĩa kiểu giá trị nhưng được hiện thực hóa dưới dạng kiểu tham chiếu.

Trong thiết kế thư viện, ngay cả khi hỗ trợ phép toán A *= B, việc ghi đè kết quả trực tiếp lên vùng nhớ của A cũng không khả thi do bản chất tham chiếu của đối tượng. Điều này giống với việc A = "hello"; A = A .. " world" - chuỗi mới được tạo ra thay vì sửa đổi chuỗi gốc.

Lua cung cấp ba kiểu dữ liệu có thể tận dụng để đóng gói kiểu giá trị phức hợp:

number (sử dụng làm ID)
lightuserdata (con trỏ thô)
string (đóng gói dữ liệu nhị phân)

Tôi từng cân nhắc dùng string.pack để nén vector/matrix, nhưng hiệu quả không hơn userdata là bao. Lightuserdata quá rủi ro do thiếu kiểm soát vòng đời. Cuối cùng, lựa chọn hợp lý nhất là sử dụng ID số học.

Từ phiên bản Lua 5.3 trở đi, khả năng lưu trữ số nguyên 64-bit giúp tạo ra các ID duy nhất dễ dàng. Kết hợp với cơ chế đánh version + số thứ tự theo từng frame, việc xác định ID rác trở nên đơn giản và an toàn hơn so với dùng con trỏ.

Động lực chính của phương án này xuất phát từ đặc điểm xử lý theo từng frame của game:

Dữ liệu không được lưu lại xuyên frame sẽ tự động hết hiệu lực
Sử dụng ID frame + số thứ tự để tạo khóa duy nhất
Quản lý dữ liệu bằng mảng liên tục giúp truy cập O(1)
Kết thúc frame chỉ cần đặt lại con trỏ ngăn xếp

Các phép toán vector/matrix được thực hiện thông qua một ngăn xếp dữ liệu độc lập, giảm thiểu tương tác Lua-C. Lấy ví dụ phép toán “nhân ma trận rồi lấy nghịch đảo”:

1

command(mat1, mat2, "*~")  -- mat1 * mat2 rồi lấy nghịch đảo

Quy trình xử lý:

Đẩy mat1 và mat2 vào ngăn xếp
Lệnh * lấy hai đỉnh ngăn xếp, nhân ma trận, đẩy kết quả vào
Lệnh ~ lấy đỉnh ngăn xếp, tính nghịch đảo, đẩy lại vào

Các lệnh xử lý ngăn xếp bao gồm:

P - Lấy ID từ đỉnh ngăn xếp trả về Lua
V - Trả con trỏ lightuserdata đến dữ liệu (có hiệu lực trong frame hiện tại)
T - Chuyển đỉnh ngăn xếp thành bảng Lua để debug
R - Loại bỏ đỉnh ngăn xếp
D - Sao chép đỉnh ngăn xếp
M - Chuyển đối tượng tạm thành đối tượng bền vững, trả ID mới

Để tối ưu hiệu năng, hệ thống phân tách rõ ràng:

Khu vực tạm thời - Quản lý bằng ngăn xếp liên tục, reset toàn bộ sau mỗi frame
Khu vực bền vững - Quản lý bằng danh sách rảnh (freelist)

Khi cần bảo tồn một giá trị, chỉ cần sử dụng lệnh M để chuyển từ khu vực tạm sang khu vực bền vững. Việc loại bỏ tính bền vững thông qua thao tác “wish freelist”, sau đó hợp nhất với freelist thật khi kết thúc frame.

Cơ chế này đặc biệt hữu dụng trong biểu thức:

1

local a = command(a, b, "*M")  -- a = a * b

Dù a trước đó có phải giá trị bền vững, nó sẽ bị đánh dấu hết hiệu lực. Nếu b là hằng số cần bảo tồn, có thể truyền ID âm:

1

local a = command(a, -b, "*M")  -- Giữ nguyên tính bền vững của b

Hiện tại tôi đã triển khai xong bản thử nghiệm, sẽ được tích hợp vào engine game 3D của chúng tôi. Phiên bản hoàn chỉnh và tài liệu chi tiết sẽ được công bố khi engine open-source.