User hash functions

[RLake@...]

Peter Hill escribió:

> I see your point. You'd have to supply a "__hash" metamethod that covered
> your concept of equality.

> Hmm, maybe that might be handy... use normal (object reference) hashing &
> equality *unless* the object has a "__hash" metamethod!

I don't rule that out. BUT there are a few counterindications.

First of all, hash is called a lot. (And it happens to be called in some
very sensitive contexts in which adjusting the stack would be a bad idea,
although that is simply an "implementation issue".)

Second, it is *very* difficult to write good hash functions for equivalence
classes in general. A hash function which fails to guarantee that hashes
will be the same for all members of an equivalence class leads to bugs
which are extremely difficult to find and fix. A hash function which fails
to randomly distribute hash values leads to random performance degradations
which are also extremely difficult to find and fix. So writing hash
functions is an art.

Third, Lua itself does not lend itself to bit manipulations. So probably
any hash function would have to be written in C.

Fourth, hashing a value implies that the value is immutable. That is, once
a key is inserted with a specific hash into a table, the hash cannot
change; otherwise the key is in the wrong place. This also leads to bugs
which are extremely difficult to find and fix.

Now, with all of the above, I suppose it is feasible that a metatable of a
userdata could do it's own hashing. This would not be a regular metamethod
because (1) and (3) effectively prevent Lua from being used to write hash
functions, and (4) prevents the application to a Lua table (since Lua
tables are not immutable). Because of (4), it is not necessary to compute
the hash more than once, so it can simply be computed at object creation.
Consequently, this would require the addition of a "hash" data field to
userdata objects (overhead: one int per userdata) and a new call which
pushes userdata with a defined hash value. (Adding the hash value after the
userdata has been created could be convenient -- you might need the memory
allocated for the userdata in order to compute its hash value -- but it
would have to be very clear that that can only be done before the userdata
is handed back to Lua the first time.)

Having said all that, I realise that the patch to make this possible is
almost trivial. Therefore I would recommend that it not be added to the
language, but that embedders who wish to do this apply the patch
themselves. I think it is something that few people would want to do; it is
not really orthogonal with the language design; and the overhead, however
small it is, is therefore not justifiable. If you are really interested in
doing this, wait until the final Lua 5.0 is out, I'll give you some hints
on how to do the patch.

R.