CODEWITHSUNDEEP
arraysmemorylua
Dale Mahalko
Dale Mahalko

Reputation: 207

LUA: Memory usage of arrays with large gaps?

If I do this:

listofstuff = {}
listofstuff[5] = 'foo'
listofstuff[9000] = 'bar'
listofstuff[200000] = 'baz'

Does it use any more memory than this?

listofstuff = {}
listofstuff[0] = 'foo'
listofstuff[1] = 'bar'
listofstuff[2] = 'baz'

If yes, does the first example create 198998 null/unused table array values, but which still take up memory to store the structure?

Upvotes: 2

Views: 645

Answers (1)

nobody
nobody

Reputation: 4264

Yes, it will use more memory (approximately 2x as much), but no, it will not store thousands/millions of empty slots.

Internally, tables are hash maps. They only allocate as many slots as needed to store the values that you put in (rounded up to the next power of two). That means

listofstuff = {}
listofstuff[5] = 'foo'
listofstuff[9000] = 'bar'
listofstuff[200000] = 'baz'

will create a table with four slots storing roughly (crude pseudo-notation)

{
  -- irrelevant metadata omitted
  -- (look at the Lua code (ltable.c/ltable.h) for the full details
  arraysize = 0,
  hashsize = 4,
  array = null,
  hash = {
   { num:5, str:"foo" },
   { dummy, dummy },
   { num:200000, str:"bar" },
   { num:9000, str:"bar"},
  },
}

(This is just an example, the order could be completely different.)

Your other example will instead store something roughly like this:

{
  arraysize = 2,
  hashsize = 1,
  array = { str:"bar", str:"baz" },
  hash = {
   { num:0, str:"foo" },
  },
}

If you have a contiguous range of integer keys, there's no need to store the keys (saving half the memory) if the values are stored as an array. (Then the position in that array is the key.)

[Like everywhere in Lua, arrays start at 1. But it's no problem if your arrays start at 0 – that extra slot is simply stored in the hash, together with the key. If you have no good reason to start at 0, make it start at 1. But if you'd have to adjust an algorithm or formula to do that, just start at 0.]

Upvotes: 2

Related Questions