Re: Function to force table to shrink?

Thanks for the reply Roberto!

That was the premise of my "allow rehash" snippet: To add a new key 
leading to a rehash, and to then immediately remove it after.

However, on the latest version of PUC-Lua (commit 
c6b484823806e08e1756b1a6066a3ace6f080fae), I have so far been unable to 
get tables to shrink at all.

When I run your example, it prints roughly the same number 3 times.

Whereas on 5.4, it works as expected, printing a much smaller number 
the third time.

This is consistent with what I see when I run my own testing script 
(<http://vps.luatic.dev/dump/shrink.lua>), which also tries a few more 
things.

Still neither PUC-Lua 5.4 or LuaJIT can be made to reliably shrink 
tables either, even if they're used only as "lists", it seems.

The "add a key to the hash part" trick shrinks only a single time. 
After that, you have a hash part capacity of 1, so the next time you 
try it, it won't work. You'd need to add two keys. Then four keys the 
time after that. And so on. And while doing this, you're also 
increasing the garbage hash part capacity unnecessarily...

This means I can get the array part to shrink (depending on the 
interpreter) by triggering a hash part rehash, but that seems to be 
about the only way, and for the above reason, can't be repeated well, 
so it's not really a solid option.

The hash part meanwhile seems impossible to shrink - unless part of it 
is migrated to the array part - but then we can't drop the garbage 
array part.

Now, what could PUC-Lua do?

It seems that you can get away surprisingly well with not shrinking, 
but I think then this should be mentioned in the reference manual, as 
programmers need to be aware that they should replace the table itself 
if possible, if many entries have been dropped. Currently an 
unsuspecting programmer might very well expect that containers shrink, 
especially as Lua is garbage collected. Indeed, this might present 
itself like a memory leak in some pathological situations: The memory 
usage of Lua is not proportional to the size of the live data 
structures.
As a consequence, iterating a table need not take time proportional to 
the number of entries.

There are ways to ensure a linear relationship between the number of 
entries of a table and its capacity,
but all of them are probably neither cheap (in terms of runtime and/or 
additional memory usage), nor are they particularly simple.
One problem here is that entry deletion not invalidating iterators 
complicates shrinking because it would lose the order.
Either this restriction could be removed, or shrinking could only run 
once it has been explicitly permitted by insertion of a new key-value 
pair.

In the meantime, I think Lua users - at least those that carefully read 
the reference manual - should be made aware of this limitation, and 
perhaps even be given a "table.shrink(t)" or similar that lets them 
explicitly get rid of unused capacity in a table.

- Lars

On Mon, Feb 2 2026 at 16:04:58 -03:00:00, Roberto Ierusalimschy 
<[email protected]> wrote:
>>  I was under the impression that PUC Lua does actually shrink tables
>>  sometimes, at least the hash part, but I will check the sources and 
>> test
>>  again (unless the authors would like to answer off the top of their 
>> heads
>>  ;)) so I can make some reasonable statements about what is likely 
>> to happen
>>  and when.
> 
> A table will shrink if you keep adding keys to it. Adding keys will
> eventually force a rehash; if, at that point, the table needs less 
> space
> than it was using, it shrinks.
> 
> ------------------------------------------------
> local a = {}
> 
> for i = 1, 1e5 do a[i] = true end
> print(collectgarbage"count" * 1024)
> 
> for i = 1, 1e5 do a[i] = nil end
> print(collectgarbage"count" * 1024)
> 
> a.x = true
> print(collectgarbage"count" * 1024)
> ------------------------------------------------
> 
> -- Roberto
> 
> --
> 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 [email protected] 
> <mailto:[email protected]>.
> To view this discussion visit 
> <https://groups.google.com/d/msgid/lua-l/20260202190458.GB10552%40arraial.inf.puc-rio.br>.

-- 
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 [email protected].
To view this discussion visit https://groups.google.com/d/msgid/lua-l/6C6W9T.NLVZWW0B5TS42%40gmx.de.