As part of the mobile port of Mushroom 11, I reluctantly engaged in a quick performance experiment focusing on optimization of array and list iterations.
I performed a few benchmark tests, running several loop function 10m times. The functions used different iteration methods to sum up the values of a short set of around 20 floats, using Unity’s C# (Mono) environment. The benchmarks were executed multiple times in different order, but clearly more elaborate tests are due. But without further ado I’ll go ahead and present the results.
For this section I set up a simple float[] array. The first test used a basic array loop with a cached length.
int len = arr.Length;
for (int i = 0; i < len; ++i)
f += arr[i];
times 10m, it elapsed the following: 00:00:00.6502370
An annoying habit that I see too much of is not caching the length. In arrays, it’s surprisingly benign, as the compiler uses inlining and value caching to avoid recalculating this value per each iteration.
for (int i = 0; i < arr.Length; ++i)
f += arr[i];
Elapsed: 00:00:00.6643670
A discussion going back to my C days argues that there's a difference between pre-increment (++i) and post-increment (i++) based on the fact the latter requires holding a copy of the value rather than simply returning it.
int len = arr.Length;
for (int i = 0; i < len; i++)
f += arr[i];
Elapsed: 00:00:00.6528710
The tests have shown minimal difference if any, possibly due to the compiler’s foresight, figuring out that there’s no reference to the pre-incremented value.
Finally, I had to test the infamous foreach. I was prepared for another inconclusive result.
foreach (float v in arr)
f += v;
Elapsed: 00:00:00.9130370
Alas, my concerns were true - foreach is significantly slower. Not much compiler foresight here, and the gain of avoiding array dereference ([]) is drowned by the use of an expensive enumerable.
Using collections has many benefits, but performance is not one of them. This time, I repeated the above tests with a List<float> collection.
int len = list.Count;
for (int i = 0; i < len; ++i)
f += list[i];
Elapsed: 00:00:05.6873850
To no surprise, that’s almost 10 times slower than an array. (I’ll skip showing the post-increment List results, as they yield identical results.)
Next, I avoided caching the list’s length (Count). This time I wasn’t surprised by the difference.
for (int i = 0; i < list.Count; ++i)
f += list[i];
Elapsed: 00:00:09.9270630
Yes, that’s 75% slower than cached length. List Count is much slower than array Length, and the compiler can’t assist much.
Last, using foreach on the list. This has to be efficient, right?
foreach (float v in list)
f += v;
Elapsed: 00:00:17.6953360
No, it is not. This is 3 times slower than standard iteration! Avoid!
Update1: Non-Indexed Collections
Non-indexed collections (i.e. no implementation for IList) don’t provide direct indexed access to its members, but offer other features instead. Going through the entire collection is generally done with foreach, which is proved slower than direct enumeration, but in the following cases there is no real alternative.
All the following results use a standard foreach loop:
foreach (float v in collection)
f += v;
HashSet elapsed: 00:00:09.4610000
Stack elapsed: 00:00:13.2449600
LinkedList elapsed: 00:00:18.6280300
So far, no huge surprises. HashSet is more efficient than List, as well as than Stack and LinkedList. But the following test is really upsetting:
LinkedListNode<float> node = linkedlist.First;
while (node != null)
{
f += n.Value;
n = n.Next;
}
Elapsed: 00:00:10.2359300
Why on earth is literal node crawl almost twice as fast as foreach? I can only imagine a general and inefficient enumerable model is in use here. At any rate, this is a clear and easy call for optimization, when linked list is in use.
A more comprehensive test is due, taking list manipulation (e.g. adding, removing, searching) into account. Clearly the choice of collection type isn’t made based on its iteration efficiency, but it’s always good to know the consequences of such choices.
Update2: The Garbage Collector (GC) plays a major role in the efficiency of enumerable collections, or lack thereof. Further tests are being conducted to figure out GC’s performance effects, on top of the given extended memory footprint.
The results are pretty clear - the compiler can only do as much. It can use certain assumptions such as unchanged array Length, or noticing that there’s not need to copy post-increment value if nothing is using it.
However, collections are volatile in nature. Cache their lengths if you know it stays intact. Also, the overhead of foreach renders it unusable in most circumstances, if performance is key. That is true even for non-indexed collections: if you can avoid looping with foreach, you likely should.
That said, your optimization efforts should likely be focused on physics or visuals (e.g. draw-calls, overdraw). However, understanding the underlying mechanics and constraints can definitely make a noticeable difference, especially on lower end devices.
I’ll conclude with reminiscing on how this could be further optimized with the right programming language, before everything was prefixed or suffixed with a hashtag ;)
float *fit = &arr[0], *fend = &fit[len];
while (fit < fend)
f += *fit++;
gummygunk
annaxmalina
kaledo-art
discoholicmusic
areudirty
romaincrisis
titsay