Dawn of the Geeks

Getting data out of an array is a pretty common occurance in programming. So I decided to find out what the fastest method was for getting data out of a two dimensional array. There are two basic methods, you can use a real two dimensional array or you can use a single dimension array and treat it like a two dimensional array with some simple math. I ran the test in release and debug mode and found that either DevPartner profiler doesn’t do release mode well or I didn’t know how to configure it properly because debug mode came back with faster results. So these two sets of results are broken apart and the idea is to show the difference, not hard numbers.

The left side numbers are the number of milliseconds it took to get the values of an array at 1 million random points.

Debug Mode

I did two runs for each of the six tests. There are three methods used to get the array value and they are done in safe and unsafe mode. The middle marker is the average of the two tests.

You can see in this test that [x+y*n] where n is the width of the array is the fastest method. One of the oddities is that [x,y] (C#’s 2 dimensional array) is faster when it’s done in safe mode.

Using a shift can be faster instead of a multiply can be faster and probably is with enough tests.

Release Mode

Release Mode came back with more consistant results. Here we can see that shifting is faster than multiplying. Which is to be expected.

In both debug and release mode you can see that when dealing with arrays you don’t want to use C#’s method and instead use simple math in unsafe mode. Based on the numbers collected the shift vs multiply gets you about a 1% speed boost. That doesn’t seem like a whole lot but when you’re accessing arrays millions of times per second it adds up.

Also, for these tests in all cases the array was 2048×2048. In a second set of tests the 2d array and the multiply had an array size of 127×127 while the shift test had an array size of 128. In that case there is about a 7-8% speed increase by using shifts. The multiply is probably being treated virtually like a shift by the CPU when it’s a power of 2.

The drawback to shifting is that you must use powers of two for the array width which could lead to wasting memory or imposing restrictions on various things such as texture or map size.

This is why graphics cards restrict everything to powers of two. It’s more efficient to shift than to multiply.