Lua misconceptions

This is a collection of various Lua misconceptions I have seen over the years.

To clarify matters regarding language semantics, we look at what the reference manuals guarantee; the relevant guarantees haven't changed from version 5.1 through 5.4.

Unfortunately the reference manuals hardly guarantee any performance characteristics, which a lot of misconceptions revolve around. We consider the two most prevalent implementations, the reference implementation, PUC Lua, and LuaJIT, renowned for its speed.

Numbers

"Numbers are exact"

This is not limited to Lua; every now and then novice programmers naively expect 0.1 + 0.2 == 0.3.

Long story short: Most programming languages use IEEE-754 binary floating point numbers, usually 32 or 64-bit. Some decimals which can be represented exactly in the decimal system, such as $0.1$, $0.2$, $0.3$, thus are periodic in the binary system and can't be represented exactly, leading to truncation when represented with a finite number of bits, e.g. 64-bit in Lua. This incurs rounding error for the last digit. When you're adding 0.1 and 0.2, you're actually adding 0x1.999999999999ap-4 (closest 64-bit float corresponding to 0.1) and 0x1.999999999999ap-3 (0.2, note how it has the same significant digits and just a different exponent) to produce 0x1.3333333333334p-2 which is off by exactly the least significant bit from the naively expected result of 0x1.3333333333333p-2 (closest float to decimal 0.3).

The solution / "workaround" typically is to not do exact float comparisons, introducing a small margin of error (tolerance). If you're just interested in absolute error, you'd typically test math.abs(a - b) <= tolerance rather than testing for equality; if you're interested in the error of b relative to a, you might want to go with something like math.abs((a - b) / a) <= epsilon - be careful with a close to zero though.

Now why would programmers believe that floats are exact? The reason is that most programming languages covertly do the rounding for the programmer when stringifying floats. If you print(0.1 + 0.2), you will get 0.3 and suspect nothing.

tostring and everything that uses it (print, table.concat etc.) will thus willingly lose precision of floats in order to present the user with a "nicer", rounded value rather than requiring the programmer to make it explicit. It is all too common that serializers simply use tostring, unnecessarily losing float precision. ¹

To serialize floats properly, you need at least 17 significant digits, meaning you should use a format specifier like %.17g for formatting. ²

"Floats can't be exact"

However it isn't true that floats always incur an error either. A common misconception is that using floats to represent integers will result in imprecisions as well, which is not the case for reasonably sized integers at all: -2^53 up to and including 2^53 can be represented exactly. ³

Representing integers with 53 (54 if you count the sign) bits exactly, floats make 64-bit integers largely obsolete and there's typically no need to worry about using floats for integers, unless you're working with something which explicitly uses those 10 bits - for example user IDs which were generated by another application to be 64 bit.

Strings

"Concatenation is fast"

What do we mean by this?

Developers may be used to the performance characteristics of languages that defer concatenation: They construct a linked data structure of strings (often called a "rope") under the hood, and when the string is read from (e.g. to print it), concatenate this rope on demand.

For example, try the following piece of code in a well-optimized JS engine (e.g. V8, SpiderMonkey, JavaScriptCore):

const n = 1e6;
let s = "";
for (let i = 0; i < n; ++i)
	s += "a";
console.log(s[Math.floor(Math.random() * n)]); // a

This will run in the blink of an eye. Now try the equivalent Lua in PUC Lua or LuaJIT:

local n = 1e6
local s = ""
for _ = 1, n do
	s = s .. "a"
end
local i = math.random(n)
print(s:sub(i, i)) -- a

This will be multiple orders of magnitude slower, taking some minutes on my machine. And Lua is not alone with this.

Most language implementations transparently do concatenation eagerly; JavaScript engines (and lazily evaluated languages) are the exception. This means you generally should expect a .. b to take time linear in #a + #b, and you should avoid building up strings by repeated concatenation (e.g. in a loop as in the above example) - otherwise you easily run into quadratic time complexity, making your code very slow for longer strings. Instead, you should generally use table.concat (or, in this example, ("a"):repeat(1e6)). Try it:

