預配置 Table
 |
||
|
預配置 Table |
|
lua_createtable [1] 的內建函式，可供 Lua 程式碼存取。lua_createtable 會建立一個 Lua table，其中陣列和雜湊區域會預配置為指定的尺寸。相較於執行 local t = {}; for i=1,N do t[i] = 0 end，預配置會更有效率，在執行後續程式碼時，大概會執行 O(log(N)) 個配置動作，即陣列每溢位一次就會重新配置為先前尺寸的倍數。
以下列出一些解決方案。
在此，我們建立一個連結至 lua_createtable C 函式的 Lua binding。如果可以連結至 C，這是最健全、最有效率且最直接的方法。
如果我們在 Lua 中使用 table 建構函式語法，例如 local t = {0,0,0,0,0}，Lua 分析器會產生預先配置 table 中所需空間並填入資料的 opcode。這通常符合我們的需求，但可能是除了填入 table 的部分。
$ echo 'local t = {0,0,0,0,0}' | luac -p -l -
main <stdin:0,0> (8 instructions, 32 bytes at 0x680e00)
0+ params, 6 slots, 0 upvalues, 1 local, 1 constant, 0 functions
1 [1] NEWTABLE 0 5 0
2 [1] LOADK 1 -1 ; 0
3 [1] LOADK 2 -1 ; 0
4 [1] LOADK 3 -1 ; 0
5 [1] LOADK 4 -1 ; 0
6 [1] LOADK 5 -1 ; 0
7 [1] SETLIST 0 5 1 ; 1
8 [1] RETURN 0 1
更棒的是，我們可以用 nil 填入 table，local t = {nil,nil,nil,nil,nil}，這會使用更有效率的 LOADNIL 和 SETLIST 指令。
$ echo 'local t = {nil,nil,nil,nil,nil}' | luac -p -l -
main <stdin:0,0> (4 instructions, 16 bytes at 0x680df8)
0+ params, 6 slots, 0 upvalues, 1 local, 0 constants, 0 functions
1 [1] NEWTABLE 0 5 0
2 [1] LOADNIL 1 5
3 [1] SETLIST 0 5 1 ; 1
4 [1] RETURN 0 1
主要的問題在於，如果所需的配置尺寸很大，這種寫法會很麻煩；而且如果尺寸需要等到執行時期才知道，那麼我們必須在執行時期建立程式碼字串，然後呼叫 loadstring。
這是可行的解決方案。要建立和編譯建立 table 的函式並不夠有效率，但另一方面，這個步驟可能只需要執行一次（或可以暫存）。一個比較次要的論點是，LOADNIL 和 SETLIST 指令在每次呼叫時都是不必要的。
透過 hack bytecode，可以更有效率地建立前一個解決方案的 table 建構函式。我們甚至可以避免初始化 table 條目。在此，我們修改 return {} bytecode 中的 NEWTABLE opcode，
$ echo 'return {}' | luac -p -l -
main <stdin:0,0> (3 instructions, 12 bytes at 0x680df8)
0+ params, 2 slots, 0 upvalues, 0 locals, 0 constants, 0 functions
1 [1] NEWTABLE 0 0 0
2 [1] RETURN 0 2
3 [1] RETURN 0 1
使用新的 table 尺寸，然後載入由新 bytecode 所定義的函式到記憶體中。這不涉及額外的 Lua 原始碼分析和較少的字串處理。然而，這仰賴 Lua bytecode 格式的假設。
-- opcreatetable.lua -- -- Creates table preallocated in array and hash sizes. -- Implemented in pure Lua. -- -- Warning: This code may be somewhat fragile since it depends on -- the Lua 5.1 bytecode format and little-endian byte order. -- -- This code has not been well tested. Please review prior to using -- in production. -- -- (c) 2009 David Manura. Licensed under the same terms as Lua (MIT license). local M = {} local loadstring = loadstring local assert = assert local string = string local string_dump = string.dump local string_char = string.char -- Encodes integer for NEWTABLE opcode. Based on lobject.c:luaO_int2fb. local xmax = 15*2^30 local function int2fb(x) assert(x >= 0 and x <= xmax) local e = 0 while x >= 16 do x = (x+1) local b = x % 2 x = (x-b) / 2 e = e + 1 end if x < 8 then return x else return (e+1) * 8 + (x - 8) end end -- Packs and unpacks 4-byte little-endian unsigned int. local function pack_int4(x1,x2,x3,x4) return ((x4*256 + x3)*256 + x2)*256 + x1 end local function unpack_int4(x) local x1 = x % 256; x = (x - x1) / 256 local x2 = x % 256; x = (x - x2) / 256 local x3 = x % 256; x = (x - x3) / 256 local x4 = x return x1,x2,x3,x4 end -- Packs and unpacks iABC type instruction. local function unpack_iABC(x) local instopid = x % 64; x = (x - instopid) / 64 local insta = x % 256; x = (x - insta) / 256 local instc = x % 512; x = (x - instc) / 512 local instb = x return instopid, insta, instb, instc end local function pack_iABC(instopid, insta, instb, instc) return ((instb * 512 + instc) * 256 + insta) * 64 + instopid end -- Returns a function that when called creates and returns a new table. -- The table has array size asize and hash size hsize (both default to 0). -- Calling this function may be slow and you may want to cache the -- returned function. Calling the returned function should be fast. local code local pos local insta local function new_table_builder(asize, hsize) asize = asize or 0 hsize = hsize or 0 if not code then -- See "A No-Frills Introduction to Lua 5.1 VM Instructions" -- by Kein-Hong Man for details on the bytecode format. code = string_dump(function() return {} end) -- skip headers local int_size = code:byte(8) local size_t_size = code:byte(9) local instruction_size = code:byte(10) local endian = code:byte(7) assert(size_t_size == 4) assert(instruction_size == 4) assert(endian == 1) -- little endian local source_size = pack_int4(code:byte(13), code:byte(14), code:byte(15), code:byte(16)) pos = 1 + 12 -- chunk header + size_t_size -- string size + source_size -- string data + 2 * int_size + 4 -- rest of function block header + 4 -- number of instructions -- read first instruction (NEWTABLE) local a1 = code:byte(pos) local a2 = code:byte(pos+1) local a3 = code:byte(pos+2) local a4 = code:byte(pos+3) local inst = pack_int4(a1,a2,a3,a4) -- parse instruction local instopid, instc, instb instopid, insta, instb, instc = unpack_iABC(inst) assert(instopid == 10) assert(instb == 0) assert(instc == 0) end -- build new instruction local instopid = 10 local instb = int2fb(asize) local instc = int2fb(hsize) local inst = pack_iABC(instopid, insta, instb, instc) -- encode new instruction into code. local inst1,inst2,inst3,inst4 = unpack_int4(inst) local code2 = code:sub(1,pos-1)..string_char(inst1,inst2,inst3,inst4)..code:sub(pos+4) local f2 = assert(loadstring(code2)) return f2 end M.new_table_builder = new_table_builder return M
測試
local new_table_builder = require "opcreatetable" . new_table_builder local nt = new_table_builder(1e6,1e6) local t1 = nt() local t2 = nt() print(t1, t2) -- wait for user to observe process memory usage io.stdin:read'*l'
Lua 5.2 應該提供更好的解決方式嗎？