Function to force table to shrink?

[Rett Berg]

I've just released a library to create immutable types which works by moving all the values to a separate proxy table. As another programmer pointed out to me however, the original table will continue to use all of its memory despite the fact that it is now guaranteed to be forever empty.

Is there an API (C or Lua) which can force a table reference to be shrunk/empty? Can one be added to force such a condition?

I think the current default is better for most cases BTW, but it would be good to let the programmer decide whether they will need the memory.

- Rett

[Rett Berg]

Just some thoughts.. if this were difficult, an alternative (for my use-case at least) is to allow just "clearing" a table's contents in-place.

A more general solution (but obviously quite dangerous) might be to swap the contents of two tables but preserve their IDs.

[Jure Bagić]

> Is there an API (C or Lua) which can force a table reference to be
> shrunk/empty? Can one be added to force such a condition?

AFAIK there is no such C API function to shrink the table memory, either in
array or hash part. And that is why there is no such Lua function in any of the
Lua standard libraries.

If you just want to clear the table but re-use it, just set all of the entries
to nil:

If you want to free the table object, make sure the table is unreachable (not
referenced by any local/global/field variable, upvalue, etc...) and then call
'collectgarbage' to invoke the garbage collector which will collect your
unreachable table thus freeing it's memory.
Small example:
> local t = { "test", a = "bla", 5, 7 };
> t = nil; -- table no longer reachable
> collectgarbage(); -- table memory freed by the garbage collector

Lua internally re-sizes the array/hash part of the table via 'luaH_resize' but
such a thing is not exposed via C API.

-- Jure

[Martin Eden]

On 2026-01-28 18:16, Rett Berg wrote:
> the original table will continue to use all of its memory despite the fact
> that it is now guaranteed to be forever empty.

Well, I checked it, that's correct. Kinda strange for hash-centric language.
Does PiL mentions "don't use table as buffer" idiom?

I wrote snippet to write to Buffer[S]..Buffer[S + N]. And then clean
data by writing nils there.

I did three calls with big chunk and one call with small chunk.

I did expect memory consumption be plateau with drop at end for
small chunk. However I observe first mountain when Lua stores
data as array. For second call it starts to store data as hash and
I see second mountain with plateau. Last call with small chunk
has no effect. Inflated memory just stands there.

Posting code and mem graph.

-- Martin

P.S. collectgarbage() won't help, table is reachable.

-- ( Code
--[[
  Table memory allocation test

  Writes data to new block in Buffer. Clears that data.

  You may expect that Buffer size is proportional to size of last block.
  But in Lua 5.4 it's proportional to maximum size of block ever written.

  -- Martin, 2026-01-29
]]

local Buffer = {}
local AllocMem
do
  local StartNum = 1
  AllocMem =
    function(N)
      local EndNum = StartNum + N - 1
      print('StartNum', StartNum, 'EndNum', EndNum)
      for i = StartNum, EndNum do
        Buffer[i] = i
      end
      for i = StartNum, EndNum do
        Buffer[i] = nil
      end
      StartNum = EndNum + 1
    end
end

local BigChunk = 5 * 1e8
local SmallChunk = 1 * 1e8
AllocMem(BigChunk)
AllocMem(BigChunk)
AllocMem(BigChunk)
AllocMem(SmallChunk)

print('Done')

while true do end
-- )

[Rett Berg]

Thanks for the confirmation. I think I have an idea of how to solve this.

Best,

Rett

--
You received this message because you are subscribed to a topic in the Google Groups "lua-l" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/lua-l/vAcAMy7GFJY/unsubscribe.
To unsubscribe from this group and all its topics, send an email to lua-l+un...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/lua-l/b5b24ff3-68b7-4e69-a34d-bed6ca15ad15%40disroot.org.

[Lars Müller]

This is an unfortunate consequence of the requirement that items can be deleted from a table while it is iterated. This means that you more or less need to avoid a rehash, because that would change the iteration order while you are iterating.

A trick to permit a (shrinking) rehash is to rawset a *new* entry, e.g. using a fresh table as key (by reference), then deleting that entry afterwards. But this need not work, it depends on whether the implementation decides to shrink.

I'm also not a fan of this behavior because it means that the "garbage collection" is unintuitive: There is no guarantee that after a full collection, the memory usage is in any way proportional to the actual observable size of the data being stored.

The solution Lua currently wants you to use is to replace the table if you drop most of its contents and need the memory back. Alternatively, Lua could fix this, even while allowing the deletion of elements during iteration, but a more sophisticated, likely less efficient table representation would be required for this.

I wrote at a bit more length about this in a blog post: https://luatic.dev/posts/2025-04-12-lua-misconceptions/#setting-elements-to-nil-frees-up-space

- Lars

--

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/b5b24ff3-68b7-4e69-a34d-bed6ca15ad15%40disroot.org.

[Martin Eden]

