lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]

The point is that you don't currently have a non-leaky implementation.

I'm not sure I follow. If it's leaky then that's a bug. Can you show me please?
It still leaks. It just leaks slower than if you weren't using weak
keys. Meanwhile, it's not exactly "leaky" if you think of it as an
interning pool or like memoization, where it's EXPECTED that the
memory usage is monotonically increasing as new unique values appear
-- allowing the memory usage to decrease is an optimization, from that

Uhm, you lost me, sorry :) Maybe you could show me with an example where it leaks?

The standard isn't "never make tradeoffs." The standard is "make sure
the tradeoffs are worth it" with a side of "avoid breaking/penalizing
existing code if you can". And one tradeoff that's ALMOST NEVER worth
it is making an extremely common operation more expensive. It's ALMOST
ALWAYS preferable to add a little bit more per-call cost to a
less-frequent scenario.

What specifically is the overhead and what is the operation?

> Why would they get more expensive? It's the same hashmap algorithm except
> now the hash function is a sum of the hashes of the elements and I don't
> think anyone would object that that should be O(#t) as it is for strings.
> What am I missing?

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?

A built-in tuple would either have more garbage from having multiple
deep copies of non-unique tuples,

No deep copies are necessary. Traversing the elements of the tuple doesn't have to be a recursive operation.

or more long-term memory usage from
having a canonical copy of the tuple interned in a pool.

I'm not sure how interning increases memory usage. Can you explain that point?
All in all: To me it strongly feels like tuples would be better served
by library code (or maybe a power patch) than core code. They aren't
broadly used enough to warrant the corresponding increase in Lua's
footprint, and the people who would benefit from its existence can use
a library or patch.

Now we're back to what I was saying about lib coders vs. app coders. How did you form the opinion that they aren't broadly used in apps? Multi-value indexing is fundamental in any data-rich app (games, web crawling, web apps -- I can't remember an app where I haven't used them).