Is it better to set a table to empty or set all elements of a table to nil?

Question

A question about a piece of lua code came up during a code review I had recently. The code in question is flushing a cache and reinitializing it with some data:

for filename,_ in pairs(fileTable) do
    fileTable[filename] = nil
end

-- reinitialize here

Is there any reason the above loop shouldn't be replaced with this?

fileTable = { }

-- reinitialize here

Answer 1

It is due to table resize / rehash overhead. When a table is created, it is empty. When you insert an element, a rehash takes place and table size is grown to 1. The same happens, when you insert another element. The rule is that a table is grown whenever there's insufficient space (in either array or hash part) to hold another element. The new size is the smallest power of 2 that can accomodate required number of elements. E.g. rehash occurs when you insert an element, if a table holds 0, 1, 2, 4, 8, etc. elemnts.

Now the technique you're describing saves those rehashes, as Lua does not shrink tables. So when you have frequent fill / flush table operations it's better (performance wise) to do it like in your example than to create an empty table.

Update:

I've put up a little test:

local function rehash1(el, loops)
    local table = {}
    for i = 1, loops do
        for j = 1, el do
            table[j] = j
        end
        for k in ipairs(table) do table[k] = nil end
    end
end

local function rehash2(el, loops)
    for i = 1, loops do
        local table = {}
        for j = 1, el do
            table[j] = j
        end
    end
end


local function test(elements, loops)
    local time = os.time();
    rehash1(elements, loops);
    local time1 = os.time();
    rehash2(elements, loops);
    local time2 = os.time();

    print("Time nils: ", tostring(time1 - time), "\n");
    print("Time empty: ", tostring(time2 - time1), "\n");

end

Results are quit interesting. Running test(4, 10000000) on Lua 5.1 gave 7 seconds for nils and 10 seconds for empties. For tables bigger than 32 elements, the empty version was faster (the bigger the table, the bigger the difference). test(128, 400000) gave 9 seconds for nils and 5 seconds for empties.

Now on LuaJIT, where alloc and gc operations are relatively slow, running test(1024, 1000000) gave 3 seconds for nils and 7 seconds for empties.

P.S. Notice the sheer performance difference between plain Lua and LuaJIT. For 1024 element tables, plain Lua did 100,000 test iterations in about 20 seconds, LuaJIT did 1,000,000 iterations over 10 seconds!

Answer 2

Unless you have evidence otherwise, you'd be better off trusting Lua's garbage collection: just create a new, empty table when you need it.