Re: Random thought: lazy interning
[
Date Prev][
Date Next][
Thread Prev][
Thread Next]
[
Date Index]
[
Thread Index]
- Subject: Re: Random thought: lazy interning
- From: Rici Lake <lua@...>
- Date: Sat, 2 Jul 2005 00:30:32 -0500
If I waited five minutes before blurting things out, I wouldn't make so
many mistakes.
The correct algorithm is to put the __newkey check in rawget: rawget is
raw with respect to the table rather than the key, which would need to
be interned even on a rawget.
So, let's say rawgetraw is the existing rawget. (I mean, it's not
really rawget, since it returns a pointer to the key-value pair, but
we'll write it as though it were):
function rawget(table, key)
local value = rawgetraw(table, key)
if value == nil and type(key) == "userdata" then
local func = getmeta(key, "__newkey")
if func then
local newkey = func(key)
if newkey ~= key then
value = rawgetraw(table, newkey)
end
end
end
return newkey, value
end
Then settable and gettable would call rawget the first time, and if
they recursed to a __index/__newindex which was a table, they would use
rawgetraw on subsequent calls. Note that rawget as written above
returns newkey even if value is nil. Of course, if value is not nil,
newkey is actually the key stored in the key-value pair, so it could
actually still be implemented as returning a key-value pair provided it
was given one to fill in. Or it could just modify the key it was given,
since that is the semantics of lazy interning.
I still don't think it's much overhead. :)
On 1-Jul-05, at 11:46 PM, Rici Lake wrote:
Suppose that I have an immutable userdata type which I would like to
be able to intern, but which I don't always want to intern. Something
like bignums, perhaps: I'd like to intern them for efficiency, but I
don't want to intern intermediate results which are going to disappear
right away. In particular, if I'm going to use the objects as table
keys, I really need to intern them so that the table lookup will work.
What would be necessary for Lua to help me do this? It occurs to me
that it wouldn't require much. If I'm willing to handle the interning,
in some manner (perhaps by constructing a canonical representation as
a Lua string), then I only need to be "informed" when Lua is about to
use the userdata as a table key. (I could handle equality myself in an
__eq metamethod, possibly by interning both comparands and then doing
object equality.)
For example: the settable operation currently calls the table's
__newindex metamethod if the key is not present. But it could also
call the *key*'s __newkey metamethod (if the key were a userdata and
had a metatable with __newkey....)
So the settable loop might look something like:
function set(table, key, value)
if rawget(table, key) ~= nil then
return rawset(table, key, value)
elseif type(key) == "userdata" then
local func = getmeta(key, "__newkey")
if func then
local newkey = func(key)
if newkey ~= key then
if rawget(table, newkey) then
return rawset(table, newkey, value)
end
key = newkey
end
end
-- Now continue with the current algorithm:
return internedset(table, key, value)
end
where internedset is the current algorithm:
function internedset(table, key, value)
local meta = getmeta(table, "__newindex")
if meta == nil then
return rawset(table, key, value)
elseif type(meta) == "table" then
return internedset(meta, key, value)
else
return meta(table, key, value)
end
end
---
I don't think this is much overhead. Is there anyone other than me who
thinks it might be useful?
R.