lua-users home
lua-l archive

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




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.