On 2026-01-29 16:38, 'Lars Müller' via lua-l wrote:
> This is an unfortunate consequence of the requirement that items can
> be deleted from a table while it is iterated. This means that you more
> or less need to avoid a rehash, because that would change the
> iteration order while you are iterating.
>
> A trick to permit a (shrinking) rehash is to rawset a *new* entry,
> e.g. using a fresh table as key (by reference), then deleting that
> entry afterwards. But this need not work, it depends on whether the
> implementation decides to shrink.
>
> I'm also not a fan of this behavior because it means that the "garbage
> collection" is unintuitive: There is no guarantee that after a full
> collection, the memory usage is in any way proportional to the actual
> observable size of the data being stored.
>
> The solution Lua currently wants you to use is to replace the table if
> you drop most of its contents and need the memory back. Alternatively,
> Lua could fix this, even while allowing the deletion of elements
> during iteration, but a more sophisticated, likely less efficient
> table representation would be required for this.
>
> I wrote at a bit more length about this in a blog post:
> <https://luatic.dev/posts/2025-04-12-lua-misconceptions/#setting-elements-to-nil-frees-up-space>
>
>
> - Lars

Thanks for link to your essay Lars, I enjoyed reading it much!

However I don't understand how and why your proposed hack can force
table rehash:

  local allow_rehash
  do
    local key = {} -- can't be in the table, because table equality is
by reference
    function allow_rehash(t)
      rawset(t, key, true) -- following this, lua is allowed to rehash t
      rawset(t, key, nil) -- restore t to original state
    end
  end

Tried it and saw no effect.

And I share opinion that collectgarbage() is not intuitive. It does
nothing for tables with nils occupying all memory.

I would join to Rett's proposal for table garbage-collect/shrink/rehash
function.

Maybe add one more ad-hoc string argument to collectgarbage()?

  collectgarbage('table', t)

  Forces rehash of table <t>. Frees memory by not storing empty slots.
  Side effect is keys sequence reordering so do not mix with
next()/pairs().

-- Martin

[Rett Berg]

Just want to quick say that I attempted an approach which returned a new (empty) table when a table was frozen, rather than freezing the table "in-place".

Of course this in-theory works, but the problem is something like the following

extra = {}

t = {

  e = extra,

}

t, extra = freeze(t), freeze(extra)

Note that you wouldn't directly do the above, but you _would_ (1) build a table, (2) use the table for one or more fields in another table, (3) try to freeze one or both.

Basically, when you freeze(t) it will create a "frozen" version for `t.e`, but the  `extra` var will NOT be frozen. In my implementation I attempted to use the raw table as the proxy value - which had other issues I won't go into here.

To protect against this I would need to make a copy of the values, and for values used multiple times I'd be making multiple copies. I'd strongly prefer being able to GC the empty tables 

Best,

Rett

--
You received this message because you are subscribed to a topic in the Google Groups "lua-l" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/lua-l/vAcAMy7GFJY/unsubscribe.
To unsubscribe from this group and all its topics, send an email to lua-l+un...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/lua-l/cb1ab78e-3b0e-49c6-8332-541f4ea424aa%40disroot.org.

[Lars Müller]

Glad you liked it!

Sorry if I made it sound like this hack can "force" a rehash. It can not. It can only "allow" it, meaning a space-conscious Lua implementation would be allowed to rehash without worrying about breaking iteration.

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.

By the way, as for the discussions for how Lua could be extended: I think a "table.rehash" function (name TBD) which shrinks the table would not be unreasonable, and not dissimilar to existing features in many other languages, like C++'s std::vector::shrink_to_fit (though that shrinks a bit more aggressively than we would like in Lua). LuaJIT already has a "table.clear", but this is explicitly supposed to keep capacities intact.

An extension of collectgarbage would feel a bit dirty.

- Lars

--

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/cb1ab78e-3b0e-49c6-8332-541f4ea424aa%40disroot.org.

[Martin Eden]

On 2026-01-30 02:56, 'Lars Müller' via lua-l wrote:
> By the way, as for the discussions for how Lua could be extended: I
> think a "table.rehash" function (name TBD) which shrinks the table
> would not be unreasonable, and not dissimilar to existing features in
> many other languages, like C++'s std::vector::shrink_to_fit (though
> that shrinks a bit more aggressively than we would like in Lua).
> LuaJIT already has a "table.clear", but this is explicitly supposed to
> keep capacities intact.
>
> An extension of collectgarbage would feel a bit dirty.
>
> - Lars

Hello Lars, well I disagree here.

Stock "table" module functions (concat, pack, unpack, sort, insert,
remove, move) do produce results observable in code. You can write
test for them.

Empty table slots (t['a'] = nil) are not observable. pairs() will never
return you key with nil value.

For that "dark matter" we have "shaman" function collectgarbage().
Which you also can't independently test.