local t = {}
for i = 1, 1e6 do
	t[i] = "a"
end
local s = table.concat(t)

In other languages you would use the equivalent of a string buffer / builder / stream, whatever it may be called. LuaJIT even provides an extension for string buffers specifically.

"Concatenation in a row is slow"

As we've just seen, a concatenation takes time linear in the lengths of the operands. What if we have a long expression that's just a bunch of concatenations "in a row"? Say:

local s = s1 .. s2 .. --[[...]] .. s99 .. s100

This situation often occurs when constructing large strings with lots of variables to be inserted. Now you could be inclined to believe that this would be executed something like this, thus incurring a similar performance problem as the one we just saw ⁴:

local s = s100
s = s99 .. s
s = s98 .. s
-- ...
s = s2 .. s
s = s1 .. s

(Note that concatenation is right-associative, so a .. b .. c is evaluated as a .. (b .. c), not (a .. b) .. c.)

But practically, it's even better: PUC Lua and LuaJIT have an optimization for such expressions - they have a variadic concatenation operation under the hood. All hundred strings s1, s2, ..., s99, s100 will just be pushed on the stack and concatenated in one go.

"Checking string equality is slow"

On LuaJIT and PUC Lua 5.1, all strings are interned: When a string is created, it is essentially looked up in a global hash map. If the string already exists, the existing instance will simply be reused. Since this can be done in expected linear time, it does not hurt the asymptotics of string creation.

The very desirable consequence is that string comparisons are just cheap constant time reference comparisons. Comparing strings is as cheap as comparing numbers. Using strings for "enums" is completely fine and encouraged. And importantly, looking up a string key in a table is essentially as cheap as looking up a number in a hash table; it runs in expected constant time.

This is also good for memory usage and caching, because strings are not duplicated unnecessarily.

However, you do often unnecessarily pay the modest constant factor cost of interning on string creation. In an attempt to make a better tradeoff, since 5.2.1, PUC Lua distinguishes between "long strings", which may have to be compared in up to linear time, and short, interned strings based on length. ⁵

"Lua strings prescribe a certain encoding"

No, Lua strings are 8-bit clean: They are just "byte strings". They are used for human-readable "text" and binary data alike. They can contain null bytes. ⁶

If you use Lua strings to encode Unicode code points, you should use UTF-8 encoding by convention, which is also supported by the standard library (utf8 module) and the rest of the sane world. But there is nothing fundamental about Lua strings that forces you to use UTF-8.

Patterns

"Character classes are always the same"

Sadly Lua inherits a locale-dependence from C here: It simply uses the is* functions from ctype.h. This is documented in the reference manual:

The definitions of letter, space, and other character groups depend on the current locale.

This means that for example %u probably is equivalent to ASCII [A-Z], but you can't be sure of it; perhaps you're on some locale where some bytes from the 128 - 255 range represent uppercase letters such as ÄÖÜ.

Note also that character classes are generally wholly inadequate for processing Unicode code points: They only work if you have exactly one byte per codepoint (ASCII).

"Patterns are fast"

The implementation in PUC Lua and LuaJIT is unfortunately a naive backtracking one and thus can get essentially arbitrarily slow given a sufficiently bad pattern, such as

assert(not ("a"):rep(100):match(("a*"):rep(10) .. "b"))

See my post for an explanation (and why it is unfortunately not trivial to do better for all patterns).

However, if you have a rough idea of how such a backtracking engine works, you can tell whether a pattern can be matched in linear time.

Tables

Length operator misconceptions

"#t is the number of entries in the table t"
"#t is the index of the largest/smallest/cutest positive integer key in the table t"
"#t is slow because Lua has to linearly search through the entire table t"

