Re: fastest way to maintain nested tables of counters?

[Mark Hamburg <mark@...>]

On May 15, 2011, at 5:48 AM, Tim Menzies wrote:

> is the following code the best way to handle auto-initialization of nested table cells to zero?
> 
>  function inc3(c,x,y,z) -- inc 3d to zero
>    c[x] = c[x] or {}
>    c[x][y] = c[x][y] or {}
>    c[x][y][z] = c[x][y][z] or 0
>    c[x][y][z] = c[x][y][z] + 1
> end	

function inc3( c, x, y, z )
	local cx = c[ x ]
	if not cx then cx = { }; c[ x ] = cx end
	local cxy = cx[ y ]
	if not cxy then cxy = { }; cx[ y ] = cxy end
	local cxyz = cxy[ z ]
	if not cxyz then cxyz = 0 end -- No need to assign since we will do so below
	cxy[ z ] = cxyz + 1
end

Faster still may be to use metatables.

local setmetatable = setmetatable
local xyzmeta = { __index = function( t, k ) return 0 end }
local xymeta = { __index = function( t, k ) local v = setmetatable( { }, xyzmeta ); t[ k ] = v; return v end }
local xmeta = { __index = function( t, k ) local v = setmetatable( { }, xymeta ); t[ k ] = v; return v end }

Now, initialize c with:

	c = setmetatable( { }, xmeta )

And do the increment with:

	local cxy = c[ x ][ y ]
	cxy[ z ] = cxy[ z ] + 1

The benefit here is that the table misses get detected in the VM index instruction rather than in a subsequent test. On the other hand, the miss handling is more expensive because it incurs function call overhead. So, whether this is faster in practice depends on how often you miss.

(And a really optimized version of the above code might try to share code between xmeta and xymeta in order to reduce the memory footprint for the code, but at that point we're really getting tweaky.)

Mark