[Lua] NTable

[MyPad]

So, here's a snippet which allows one to easily reuse and request tables, instead of creating and destroying them regularly.

EDIT: Updated with a redesign in the system. Now, creating NTables will instead generate an allocator table. (Best explained with example code)

--[[
    --------------
        NTable
    --------------

    NTable:create(size, constructor, destructor)
    NTable:new(size, constructor, destructor)
    NTable(size, constructor, destructor)
        - Returns a table with a preloaded list of tables defined by size.
        - constructor is a function with variable arguments.
        - destructor is a function with one argument, the destroyed table instance.
    NTable:flush(table)
- Explicitly recycles the table back into the list of tables, if and only if
          the table belongs to the NTable object.
     
    NTable:destroy()
        - Flushes all associated tables to the NTable object, then nullifies
          the NTable object.
]]

NTable = setmetatable({PRELOAD_SIZE=16}, {})
do
    local tab           = NTable
    local mtab          = getmetatable(tab)
    local weak_tab      = {clear=false, __mode = 'k'}
    local weak_val      = {__mode = 'v'}
    local very_weak_tab = {__mode = 'kv'}
    local func_tables   = {construct=setmetatable({}, weak_tab), destroy=setmetatable({}, weak_tab),
                           shadow=setmetatable({}, weak_tab)}
    local meta_set, meta_get, m_table   = setmetatable, getmetatable, setmetatable({}, weak_tab)
    mtab.__metatable    = tab
    mtab.__index        = mtab
    mtab.__newindex     = function(t, k, v) if mtab[k] then return; end; rawset(t, k, v) end

    local function recycle(self, t)
        if self.list.index[t] then return end
        if func_tables.destroy[self] then func_tables.destroy[self](t) end
        self.list[#self.list + 1]   = t
        self.list.index[t]          = #self.list
        func_tables.shadow[t]       = self
    end
    local n_shadow      = {__gc = function(t)
        if not func_tables.shadow[t] then
            print("func_tables.shadow[t] >> Something's wrong")
        else
            print("func_tables.shadow[t] >> everything's fine")
            print("func_tables.shadow[t] >> " .. tostring(func_tables.shadow[t]))
        end
        if m_table[t] and m_table[t].__gc then
            m_table[t].__gc(t)
        end
        m_table[t]  = nil
        if weak_tab.clear then
        else
            recycle(func_tables.shadow[t], t)
        end
    end, __mode='kv'}
    local cache_clear   = setmetatable({}, {__gc = function(t) weak_tab.clear = (not IsPlayerSlotState(GetLocalPlayer(), PLAYER_SLOT_STATE_PLAYING)) end})

    function getmetatable(t)
        if func_tables.shadow[t] then
            --  This is a sub-table of a Child table
            if m_table[t] then
                return m_table[t].__metatable or m_table[t]
            end
            return nil
        end
        return meta_get(t)
    end
    function setmetatable(t, mt)
        if func_tables.shadow[t] then
            --  This is a sub-table of a Child table
            if m_table[t] and m_table[t].__metatable then
                return t
            end
            if mt ~= n_shadow then
                m_table[t] = mt
            end
            return t
        end
        return meta_set(t, mt)
    end

    local function new_table(o)
        o               = o or {}
        o.list          = {index=setmetatable({}, weak_tab)}
        o.total_list    = setmetatable({}, weak_val)
        o.var_table     = setmetatable({}, weak_tab)
        setmetatable(o, mtab)
        return o
    end
    function mtab:create(size, constructor, destructor)
        local is_func = {is_function(constructor), is_function(destructor)}
        local o       = new_table()
        size          = math.max(size or tab.PRELOAD_SIZE, 1)

        if is_func[1] then func_tables.construct[o] = constructor end
        if is_func[2] then func_tables.destroy[o] = destructor end
        for i=1,size do
            o.list[i]                       = {}
            o.total_list[i]                 = o.list[i]
            o.list.index[o.list[i]]         = i
            func_tables.shadow[o.list[i]]   = o
            meta_set(o.list[i], n_shadow)
        end
        return o
    end
    function mtab:new(size, constructor, destructor)
        return self:create(size, constructor, destructor)
    end
    function mtab:__call(...)
        if self == tab then
            return self:create(...)
        end

        local o, func
        if #self.list > 0 then
            o                       = self.list[#self.list]
            self.list[#self.list]   = nil
            self.list.index[o]      = nil
        else
            o                                       = {}
            self.total_list[#self.total_list + 1]   = o
            func_tables.shadow[o]                   = self
            meta_set(o, n_shadow)
        end
        func = func_tables.construct[self]
        if func then func(o, ...) end
        return o
    end
    function mtab:flush(t)
        if func_tables.shadow[t] == self then
            --  Forcibly collects the table.
            n_shadow.__gc(t)
        end
    end
    function mtab:constructor(constructor)
        if is_function(constructor) then func_tables.construct[self] = constructor end
    end
    function mtab:destructor(destructor)
        if is_function(destructor) then func_tables.destroy[self] = destructor end
    end
    function mtab:destroy()
        if self == tab then return end
        for i=1,#self.total_list do
            self:flush(self.total_list[i])
        end
        func_tables.construct[self] = nil
        func_tables.destroy[self]   = nil
        self.var_table  = nil
        self.total_list = nil
        self.list.index = nil
        self.list       = nil
    end

    function n_shadow.__index(t, k)
        if m_table[t] then
            if m_table[t].__index then
                if type(m_table[t].__index) == 'function' then
                    return m_table[t].__index(t, k)
                else
                    return m_table[t].__index[k]
                end
            end
        end
        return func_tables.shadow[t].var_table[k][t] or nil
    end
    function n_shadow.__newindex(t, k, v)
        if m_table[t] then
            if m_table[t].__newindex then
                m_table[t].__newindex(t, k, v)
                return
            end
        end
        if not func_tables.shadow[t].var_table[k] then
            func_tables.shadow[t].var_table[k] = setmetatable({}, weak_tab)
        end
        func_tables.shadow[t].var_table[k][t] = v
    end
    function n_shadow.__call(t, ...)
        if m_table[t] then
            if m_table[t].__call then
                return m_table[t].__call(t, ...)
            end
        end
        return nil
    end
    function n_shadow.__tostring(t)
        if m_table[t] then
            if m_table[t].__tostring then
                return m_table[t].__tostring(t)
            end
        end
        return tostring(t)
    end
    function n_shadow.__unm(t)
        if m_table[t] then
            if m_table[t].__unm then
                return m_table[t].__unm(t)
            end
        end
        return nil
    end
    function n_shadow.__add(lhs, rhs)
        if m_table[lhs] and (m_table[lhs] == getmetatable(rhs)) then
            if m_table[lhs].__add then
                return m_table[lhs].__add(lhs, rhs)
            end
        end
        return nil
    end
    function n_shadow.__sub(lhs, rhs)
        if m_table[lhs] and (m_table[lhs] == getmetatable(rhs)) then
            if m_table[lhs].__sub then
                return m_table[lhs].__sub(lhs, rhs)
            end
        end
        return nil
    end
    function n_shadow.__mul(lhs, rhs)
        if m_table[lhs] and (m_table[lhs] == getmetatable(rhs)) then
            if m_table[lhs].__mul then
                return m_table[lhs].__mul(lhs, rhs)
            end
        end
        return nil
    end
    function n_shadow.__div(lhs, rhs)
        if m_table[lhs] and (m_table[lhs] == getmetatable(rhs)) then
            if m_table[lhs].__div then
                return m_table[lhs].__div(lhs, rhs)
            end
        end
        return nil
    end
    function n_shadow.__idiv(lhs, rhs)
        if m_table[lhs] and (m_table[lhs] == getmetatable(rhs)) then
            if m_table[lhs].__idiv then
                return m_table[lhs].__idiv(lhs, rhs)
            end
        end
        return nil
    end
    function n_shadow.__mod(lhs, rhs)
        if m_table[lhs] and (m_table[lhs] == getmetatable(rhs)) then
            if m_table[lhs].__mod then
                return m_table[lhs].__mod(lhs, rhs)
            end
        end
        return nil
    end
    function n_shadow.__pow(lhs, rhs)
        if m_table[lhs] and (m_table[lhs] == getmetatable(rhs)) then
            if m_table[lhs].__pow then
                return m_table[lhs].__pow(lhs, rhs)
            end
        end
        return nil
    end
    function n_shadow.__concat(lhs, rhs)
        if m_table[lhs] and (m_table[lhs] == getmetatable(rhs)) then
            if m_table[lhs].__concat then
                return m_table[lhs].__concat(lhs, rhs)
            end
        end
        return nil
    end
end

Example Code: (Pseudo-code)

local t = NTable:create(24)
for i=1, 30 do
    local t1 = t()
    -- This will use all preloaded tables, and generate 6 more tables.
end

local t = NTable:create(10)
t:constructor(function(o, x, y) o.x = x; o.y = y end)
t:destructor(function(o) o.x, o.y = nil end)
-- One can explicitly define constructor and destructor functions outside of NTable:create.
for i = 1,15 do
    local t1 = t(math.random(1,5), math.random(-5, -1))
    -- This will use all preloaded tables, and generate 5 more tables.
end

The idea behind this is that when NTables are out of scope, they will be cleared and recycled, instead of being removed entirely. However, to combat crashes when leaving the game, a cache_clear event watcher will flag the NTables for removal, ensuring that no NTables are ever destroyed in-game for all players.

Spoiler: Previous Remark

This is still kinda experimental, since I'm kinda new to lua garbage collection, so there's that.

 

[Lizreu]

It'd be nice if you outlined what the cases are where you'd might want to use it.

I've seen this trick done before in Lua but IIRC it only makes sense to use this in certain scenarios where the performance gained from not reallocating table storage outweighs the performance lost from having to clear the table in the first place. So in the real world this will need a lot of benchmarking and fine-tuning to get right in each individual case.

I think a similar system that doesn't clear the tables could also be useful for things like vectors/quats, where you don't really need to clear each table's contents and can just blank it all out to 0 instead.

 

[MyPad]

I've seen this trick done before in Lua but IIRC it only makes sense to use this in certain scenarios where the performance gained from not reallocating table storage outweighs the performance lost from having to clear the table in the first place.

Interesting. It's nice knowing that a previous attempt at something like this was made.

It'd be nice if you outlined what the cases are where you'd might want to use it.

Only a few cases come into mind:

• Spell Making
• System Design (whereby object construction is dynamic in nature)

These cases are based on the resources using a previous version of the snippet, which did not take advantage of garbage collection. The snippet above considers and takes advantage of garbage collection.

I think a similar system that doesn't clear the tables could also be useful for things like vectors/quats, where you don't really need to clear each table's contents and can just blank it all out to 0 instead.

You mean something like this? (Pseudo-code)

t = {} -- t is a 2D-Vector
t.x = 25
t.y = 10
t.z = 15

-- on garbage collection (or something close to it)
t.x = 0
t.y = 0

-- on 2D Vector request
newT = t

 

[Lizreu]

You mean something like this? (Pseudo-code)

t = {} -- t is a 2D-Vector
t.x = 25
t.y = 10
t.z = 15

-- on garbage collection (or something close to it)
t.x = 0
t.y = 0

-- on 2D Vector request
newT = t

More or less, yeah. I think this kind of system would benefit tables that aren't too huge in size (so that clearing it doesn't outweigh the cost of just creating a new table) and tables that are frequently created/freed.

Though, to be fair, I've yet to encounter a real need for any kind of GC tweaking in my own use cases (which have been growing steadily in the past couple months). Maybe I just haven't bumped into corner cases like some other people here on Hive have, or maybe there are some WC3-specific bugs that people are misattributing to GC issues. Bottom line, though, you shouldn't be creating so many tables that you're overloading the GC in the first place. It's a bad code smell.

 

[MyPad]

More or less, yeah. I think this kind of system would benefit tables that aren't too huge in size (so that clearing it doesn't outweigh the cost of just creating a new table) and tables that are frequently created/freed.

Alright. Will consider redesigning the system to allow for more specific cases.
The pseudo-code of the redesigned system would behave like this:

local system       = {}   -- The system table.
local sys_tables  = NTable:create([preload_size, constructor, destructor])    -- Creates a child table of NTable which will handle recycling of tables falling under this child table.

-- Some lines of code later.
function some_func(o)
    o = o or sys_tables(…) -- -> Constructor call
    return o
end

-- on garbage collection (externally called)
sys_tables.destructor()  -- Called internally, not visible outside sys_tables

So the code presented before would look like this:

local vct         = {}
local vct_tab   = NTable:create(64, function(x, y, o) o.x = x; o.y = y; return o end, function(o) o.x = 0; o.y = 0 end)

-- Some code later
function vct.create(x, y) return vct_tab(x, y) end

t = vct.create(25, 15) -- t is a 2D-Vector
t.z = 15

-- on garbage collection
vct_tab.destructor(..., t, ...)

 

[MyPad]

A minimalist update on NTable:

Managed to rewrite the entire system into a more compact version.
Due to this, the system was renamed WeakObject, though the key concept remains.

local tb    = {__index = function(t, k) return tb[k] end, __newindex = function() end}
local wt    = {__mode  = 'kv'}
tb.__DEF    = 16
WeakObject  = setmetatable({}, tb)

function tb:__call(size)
    local mo    = {}
    local o     = {}
    local co    = {}

    size        = size or tb.__DEF
    for i = 1, size do
        co[i]   = {}
    end
    o.__index       = function(t, k)
        if o[k] then return o[k];
        elseif not mo[k] then return nil;
        end
        return mo[k][t]
    end
    o.__newindex    = function(t, k, v)
        if o[k] then return;
        end
        if not mo[k] then
            mo[k]   = setmetatable({}, wt)
        end
        mo[k][t]    = v
    end
    o.__call        = function(t, ...)
        local oo
        if #co > 0 then
            oo      = co[#co]
            co[#co] = nil
        else
            oo      = {}
        end
        setmetatable(oo, o)
        if o.__constructor then
            o.__constructor(oo, ...)
        end
        return oo
    end
    o.__destroy     = function(t)
        local mt        = o.__metatable
        o.__metatable   = nil
        setmetatable(t, nil)
        o.__metatable   = mt
       
        if o.__destructor then
            o.__destructor(t)
        end
        co[#co + 1] = t
    end
    o.__gc          = function(self)
        self:__destroy()
    end
    return o, mo, co
end

With the same example above now rewritten for WeakObject

local vct_tab   = WeakObject([preload_size])
local vct         = setmetatable({}, vct_tab)

function vct_tab:__constructor(x, y)
    self.x = x or 0
    self.y = y or 0
end
function vct_tab:__destructor()
    self.x = nil
    self.y = nil
end

-- Some code later
function vct_tab:create(x, y)
    return self(x, y)
end

t = vct(25, 15) -- t is a 2D-Vector
t.z = 15

-- on garbage collection
t = nil
collectgarbage()
collectgarbage()
-- t.z will also be nulled.