The length operator #t is defined to yield any valid boundary - that is, an index i >= 1 such that t[i] ~= nil and t[i+1] == nil, or 0 if no such index exists (which is the case precisely if the table is empty; this is typically detected by t[1] == nil); this means that excepting the edge case of number type limits, t[#t + 1] will always be nil and setting t[#t + 1] = x will never overwrite an entry.

This seemingly odd specification, which allows for multiple possible values of #t for a given table t, exists to allow Lua implementations to optimize this using a binary search on the table. Thus in a good implementation, it takes worst-case logarithmic, not linear time.

However this is of course still much slower than if the length is stored in a variable or field. Different PUC Lua versions (and other Lua implementations) optimize this differently; many attempt to cache length in one way or another (the downside then being that this cache needs to be kept up to date).

Let's look at a few examples:

#{1, 2, 3} is 3: This is the intended usage of the length operator - to get the length of a sequence of elements.
#{a = 1, b = 2} is 0: The table has no numerical keys. This surprises those who think #t "counts" the number of entries. Those who (falsely) believe Lua to have a clear distinction between "lists" and "maps" may think they know what's going on.
#{1, nil, 3} can be either 1 or 3, since the second element is nil (a "hole").
This surprises everyone who doesn't know the exact definition.

As an extreme example, consider the following innocuous snippet:

local function table_append_all(t, ...)
	for _, v in ipairs({...}) do
		table.insert(t, v)
	end
end
local t = {1, 2, 3}
table_append_all(t, 4, 5, 6)
print(table.concat(t, ", ")) -- 1, 2, 3, 4, 5, 6

Works as expected, right? Well, only if there are no nils in ..., and no holes in t.

Consider table_append_all({1, nil, 3}, 4, 5). You don't know what happens next.

Lua could say #{1, nil, 3} is 1. Then the first table.insert would result in {1, 4, 3}, "filling" the hole; you would end up with {1, 4, 3, 5}.

Or it could say the length is 3 and thus start appending at the end, giving you {1, nil, 3, 4}. And then again, the same problem reoccurs: 5 can either be inserted into the hole or at the end.

Which of these three things happens ultimately depends on various factors and is not trivial to predict.

But that's not all: What happens with table_append_all({1}, 2, nil, 3)? What should even happen? It could make sense to ignore the nil, as table.insert would. It could make sense to error. But what do we do? We simply ignore everything after 2. ipairs only iterates values in sequence until it hits the first nil. This is certainly not what we want.

For reasons like this, generally try to avoid holes in tables you plan to use like "lists". (Oh, and also, always use select for iterating varargs.)

"`pairs` always iterates tables in the same order"

It doesn't. The only guarantees are that it visits all entries in some order; and that you can set values to nil during iteration. In PUC Lua and LuaJIT, pairs just goes through the array and hash part. The sequential entries (keys 1, 2, ...) are usually traversed in order (pairs "degrades" to ipairs), but you may not rely on this. ⁷

To traverse a sequence in order, use ipairs rather than pairs. Only use pairs if order does not matter. All other entries are traversed in whatever order the hashes are in, which may also depend on insertion order. Newer PUC Lua versions also seed the hashing with each run (to prevent hash collision attacks), so it won't even be consistent across runs.

The reference manual has the final say, and no guarantees regarding order are made.

"You can't delete entries while iterating"

You can - this is guaranteed in Lua (but not in other languages).

Implementation-wise, the hash tables usually don't delete entries, they just mark them for deletion; the actual deletion is then deferred to either another element overwriting the deleted slot or a rehash happening (triggered by the insertion of a new key), which may shrink the table.

Just deleting elements will however not shrink the table. Thus it's not an issue if you mark an element as deleted while iterating. Generally, you can change values while iterating, including setting values to nil.

"Tables are just hash tables"

