CODEWITHSUNDEEP
optimizationlua
masrtis
masrtis

Reputation: 1310

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

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

Upvotes: 5

Views: 2951

Answers (3)

W.B.
W.B.

Reputation: 5525

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!

Upvotes: 4

lhf
lhf

Reputation: 72312

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.

Upvotes: 3

Oleg V. Volkov
Oleg V. Volkov

Reputation: 22421

Allocating a new table is a costly operation in Lua (which is true for any object allocation in pretty much any dynamic language). Additionally, constantly "losing" newly created to GC will put additional strain on performance, as well as memory, since every created table will still be in memory until GC actually comes to claim it.

Technique in your example trades those disadvantages for time required to explicitly remove all elements in table. This will always be a memory save and, depending on amount of elements, may often be a performance improvement as well.

Upvotes: 0

Related Questions