Re: Tuples and other constant values

[Coda Highland <chighland@...>]

On Mon, Jul 6, 2015 at 3:43 PM, Cosmin Apreutesei
<cosmin.apreutesei@gmail.com> wrote:
>> 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.
>
>
> Did you actually test the code before saying that? My unit tests[1] disagree
> with that statement.
>

No, I did it by inspection, and I do see where I made a mistake in my
analysis. Your implementation is subtly different from my own, and the
memory-freeing trick is pretty clever. Props on that one.

>> >> 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.
>
>
> I know there are two operations, I must be missing something else then
> because I can't see how that would be any different for tuples than for
> strings.

I think at this point I'm the one missing something, because I have no
idea what you're confused about.

>
>> 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.
>
>
> That doesn't make any sense. That would make some of my apps crash in
> minutes.

Yeah, you're right, my recollection was faulty there. Not sure I know
exactly what it was I was thinking about there.

/s/ Adam