Re: table.new in 5.3?

[Philipp Janda <siffiejoe@...>]

Am 25.11.2013 18:37 schröbte Coda Highland:
> On Mon, Nov 25, 2013 at 7:00 AM, Philipp Janda <siffiejoe@gmx.net> wrote:
> > Am 25.11.2013 14:54 schröbte Javier Guerra Giraldez:
> > So LuaJIT's `table.clear` should work fine for its purpose (although it's
> > basically an alias for `for k in pairs( t ) do t[ k ] = nil end` anyway).
> > The proposed Lua `table.clear` (or `table.wipe`) would be a way to actually
> > release the memory owned by a clear table, but what I think would be needed
> > more is a `table.fit` function that makes array and hash part exactly as
> > large as needed for the values currently in the table.
>
> I would recommend "table.compact" for that behavior, as the concept of
> compacting free space is well-known.

That's fine with me, too, although I have recently suggested the name 
`table.compact` in another context (where `table.fit` definitely 
wouldn't fit ;-).

I have collected some data about table memory by creating and clearing a 
large array/table and checking what I have to do to make the allocated 
memory change (script attached):

Lua 5.2.2  Copyright (C) 1994-2013 Lua.org, PUC-Rio
memory baseline before:	26.912109375	kB
full array (100000 elements):	8324.51171875	kB
clear array (100000+ empty array slots):	2074.5224609375	kB
after filling (and clearing) 1 array slots:	2074.603515625	kB
after filling (and clearing) 5 array slots:	2074.697265625	kB
after filling (and clearing) 25 array slots:	2074.6982421875	kB
after filling (and clearing) 125 array slots:	2074.69921875	kB
after filling (and clearing) 625 array slots:	2074.69921875	kB
after filling (and clearing) 3125 array slots:	2074.7001953125	kB
after filling (and clearing) 15625 array slots:	2074.701171875	kB
after filling (and clearing) 78125 array slots:	2074.701171875	kB
after filling (and clearing) 1 hash slots:	26.7353515625	kB
after filling (and clearing) 5 hash slots:	27.0087890625	kB
after filling (and clearing) 25 hash slots:	27.947265625	kB
after filling (and clearing) 125 hash slots:	31.6982421875	kB
after filling (and clearing) 625 hash slots:	66.6982421875	kB
after filling (and clearing) 3125 hash slots:	186.69921875	kB
after filling (and clearing) 15625 hash slots:	666.7001953125	kB
after filling (and clearing) 78125 hash slots:	5146.7001953125	kB
full table (100000 elements):	11396.51171875	kB
clear table (100000+ empty hash slots):	5146.521484375	kB
after filling (and clearing) 1 array slots:	5146.603515625	kB
after filling (and clearing) 5 array slots:	5146.697265625	kB
after filling (and clearing) 25 array slots:	5146.6982421875	kB
after filling (and clearing) 125 array slots:	5146.69921875	kB
after filling (and clearing) 625 array slots:	5146.69921875	kB
after filling (and clearing) 3125 array slots:	5146.7001953125	kB
after filling (and clearing) 15625 array slots:	5146.701171875	kB
after filling (and clearing) 78125 array slots:	5146.701171875	kB
after filling (and clearing) 1 hash slots:	5146.6962890625	kB
after filling (and clearing) 5 hash slots:	5146.6962890625	kB
after filling (and clearing) 25 hash slots:	5146.697265625	kB
after filling (and clearing) 125 hash slots:	5146.6982421875	kB
after filling (and clearing) 625 hash slots:	5146.6982421875	kB
after filling (and clearing) 3125 hash slots:	5146.69921875	kB
after filling (and clearing) 15625 hash slots:	5146.7001953125	kB
after filling (and clearing) 78125 hash slots:	5146.7001953125	kB
memory baseline after:	26.396484375	kB

The interesting point is that you can easily reclaim the memory of a 
cleared array by filling up the hash part (one assignment is enough for 
a pure array), but not the other way around. A large hash part stays 
large, unless you overflow it and most of the elements can be moved to 
the array part. I have seen one case though, where the table was resized 
before the hash part was full (try setting `F` to `15` in the test script):

...
clear table (100000+ empty hash slots):	5146.404296875	kB
...
after filling (and clearing) 225 hash slots:	5146.5810546875	kB
after filling (and clearing) 3375 hash slots:	5146.58203125	kB
after filling (and clearing) 50625 hash slots:	2586.5830078125	kB
memory baseline after:	26.279296875	kB

Trying to find out why and when that happens ...

> /s/ Adam

Philipp

#!/usr/bin/lua -v

local N, F = 100000, 15

local clear = table.clear or function( t )
  for k in pairs( t ) do
    t[ k ] = nil
  end
end

local function mem( s )
  collectgarbage( "collect" )
  collectgarbage( "collect" )
  print( s or "memory:", collectgarbage( "count" ), "kB" )
end

local function stresstest( t, n, factor )
  -- fill array part
  local limit = 1
  repeat
    for i = 1, limit do
      t[ i ] = {}
    end
    clear( t )
    mem( "after filling (and clearing) "..limit.." array slots:" )
    limit = math.min( limit*factor, n )
  until limit >= n

  -- fill hash part
  limit = 1
  repeat
    for i = 1, limit do
      local x = {}
      t[ x ] = x
    end
    clear( t )
    mem( "after filling (and clearing) "..limit.." hash slots:" )
    limit = math.min( limit*factor, n )
  until limit >= n
end


mem( "memory baseline before:" )
local t = {}
-- fill array
for i = 1, N do
  t[ i ] = {}
end
mem( "full array ("..N.." elements):" )
clear( t )
mem( "clear array ("..N.."+ empty array slots):" )
stresstest( t, N, F )

t = {}
-- fill hash part of table
for i = 1, N do
  local x = {}
  t[ x ] = x
end
mem( "full table ("..N.." elements):" )
clear( t )
mem( "clear table ("..N.."+ empty hash slots):" )
stresstest( t, N, F )

--[[
for i = 1, 2*N do -- fill up the hash part with array elements
  t[ i ] = {}
end
clear( t )
mem( "clear table transformed to array:" )
t[ {} ] = {}
clear( t )
mem( "clear transformed array after rehash:" )
--]]

t = nil
mem( "memory baseline after:" )