 |
lua-l archive |
|
|
||
|
Create a tuple. Destroy the tuple. The index tree keeps all of the
intermediate nodes that it had to add in order to pick up that tuple,
and only the leaf node is actually removed.
>> It's not O(#t) for short strings (that is, the kind you're most likely
>> to use as table keys), it's O(1) thanks to string interning.
>
>
> Creating a new string implies hashing it (which implies traversing at least
> part of it). It would be the same with tuples. Hashing is O(min(#s,
> some_threshold)) in both cases. The rest of the lookup algorithm would be
> exactly the same. What am I missing?
What you're missing is that there are two different operations being
discussed here: constructing a value, and indexing into a table.
You don't hash a string every time you want to look up a value in a
table. You intern it once, and then the interned value can be used to
index into a table in O(1) time.
The difference between these methods gets increasingly significant
when you cache tuples in variables.
Interning requires you to maintain a pool of values. If you don't have
a mechanism in place to reap gc'ed values (and AFAIK Lua's string pool
doesn't reap gc'ed strings) then the pool's memory usage is
monotonically increasing.