How to deal with arrays of a lot of spawned objects

Solar2D General Questions/Discussion
#1

Hi there !

In my app, I’m spawning a lot of objects, and all of them are stored in tables in order to track them. But at some point of their life, they can be removed from the scene and of course, every time that happens, I nil their “slot” in the array.

But in the end, my table looks like something like that : 

spawnObjects = {nil, nil, nil, objectInfos, nil, objectInfos, nil, nil, etc...}.

So, when I try to pause or quit the scene, running a loop through this array can take a lot of time. And even if there are actually only 4 spawned objects in the scene, it would still need to go through all the created slots (holes?) in this array in order to find them, and pause / destroy them.

  • I tried to add a condition that checks that if it has already been nilled, it would skip it, but it doesn’t seem to change anything.

  • I also considered cleaning the array everytime an object would be destroyed, and shifting all the slots in the table in order to avoind getting holes, but then, I would have to run a loop everytime I track an object with its id number : not sure it would help me then…

So, my big question is : Is there any way to avoid this ? :slight_smile:

#2

Hi @evanspro,

Just curious, have you tested the performance of this? Just iterating through a table should be quite fast, even if there are a lot of entries to process… and if this happens during a non-time-sensitive place in your game (i.e. during a pause or scene change) then it probably won’t even be noticed by the player.

An alternative may be to use a dictionary table (key-value pairs) and remove the objects by some sort of name/label. But then, upon cleanup, you’ll probably need to iterate using a pairs() loop, which is inherently slower than an indexed loop, so the benefit may be outweighed.

Brent

#3

Also, table.remove() is designed to be used in this situation. It will fix your issue as it shifts elements down to fill the holes

#4

brent is already heading you down the right road, so i’ll just add a bit more…

There are many ways to structure such data, each with varying trade-offs.  In the end, you’ll want to benchmark the most promising approaches to really know for sure.  But first thing you should get a better handle on is how you’re actually using your data.

This is one of those “CS102” -type topics.  Once you really understand your data, you can match it with an appropriate structure.

For example, let’s say your game mechanics impose a maximum of 100 such objects.  (just to give us an upper bound to talk about).  So, if 100 is the limit, is it more common for 80 to be active, or 20 active?  That is, is your list more typically dense or sparse?  And how much thrashing is going on?  (that is, say it’s always 80% full, but of that 80%, 40% are newly dead/alive on each pass - that’s a fairly static overall load, but a lot of thrashing).  Also ask yourself if any of your list actions (insertion, iteration, removal, etc) are less-critical than others.

If more-commonly dense, then your simple “array” (table with numeric indicies) might be best, even if 20% sparse - simpler to iterate over all 100 and skip 20, than to ‘clean’ the array with table.insert/table.remove.  And vice versa for keyed table with sparse usage.

A common approach is to create a “pool” of such objects, and recycle them in/out of an “active list”.  Again, depending on your usage metrics, your “active list” might just be iterating the whole pool of 100 and checking a “isAlive” property.  Or you might actually pull out the alive ones into a separate list (keyed or indexed, as usage dictates).  Or you might build a doubly-linked-list “in-place/on-top-of” your pool for the alive ones (just giving each object next/prev refs to other list members, then insertion/deletion become trivial, but traversal will be slower - always tradeoffs).  Or, or, or, …

fwiw, hth

#5

To all : first of all, thank you for replying :wink:

I didn’t say it earlier, but I’m talking about 300 items to pause / remove (particles), and that’s definitely not all the items I need to pause / remove when I iterate. Which is probably one of the reason iterating can take “a lot” of time.

@Brent Sorrentino

I’m actually doing this while I quit a scene (exitScene), so at this point, it doesn’t really matter since the loading screen is displayed.

But also when I pause/unpause the game. Then, it actually takes about 3 to 5 seconds, depending on what’s displayed. In my opinion, 3 to 5 secs is not acceptable when you try to pause your game (but there are a loooot of stuff to pause in my game…).

I did try using a dictionary table, but for other reasons, unfortunately it didn’t do the job in my case.

@Davebollinger

What you’re saying actually reassures me a lot : I’ve spent my whole day trying different things, and wasn’t sure if I was losing my time… And eventually, I did what you suggest : trying to see what would be the best solution according to my own gameplay, and setting a limit to how many objects could spawn, depending of other objects at screen. And finally, I’ve chosen -for now- a solution which is…

@Gremlin Interactive

… yours :wink: For now at least since the project is still in production. Guess it might change if I add other stuffs. table.remove() was initially what I intended to do, but wasn’t sure on how it would run eventually. Seems to run OK so I’ll keep it that way for the moment.

So, again : thanks to all of you :wink:

#6

Hi.  This question inspired me to write two articles (one as a pre-cursor to examining the question of tables and object tracking):

http://roaminggamer.com/2014/06/26/simple-bench-for-corona-sdk/
http://roaminggamer.com/2014/06/26/tracking-objects-in-tables-best-practices-corona-sdk/

Cheers,

Ed

#7