While conceptually you can, and often should, view tables as "associative arrays", it is wrong to conclude that they need to be implemented as hash tables. Some entries may be stored in an "array part" by both PUC Lua and LuaJIT. In these implementations, each table consists of a hash part and an array part; both may be empty, but both may also be nonempty - a table may be "mixed". This may be confusing to programmers who are used to having an explicit distinction between lists and maps. Whether entries use the hash or array part depends on how the table is populated.

Typically, if entries are added sequentially, you can expect the array part to be used. ⁸ That is, if keys 1 to n are in the array part and you add key n + 1, the array part may be extended to fit the new key. Thus you sometimes see the following pattern for "allocating" the array part:

local t = {}
for i = 1, 42 do
	t[i] = nil
end

Similarly, table constructors like {1, 2, 3} or {x = 1, y = 2, z = 3} allocate a table to the right size from the get go.

"Setting table entries to `nil` frees them"

Setting table entries to nil does remove the references to key and value of the entry, but the unused table slot may remain. ⁹

In the hash part, it may be used again by any other key later on; in the array part, it will only be used again for the same key.

Note that LuaJIT and PUC Lua never shrink tables when you're just setting entries to nil. Consider the following code:

local t = {}
for i = 1, 2^20 do
	t[i] = i
end
for i = 1, 2^20 - 1 do
	t[i] = nil
end

Slots 1, 2, ..., 2^20 - 1 will still taking up memory as long as t lives.

Now suppose you were to iterate this table:

for _, v in pairs(t) do
	print(v)
end

This will run rather slowly: It has to iterate over all 999999 empty slots in the array part to find the one live slot!

In a nutshell, there are two nasty consequences for asymptotics to be aware of: Neither memory usage nor the time required for the iteration of tables is necessarily proportional to the number of currently live entries.

This surprisingly seems to be not all that problematic in practice, but it might conceivably lead to denial-of-service vulnerabilities in some scenarios; an attacker could simply populate a table with "dead" entries which the program logic doesn't care about, then exploit the unexpectedly large memory usage or runtime.

In order to allow Lua to rehash a table, you must insert something new:

local not_in_table = {} -- can't be in the table, because table equality is by reference
rawset(t, not_in_table, 42) -- at this point, lua may rehash t
rawset(t, not_in_table, nil) -- restore t to its original state

Varargs

"Nothing is the same as `nil`"

No, varargs distinguish and preserve nils. ¹⁰ An empty vararg is not the same as a vararg containing a single nil value.

local function f()
	return
end
local function g()
	return nil
end
print(f()) -- empty line
print(g()) -- nil

The reason for this confusion is that when evaluating varargs as expressions, Lua truncates them, coercing "none" to nil:

local a = f()
print(a) -- nil

You can notice the difference when you do math.min(1, nil) vs math.min(1). One will error, the other won't.

In general, select("#", ...) gives you the true length of a vararg, including nils. You can then use select(i, ...) to look at varargs starting at the i-th element. select should be your go-to tool when processing varargs.

"The comma 'operator' concatenates varargs"

local function f()
	return 1, 2, 3
end
local function g()
	return 4, 5, 6
end
print(f(), g()) -- 1, 4, 5, 6

In any list of expressions in Lua, all varargs except for the last one get truncated to the first value (or nil if they are empty).

This may also cause surprises if you expect the last vararg to be truncated. If you want to be sure, surround it with parentheses: (g()).

Be careful - this also applies in perhaps unexpected ways in table constructors:

local function f()
	return 1, 2, 3
end
local t = {f(); foo = "bar"}
print(table.concat(t, ", ")) -- 1

"Collecting varargs in a table is fine"

Every now and then you see something like

for _, arg in ipairs{...} do
	print(arg)
end

local t = {...}
for i = 1, #t do
	local arg = t[i]
	print(arg)
end

There are performance implications of this, but more importantly, this won't deal properly with nils.

The ipairs variant will simply ignore everything starting at the first nil, and the #t variant may choose any cut off at any nil value.

"`select` is linear time"

Not in a good implementation.

