Re: Performance problem with table.move

[Xmilia Hermit <xmilia.hermit@...>]

It is possible to preallocate tables with a specific size by creating 
bytecode ourselves. Using this method it is even faster:

local table_new = table.new

if not table_new then
    table_new = function(asize, hsize) return {} end
    local I2S = {
        [true] = function(i)
            return string.char(i & 0xFF, (i>>8) & 0xFF, (i>>16) & 0xFF, 
(i>>24) & 0xFF)
        end,
        [false] = function(i)
            return string.char((i>>24) & 0xFF, (i>>16) & 0xFF, (i>>8) & 
0xFF, i & 0xFF)
        end
    }
    local d = string.dump(table_new, false)
    local MAGIC = "\x1bLua"
    if string.sub(d, 1, 4) == MAGIC then -- Magic
        if string.sub(d, 5, 5) == "\x54" then -- Version
            if string.sub(d, 6, 6) == "\x00" then -- Format
                local inst_size, int_size, num_size = string.byte(d, 
13, 15) -- Sizes
                if inst_size == 4 then
                    local HEADER = string.sub(d, 1, 15 + int_size + 
num_size) ..
                    "\x00" .. -- num upvalues
                    "\x80" .. -- size of source
                    "\x81" .. -- line defined
                    "\x82" .. -- last line defined
                    "\x00" .. -- num params
                    "\x00" .. -- is vararg
                    "\x02" .. -- max stack size
                    "\x83"    -- num instructions
                    local Inst = I2S[string.sub(d, 16, 16) == "\x78"]
                    table_new = function(asize, hsize)
                        asize = math.tointeger(asize)
                        if asize == nil or asize < 0 then
                            error("Invalid array size")
                        end
                        if asize >= 0x200000000 then
                            asize = 0x1FFFFFFFF
                        end
                        hsize = math.tointeger(hsize)
                        if hsize == nil or hsize < 0 then
                            error("Invalid array size")
                        end
                        local bits = 0
                        if hsize > 0 then
                            hsize = hsize - 1
                            bits = 1
                            while hsize > 0 do
                                hsize = hsize >> 1
                                bits = bits + 1
                            end
                        end
                        local bin = HEADER ..
                        Inst(0x00008093 | (bits << 16) | ((asize & 
0xFF) << 24)) .. -- OP_NEWTABLE (0x13) A = 1 k = 1 B = bits C = asize
                        Inst(0x00000052 | ((asize >> 1) & 0xFFFFFF80)) 
.. -- OP_EXTRAARG (0x52) Ax = size
                        Inst(0x000000C8) .. -- OP_RETURN1 (0x48) A = 1
                        "\x80\x80\x80\x80\x80\x80\x80" -- num 
constants, upvalues, protos, lineinfo, lineinfo2, localvarinfo, upvalueinfo
                        local f = load(bin, "ArrayCreate", "b")
                        return f()
                    end
                end
            end
        end
    end
end

function solution5(level)
    local last_index = (2 << level) - level - 1
    local step = {}
    for j = 1, level do
       step[(1 << j)-1] = j
    end
    local t = table_new(last_index, 0)
    t[1] = "Lua"
    local p = 1
    for j = 1, (1 << level)-1 do
       p = p + step[j ~ (j - 1)]
       t[p] = "Lua"
    end
    return t, last_index
end


local level = tonumber(arg[1])
local t, last_index = solution5(level)


time ./lua student5.lua 20

real    0m0.035s
user    0m0.017s
sys     0m0.018s

Not that this only runs on lua 5.4 as should be seen as a proof of concept.