Roku Developer Program

Developers and content creators—a complete solution for growing an audience directly.
cancel
Showing results for 
Search instead for 
Did you mean: 
Komag
Level 9

many nested FOR loops, which is better EACH or i=0 TO...

So in my game there are a few places where I need to do quite a few nexted FOR loops, and I can see some performance inpact.

I'm just wondering which is more efficient, or if there is any difference at all:

FOR EACH wgt IN widgets

vs

FOR i = 0 TO (widgets.Count() - 1)
0 Kudos
8 Replies
dcrandall
Level 7

Re: many nested FOR loops, which is better EACH or i=0 TO...

If I recall correctly, there used to be an obscure javascript thing that said if you know the list isn't going to grow dynamically, it was best to do this:

var whateverMax = yourArray.length();

for(i=0;i < whateverMax;i++)


The idea is that the problem wasn't the loop, it was that check for the length count on each iteration.
0 Kudos
NewManLiving
Level 7

Re: many nested FOR loops, which is better EACH or i=0 TO...

Theoretically anything not handled in brightscript should be faster
But that would all depend on how many layers of interface is involved
With For each, the iterator is handled internally instead of a BS counter
But what for each resolves to may be more time consuming

You can always create a timer and check execution yourself
My Channels: 2D API Framework Presentation: https://owner.roku.com/add/2M9LCVC
Updated: 11-11-2015 - Completed Keyboard interface
The Joel Channel ( Final Beta )
0 Kudos
Rek
Level 7

Re: many nested FOR loops, which is better EACH or i=0 TO...

It appears arrays are noticeably faster than lists, and for-each is significantly faster than index-based loops.

(All tests performed on Roku 3)

Test code:

function tests() as Void
timer = createObject("roTimespan")

size = 400000
array = createObject("roArray", size, false)
for i = 0 to size - 1
array[i] = i
end for

list = createObject("roList")
for i = 0 to size - 1
list.push(i)
end for

' -----------------------------------------------------
' Array Tests

' Test 1: For i = 0 to array.count() - 1
timer.mark()
for i = 0 to array.count() - 1
r = array[i] + 1
end for
elapsed = timer.totalMilliseconds()
?"Array 1 - Elapsed: ";elapsed;" ms"

' Test 2: For i = 0 to size - 1
timer.mark()
for i = 0 to size - 1
r = array[i] + 1
end for
elapsed = timer.totalMilliseconds()
?"Array 2 - Elapsed: ";elapsed;" ms"

' Test 3: For-each
timer.mark()
for each i in array
r = i + 1
end for
elapsed = timer.totalMilliseconds()
?"Array 3 - Elapsed: ";elapsed;" ms"

' -----------------------------------------------------
' List Tests

' Test 1: For i = 0 to list.count() - 1
timer.mark()
for i = 0 to list.count() - 1
r = list[i] + 1
end for
elapsed = timer.totalMilliseconds()
?"List 1 - Elapsed: ";elapsed;" ms"

' Test 2: For i = 0 to size - 1
timer.mark()
for i = 0 to size - 1
r = list[i] + 1
end for
elapsed = timer.totalMilliseconds()
?"List 2 - Elapsed: ";elapsed;" ms"

' Test 3: For-each
timer.mark()
for each i in list
r = i + 1
end for
elapsed = timer.totalMilliseconds()
?"List 3 - Elapsed: ";elapsed;" ms"
end function


Results:

Size = 100,000
Array 1 - Elapsed: 81 ms
Array 2 - Elapsed: 79 ms
Array 3 - Elapsed: 56 ms
List 1 - Elapsed: 116 ms
List 2 - Elapsed: 97 ms
List 3 - Elapsed: 67 ms

Size = 200,000
Array 1 - Elapsed: 158 ms
Array 2 - Elapsed: 164 ms
Array 3 - Elapsed: 110 ms
List 1 - Elapsed: 218 ms
List 2 - Elapsed: 215 ms
List 3 - Elapsed: 130 ms

Size = 400,000
Array 1 - Elapsed: 315 ms
Array 2 - Elapsed: 318 ms
Array 3 - Elapsed: 219 ms
List 1 - Elapsed: 426 ms
List 2 - Elapsed: 393 ms
List 3 - Elapsed: 256 ms
0 Kudos
Komag
Level 9

Re: many nested FOR loops, which is better EACH or i=0 TO...

Wow, thanks for that code, here are my results on my test platform, old Roku XD 2050X:
Size = 100,000
Array 1 - Elapsed: 995 ms
Array 2 - Elapsed: 1005 ms
Array 3 - Elapsed: 550 ms
List 1 - Elapsed: 1069 ms
List 2 - Elapsed: 1048 ms
List 3 - Elapsed: 403 ms

Size = 200,000
Array 1 - Elapsed: 1989 ms
Array 2 - Elapsed: 1989 ms
Array 3 - Elapsed: 1107 ms
List 1 - Elapsed: 2122 ms
List 2 - Elapsed: 2099 ms
List 3 - Elapsed: 799 ms

Size = 400,000
Array 1 - Elapsed: 3977 ms
Array 2 - Elapsed: 3988 ms
Array 3 - Elapsed: 2194 ms
List 1 - Elapsed: 4263 ms
List 2 - Elapsed: 4177 ms
List 3 - Elapsed: 1602 ms


In each case, the Roku took about twice as long as the first Elapsed time to "prep" the test. For example, for 400,000, when I hit my button to run the test, the game froze for about 12 seconds before printing the first results, so about 8 seconds of that freeze was just prepping the array and the list.