select(n, ...) returns a vararg starting at the n-th element of .... One might be led to believe that this could be implemented by copying the entire "tail". Alternatively, one might think that varargs could be implemented as linked lists, in which case selecting the n-th element would require following n-1 pointers.

If either of these was the case, the following script ought to run in quadratic time in the length of the vararg ...:

local sum = function(...)
	local n = select("#", ...)
	local sum = 0
	for i = n, 1, -1 do
		sum = sum + select(i, ...)
	end
	return sum
end

In practice, neither of these seems to be the case. ¹⁰ When you select, you effectively slice a vararg; all it does is some pointer arithmetic - it isn't traversing a linked list or anything like that.

Variable Scope

Variables are "environmental" by default. However, the environment can differ from one function to another, and need not be the global environment. For example, a common pattern to give modules their own environment separate from the global environment is

local print = print -- localize the globals we need ("imports")
_ENV = {} -- _ENV is an (implicit) function upvalue in 5.2+
-- local env = {}; setfenv(1, env) -- in 5.1
function foo() print"foo" end
return _ENV

This messes with many static analysis tools which assume the environment to always be global.

Locals are strictly lexically scoped and may shadow environmental variables or other local variables.

Closures

Closures are compiled just once, not every time they are created. (This is the case in basically every sane programming language.)

Upvalues in Lua are references, not copies. Changing an upvalue after creating a closure will affect the upvalue the closure, as well as other closures that "share" the upvalue, are working with. Upvalues live at least as long as any closure referencing them exists; after that they may be garbage-collected. Closures only keep specific upvalues and not entire scopes alive.

Another issue is that tostring guarantees no particular formatting; you should use formatting specifiers if you need a particular format, for example %d if you want something to be formatted as an integer.
The typical bug this causes is serialization libraries messing up larger integers like user IDs in JSON. For example 2^53, which can be represented exactly as a float due to being a power of two (with a reasonable exponent), gets tostringed to 9.007199254741e+15, which is not the same as 2^53. ↩
It is an interesting problem to find the shortest decimal representation which gets converted exactly into a given binary representation. Sophisticated algorithms have been designed to do this efficiently.
The ideal simple way to serialize floats - if you're willing to compromise on readability - would be to use the hex format %q produces (which effectively just dumps the mantissa-exponent representation as-is), but sadly this is pretty niche and not an option if you're e.g. working with JSON (or another human-readable format which uses decimal notation), or if you're working with older Lua versions. ↩
JavaScript calls this limit Number.MAX_SAFE_INTEGER. ↩
Technically, even if this was the case, the runtime would still linear because you only concatenate a constant number of strings, just with a possibly nasty constant factor (about two orders of magnitude in this case). ↩
Many scripting languages even distinguish between interned "symbols" and strings explicitly. ↩
However, due to implementation details, the null byte used to not be allowed in patterns; you had to use %z instead. ↩
In fact counterexamples can be construed where this doesn't hold, but they are usually somewhat contrived. ↩
But, perhaps surprisingly, also in some other circumstances! PUC Lua will typically use rehashing (the need to grow the table because a new entry doesn't fit; as well as occasional shrinking, which is only allowed when new keys are added however) as an opportunity to decide whether entries can be moved to the array part. This is done by counting - for powers of two - how many keys less than each power (and larger or equal than the preceding power) there are. Then you simply look at the prefix sums, and find the largest power of two where the array part will be at least half full. This is quite clever: Lua simply automatically decides what's the best representation for you, with no increase in asymptotic cost. A few nils in an array won't make it a hash map; and conversely, what's conceptually used like a hash map may very well use an array internally, if the keys are dense enough. ↩
(PUC) Lua is simply not allowed to mess with the structure of the table, because iterating tables while removing entries is allowed; thus the order of keys must be preserved. All Lua can do is mark entries as deleted. ↩
Varargs are efficiently implemented as stack-allocated slices of values (this also means the space left on the stack imposes a limit on their size). ↩