Re: object addresses in Lua

["Robert G. Jakabosky" <bobby@...>]

On Monday 30, Xingzhi Pan wrote:
> Thanks for the detailed reply.  I have further questions inlined below.
> 
> On Fri, May 27, 2011 at 11:44 AM, Robert G. Jakabosky
> 
> <bobby@sharedrealm.com> wrote:
> > On Thursday 26, Xingzhi Pan wrote:
> >> Hi,
> >> 
> >> We all know that tables, functions, threads, and (full) userdata are
> >> objects in Lua.  I'm wondering how the addresses of such objects are
> >> treated in the Lua runtime system.  In particular, I want to know how
> >> hard it is (or possible at all) to modify the Lua VM so that these
> >> addresses can change at runtime without breaking the execution of the
> >> running Lua program.
> > 
> > The pointer for some Lua values
> > (lightuserdata,userdata,table,function,thread) are used in the hash
> > value when they are used as keys in a table.  Either you will have to
> > change how those values are hashed, or you will have to re-hash all
> > values that you move.
> 
> I don't quite understand "The pointer...are used in the hash value
> when they are used as keys in a table”.  So you're saying for example
> when a function is used as a key in a table, its pointer is used "in
> the hash value"?  What does "in the hash value" mean here?

"in the hash value" should have been "as the hash value".  Basically I was 
saying that the pointer is used to create the semi-unique hash value for 
complex Lua objects.  For string keys a hash function is used to convert the 
string's contents to a semi-unique hash value.

> I suppose
> this function, as a key, can be used to retrieve a value (e.g., a
> string) from the table.  According to you, how is this value connected
> to this function's pointer?

The Lua code below shows how a function value is used as a key:
local tab = {} -- some table
tab[print] = "some value"
print(tab[print]) -- print value store in previous line.

Lua needs to be able to lookup that key in the internal hash part of the 'tab' 
table, to do that Lua needs to be able to hash the key (convert it to a semi-
unique number) to find the first bucket where that value might be stored.  For 
values that are not a string/number/boolean Lua uses the pointer to that value 
as the hash when doing that lookup.

> > One way to handle the rehashing is to replace the old GC value with a
> > redirect/link value, which contains a pointer to the new location.  Then
> > during garbage collection you can re-hash all link values to the new
> > value.  I haven't read much on compacting GCs, so there might be a
> > better way of handling this.
> 
> Please define "rehashing".  It seems that you're saying adding another
> level of indirection but I'm confused.

Rehashing means to find all keys in all tables that used the old pointer (the 
old hash), which will need to be removed and then re-inserted using the new 
pointer (the new hash).


> >> The motivation behind this question is that I'm playing with Lua's
> >> incremental mark-and-sweep garbage collector and am wondering if it's
> >> possible to replace it with a moving collector (e.g., a copying
> >> collector).  This is a personal project aiming at learning GC and
> >> having fun.
> > 
> > You might want to start by classifying each allocation as
> > movable/non-movable. Some allocations (node arrays in tables, the
> > internal string table) can be moved/reallocated without having to do a
> > lot of fix-ups.
> 
> I guess I need to read more about ltable.c to understand how objects
> are connected together in a Lua VM instance.  But thanks to you I
> already at least realized that they are mainly interconnected via
> tables.  A little pointers would be appreciated.

Yes, I recommend that you understand what the code in ltable.c does.

Vaughan McAlley, has provided more info about how hashtables work, which you 
will need to understand before you try to understand the hashing code in 
ltable.c.

-- 
Robert G. Jakabosky