Ed, fwiw, if you wanted… you could do a third segment to cover:

  • give device times.  must suspect that 100K iters of anything, even NOP, using any method, in 4ms means desktop simulator. (might matter with JIT/caching/etc?)

  • put some actual thrashing/sparseness in there, that is your ‘array’ is always full so “if (tmp)” test for indexed never takes the false path, then compare the two at 25%, 50%, 75% sparse, for example.  (might be a surprise in the results)

  • put to bed the myth that for i=#t,1,-1 has ANY advantage over for i=1,#t (maybe due to thinking #t is reevaluated if at end?)

etc

#8

@Dave

  • Ah yes, I should have mentioned those were simulator times.  I have updated the article.  It now has simulator and Nexus 7 times.
  • I updated the test to run a sparse variant in which 500 entries are removed.  If you look, you’ll see sparse arrays are faster in all cases where work is done.
  • re: variants on ‘for’ increment vs. decrements, yes maybe another day.  However, any differences in speed will be a function of the way the processor on a specific device physically implements addition and subtraction.

Cheers,

Ed

#9

1 thanks :slight_smile:

2 i was hinting at an aspect of the if statement itself, something like (using your bench):

local bench = require "simpleBench" &nbsp; local function sparseIfLoop() &nbsp; for i=1,1000000 do &nbsp; &nbsp; -- pretend we have an array that is 10% filled &nbsp; &nbsp; if (i \< 100000) then &nbsp; &nbsp; &nbsp; -- do something (but not really, do nothing) &nbsp; &nbsp; else &nbsp; &nbsp; &nbsp; -- do nothing, really &nbsp; &nbsp; end end end local sparseTime = bench.measureTime( sparseIfLoop ) print( "sparseTime =", sparseTime )&nbsp; &nbsp; local function denseIfLoop() &nbsp; for i=1,1000000 do &nbsp; &nbsp; -- pretend we have an array that is 90% filled &nbsp; &nbsp; if (i \< 900000) then &nbsp; &nbsp; &nbsp; -- do something (but not really, do nothing) &nbsp; &nbsp; else &nbsp; &nbsp; &nbsp; -- do nothing, really &nbsp; &nbsp; end end end local denseTime = bench.measureTime( denseIfLoop ) print( "denseTime =", denseTime )&nbsp;

[edit] oops, forum always “loses” last part of my post after code block

Now comment out both “else” and re-run.  Same results?  Or not?

It’s a tiny difference, in all cases doing nothing 1M times, but it’s faster to take the else branch when present.  (due to an extra hopscotch jump in the vm)  My only point (and it’s a small one) is that even seemingly innocuous do-nothing statements can affect benchmarking if not ‘exercised’ fully.

#10

@Dave,

Thanks for the info.  You are right.  I have not fully examined the effects of the environment itself on the test.  It would be interesting to do a series of tests measuring the A vs B vs C … cost of creating different kinds of loops, code paths, etc.  

For the purpose of these measurements, I’ve ignored any benefits or drawbacks associated with using specific looping and other constructs.  As you noted, the difference should be small and I’m hoping small enough not to bias results.

Thanks again,

Ed

#11

Hi @evanspro,

Just curious, have you tested the performance of this? Just iterating through a table should be quite fast, even if there are a lot of entries to process… and if this happens during a non-time-sensitive place in your game (i.e. during a pause or scene change) then it probably won’t even be noticed by the player.

An alternative may be to use a dictionary table (key-value pairs) and remove the objects by some sort of name/label. But then, upon cleanup, you’ll probably need to iterate using a pairs() loop, which is inherently slower than an indexed loop, so the benefit may be outweighed.

Brent

#12

Also, table.remove() is designed to be used in this situation. It will fix your issue as it shifts elements down to fill the holes

#13

brent is already heading you down the right road, so i’ll just add a bit more…

There are many ways to structure such data, each with varying trade-offs.  In the end, you’ll want to benchmark the most promising approaches to really know for sure.  But first thing you should get a better handle on is how you’re actually using your data.

This is one of those “CS102” -type topics.  Once you really understand your data, you can match it with an appropriate structure.

For example, let’s say your game mechanics impose a maximum of 100 such objects.  (just to give us an upper bound to talk about).  So, if 100 is the limit, is it more common for 80 to be active, or 20 active?  That is, is your list more typically dense or sparse?  And how much thrashing is going on?  (that is, say it’s always 80% full, but of that 80%, 40% are newly dead/alive on each pass - that’s a fairly static overall load, but a lot of thrashing).  Also ask yourself if any of your list actions (insertion, iteration, removal, etc) are less-critical than others.

If more-commonly dense, then your simple “array” (table with numeric indicies) might be best, even if 20% sparse - simpler to iterate over all 100 and skip 20, than to ‘clean’ the array with table.insert/table.remove.  And vice versa for keyed table with sparse usage.

A common approach is to create a “pool” of such objects, and recycle them in/out of an “active list”.  Again, depending on your usage metrics, your “active list” might just be iterating the whole pool of 100 and checking a “isAlive” property.  Or you might actually pull out the alive ones into a separate list (keyed or indexed, as usage dictates).  Or you might build a doubly-linked-list “in-place/on-top-of” your pool for the alive ones (just giving each object next/prev refs to other list members, then insertion/deletion become trivial, but traversal will be slower - always tradeoffs).  Or, or, or, …