So for all three sizes, the fastest was actually the FOR EACH List, with FOR EACH Array in second. The different between FOR i = and FOR EACH was dramatic! The difference between knowing the Count() and measuring the Count() seemed insignificant.

Also interesting the raw Roku 3 performance in this case is 10X the classic Roku, a full order of magnitude.

I'll try to opt for FOR EACH whenever I can!
0 Kudos
Komag
Level 9

Re: many nested FOR loops, which is better EACH or i=0 TO...

Here is a real-world example of the performance increase from my game code:

' part of updateChLMap(mAA)
FOR y=0 TO 10
FOR x=0 TO 18
lit = FALSE
FOR EACH ch IN chMap[y][x][0]
IF chamL[ch][1] THEN lit = TRUE
END FOR
IF lit THEN chMap[y][x][1] = 0 ELSE chMap[y][x][1] = -50
END FOR
END FOR ' Takes 17-29ms over multiple tests

' REPLACED WITH:

FOR EACH row IN chMap
FOR EACH sq IN row
lit = FALSE
FOR EACH ch IN sq[0]
IF chamL[ch][1] THEN lit = TRUE
END FOR
IF lit THEN sq[1] = 0 ELSE sq[1] = -50
END FOR
END FOR ' Takes 12-24ms, about 5ms faster than FOR i= format

So I'm seeing a 20-30% efficiency boost for that bit.
0 Kudos
EnTerr
Level 9

Re: many nested FOR loops, which is better EACH or i=0 TO...

Yes, enumerating array with FOR EACH is faster than doing FOR + [indexing]. Almost 2x as fast, as demonstrated by a back-of-the-envelope test:
BrightScript Debugger> a = [] : for i=1 to 10000: a.push(i): end for
BrightScript Debugger> tm = createObject("roTimeSpan"): s = 0: for each el in a: s = s + el: end for: ? s, tm.totalMilliseconds()
50005000 119
BrightScript Debugger> tm = createObject("roTimeSpan"): s = 0: for i = 0 to a.count()-1: s = s + a[i]: end for: ? s, tm.totalMilliseconds()
50005000 207

However, Komag -
looking at your code, it feels to me it's a micro-optimization you shouldn't be resorting to - not yet anyway. Why are you running all these loopy loops in the first place? It would help knowing what it's doing - to me (uneducated guess) seems is checking some 19 x 11 cell map with list of objects in each and based on property of some of the objects, decides whether cell is visible or not. Does it need to do that on every redraw? Probably not. Does it have to enumerate every cell, every object, every time? Probably not and it can be done only when something that can change the outcome has changed/moved; and it affects only specific cell. Improving your algorithm would have much, much higher payoff that micro-managing the loops (e.g. i can give you advice on moving invariant code but i won't).
0 Kudos
Komag
Level 9

Re: many nested FOR loops, which is better EACH or i=0 TO...

Yeah it's sort of a micro optimization in this case, but now that I'll always use FOR EACH (if I can), cumulatively it will help. But I hear you on trying to think of ways to drastically reduce wasted compute cycles by only doing things when needed, and only doing what's needed.

I'm not really a programmer, just feeling my way through. Your guess is good, it's about a lighting system that updates only when the lighting changes based on player walking into doorways between "chambers". It's also affected by which other open doors are nearby. I'm planning to rework that bit some to just update changed squares instead of scanning through the whole room, but in this case it would save very little, perhaps reduce from 20ms down to 5ms if I can cut out 3/4 of the work (and that's on an old classic Roku). I'll try to see if I can do similar reductions in work elsewhere where the effect will be felt.

Maybe it's a dangerous questions, but now you've got me curious, what is "invariant code" and why should or shouldn't I move it (and what do you mean by moving it)?
0 Kudos
EnTerr
Level 9

Re: many nested FOR loops, which is better EACH or i=0 TO...

"Komag" wrote:
Your guess is good, it's about a lighting system that updates only when the lighting changes based on player walking into doorways between "chambers". It's also affected by which other open doors are nearby. I'm planning to rework that bit some to just update changed squares instead of scanning through the whole room, but in this case it would save very little, perhaps reduce from 20ms down to 5ms if I can cut out 3/4 of the work (and that's on an old classic Roku). I'll try to see if I can do similar reductions in work elsewhere where the effect will be felt.

Let me ask this, how often is that code executed?
I was guessing it was on every screen redraw and if you were striving for 30 times per second, that leaves you 33ms per frame for everything, to re-calculate and re-draw. If that were the case, reducing from 20ms down to 5ms would be huge difference.

But i see now you said it "updates only when the lighting changes based on player walking into doorways", which makes me think that recalc is need only once every few seconds, which would be 2 orders of magnitude (100x) less. In that case decreasing from 20ms to 5ms is [pea]nuts, not worth it. If it were the first case, you had potential to improve performance by almost 50% (15/33). In the second, the payoff will be only ~0.5%, totally not worth the effort.

Should we do optimizations that we don't need? Most often the answer is "no" - since it comes at the cost of something else. It may be readability - and it the case of algorithmic optimization mentioned above, it comes at cost of complexity. E.g. if when light conditions need refresh you re-calculate the whole map, it's a single piece of code that always works the same. If you optimize it into two pieces though - one full recalc and an incremental/differential recalc that does it only for the cells you know something have changed, now you have two pieces to maintain and keep in sync, when you change your structures. Also you are running the risk of missing a condition of when certain cell needs refresh - where the "brute force" approach always gets cells right since it always recalculates all. Readability and correctness are worth more than speed, most of the time.

So i say, optimize with eye on the goal. Is there a need for the program to be faster? And if so, is there much juice to be squeezed from that particular piece? If not, never mind re-working it.
0 Kudos