table compare benchmark

function _TableCompare(table1, table2)
    local n1, n2 = 0, 0
    for k, v in pairs(table1) do
        n1 = n1 + 1
        local v2 = table2[k]
        if not v2 then return false
        elseif type(v) == 'table' then
        if type(v2) ~= 'table' or not _TableCompare(v, v2) then return false end
        elseif table2[k] ~= v then return false end
    end
    for k, v in pairs(table2) do
        if n2 == n1 then return false end
        n2 = n2 + 1
    end
    return n1 == n2
end

function areTablesEqual1(table1, table2)
    for k, v in pairs(table1) do
        if table2[k] ~= v then
            return false
        end
    end
    for k, v in pairs(table2) do
        if table1[k] ~= v then
            return false
        end
    end
    return true
end

function deepcompare(t1,t2,ignore_mt)
    local ty1 = type(t1)
    local ty2 = type(t2)
    if ty1 ~= ty2 then return false end
    -- non-table types can be directly compared
    if ty1 ~= 'table' and ty2 ~= 'table' then return t1 == t2 end
    -- as well as tables which have the metamethod __eq
    local mt = getmetatable(t1)
    if not ignore_mt and mt and mt.__eq then return t1 == t2 end
    for k1,v1 in pairs(t1) do
        local v2 = t2[k1]
        if v2 == nil or not deepcompare(v1,v2) then return false end
    end
    for k2,v2 in pairs(t2) do
        local v1 = t1[k2]
        if v1 == nil or not deepcompare(v1,v2) then return false end
    end
    return true
end

function deepcompare2(t1,t2,ignore_mt)
    -- t1 and t2 must be of 'table' types otherwise behaviour is undefined
    local mt = getmetatable(t1)
    if not ignore_mt and mt and mt.__eq then return t1 == t2 end
    for k1,v1 in pairs(t1) do
        local v2 = t2[k1]
        if v2 == nil then return false end
        if type(v1) == 'table' and type(v2) == 'table' then
            if not deepcompare2(v1,v2) then return false end
        elseif v1 ~= v2 then return false end
    end
    for k2,v2 in pairs(t2) do
        local v1 = t1[k2]
        if v1 == nil then return false end
        -- no need to compare value at k2 again since it was already handled by the first loop
    end
    return true
end

function nkTablesEqu(t1, t2)
    local k1,v1;
    for k, v in pairs(t1) do
        k1,v1=next(t2,k1)
        if v~=v1 or k~=k1 then return false end
    end
    k1,v1=next(t2,k1);
    if v1~=nil then return false; end
    return true
end

-----------------------------------------------------
function gen_table(n)
    t={}
    for i=1, n do
        t[string.format("%08d", i)] = i
    end
    return t
end

function gen_table1(n)
    t={}
    x=math.random(1, n)
    for i=1, n do
        if i == x then
            t[string.format("%08d", i)] = math.random()
        else
            t[string.format("%08d", i)] = i
        end
    end
    return t
end

-----------------------------------------------------

function benchmark_compare_tables(cmp_func_, t1_, t2_, ttype, expected_result)
    local cmp_func = cmp_func_
    local t1 = t1_
    local t2 = t2_
    if cmp_func(t1, t2) ~= expected_result then
        io.write(" FAILED to compare '", ttype, "' tables, benchmarking anyway...")
    else
        io.write(" benchmarking '", ttype, "' tables...")
    end
    local start = os.clock()
    for i = 1, 100000 do
        cmp_func(t1, t2)
    end
    local stop = os.clock()
    io.write(" time: ", stop - start, "\n")
end

function run_test(cmp_func)
    local a1={1,2,3,4}
    local a2={1,2,3,4}
    benchmark_compare_tables(cmp_func, a1, a2, "array", true)

    local t1={["c"]=3,["a"]=1,["aa"]=6,["b"]=2,["d"]=4,["ba"]=7,["ca"]=8}
    benchmark_compare_tables(cmp_func, t1, t1, "same", true)

    local t2={["ca"]=8,["b"]=2,["a"]=1,["aa"]=6,["c"]=3,["d"]=4,["ba"]=7}
    benchmark_compare_tables(cmp_func, t1, t2, "shuffled", true)

    local t11={["c"]=3,["a"]=1,["aa"]=6,["b"]=2,["d"]=4,["ba"]=7,["ca"]=9}
    benchmark_compare_tables(cmp_func, t1, t11, "same size, single different value", false)

    local nested1 = {k1="value1", nested={k2="value3"}}
    local nested2 = {k1="value1", nested={k2="value3"}}
    benchmark_compare_tables(cmp_func, nested1, nested2, "nested", true)

    local nested22 = {k1="value1", nested="value2"}
    benchmark_compare_tables(cmp_func, nested1, nested2, "nested vs non-nested", true)

    local metatable = {__eq = function(t1, t2) return true end}
    local m1={k1=1}
    local m2={k1="one"}
    setmetatable(m1, metatable)
    setmetatable(m2, metatable)
    benchmark_compare_tables(cmp_func, m1, m2, "with metatable.__eq", true)

    local t1000_1=gen_table(1000)
    local t1000_2=gen_table(1000)
    benchmark_compare_tables(cmp_func, t1000_1, t1000_2, "size=1000", true)
    local t1000_3=gen_table1(1000)
    benchmark_compare_tables(cmp_func, t1000_1, t1000_3, "size=1000 vs random", false)
end

math.randomseed(os.time())

io.write("--- areTablesEqual1\n")
run_test(areTablesEqual1)
io.write("--- _TableCompare\n")
run_test(_TableCompare)
io.write("--- deepcompare\n")
run_test(deepcompare)
io.write("--- deepcompare2\n")
run_test(deepcompare2)
io.write("--- nkTablesEq\n")
run_test(nkTablesEqu)