Most efficient way to determine if a Lua table is empty (contains no entries)?

Question

What's the most efficient way to determine if a table is empty (that is, currently contains neither array-style values nor dict-style values)?

Currently, I'm using next():

if not next(myTable) then
    -- Table is empty
end

Is there a more efficient way?

Note: The # operator does not suffice here, as it only operates on the array-style values in the table - thus #{test=2} is indistinguishable from #{} because both return 0. Also note that checking if the table variable is nil does not suffice as I am not looking for nil values, but rather tables with 0 entries (i.e. {}).

Earthwork

Answer 1

Your code is efficient but wrong. (Consider {[false]=0}.) The correct code is

if next(myTable) == nil then
   -- myTable is empty
end

For maximum efficiency you'll want to bind next to a local variable, e.g.,

...
local next = next 
...
... if next(...) ...

(When next is local, the code finds primitive function next by a constant-time indexing operation into an array of "upvalues." When next is left global, finding next involves indexing index the "environment" hash table, which contains the values of the global variables. This indexing operation is still constant-time, but it is significantly slower than the array lookup for a local variable.)

Evania

Good point on the technical correctness; in the particular cases I've been utilizing the original code, false wouldn't be an expected key so the if not worked fine, but I'll probably make a habit of comparing to nil instead in the future, just as a good habit. And yes, I've been binding common utility functions to local vars for speed. Thanks for the input though. – Earthwork

I find it hard to agree with wrongness when the code works as intended – Woodcut

Why do we gain speed by doing local next? – Nikolai

@Nikolai This is due to how LUA handles its namespace. The very dumbed down version, is it will first climb up the local tables, so if there is a local next in the current block, it will use that, then climb up to the next block, and repeat. Once out of locals, it will only then use the Global Namespace. This is a dumbed down version of it, but in the end, it definitely means the difference in regards to program speed. – Lenard

@Nikolai the less dumbed down version, in the context of lua 5.2 & 5.3, is that non locals are either upvals or _ENV lookups. An upval has to go through an extra layer of indirection, whereas an _ENV lookup is a table lookup. Whereas a local is a register in the VM – Brachycephalic

@Nikolai at run time a global variable requires a hash-table lookup but a local variable requires only an array lookup. – Evania

@NormanRamsey the "local" binding will only improve performance if you use the binding more than once, correct? if you use it only once, then in both cases you'll have one global lookup, but on one case you'll have a local variable binding as well. – Skeptical

Question, why is faster the " == nil" than "if not"? – Comfy

@Comfy It's not faster, it's more correct. if not will miss one case where the table is not empty, as described in the answer, for the table {[false]=0}. next() returns the key, which is false in that example, and if not false will mislead you into thinking the table is empty. The == null approach will work correctly even in that case. – Phenix

Answer 2

One possibility would be to count the number of elements, by using the metatable "newindex" key. When assigning something not nil, increment the counter (the counter could live in the metatable as well) and when assigning nil, decrement the counter.

Testing for empty table would be to test the counter with 0.

Here's a pointer to metatable documentation

I do like your solution though, and I honestly can't assume that my solution is faster overall.

Smarm

The original question is not about counting just "array" entries. – Prelature

0x6's suggestion isn't specific to array-style entries (newindex works for both numerical and non-numerical indices). However, the main issue would be detecting when nil is assigned, since __newindex does not trigger if the key already exists in the table. – Earthwork

For this trick to work, the metatable would have to implement both __index and __newindex, storing the actual data in a shadow table and keeping the real table empty so that __index will be invoked at all. Thinking out loud, I suspect that the raised cost of every single lookup can't be worth it. – Gump

Answer 3

better to avoid the evaluation of __eq if overloaded.

if rawequal(next(myTable), nil) then
   -- myTable is empty
end

or

if type(next(myTable)) == "nil" then
   -- myTable is empty
end

Jarita

I'm a Lua noob trying to understand why this answer was down voted. I'm guessing it is because in Lua, "if two objects have different metamethods, the equality operation results in false, without even calling any metamethod". (The quote is at the bottom of this page from Programming in Lua on lua.org ). Does that remove the need to avoid __eq overloading for nil? – Lovieloving

SansWit: Yes, it does. – Shipshape

Answer 4

This is probably what you wanted:

function table.empty (self)
    for _, _ in pairs(self) do
        return false
    end
    return true
end

a = { }
print(table.empty(a))
a["hi"] = 2
print(table.empty(a))
a["hi"] = nil
print(table.empty(a))

Output:

true
false
true

Aposematic

next() is more efficient (and more concise) than looping over pairs(). – Earthwork

In fact, looping over pairs() is essentially just using the next() technique, but with more overhead. – Adaptation

Also, writing into the standard table library is not recommended. – Danikadanila

Answer 5

try serpent, work for me

serpent = require 'serpent'

function vtext(value)
  return serpent.block(value, {comment=false})
end

myTable = {}

if type(myTable) == 'table' and vtext(myTable) == '{}' then
   -- myTable is empty
end

Menke

Answer 6

I know this is old, and I could be misunderstanding you somehow, but it you just want the table to be empty, that is, unless you are just checking if it is and you don't actually want or need it to be empty, you can clear it by simply recreating it, unless I'm mistaken. this can be done with the below syntax.

yourtablename = {} -- this seems to work for me when I need to clear a table.

Ambiguous

That's not the question. – Terrence

Answer 7

How about this ?

if endmyTable[1] == nil then
  -- myTable is empty
end

Kurdish

This won't work on a table that as strings as index's – Tall

Or a table that doesn't have a value at index 1. Consider {[2] = true} – Proffer

Answer 8

Try using #. It returns all the instances that are in a table. If there aren't instances in a table,then it returns 0

if #myTable==0 then
print('There is no instance in this table')
end

Adenoma

The asker says that # won't suffice here, and gives reasons why; could you explain why this gets around those reasons? – Euphemiah

well...i don't know.I am new in this so the only way i know is using # – Adenoma

# only works on contiguous arrays which begin at index 1. The following tables won't work: {a=true}, {[2]=true}. – Proffer