New Luau should fix this undefined Lua table operation

Feature Requests Engine Features
#1

As a Roblox developer, it is currently too hard to understand why this code does what it does:

print(#{1, 2, 3, nil, 5, 6, 7, 8, 9, nil})   -- prints 9
print(#{1, 2, 3, nil, 5, 6, 7, 8, nil})      -- prints 3
print(#{1, nil, 3, 4, 5, 6, 7, 8, nil})      -- prints 8

The length of a lua table depends on the location of nil values inside the table. According to the Lua manual, this behavior is actually undefined. From the manual:

“it may consider any such nil value as the end of the array”

It doesn’t say which nil value will be considered the end of the table. Hence, the length of these tables is unpredictable.

Not convinced? Look at the following example:

local arr = table.create(1000, "Hello!")
for i = 1, #arr do
    if i % 2 == 0 then
        arr[i] = nil
    end
end
print(#arr)

Every second element is nil. Guess what the code prints:
Answer: 187

This is obviously a meaningless and unpredictable result.

If Roblox is able to address this issue, it would improve my development experience because I wouldn’t have to spend hours debugging code that should work.

In any other programming language (except assembly), assigning array elements would not effect the length of the array. Lua is truly unique in this one. This behavior is impossible to predict and detrimental to development.

Here is another example of unintuitive behavior:

local arr = table.create(1000) -- Allocate 1000 elements
print(#arr)                    -- Prints 0 (where'd they go?)

Another example:

local arr = {nil, "ImportantInformation", nil}
for _, val in ipairs(arr) do
    print(val)       -- Never gets executed
end

Here is a reasonable example of a script that should work, but doesn’t:

-- Return an array of players on the given team
function getPlayersOnTeam(teamName)
	local players = game.Players:GetChildren()
	for i = 1, #players do
		if players[i].Team.Name ~= teamName then
			players[i] = nil
		end
	end
	return players
end

-- Do something with each team member
local teamMembers = getPlayersOnTeam("Green Team")
for i = 1, #teamMembers do
	if teamMembers[i] then
		doWhateverWidthThisTeamMember()
	end
end

I’m not saying that the above code can’t be rewritten in a way that works, I’m saying that any logical programmer would expect it to work, but it doesn’t.

I’m sure nobody relies on this confusing behavior. I hope that in the new Luau runtime, this unpredictable table behavior is eliminated to improve the consistency and intuition of the programming language.

7 Likes
Question about the length operator
Table inspection seems to ignore nil entries when debugging. Also missing locals
#2

I don’t think the example with table.create belongs in this post. Surely you’d want the length operator of a table to refer to the length of the actual ‘contents’ of the array and not the allocated length? I don’t see a case where it’s useful to read the length of an empty array as greater than 0.

6 Likes
#3

Because the behavior is undefined you do not rely on it.

table.create does not bloat the array with arbitrary values. The second argument can be used for just that. The table.create function pre-allocates the given amount of slots. Since Lua arrays don’t have a fixed size, resizing it can be expensive.

For instance when you do this in C#

int[] arr = new int[5] { 5, 10, 15, 20, 25 };

Five ints are expected. It’s kinda the same with table.create but no exception would be raised if array constructed by table.create has too many/too few elements.

tbh with that c# comparison i got kinda lost so it might be wrong comparison, but i included it because of the fixed size idea??

ipairs stops at the first nil value. arr[1] is nil so of course the body will not execute since the iterator function that ipairs returns returned nil.

This replicates the behaviour of ipairs:

function ipairs(a)
    return function(a, i)
        i = i + 1

        if a[i] ~= nil then
            return i, a[i]
        end
        return nil
    end, a, 0
end

for _, v in ipairs({ "a", "b", nil, "c" }) do
    print(v)
end

I an not sure why you set the index to nil without moving trailing elements to the left. Why not use table.remove? It accounts for potential holes after removal of an element by shifting the table elements to the left to close the gap.

4 Likes
#4

Everything’s already been said by the people above me, but I’ll also leave this stackoverflow answer here. It describes the “conditions” lua takes into account when calculating the length of the table, as well as the reasoning behind them: Why does Lua's length (#) operator return unexpected values? - Stack Overflow

3 Likes
#5

Here is a use case:

local arr = table.create(1000)
for i = 1, #arr do
    arr[i] = i
end

This works in every programming language except Lua (and hence it is not intuitive).
In most programming languages, arrays of objects are always initially filled with null values. So it is necessary to be able to properly read the length of an array of nulls before it is populated.

#6

That would be a good justification if we were talking about assembly, C, or C++, but Lua is a very high level programming language. It shouldn’t give the programmer access to undefined behavior in the first place.

#7

As much as you should not rely on UB in general in the first place.

1 Like
#8

It may be my experience with Lua but if anything that seems unintuitive. Lua doesn’t really have null in the same way that Javascript and other languages do. nil is essentially a mixture of undefined and uninitialized. An array filled with nil can either be interpreted as a table filled with undefined or a table filled with nothing. I would rather the language assume nil mean that something was meant to be nothing than assume I meant undefined; I can’t think of a time when I’ve intentionally stored nil in a table.

The length operator is pointedly not a property of the table; it doesn’t indicate how many array slots are allocated, just (roughly) where the last item in the array part is. Consider the following:

local array = table.create(5, "a")
array[5] = nil
for i = 1, #array do
  print(string.byte(array[i]))
end

In a situation like this, why would you want #array to read 5 instead of 4? That would introduce a bug into your code that is completely unexpected.

It’s worth noting that table.create(5) is the equivalent to {nil, nil, nil, nil, nil}. If you created a table like that in normal code (with, say, a stack), the table wouldn’t reallocate when you removed a value from it – allocations only happen when valued are added. Would you want # to return the allocated length of a stack if you popped a value off it, or would you want the new size of the stack?

That said, I think part of the problem is that Lua tables aren’t arrays, even when you make them look like one. Once you skip the index sequence, you should assume you’re creating a dictionary (consider whether {[4737] = true, [100394] = false, [444000] = "foo"} is an array).

2 Likes
#9

The only thing that’s not intuitive in your example is that Lua doesn’t have a way to get the table’s allocated array size. # operator doesn’t check the array’s size, it counts the objects in your table that are indexed with numbers. Since there is no way to pre-allocate table slots in vanilla Lua, there is no reason to define such methods.

#10

Here’s a counterexample: 1

These work the same way, not that you can easily tell from the docs: 2 3

Notice these all talk about “capacity”. Capacity is the size of the memory allocation that has been created to store the contents of the list, not how many items are actually present in the list. table.create is intended to be a capacity-reserving constructor like these other programming language’s methods. If the # operator reported capacity, you’d get all sorts of problems - “I ran table.insert(t, 1) five times! Why is #t 8?!”

The problem Lua has is, unlike those languages, you can place items into arbitrary indices in a table, like 10 or 100 or 1000000, without placing anything in the indices before.

(Lua is smart enough to not create a huge empty backing array in cases like this - it instead uses the hash part of the table that’s used for things like strings. But that makes this more complicated - the array capacity of t = { [100000] = 1 } is zero!)

So what is the length of a table like this? Here are a couple of sane possible answers (and it’s already a problem that there are a couple. If you implemented one, people could reasonably guess the other):

  • The highest natural (integer > 0) index i such that t[i] is non-nil. (or zero, if there’s no such i.)
  • The lowest natural index i such that t[i + 1] is nil. (or zero, if t[1] is zero)

But the problem with these is that they’re slow to compute for tables with a lot in them. For the first one, you’d effectively have to write:

function getLength(t)
    local highest = 0
    for k, _ in pairs(t) do
        if type(k) == "number" then
            highest = math.max(highest, k)
        end
    end
    return
end

This is what is called an O(n) algorithm - the time taken to run it grows linearly with the number of elements in the table.

What Lua does instead is declare that #t is allowed to find any natural i such that t[i] is non-nil and t[i + 1] is nil. Thanks to clever algorithms, this only takes O(log n) time to find, which is much faster for large tables (log_10(1000000) = 6, for instance.)

So that’s why Lua does what it does. I get it, it’s unintuitive, I didn’t even believe this was the behaviour when I was first told. But the alternatives are worse for performance. There is one thing you can do as a programmer to avoid having to deal with this mess - don’t put nil in arrays.

Sorry for the wall of text

5 Likes
#11

Most of what I wanted to say has already been said.

Generally, an array with holes in is a code smell - a sign you’ve got a larger issue with your code. You shouldn’t be putting nil values into the middle of the array part of tables in the first place. If you can name me a problem where using an array with holes is the only reasonable solution, I’ll eat my metaphorical hat :stuck_out_tongue:

I also don’t see much value in exposing array capacity - it’s an implementation detail of tables that doesn’t really seem to serve any good use cases, and it’d be one extra thing to consider and maintain if arrays need certain functional changes down the line. Just use a variable constant instead if you want to numerically iterate over a freshly allocated table (you are using constants in your code, right?)

2 Likes
#12

Here’s a related reply from @zeuxcg:

If you really need to track the length of an array with holes, you should probably store it yourself instead of using #, as the behavior is somewhat undefined. The implementation is a balance between performance and consistency.

2 Likes
#13

I’m going to respond to a bunch of posts here.

A lot of people are comparing Lua tables to Lists or ArrayLists in other languages.

I should point out that the behavior is unintuitive even when compared to those other expanding constructs.

Here is an example in Lua:

local arr = table.create(50, nil)
print("Length is " .. #arr)
arr[1] = "Num 1"
arr[2] = "Num 2"
arr[3] = "Num 3"
arr[4] = "Num 4"
arr[5] = "Num 5"
arr[6] = "Num 6"

arr[1] = nil
arr[4] = nil
arr[6] = nil
print("Length is " .. #arr)
for i = 1, #arr do
   print(arr[i])
end

And the equivalent code in Java:

ArrayList arr = new ArrayList(50);
print("Length is " + arr.size());
arr.add(0, "Num 1");                // Java arrays start at '0'
arr.add(1, "Num 2");
arr.add(2, "Num 3");
arr.add(3, "Num 4");
arr.add(4, "Num 5");
arr.add(5, "Num 6");

arr.set(0, null);
arr.set(3, null);
arr.set(5, null);
print("Length is " + arr.size());
for (int i = 0; i < arr.size(); i++) {
	print(arr.get(i));
}

The outputs are:
In Lua:

Length is 0
Length is 3
nil
Num 2
Num 3

In Java:

Length is 0
Length is 6
null
Num 2
Num 3
null
Num 5
null

Notice that in Lua, the loop fails to iterate over the remaining non-nil contents of the table. Why shouldn’t it continue to iterate over the rest of the non-nil elements? Why did Lua decide to stop at the second nil instead of the first one? Why not stop at the last nil instead? The printout from the Java code seems much more logical to me.

@sncplay42 makes a good point that this confusing behavior is due to “clever algorithms” that only take O(log n) to compute the length of the table. I need to point out that computing the length of an expandable table in other programming languages takes only O(1). From the ArrayList Javadocs:

The size, isEmpty, get, set, iterator, and listIterator operations run in constant time

This is made possible by storing an internal “length” count in a table that is updated (using a constant-time algorithm) every time an table element is modified. It seems to me like this would be a great improvement to the way the length function is currently constructed. The big caveat would be having to distinguish between contiguous arrays and discontinuous dictionaries.

Now that I look back over my examples, I definitely agree. But Lua still fails to compute the non-nil content length in a way that is consistent with other language’s expanding array constructs.

#14

This is not applicable to Lua. Lua already stores the length of the array, but the issue comes that array elements aren’t always in the array part.

https://www.lua.org/source/5.1/ltable.c.html#luaH_getn

Lua optimizes here for when there are no items in the hash part and just uses the internal count of the array part. But when there are items both in the hash and array part, it has no choice but to do a search for the real end of the “array”. This is a binary search, which is O(log n) on average.

1 Like
#15

table.create/new ArrayList(capacity) did not have any (semantic) effect (obviously there was a performance one) in these code samples. (Capacity never does, outside of asking the array what its capacity is.) If you substituted them with {}/new ArrayList() their behaviour would not change (Lua might pick a different boundary to be the value of #t, because it’s unspecified, but either version is allowed to pick any boundary). So I don’t think blame lies with table.create.

The problem is that these aren’t completely equivalent. In Java, arr.set(0, null) places a null value in index 0 of the array - there’s still a value in the array at index 0, but that value is null - null behaves no differently, as far as the array is concerned, than "Num 1" or any other value. In Lua,
table[1] removes table[1] from the table.

What’s the cause of this difference?

A Java ArrayList is a list: for the integers 0 <= i < arr.len(), arr.get(i) will be present and will result in some value. It is an error to attempt arr.get(i) with other values of i.

A Lua table is an associative array (or “dictionary”, or “map”): for any Lua value key, table[key] may or may not be present. If it is present, it will be some value other than nil, if it is not present, it will be nil. table[key] = value causes table[key] to be value, so if value is nil, table[key] must no longer be present. “Presence” matters for things like pairs loops: in for k, v in pairs(t), v will never be nil, because pairs never visits absent keys.

Lua tables have functionality to pretend to be lists (they are even optimized for it with the whole array vs hash part thing), but because nil is special to their associative array behaviour, this emulation breaks down in the presence of nils: if you have t = { 1, 2, 3 } and write t[2] = nil, then t[2] is now absent - there is a gap in the table! Arrays don’t allow that!

(Lua could have instead done what Python does and have a dedicated del(ete) statement and make it an error to access nonexistent keys - that way None (the nil equivalent) isn’t special and this problem wouldn’t happen - but Lua didn’t.)

ArrayList is designed such that this can be the case - the effects of the ArrayList operations are simple: add increments the length by 1, remove decrements it by 1, get and set never affect it.

This isn’t the case in Lua! Look what happens when we try to work out what happens to the length when I write t[100000] = nil:

  • Okay, so if the length of the table was 1000000, it should now be 999999, right?
  • But what if t[999999] is nil? Now we have to check t[999998]. What if it’s nil? - oh no, we’re back to a linear time algorithm!

(This assumes length is defined as the first option in my previous post. With the second definition, the same problem happens if you make t[1] non-nil and t[2], t[3]… already exist.)

The Real Solution to this problem would be to add to Lua a distinct data type for lists/arrays (like every other programming language has), but that’s quite a big change.

Presumably I can’t have been all that sorry for the wall of text, because I’ve done it again.

3 Likes