fwiw, hth

#14

To all : first of all, thank you for replying :wink:

I didn’t say it earlier, but I’m talking about 300 items to pause / remove (particles), and that’s definitely not all the items I need to pause / remove when I iterate. Which is probably one of the reason iterating can take “a lot” of time.

@Brent Sorrentino

I’m actually doing this while I quit a scene (exitScene), so at this point, it doesn’t really matter since the loading screen is displayed.

But also when I pause/unpause the game. Then, it actually takes about 3 to 5 seconds, depending on what’s displayed. In my opinion, 3 to 5 secs is not acceptable when you try to pause your game (but there are a loooot of stuff to pause in my game…).

I did try using a dictionary table, but for other reasons, unfortunately it didn’t do the job in my case.

@Davebollinger

What you’re saying actually reassures me a lot : I’ve spent my whole day trying different things, and wasn’t sure if I was losing my time… And eventually, I did what you suggest : trying to see what would be the best solution according to my own gameplay, and setting a limit to how many objects could spawn, depending of other objects at screen. And finally, I’ve chosen -for now- a solution which is…

@Gremlin Interactive

… yours :wink: For now at least since the project is still in production. Guess it might change if I add other stuffs. table.remove() was initially what I intended to do, but wasn’t sure on how it would run eventually. Seems to run OK so I’ll keep it that way for the moment.

So, again : thanks to all of you :wink:

#15

Hi.  This question inspired me to write two articles (one as a pre-cursor to examining the question of tables and object tracking):

http://roaminggamer.com/2014/06/26/simple-bench-for-corona-sdk/
http://roaminggamer.com/2014/06/26/tracking-objects-in-tables-best-practices-corona-sdk/

Cheers,

Ed

#16

Ed, fwiw, if you wanted… you could do a third segment to cover:

  • give device times.  must suspect that 100K iters of anything, even NOP, using any method, in 4ms means desktop simulator. (might matter with JIT/caching/etc?)

  • put some actual thrashing/sparseness in there, that is your ‘array’ is always full so “if (tmp)” test for indexed never takes the false path, then compare the two at 25%, 50%, 75% sparse, for example.  (might be a surprise in the results)

  • put to bed the myth that for i=#t,1,-1 has ANY advantage over for i=1,#t (maybe due to thinking #t is reevaluated if at end?)

etc

#17

@Dave

  • Ah yes, I should have mentioned those were simulator times.  I have updated the article.  It now has simulator and Nexus 7 times.
  • I updated the test to run a sparse variant in which 500 entries are removed.  If you look, you’ll see sparse arrays are faster in all cases where work is done.
  • re: variants on ‘for’ increment vs. decrements, yes maybe another day.  However, any differences in speed will be a function of the way the processor on a specific device physically implements addition and subtraction.

Cheers,

Ed

#18

1 thanks :slight_smile:

2 i was hinting at an aspect of the if statement itself, something like (using your bench):

local bench = require "simpleBench" &nbsp; local function sparseIfLoop() &nbsp; for i=1,1000000 do &nbsp; &nbsp; -- pretend we have an array that is 10% filled &nbsp; &nbsp; if (i \< 100000) then &nbsp; &nbsp; &nbsp; -- do something (but not really, do nothing) &nbsp; &nbsp; else &nbsp; &nbsp; &nbsp; -- do nothing, really &nbsp; &nbsp; end end end local sparseTime = bench.measureTime( sparseIfLoop ) print( "sparseTime =", sparseTime )&nbsp; &nbsp; local function denseIfLoop() &nbsp; for i=1,1000000 do &nbsp; &nbsp; -- pretend we have an array that is 90% filled &nbsp; &nbsp; if (i \< 900000) then &nbsp; &nbsp; &nbsp; -- do something (but not really, do nothing) &nbsp; &nbsp; else &nbsp; &nbsp; &nbsp; -- do nothing, really &nbsp; &nbsp; end end end local denseTime = bench.measureTime( denseIfLoop ) print( "denseTime =", denseTime )&nbsp;

[edit] oops, forum always “loses” last part of my post after code block

Now comment out both “else” and re-run.  Same results?  Or not?

It’s a tiny difference, in all cases doing nothing 1M times, but it’s faster to take the else branch when present.  (due to an extra hopscotch jump in the vm)  My only point (and it’s a small one) is that even seemingly innocuous do-nothing statements can affect benchmarking if not ‘exercised’ fully.

#19

@Dave,

Thanks for the info.  You are right.  I have not fully examined the effects of the environment itself on the test.  It would be interesting to do a series of tests measuring the A vs B vs C … cost of creating different kinds of loops, code paths, etc.  

For the purpose of these measurements, I’ve ignored any benefits or drawbacks associated with using specific looping and other constructs.  As you noted, the difference should be small and I’m hoping small enough not to bias results.

Thanks again,

Ed