Tracking Objects in Tables Best Practices – Corona SDK

Note: I have corrected a flaw in this article.  See notes below.

Yesterday, I saw this post “How to deal with arrays of a lot of spawned objects” and also received a similar question from a friend of mine (Bud).  It is worth noting that I often see similar questions.

In today’s article, I hope to lay this question to rest.  Specifically, I will be examining three ways to store objects in tables and to then operate on those objects.  Furthermore, I will use the benchmarking module from this article to test some actual test cases.

The Code

You can download the full code for this article here.

The Problem

You have a game in which you are creating (and destroying) many objects.  You want to track these objects in a table(s) in order to make processing and modifying these objects easy.

Question: How should you do this?

Answer: You have two basic options for indexing this table:

  1. Integer-Indexed Table – You can create an integer-indexed table and add objects to the table in order. This is easy to do and seems like a good idea because iterating over an integer-indexed table is the fastest method of iteration.
  2. Object-Indexed Table – Alternately, you can use the objects themselves as indexes.  However, if you are performance-minded, this may seem like a bad idea.  Then again, maybe not.  We’ll find out shortly.

myObjects

For this article, I will be creating a table containing references to 10,0000 display objects.  This is the integer-indexed version of the table/object builder.

-- Create a list 10,000 randomly chosen display objects
local myObjects = {}
for i = 1, 10000 do
   local x = mRand( 30, 450)
   local y = mRand( 30, 290)
   local type = mRand(1,2)
   if(type == 1) then
      tmp = display.newCircle( x, y, 20)
   else
      tmp = display.newRect( x, y, 40, 40 )
   end

   -- Store references using integer indexes
   myObjects[#myObjects+1] = tmp
end

The object-indexed version is exactly the same, except for the last line:

   myObjects[tmp] = tmp

 Integer Iteration

Using integers to iterate over our table, we would write code similar to this:

   local tmp
   for i = 1, #myObjects do
      tmp = myObjects[i]
      -- Do some work here on 'tmp'
   end

Integer Iterations with ‘nil’ Testing

Note: This code was corrected.  Originally I set deleted entries to ‘nil’, but this causes the ‘#’ operator to count to the highest non-nil entry and stop.  i.e. ‘#’ doesn’t work as expected with sparse tables.

Whoa!  You may ask, “What happens if I need to remove objects?”.   Well, one way you could handle this is by removing the objects and then setting that entry in the table to nil.

display.remove( myObjects[21] ) -- Remove the object from 'Corona'
myObjects[21] = "" -- Now 'Lua' can free the left over memory from our object,
                   -- however, we need something in this space or '#' will only
                   -- count to the highest non-nil entry.

Now, when we iterate over the list, we need to check whether an entry is ‘nil’ first before operating on it:

   local tmp
   for i = 1, #myObjects do
      tmp = myObjects[i]
      if( tmp == "" ) then
         -- Do nothing, this entry is empty
      else
         -- Do some work here on 'tmp'         
      end
   end

‘pairs()’ Iteration

Lastly, if we chose to use an object-indexed table, we could simply iterate over it like this.

   for k,v in pairs(myObjects) do
      v:setFillColor(rcolor(),rcolor(),rcolor())
   end

Also, if we should choose to remove an object from our table later, setting the index to nil does not affect our iteration code.  i.e. It doesn’t need to check for nils.

Some Numbers

Now that we have some idea of how to store references to objects in a table and how to iterate over those tables, lets compare them based on time.

No Workload

First, let’s test each of the three iteration styles (as shown above) with empty work loads.

  • 10 x ‘#’ iteration: 4 ms on simulator, 19.17 ms on Nexus 7
  • 10 x ‘#’ iteration + ‘nil’ check: 6 ms on simulator, 25.85 ms on Nexus 7
  • 10 x ‘pairs()’: 12 ms on simulator, 52.80 ms on Nexus 7

Hmm… That seems pretty clear.  ‘#’ iteration is way faster than ‘pairs()’ iteration.  Even the ‘nil’ testing version is twice as fast using ‘pairs()’.

However, this is deceptive.  Let’s do the same comparison with a workload.

Random Re-Color Workload

Second, let’s repeat our test, but on each iteration we will randomly re-color each object. (Download the code to see how this is done.)

  • 10 x ‘#’ iteration: 179 ms on simulator, 618.95 ms on Nexus 7
  • 10 x ‘#’ iteration + ‘nil’ check: 182 ms on simulator, 662.40 ms on Nexus 7
  • 10 x ‘pairs()’: 197 ms on simulator, 799.68 ms on Nexus 7

As you can see, when we do some kind of work, the cost of the iteration gets drowned out.  Now, using ‘pairs()’ is only nominally slower than the other two methods.

Note: I added a sparse test after writing this article.  In this ‘spare test’ I removed 500 entries from the object table and re-ran the last (work) test.  Here were the results:

  • 10 x ‘#’ iteration + ‘nil’ check: 180 ms on simulator, 574.65 ms on Nexus 7
  • 10 x ‘pairs()’: 200 ms on simulator, 592.75 ms on Nexus 7

As can be seen, the sparse version of each is faster and the pairs() version speeds up significantly as the data set gets smaller.

What Should I Use

So, what method of indexing and iteration do I suggest you use?

Well, if you must operate on the objects in the order they were created, you should use integer-indexed tables.  However, in all other cases, I suggest using start by using object-indexed tables and the ‘pairs()’ function for iteration.  Later, when you finish your game, if it is too slow, then you should profile it, find the hot spot(s), and if one of them is the iterator, try an interger-indexed approach.

I think that in most cases, you will find object-indexed tables superior for ease-of-use.