Re: memory consumed by table

[Rici Lake <lua@...>]

On 16-Aug-04, at 11:36 PM, Paul Du Bois wrote:

> I'm trying to get some rough memory usage numbers for my large lua
> app. Is there any built-in support for figuring out how much memory a
> particular table uses? It can be a shallow operation; I can apply
> domain-specific logic to determine when I want to recurse.

The short answer is "no", I'm afraid.

By the way, tables are not recursive; that is, each table is a separate 
data structure, so a table (some of) whose (keys and) values are tables 
is still just a table. I hope that made sense.

Deleted elements may or may not occupy space in a table and this space 
may be recovered at somewhat unpredictable moments (although it will 
not be recovered except when the table is actually modified). However, 
there is no way either in Lua or with the Lua API to interrogate a 
table about deleted elements.

You can use gcinfo() to find out how much memory (approximately) is 
being used in total by your application. However, that will include 
uncollected garbage at the moment in time. Calling collectgarbage() at 
least twice (and possibly more times) before hand will give you a 
better idea. You could use this technique to periodically spotcheck the 
amount of memory being used; however, the interface will change in 5.1 
so I wouldn't base a complex system on it just at the moment.

You can estimate the amount of memory used by a table in the absence of 
deletions: a table has a fixed size header, an array part, and a hash 
part. Both the array and the hash parts are usually a power-of-two 
number of elements. The array part contains values associated with 
integer keys where the key is in the range 1..n for some n; it is a 
vector of Lua objects. All other key-value pars are stored in the hash 
part, which is a vector of structures consisting of two objects and a 
pointer.

A Lua object occupies 12 bytes on i386 architecture with the default 
numerics (doubles); it would probably be 8 bytes if numerics were 
floats or ints. On a machine where doubles must be doubleword aligned, 
it would occupy 16 bytes. Consequently, in the default architecture 
(that is, numbers are doubles), an array element occupies 12 bytes on 
i386 and 16 bytes on PPC; a hash element occupies 28 bytes on i386 and 
40 bytes on PPC. (I think.) The fixed-size header is, I believe, 32 
bytes on machines with 32-bit pointers, and probably double that, give 
or take a word, on machines with 64-bit pointers.

The array part of the table may be sparse but Lua attempts to keep its 
sparseness to a maximum of 50%; consequently, some integer keys may be 
stored in the hash part of the table. The hash algorithm Lua uses 
allows for quite a high occupancy in the hash table. It does not use 
bucket chains outside of the hash table; all hash elements are in the 
vector, which is doubled in size if necessary.

Once you start deleting elements, as I said, all bets are off.

Hope that helps.

Rici