Performance issues when deleting some keys during table construction

[最萌 小汐]

I discovered a strange performance issue. Once I added the line "cache[uid] = nil," the time it takes to run this code becomes significantly longer.

```lua

local cache = {}

for x = 1, 1000 do

    for i = x * 10000, (x + 1) * 10000 do

        local uid = i * 1000 + 100000000

        cache[uid] = 1

    end

    -- remove some garbages for some reasons

    for i = 1, 1000 do

        local uid = next(cache)

        if uid then

            cache[uid] = nil -- delete this line to make it faster

        end

    end

end

print('done!')

```

Background: I am investigating a performance issue. I have a large hash table that maintains a size of around 500k. I continuously add temporary data to the table (using a large integer as the key to ensure it hashes properly). Additionally, I periodically traverse this table to remove some expired data.

After running for several hours, I encountered a strange performance issue: the assignment operation for adding temporary data to the table sometimes takes several seconds. Moreover, as the runtime increases, this operation's duration grows longer, eventually taking several minutes. The time taken to traverse the table also increases from around ten milliseconds to several minutes.

During this period, the table size remains around 500k. I suspect that the table may be experiencing some erroneous resizing behavior. I have not yet found a way to reproduce this situation with a demonstration code, but I discovered the aforementioned issues while searching. These problems occur in both Lua 5.3 and Lua 5.4.

-- sumneko

[Yan]

Which Lua version you use?

See this thread, is it relevant ?
http://lua-users.org/lists/lua-l/2021-03/msg00069.html

Lua 5.4.4 Optimized this issue. So Lua 5.4.3 and prevision versions, this issue existed.

https://github.com/lua/lua/commit/7fbe2158089898f09d741e991737f282e514ffaa

[Denis Dos Santos Silva]

  For certain performance-critical activities, it may be necessary to temporarily pause the garbage collector.  

https://www.tutorialspoint.com/lua/lua_garbage_collection.htm

collectgarbage("collect") − Runs one complete cycle of garbage collection.

collectgarbage("count") − Returns the amount of memory currently used by the program in Kilobytes.

collectgarbage("restart") − If the garbage collector has been stopped, it restarts it.

collectgarbage("setpause") − Sets the value given as second parameter divided by 100 to the garbage collector pause variable. Its uses are as discussed a little above.

collectgarbage("setstepmul") − Sets the value given as second parameter divided by 100 to the garbage step multiplier variable. Its uses are as discussed a little above.

collectgarbage("step") − Runs one step of garbage collection. The larger the second argument is, the larger this step will be. The collectgarbage will return true if the triggered step was the last step of a garbage-collection cycle.

collectgarbage("stop") − Stops the garbage collector if its running.

[Francisco Olarte]

Your reports is a bit strange, but lets give it a try....

On Sun, 4 May 2025 at 12:14, 最萌 小汐 <sum...@hotmail.com> wrote:
> I discovered a strange performance issue. Once I added the line "cache[uid] = nil," the time it takes to run this code becomes significantly longer.

You mean EXACTLY THIS CODE? Because time to run a code tends to get
longer as you add lines. If you have a problem with similar but
different code you should probably elaborate a bit more.

> local cache = {}
> for x = 1, 1000 do
> for i = x * 10000, (x + 1) * 10000 do
> local uid = i * 1000 + 100000000
> cache[uid] = 1
> end
>
> -- remove some garbages for some reasons
> for i = 1, 1000 do
> local uid = next(cache)
> if uid then
> cache[uid] = nil -- delete this line to make it faster
> end
> end
> end

