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

["Soni L." <fakedme@...>]

On 07/07/16 09:22 AM, Peter Aronoff wrote:
> "Soni L." <fakedme@gmail.com> wrote:
> > You need to think of Lua tables as C strings.
> Two comments:
>
> 1. I have no idea at this point if this is sarcasm or not. But either way,
>     isn’t this tantamount to saying that they are a mistake in the
>     language’s design?

I don't consider C to be a mistake, no. C strings and Lua tables are 
both NUL/nil-terminated sequences. The main difference is that the 
algorithm for Lua table length is O(log n) depending on the 
implementation, while the one for C string length is always O(n).

C strings are good for iteration, but poor for length calculation. 
They're also very efficient in terms of space, however this doesn't 
apply to Lua tables.

Unlike C strings, Lua tables are a general-purpose mutable data 
structure, and this is where nil-terminated really shines. Lua tables 
are efficient whether you use them as arrays or as maps, this wouldn't 
be possible if they weren't nil-terminated. If they weren't nil-terminated:

- #t would return a number directly. This is the only good point.
- t[#t+1]=v would:
    - check if the key is an integer (1 op)
    - check if the value is not nil (1 op)
    - check if the key is greater than the current length (2 ops, as it 
has to retrieve the current length)
    - set the length to the value of the key (1 op)
- t[#t]=nil would:
    - check if the key is an integer (1 op)
    - check if the value is nil (1 op)
    - check if the key is equal to the current length (2 ops)
    - check if how much before the key is empty (O(n))
        - imagine setting t[#t-10] to t[#t-1] to nil, then setting 
t[#t] to nil.
    - set the length to the index of the last nonnil followed by nil (1 
op, we find this in the previous step)
- t[huge_number]=v would potentially cause Lua to run out of memory.
- table.remove and table.insert would have to do all checks t[#t+1]=v 
and t[#t]=nil have to do, as well as being O(n) by themselves, as they 
have to shift elements around.

Alternatively, length could be fixed, having to be manually set. That 
would be even less intuitive than what we currently have.

Overall, this would either cause a huge slowdown in the general case for 
little to no benefit, or be more of a pain than what we currently have. 
What we currently have is a pretty good compromise between intuitiveness 
and efficiency.

> 2. Your reply style (quote everything and add your replies immediately
>     below whatever you’re replying to without any extra space) is pretty
>     painful to read. Would you consider adding in some linebreaks, please?
>     (As an example, I had to scan this reply three or four times before
>     I could find your reply. Trimming down what you’re quoting to the
>     relevant bit and adding some whitespace would go a long way.) Thanks for
>     considering it.

Sorry about that.

> P

--
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.