Performance and Lua tables

Lua tables - memory

Everything written in this article completely depends on your Lua environment. This article is specifically written for the Lua environment of Supreme Commander: Forged Alliance.

A Lua table

A Lua table consists of two parts: an array part and a hash part. This is best explained in chapter 4 of The implementation of Lua 5.0. We'll use the same terminology as the paper and we'll assume you've read at least that chapter.

Some table functions only interact with the array part. We'll summarize a non-exhaustive list:

• (1) table.insert
• (2) table.getn
• (3) table.random
• (4) table.remove
• (5) table.sort

Other table functions that operate on both parts:

• (6) table.getsize
• (7) table.empty

We mention this because these functions may not act as you'd expect if you do not know the distinction. As an example: table.getn does not take into account elements in the hash part, and may therefore be inaccurate.

Comparison to create perspective

A Lua table is an expensive data structure in comparison to data structures available in other languages. The header consumes 40 bytes, regardless of whether the table has any elements in it. Each element in the array part consumes 8 bytes. Each element in the hash part consumes 20 bytes.

We'll make a comparison to create a perspective on how much more expensive these data structures are. For simplicity we'll start our comparison with structs from C. We'll start with a data structure that represents a vector or a point. Such a data structure has two entries, one for each axis.

// occupies 8 bytes
struct Vector {
  float x;
  float y;
}

-- occupies 40 + 16 = 56 bytes
local vector1 = { 0, 0 }

-- occupies 40 + 80 = 120 bytes
local vector2 = { x = 0, y = 0 }

This initial comparison on a simple data structure shows the overhead of Lua tables: in comparison to a struct in c a Lua table can occupy up to 10 times the amount of memory. A consequence of this is that we need to be careful how and when we use tables.