lua fulluserdata代替table的尝试
lua fulluserdata代替table的尝试
使用fulluserdata来实现复杂的数据结构，然后尝试替代table，以验证是否可以实现更快的框架（Table的Value为Table时，会有内存不连续的情况，缓存不友好）
环境
- xlua版本：2.1.16
- lua版本：5.3.5
- 运行环境：Unity Editor
- PC配置：i5 10400F
为了方便测试，所有的测试基于Unity Editor(PC)环境，采用Unity Profiler和Lua Profiler。
Array
以fulluserdata为基础，在C实现了一个Array[double]。
luaarray.h:
#ifndef LUAARRAY_H
#define LUAARRAY_H
#include "lua.h"
/*-------------------------------------------------------------------------*\
* Initializes the library.
\*-------------------------------------------------------------------------*/
LUA_API int luaopen_array(lua_State *L);
#endif /* LUAARRAY_H */
luaarray.c:
#include "luaarray.h"
#define LUA_LIB
#include "lua.h"
#include "lauxlib.h"
#include "lualib.h"
#include "limits.h"
#define ARRAY_TAG "LuaArrayMatetable"
typedef struct NumArray {
int size;
double values[1];
} NumArray;
static NumArray *checkarray(lua_State *L)
{
void *ud = luaL_checkudata(L, 1, ARRAY_TAG);
luaL_argcheck(L, ud != NULL, 1, "'array' expected");
return (NumArray *)ud;
}
static double *getelement(lua_State *L)
{
NumArray *a = checkarray(L);
int index = luaL_checkinteger(L,2) - 1;
luaL_argcheck(L,a != NULL,1,"'array' expected.");
luaL_argcheck(L,0 <= index && index < a->size,2,"index out of range.");
return &a->values[index];
}
static int newarray(lua_State* L)
{
int i, n;
n = luaL_checkinteger(L,1);
luaL_argcheck(L, n >= 1, 1, "invalid size.");
size_t nbytes = sizeof(NumArray) + (n - 1) * sizeof(double);
NumArray* a = (NumArray*) lua_newuserdata(L,nbytes);
a->size = n;
for (i = 0; i < n - 1; ++i)
a->values[i] = 0;
luaL_getmetatable(L, ARRAY_TAG);
lua_setmetatable(L, -2);
return 1;
}
static int setarray(lua_State* L)
{
double value = luaL_checknumber(L, 3);
*getelement(L) = value;
return 0;
}
static int getarray(lua_State* L)
{
lua_pushnumber(L, *getelement(L));
return 1;
}
static int getsize(lua_State* L)
{
NumArray *a = checkarray(L);
lua_pushnumber(L, a->size);
return 1;
}
static int array2string(lua_State* L)
{
NumArray* a = checkarray(L);
lua_pushfstring(L,"array(%d)",a->size);
return 1;
}
static luaL_Reg arraylib_f [] = {
{"new", newarray},
{NULL, NULL}
};
static luaL_Reg arraylib_m [] = {
{"set", setarray},
{"get", getarray},
{"size", getsize},
{"__tostring", array2string},
{NULL, NULL}
};
LUA_API int luaopen_array(lua_State* L)
{
luaL_newmetatable(L, ARRAY_TAG);
lua_pushstring(L, "__index");
lua_pushvalue(L, -2);
lua_settable(L, -3);
luaL_setfuncs(L, arraylib_m, 0);
luaL_newlib(L, arraylib_f);
return 1;
}
对比
local array = require "array"
local num = 1000000
function TestTable()
local time = os.clock()
local tb = {}
local value
time = os.clock()
local insert = table.insert
for i=1,num do
tb[i] = i
end
print(string.format("set table: %sms", (os.clock() - time) * 1000))
time = os.clock()
for i=1,num do
value = tb[i]
end
print(string.format("get table:%sms", (os.clock() - time) * 1000))
end
function TestUserdata()
local time = os.clock()
local arr = array.new(num)
local value
time = os.clock()
for i=1,num do
arr:set(i, i)
end
print(string.format("set array: %sms", (os.clock() - time) * 1000))
time = os.clock()
for i=1,num do
value = arr:get(i)
end
print(string.format("get array:%sms", (os.clock() - time) * 1000))
end
print(num)
TestUserdata()
TestTable()
在完成luaarray.c的实现后，就编写基于两者的对比用例，并且在unity中进行测试。原本以为fulluserdata的实现会比table性能好，最差也是相差无几，但实际情况却出人意料：
| 方案 | set耗时(ms) | get耗时（ms） |
|---|---|---|
| Table | 24 | 9 |
| Array | 82 | 79 |
优化Array
从上面对比的情况可以看出，Table远远比Array快，特别在get的情况。在经过一番思考过后，排查出一个问题：那就是Array由于需要区分当前userdata类型，防止意外的内存指针传入导致出问题，所以使用了metatable，所以在调用时，会先判断metatable的情况。以此作为优化目标进行优化：
static NumArray *checkarray(lua_State *L)
{
// 不再检查matetable
//void *ud = luaL_checkudata(L, 1, ARRAY_TAG);
void *ud = lua_touserdata(L, 1);
luaL_argcheck(L, ud != NULL, 1, "'array' expected");
return (NumArray *)ud;
}
static int newarray(lua_State* L)
{
int i, n;
n = luaL_checkinteger(L,1);
luaL_argcheck(L, n >= 1, 1, "invalid size.");
size_t nbytes = sizeof(NumArray) + (n - 1) * sizeof(double);
NumArray* a = (NumArray*) lua_newuserdata(L,nbytes);
a->size = n;
for (i = 0; i < n - 1; ++i)
a->values[i] = 0;
// 不再设置metatable
//luaL_getmetatable(L, ARRAY_TAG);
//lua_setmetatable(L, -2);
return 1;
}
//将function赋值给array
static luaL_Reg arraylib_f [] = {
{"new", newarray},
{"set", setarray},
{"get", getarray},
{"size", getsize},
{"__tostring", array2string}, //print(a)时Lua会调用该元方法。
{NULL, NULL}
};
function TestUserdata()
local time = os.clock()
local arr = array.new(num)
local value
time = os.clock()
local set = array.set --改为array的function，并缓存起来
for i=1,num do
set(arr, i, i)
end
print(string.format("set array: %sms", (os.clock() - time) * 1000))
time = os.clock()
local get = array.get --改为array的function，并缓存起来
for i=1,num do
value = get(arr, i)
end
print(string.format("get array:%sms", (os.clock() - time) * 1000))
end
测试后，耗时有所改善，但仍然不太乐观：
| 方案 | set耗时(ms) | get耗时（ms） |
|---|---|---|
| Table | 24 | 9 |
| Array (no metatable) | 44 | 38 |
可以看出，metatable对于代码效率影响巨大。如果需要标记当前的内存指针是否正确，就需要另辟蹊径。
分析
- 首先分析table的get耗时为什么比table的set要高？
这是因为table插入数据时存在扩容的情况。
- table的set为什么这么快？
这是有两个原因。
一是示例中的table放入的是number值，number值在table的Value中是以连续内存存在的，这是因为TValue是一个联合体，在number的情况下TValue就保存着值，因此内存是连续的，就不存在缓存不友好的情况。
二是table[x]在运行时是使用OP_SETTABLE和OP_GETTABLE两个指令。而示例中的array.set则需要使用多次OP_MOVE，最后还要调用OP_CALL，在指令中不占优，并且需要频繁操作寄存器导致耗时较大。
local array = require "array"
local num = 1000
local a = {}
for i=1,num do
a[i] = i
end
main <table.lua:0,0> (12 instructions at 0000000000028a70)
0+ params, 7 slots, 1 upvalue, 7 locals, 4 constants, 0 functions
1 [1] GETTABUP 0 0 -1 ; _ENV "require"
2 [1] LOADK 1 -2 ; "array"
3 [1] CALL 0 2 2
4 [3] LOADK 1 -3 ; 1000
5 [5] NEWTABLE 2 0 0
6 [7] LOADK 3 -4 ; 1
7 [7] MOVE 4 1
8 [7] LOADK 5 -4 ; 1
9 [7] FORPREP 3 1 ; to 11
10 [8] SETTABLE 2 6 6
11 [7] FORLOOP 3 -2 ; to 10
12 [9] RETURN 0 1
local array = require "array"
local num = 1000
local arr = array.new(num)
local set = array.set
for i=1,num do
set(arr, i, i)
end
main <table.lua:0,0> (19 instructions at 00000000001b8a70)
0+ params, 12 slots, 1 upvalue, 8 locals, 6 constants, 0 functions
1 [1] GETTABUP 0 0 -1 ; _ENV "require"
2 [1] LOADK 1 -2 ; "array"
3 [1] CALL 0 2 2
4 [3] LOADK 1 -3 ; 1000
5 [11] GETTABLE 2 0 -4 ; "new"
6 [11] MOVE 3 1
7 [11] CALL 2 2 2
8 [13] GETTABLE 3 0 -5 ; "set"
9 [15] LOADK 4 -6 ; 1
10 [15] MOVE 5 1
11 [15] LOADK 6 -6 ; 1
12 [15] FORPREP 4 5 ; to 18
13 [16] MOVE 8 3
14 [16] MOVE 9 2
15 [16] MOVE 10 7
16 [16] MOVE 11 7
17 [16] CALL 8 4 1
18 [15] FORLOOP 4 -6 ; to 13
19 [17] RETURN 0 1
复杂场景
上述的示例只是一个很简单的场景，在实际开发中，往往会比这个更加复杂，例如实体是一个复杂的结构，可能是面向对象（存在元表），管理时也会对实体增删查改。
而访问元表、table的创建删除、table的扩容都是较为耗时的操作。
800个单位的碰撞测试（未优化过算法，碰撞测试次数在800 * 800 * 0.5 = 320000）。测试场景中只是简单模拟了实体的创建和获取，至于隐藏在实体框架中的耗时并没有包含在测试过程（例如框架的继承需要用到元表、C侧的框架逻辑），因此只是比较了Lua Table和Userdata对于复杂数据的读写耗时。
为了快速验证，本次测试只封装了Component读的方法，写的方法还是采用旧的方案
static int getcomponents(lua_State* L)
{
NumArray *a = checkarray(L);
int index = luaL_checkinteger(L,2) - 1;
int entityGroup = luaL_checkinteger(L,3); //实际情况下，需要告知实体管理需要获取哪些Component，这里模拟了参数传入
int start = index * 9;
int end = start + 9 - 1;
luaL_argcheck(L,a != NULL,1,"'array' expected.");
luaL_argcheck(L,0 <= index && end < a->size,2,"index out of range.");
for (size_t i = 0; i < 9; i++)
{
lua_pushnumber(L, a->values[start + i]);
}
return 9;
}
| 方案 | create耗时(ms) | 碰撞检测耗时（ms） |
|---|---|---|
| Table（结构） | 1 | 41 |
| Table（连续内存） | 1 | 41 |
| Component | 1 | 31 |
可以看出来，Lua Table在复杂情况下是比userdata要更耗时的，这也比较好理解，userdata一次性全返回了需要的Component属性，这样子就可以减少函数调用和参数入栈出栈次数，而table不管是结构和连续内存，都需要重复的压入索引或获取返回值，这样OP_SETTABLE和OP_GETTABLE的优势将荡然无存。
假设再加上实体框架的逻辑，那么userdata方案将会比table更有优势，因为lua侧只能是用table和metatable来进行管理，而userdata将大量的实体管理逻辑隐藏在C侧。