Two-Dimensional Arrays and foreach

It’s well known that if you make a list List<TestObject> list and iterate it with foreach:

it will be slower than if we had an array TestObject [] array and iterated it element by element, or with the same foreach:

The difference in speed is roughly 2-3x, but it’s often not critical, since the operations performed on the objects themselves take so long that iterating the collection is just a grain of sand next to them.

The reason arrays are faster is that the compiler and the JIT recognize this pattern, and the resulting machine code for iterating an array is already comparable to plain C — advancing a pointer to the array element on every step. With List<>, on the other hand, an enumerator gets created, MoveNext gets called on every iteration, and so on.

Not long ago I ran into a further wrinkle of this same topic with two-dimensional arrays. A collection of map objects (tiles) was stored as a two-dimensional array that got fully iterated on a regular basis. Previously this was implemented as two nested loops, something like:

After a while the collection had to be moved elsewhere, and the array ended up being retrieved as TestObject[,]. That’s when the idea came up to write the iteration as a single loop with plain foreach:

The compiler wasn’t happy with that construct, so the array got cast to Array, and the following example compiled and worked without any issues:

A few days later I noticed that CPU load had risen noticeably after this “optimization.” A closer look showed that once cast to Array, the collection iteration stopped being optimized and fell back to Array.GetEnumerator(), whose efficiency is, to put it mildly, not great.

One option was to go back to the double nested loop over the array, but in the end I picked a simpler path — dropping two-dimensional arrays altogether. Indeed, with zero-based indices we can perfectly well replace the access array[x,y] with array[x + y*max_x], and for iteration just get a plain TestObject[] array and work with it via foreach/for/while, relying on the compiler and JIT to optimize it.

As a takeaway, I’ll quote Mike Stall (http://blogs.msdn.com/jmstall/):

Optimizing for the wrong scenario can kill performance