Roku Developer Program

[Komag]

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)

[dcrandall]

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.

[NewManLiving]

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

[Rek]

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

[Komag]

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!

[Komag]

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.

[EnTerr]

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).

[Komag]

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)?

[EnTerr]

"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.