Re: New array type? (was: 'table' as fallback for tables)

[William Ahern <william@...>]

On Thu, Jul 07, 2016 at 05:01:09PM -0700, Ross Berteig wrote:
> On 7/7/2016 4:05 PM, William Ahern wrote:
> >On Fri, Jul 08, 2016 at 12:36:30AM +0200, Dirk Laurie wrote:
> >>Suppose that t represents the rooms in an hotel. Guests arrive
> >>and leave. You evaluate #t. It tells you where to find an empty
> >>room. You put a guest in that room. Next guest comes. Again
> >>#t finds an empty room. Why is it bad if that room happens to
> >>have a lower number? But it would be bad if the guarantee
> >>that t[#t+1] is empty did not hold.
> >
> >So you've put them in the room. Then what? You can't find them again. You
> >can't do `for i=1,#t do ... end` and expect to find them.
> 
> But what if you don't need to remember. In the hotel case, once they have a
> key and are in a room, for the most part the rest of the hotel only cares if
> that room is occupied (clean it during the day, don't assign another guest
> to it, etc.) or not.
> 
> Besides, the hotel is itself a fixed size array of floors (often with 13
> missing aka nil) each containing a fixed array of rooms. Extending a hotel
> is a big deal, involving lots of money and other resources, and mediated by
> building permits and inspections.

But the hotel in this case isn't fixed sized, and least not in a way that
you can reliably depend on. You can't use #t to find the size; nor to find
the last occupied room; nor even to reliably find _any_ vacant room within
some fixed size, even where more than half the rooms are empty.

When you check them into the hotel, #t might 100. Immediately after checking
them into room 101, #t might now evaluate to 50 because the insertion caused
a rehash, and the first found frontier might shift backward. So how do you
know to clean rooms 1..101 and not 1..10000 or 1..1000000? You'd have to
keep some accounting on the side to know which rooms are occupied, how many,
etc. But it would be completely superfluous. If you have that accounting,
there are simpler alternatives and so there's little utility in relying
alone on t[#t+1] being an empty slot. The even simpler solution, as I said,
if you just want a place to house an object is by doing t[o] = true.

The only way to keep an array compact when removing arbitrary indexes is to
pop the last index and use it to fill the hole. For insertion you always
insert at the end, in which case you're relying on the array being a proper
sequence. You don't even need auxiliary accounting for that.

> So iterating over all rooms is already an O(n) task, and normally doesn't
> stumble over the missing 13th floor.
> 
> >You could remember the index somewhere, but then you've only created a level
> >of indirection. Wherever you store the index you could have kept the object
> >itself. You if you wanted to anchor the object in memory, it would be
> >simpler and more performant to store it as the key.
> >
> >Hmmmm... I guess one use would be for implementating luaL_ref. I'm not sure
> >how useful that would be in Lua code. Maybe I just need to think about it
> >longer.
> 
> IIRC, that is exactly how luaL_ref() was implemented. At least in a
> high-order pseudo-code description. The integer returned is used to look up
> the saved object, and needed to be something (like an integer) that would be
> easy to return to C code as plain data. Using #t+1 to get it is cheap, easy,
> and reliable. And looking it up later is also cheap and easy.
> 

Right, and that makes sense in C code where you use the integer index to
indirectly reference another object. But the reason that's an elegant
solution is because C can't use a reference to the Lua object directly; the
Lua stack API doesn't permit that, and even if so the garbage collector
couldn't trace such a reference for liveness detection. luaL_ref is an
out-of-the-box solution to anchoring for use by C code, because C code has
unique constraints.

I can't think of a use case where that makes sense in Lua code. You don't
have the same kind of anchoring problems because in Lua code you don't need
such indirection. The only similar situation would be caching or
memoization, but I can't think of a scenario where relying on the #t+1
guarantee alone is either more concise or more performant.