data/core/lualib/util.lua table.compare optimization

[sparr]

The recursive implementation of table.compare leads to significant duplication of effort for nested tables. Comparing {{{1,2},{3,4}},{{5,6},{7,8}}} to itself will perform each of the value comparisons eight times (2**nestinglevel).

A fix would be to replace the body of the second loop to just check if tbl2 contains any keys that tbl1 does not, because equality has already been checked for any keys that tbl1 does contain.

Code: Select all

function table.compare( tbl1, tbl2 )
    for k, v in pairs( tbl1 ) do
        if  type(v) == "table" and type(tbl2[k]) == "table" then
            if not table.compare( v, tbl2[k] )  then return false end
        else
            if ( v ~= tbl2[k] ) then return false end
        end
    end
    for k, v in pairs( tbl2 ) do
        if tbl1[k] == nil then return false end
    end
    return true
end

Thanks to rivers and gy_be on discord for discussion and help with this.