lua-users home
lua-l archive

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




On 15/07/16 04:02 AM, Tim Hill wrote:

On Jul 14, 2016, at 1:57 PM, Sean Conner <sean@conman.org <mailto:sean@conman.org>> wrote:

It was thus said that the Great Soni L. once stated:

 Oh, so to clarify (kind of making the bigint library up):

bi = require "bigint"

x = bi.make(2^128) -- syntax issues but I want something
y = bi.make(2^128) -- really really large

t = {}
t[x] = "booya!"
print(t[y])
booya!

 As it stands now, Lua will treat x and y as distinct values whereas Soni
doesn't consider them distinct values (because they're distinct uservalues).

 Oddly enough, Common Lisp *may* treat to values as distinct, i.e. 2 does
not necessarily eq 2 in CL (they may eql and equal, but not eq).  Common
Lisp gets around this by using different forms of equality testing.


Why isn’t this just an exercise in interning, and so just a property of the (hypothetical) bigint library? That is, for any given big integer X, the returned user data is always the same. This also makes equality cheap. Of course there are implementation issues (several occur to me), but it avoids the nasties around __key...

For example, what happens when __key starts returning different values each time it is used? What happens if it returns a very restricted range of keys (and hence stresses Lua’s hash collision processing)? How are collisions avoided for __key values? Remember that __key isn’t returning a hash, it’s returning the definitive unique identifier for that userdata, and Lua assumes these are guaranteed unique for a given type (the hash need not be, of course).

—Tim

We can't have __hash because the reference manual doesn't specify how tables are implemented. For all we know, there could be a Lua table implementation that uses tries, arrays and binary search trees, instead of an array and a hashtable. __key provides a __hash-like interface without breaking such implementations.

Also, if implemented like __gc (a flag on the object), testing for __key is cheap.

--
Disclaimer: these emails may be made public at any given time, with or without reason. If you don't agree with this, DO NOT REPLY.