Biên Dịch Thời Gian Thực Các Phép Toán Và Vài Mẹo Vặt Tinh Vi Trong Lua

2018-07-01 Khoảng 1000 từ 5 phút

Nội dung

Thư viện vector mà tôi thiết kế cho dự án 3D engine đã vận hành được một thời gian. Trong quá trình sử dụng, tôi liên tục tối ưu hóa và cải tiến. Từ đầu, tôi xác định rõ yêu cầu cốt lõi là giảm thiểu chi phí tương tác giữa Lua và C, đồng thời tăng tính kết dính của hệ thống. Về mặt dễ sử dụng, tôi dự kiến sẽ xây dựng lớp bao bọc phía trên.

Hiện tôi đang tập trung nghiên cứu cách tự nhiên nhất để chuyển đổi từ biểu thức toán học sang dòng lệnh hậu tố của thư viện. Hướng nghiên cứu có hai:

Xây dựng ngôn ngữ nhỏ (mini language) sử dụng chuỗi ký tự để biểu diễn các biểu thức
Tận dụng cơ chế phân tích cú pháp sẵn có của Lua để dịch một hàm Lua thành dòng lệnh toán học tương ứng

Cả hai hướng đều có thể coi là quá trình biên dịch JIT - dịch thuật toán thành dòng lệnh có thể xử lý bởi C hoặc thư viện toán học hiện có khi chạy lần đầu. Hoặc cũng có thể thêm giai đoạn tiền xử lý nguồn Lua để biên dịch AOT (Ahead-Of-Time).

Yêu cầu này được chia thành ba bài toán:

Kết nối mã nguồn thân thiện với mã Lua bản địa
Biến đổi thành dòng lệnh toán học chính xác
Quyết định tích hợp theo kiểu JIT hay AOT

Sau khi cân nhắc, tôi nhận ra có thể tận dụng những tính năng đặc biệt của Lua để tránh việc tự xây dựng ngôn ngữ mới. Chẳng hạn với biểu thức a * b * c:

Cách viết thông thường đòi hỏi 2 lần gọi hàm nhân, mỗi lần đều có chi phí chuyển giao giữa Lua-C
Phép nhân vector thường được cài đặt bằng C, nhưng việc nạp chồng toán tử * qua metamethod lại làm phát sinh chi phí kích hoạt meta
Kết quả trung gian (từ a * b) là đối tượng tạm không được thu gom ngay, tạo gánh nặng cho GC

Thay vì vậy, nếu đóng gói toàn bộ thành một đối tượng toán tử tổng thể (gồm 3 đầu vào a,b,c và một biểu thức lambda), ta chỉ cần một lần tương tác Lua-C duy nhất, loại bỏ hoàn toàn chi phí meta và quản lý được các đối tượng tạm trong môi trường C.

Tuy nhiên tồn tại thách thức: Các biến a,b,c có thể là local hoặc upvalue trong ngữ cảnh Lua, nhưng hàm C không thể truy cập trực tiếp các giá trị này. Giải pháp là truyền tham số tường minh, yêu cầu hàm C phải có nguyên mẫu function(a,b,c).

Vì vậy, cách viết tự nhiên nhất:

1
2
3


...
v = a * b * c
...

phải được chuyển thành:

1
2
3


...
v = lambda(function() return a * b * c end)
...

Ở đây, biểu thức được đóng gói trong hàm và xử lý bởi lambda. Về bản chất, đây là mô hình tương tự các công cụ mở rộng cú pháp như MoonScript hay TypeScript, nhưng thực hiện ở giai đoạn tiền xử lý.

Cơ chế phân tích biểu thức toán học

Với hàm function() return a * b * c end, làm thế nào để biết chính xác gì đang xảy ra? Câu trả lời nằm ở việc xây dựng kiểu dữ liệu phân tích đặc biệt để ghi lại quá trình xử lý. Dưới đây là ví dụ minh họa:

1
2
3
4
5
6
7


local lambda_object_mt = {}
local function lambda_object(name)
  return setmetatable({ expression = name }, lambda_object_mt)
end 
function lambda_object_mt.__mul(a,b)
  return lambda_object(a.expression .. "*" .. b.expression)
end

Khi thay thế các tham số bằng lambda_object, phép toán không được thực thi mà biểu thức được ghi lại vào object.expression. Dưới đây là hàm lambda hoàn chỉnh:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


local function lambda(func)
  local info = debug.getinfo(func,'u')
  local n = info.nups
  assert(info.nparams == 0 and not info.isvararg and n > 0)
  local func_gen = lambda_gen[n]
  local call_lambda = func_gen()
  for i = 1, n do
    debug.upvaluejoin (call_lambda, i+1, func, i)
  end
  local dummy = func_gen()
  for i = 1, n do
    debug.upvaluejoin (func, i, dummy, i)
    local name = debug.getupvalue(func, i)
    debug.setupvalue(func, i, lambda_object(name))
  end
  local lambda_object = func()
  local lambda_func = gen_lambda(lambda_object.expression)
  debug.setupvalue(call_lambda, 1, lambda_func)
  return call_lambda
end

Hạn chế và mở rộng

Hàm toán học cần tuân thủ:

Không có tham số, chỉ sử dụng upvalue để truy cập dữ liệu
Không gọi hàm bên ngoài (không tham chiếu đến _ENV)
Hỗ trợ biểu thức phức tạp với biến tạm: local temp = a*b; return temp*temp
Ngoại lệ cho toán tử đặc biệt: a:cross(b) cho tích chéo, a:normalize() cho chuẩn hóa

Biến đổi biểu thức thành dòng lệnh

Đây là phần phức tạp nhất: Biến đổi chuỗi các phép toán (không có rẽ nhánh) thành dòng lệnh dựa trên ngăn xếp hoặc thanh ghi. Các bước chính:

Gán nhãn cho mọi giá trị trung gian
Xác định quan hệ phụ thuộc để sắp xếp topo
Tối ưu việc sao chép/xóa giá trị trên ngăn xếp dựa trên tần suất sử dụng

Ví dụ với a*b*c:

Nếu a,b,c chỉ dùng 1 lần: push a, push b, multiply -> ab; push c, multiply -> ab*c
Nếu b được dùng lại: push b, duplicate, ...

Tối ưu biên dịch

Để tránh biên dịch lặp lại, sử dụng caching theo prototype function. Trong Lua, mỗi closure có con trỏ đến prototype của nó. Dù không thể truy cập trực tiếp qua API công khai, ta có thể dùng đoạn mã C sau:

1
2
3
4
5
6
7


static int
lproto(lua_State *L) {
  if (!lua_isfunction(L, 1) || lua_iscfunction(L,1))
    return 0;
  const LClosure *c = lua_topointer(L,1);
  lua_pushlightuserdata(L, c->p);
  lua_pushinteger(L