Tối Ưu Hóa Bảng Hằng Số Trong Lua

2016-04-01 Khoảng 600 từ 3 phút

Hôm nay tôi đã dành cả ngày để nghiên cứu một cải tiến nhỏ cho máy ảo Lua. Trong phiên bản hiện tại, Lua lưu trữ một bảng hằng số trong cấu trúc prototype của hàm, chứa các hằng số thuộc kiểu string, number, nil và boolean. Tuy nhiên, các bảng (table) không được hỗ trợ tính hằng số, dẫn đến một số vấn đề hiệu năng khi sử dụng.

Chẳng hạn, khi bạn viết:

1

for _, v in ipairs { "one", "two", "three" } do

Mỗi lần vòng lặp chạy, Lua sẽ phải xây dựng một bảng tạm thời và lần lượt chèn các giá trị “one”, “two”, “three”. Tương tự, khi bạn trả về một bảng từ hàm:

1
2
3


function foo()
  return { x=1, y=2 }
end

Lua sẽ tạo mới bảng này mỗi lần gọi hàm foo(), dù bản chất nó hoàn toàn gồm các giá trị hằng số. Tôi đã nhận ra rằng bất kỳ bảng nào có tất cả khóa và giá trị đều là hằng số đều có thể được tối ưu hóa.

Giải pháp tôi đề xuất là tích hợp quá trình xử lý này vào giai đoạn phân tích cú pháp (parser). Tương tự cách Lua xử lý chuỗi và số, chúng ta có thể tạo sẵn các đối tượng bảng hằng số và lưu trữ chúng trong bảng hằng số của prototype hàm. Điều này giúp giảm đáng kể thời gian chạy chương trình.

Đặc biệt, thay vì tạo mới bảng mỗi lần, chúng ta chỉ cần trả về một “proxy bảng” chứa con trỏ trỏ đến bảng hằng số đã được lưu trữ. Trường hợp thật sự cần sửa đổi bảng (ví dụ: a.x = 3), chúng ta mới sao chép (clone) bảng hằng số thành một bảng thông thường - kỹ thuật này được gọi là Copy-on-Write (COW).

Vì bảng hằng số luôn có cấu trúc đơn giản một lớp, việc sao chép bằng memcpy nhanh hơn 2-3 lần so với chèn từng cặp khóa-giá trị. Dù việc này yêu cầu thêm một bước kiểm tra nhỏ mỗi lần truy cập bảng, lợi ích về hiệu năng mang lại rất đáng kể.

Dưới đây là kết quả thử nghiệm cụ thể:

1
2
3
4
5
6
7


function f(a)
end
local t = os.clock()
for i=1, 10000000 do
  f { x=1, y=2 }
end
print(os.clock() -t)

Kết quả:

Phiên bản Lua 5.3.2 gốc: 3.276 giây
Phiên bản đã tối ưu: 1.278 giây

Và với trường hợp sửa đổi bảng:

1
2
3
4
5
6
7
8


function f(a)
  a.x = 3
end
local t = os.clock()
for i=1, 10000000 do
  f { x=1, y=2 }
end
print(os.clock() -t)

Kết quả:

Phiên bản gốc: 3.376 giây
Phiên bản tối ưu: 1.413 giây

Cải tiến này hiện đã được tích hợp trong kho lưu trữ cá nhân của tôi. Các bạn quan tâm có thể kiểm tra các commit gần đây để tham khảo chi tiết cách triển khai.

Tôi tin rằng đây là một phương pháp tối ưu hóa rất hiệu quả cho các ứng dụng Lua cần xử lý nhiều bảng hằng số. Các bạn có thể áp dụng tương tự trong các dự án của mình để cải thiện hiệu suất.