This repeats, 1000 times.
1.- Add 10k entries to a table.
2.- Delete the first 1k entries from it.
Note you are not deleting the recently added, but allways searching
from the start of the table. And with a test which in the code is
superflous ( next(cache) is only nil ( it cannot be false there ) on
empty tables.
IIRC lua tables do some kind of chaining of deleted entries ( it is
needed for proper working of some things ), so I suspect your second
loop is creating longer and longer chains of deleted elements and you
are invoking the infamous quadratic behaviour in the deleting loops,
some one more knowledgeable of the internals may confirm or deny that.

> After running for several hours,

I assume a similar but different code....

> I encountered a strange performance issue: the assignment operation for adding temporary data to the table sometimes takes several seconds. Moreover, as the runtime increases, this operation's duration grows longer, eventually taking several minutes. The time taken to traverse the table also increases from around ten milliseconds to several minutes.

You may be building some kind of pathologically bad hash table there.
Lots of pointer chains.

> During this period, the table size remains around 500k. I suspect that the table may be experiencing some erroneous resizing behavior. I have not yet found a way to reproduce this situation with a demonstration code, but I discovered the aforementioned issues while searching. These problems occur in both Lua 5.3 and Lua 5.4.

Is your code really doing that, deleting some kind of cache entries by
always swapping a chunk of the table from the start? Be sure you are
not having a problem but reporting a different one ( your sample does
no make much sense TO ME, you generate keys with an increasing
sequence, this I have seen, but then your "garbage deletion" just
grabs the first "random" key the hash gives you in next(cache)).

Francisco Olarte.

[最萌 小汐]

This is not the code mentioned in the background.

So far, I haven't been able to find the code to quickly reproduce the background. I'm still trying.

I mentioned the background to see if anyone has encountered similar problems or has relevant experience.

Thank you for your try and answer!

-- sumneko

---

发件人: lu...@googlegroups.com <lu...@googlegroups.com> 代表 Francisco Olarte <fol...@peoplecall.com>
发送时间: 2025年5月5日 15:41
收件人: lu...@googlegroups.com <lu...@googlegroups.com>
主题: Re: Performance issues when deleting some keys during table construction

 

--
You received this message because you are subscribed to the Google Groups "lua-l" group.
To unsubscribe from this group and stop receiving emails from it, send an email to lua-l+un...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/lua-l/CA%2BbJJbx7C%2BNta7HGQruNaxFMWi9YWe1b8MdbyRJE6JdCkBzWRA%40mail.gmail.com.

[最萌 小汐]

The issue in the code can be reproduced in all versions of Lua (including the latest version on GitHub).
The issue in the background occurs in the latest version of Lua 5.3.

> See this thread, is it relevant ?
> http://lua-users.org/lists/lua-l/2021-03/msg00069.html

I think it is not related to this thread.

-- sumneko

---

发件人: lu...@googlegroups.com <lu...@googlegroups.com> 代表 Yan <yl.mec...@gmail.com>
发送时间: 2025年5月5日 10:21
收件人: lua-l <lu...@googlegroups.com>

主题: Re: Performance issues when deleting some keys during table construction

--

You received this message because you are subscribed to the Google Groups "lua-l" group.
To unsubscribe from this group and stop receiving emails from it, send an email to lua-l+un...@googlegroups.com.

To view this discussion visit https://groups.google.com/d/msgid/lua-l/d169982d-1d4d-41b1-87c7-b2e2db5249b1n%40googlegroups.com.

[Roberto Ierusalimschy]

> I discovered a strange performance issue. Once I added the line "cache[uid] = nil," the time it takes to run this code becomes significantly longer.
>

> [...]

> -- remove some garbages for some reasons
> for i = 1, 1000 do
> local uid = next(cache)
> if uid then
> cache[uid] = nil -- delete this line to make it faster
> end
> end

This code is quadratic. 'next' finds the first non-nil entry in a table.
Whey you remove that "first" entry, the next call to 'next' will need to
traverse one more element to find the first non-nil entry in a table.
So, the first call traverses 1 element, the next traverses 2 elements,
and so on. If the table is full, that loop alone will take ~(1000^2/2)
steps.

As you keep adding elements to the end of the table, that initial
growing empty portion is not removed (except when the table rehashes).
So, each time the code repeats this loop, it gets worse.

-- Roberto

[最萌 小汐]

Thank you for your answer

But I wonder why new elements are always added to the end of the table?
I don't know much about Lua's C implementation, but in my understanding of the hash table, new elements should be evenly added to all positions.

-- sumneko

---

发件人: lu...@googlegroups.com <lu...@googlegroups.com> 代表 Roberto Ierusalimschy <rob...@inf.puc-rio.br>
发送时间: 2025年5月5日 21:57
收件人: lu...@googlegroups.com <lu...@googlegroups.com>

主题: Re: Performance issues when deleting some keys during table construction

--
You received this message because you are subscribed to the Google Groups "lua-l" group.
To unsubscribe from this group and stop receiving emails from it, send an email to lua-l+un...@googlegroups.com.

To view this discussion visit https://groups.google.com/d/msgid/lua-l/20250505135720.GA43179%40arraial.inf.puc-rio.br.

[云风 Cloud Wu]

最萌 小汐 <sum...@hotmail.com>于2025年5月5日 周一22:38写道：

Thank you for your answer

But I wonder why new elements are always added to the end of the table?
I don't know much about Lua's C implementation, but in my understanding of the hash table, new elements should be evenly added to all positions.

Because lua relies on the behavior of adding new elements to trigger rehash. Removing elements shouldn’t trigger rehash because lua allows removing elements during iterations.

If you understand this behavior of lua table, you will find a better way to implement a LRU cache is to use multiple tables : drop old tables entirely instead of removing slots from one table.

[最萌 小汐]

Thank you very much for your help. The performance issue I encountered in the background was indeed caused by this reason.

 I also want to express my gratitude to everyone else who helped; I have learned a lot!

-- sumneko

---

发件人: lu...@googlegroups.com <lu...@googlegroups.com> 代表 Yan <yl.mec...@gmail.com>
发送时间: 2025年5月5日 10:21

收件人: lua-l <lu...@googlegroups.com>

主题: Re: Performance issues when deleting some keys during table construction

--

You received this message because you are subscribed to the Google Groups "lua-l" group.
To unsubscribe from this group and stop receiving emails from it, send an email to lua-l+un...@googlegroups.com.

To view this discussion visit https://groups.google.com/d/msgid/lua-l/d169982d-1d4d-41b1-87c7-b2e2db5249b1n%40googlegroups.com.