It deals with mysterious "garbage". And when your code replaced
main tables it may come there and say: "Oh collectgarbage()!
We with guys just switched flow to new data tables. We kindly ask
you to free memory from the old ones."..

And so it will come there again and say similar thing regarding
table at which they discharged gatling and so now it has many holes.

-- Martin

[Gé Weijers]

On Fri, Jan 30, 2026 at 12:09 PM 'Martin Eden' via lua-l <lu...@googlegroups.com> wrote:

Stock "table" module functions (concat, pack, unpack, sort, insert,
remove, move) do produce results observable in code. You can write
test for them.

Empty table slots (t['a'] = nil) are not observable. pairs() will never
return you key with nil value.

A 'rehash' would change the order in which 'next' and therefor 'pairs' would return key-value pairs, and when 'rehash' is called during an iteration you'd likely see duplicate values. You cannot add new key values to a table during an iteration for the same reason.

One primitive that could be useful instead of 'table.rehash' would be a 'table.swap', which would swap the contents of two distinct tables, i.e. swap the array and hash table sections of the two tables and their metatables without allocating or deallocating anything. The garbage collector would have to be aware of this, I assume, just like it has to be aware of growing a table.

A rehash could look like the following code, and you could do more with this, like make a table read-only by introducing a proxy table in O(1) time.

local function rehash(t)

  local new_t = {}

  for k, v in pairs(t) do new_t[k] = v end

  table.swap(t, new_t)

end

local function read_only(t)

   local proxy = {}

   local mt = {

     __index = proxy,

     __newindex = refuse, -- left to the reader

     __pairs = function(_) return pairs(proxy) end,

   }

   setmetatable(proxy, mt)

   table.swap(t, proxy)

end

Just an idea. 

--

Gé

[Roberto Ierusalimschy]

> 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

[Rett Berg]

Okay, so a `clear` algorithm could:

* set all keys returned by pairs() to nil
* set any key (i.e. t.a) to any value, then back to nil.

The table will then be effectively clear.

SGTM, thanks for the tip!

It would still be nice IMO to have a table.clear() which just
force-deallocates the table since this would save the cost of manually
setting every key to nil, but this isn't required for my use-cases.

Best,
- Rett

> --
> You received this message because you are subscribed to a topic in the Google Groups "lua-l" group.
> To unsubscribe from this topic, visit https://groups.google.com/d/topic/lua-l/vAcAMy7GFJY/unsubscribe.
> To unsubscribe from this group and all its topics, send an email to lua-l+un...@googlegroups.com.
> To view this discussion visit https://groups.google.com/d/msgid/lua-l/20260202190458.GB10552%40arraial.inf.puc-rio.br.

[bil til]

> It would still be nice IMO to have a table.clear() which just

sorry for a stupid question, I did not really understand all the
details of this discussion.

But if for a table t you just write t=nil, won't this also delete the table?

(so it would do the same as what you want to do by t.clear()?

[Rett Berg]

Yes, but I want other references to see an empty table 

For example, if there are a bunch of workers (coroutines) putting stuff to do into a table. After all the stuff is done I could do table.clear

ITT I literally move all values to a proxy, then clear the table.

--
You received this message because you are subscribed to a topic in the Google Groups "lua-l" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/lua-l/vAcAMy7GFJY/unsubscribe.
To unsubscribe from this group and all its topics, send an email to lua-l+un...@googlegroups.com.

To view this discussion visit https://groups.google.com/d/msgid/lua-l/CAOnDXmHrPmsSRsq6MtnQkOp7oV%2Batt_7G8oeFGnLtrpbGWTVBQ%40mail.gmail.com.

[Rett Berg]

For my example I should have added "now the workers see an empty table that they can keep putting work on"

[Roberto Ierusalimschy]

> Okay, so a `clear` algorithm could:
>
> * set all keys returned by pairs() to nil
> * set any key (i.e. t.a) to any value, then back to nil.
>
> The table will then be effectively clear.

Unfortunately, it is not that simple. You must add enough new keys to force
a rehash. In the example I gave, the table had only integer keys, all in
its array part, so the hash part was empty (no slots). One new element there
was enough for a hehash. But other scenarios can be way more tricky.

-- Roberto

[Lars Müller]

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 <rob...@inf.puc-rio.br> 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 lua-l+un...@googlegroups.com. To view this discussion visit https://groups.google.com/d/msgid/lua-l/20260202190458.GB10552%40arraial.inf.puc-rio.br.

[bil til]

> For my example I should have added "now the workers see an empty table that they can keep putting work on"

But this sounds, as if the "workers" have to inquire this table state
very often and regularly.

In this case I would typically strongly prefer to present an "element
counter variable" for this table, although this adds a small overhead
for every key add and key delete (inc/dec this counter... also it
might then be better to hide / encapsulate the raw table in a sort of
class - so that access only possible by access functions).