one vs two vs three dimensional array, why the speed difference?

Question

when I run this code

Enum l
    NormalFor
    NormalForEach
End Enum

Sub Main()
    run(l.NormalFor)
    run(l.NormalForEach)
    Console.Read()
End Sub

Sub run(ByVal l As l)
    Dim one(999999) As Integer
    Dim two(999, 999) As Integer
    Dim three(99, 99, 99) As Integer
    Dim r As Random
    Dim sw As Stopwatch

    r = New Random(42)
    Select Case l
        Case Module1.l.NormalFor
            sw = Stopwatch.StartNew
            For i = 0 To 999999
                one(i) = r.Next
            Next
            sw.Stop()
        Case Module1.l.NormalForEach
            sw = Stopwatch.StartNew
            For Each i In one
                i = r.Next
            Next
            sw.Stop()
    End Select
    Console.WriteLine("One dimension, Array of " & one.Length.ToString & " items " & sw.ElapsedMilliseconds & "ms (" & l.ToString & ")")

    r = New Random(42)
    Select Case l
        Case Module1.l.NormalFor
            sw = Stopwatch.StartNew
            For i = 0 To 999
                For j = 0 To 999
                    two(i, j) = r.Next
                Next
            Next
            sw.Stop()
        Case Module1.l.NormalForEach
            sw = Stopwatch.StartNew
            For Each i In two
                i = r.Next
            Next
            sw.Stop()
    End Select
    Console.WriteLine("Two dimension, Array of " & two.Length.ToString & " items " & sw.ElapsedMilliseconds & "ms (" & l.ToString & ")")

    r = New Random(42)
    Select Case l
        Case Module1.l.NormalFor
            sw = Stopwatch.StartNew
            For i = 0 To 99
                For j = 0 To 99
                    For k = 0 To 99
                        three(i, j, k) = r.Next
                    Next
                Next
            Next
            sw.Stop()
        Case Module1.l.NormalForEach
            sw = Stopwatch.StartNew
            For Each i In three
                i = r.Next
            Next
            sw.Stop()
    End Select
    Console.WriteLine("Three dimension, Array of " & three.Length.ToString & " items " & sw.ElapsedMilliseconds & "ms (" & l.ToString & ")")
End Sub

I get this result

One dimension, Array of 1000000 items 8ms (NormalFor)
Two dimension, Array of 1000000 items 14ms (NormalFor)
Three dimension, Array of 1000000 items 13ms (NormalFor)
One dimension, Array of 1000000 items 9ms (NormalForEach)
Two dimension, Array of 1000000 items 230ms (NormalForEach)
Three dimension, Array of 1000000 items 241ms (NormalForEach)

Anyone know why it's way slower with a >= 2 dimensional array?

Answer 1

My best guess would be that it is to with memory access.

memory isn't a 3 dimensional array, it's a 1 dimensional array. So your 3d array has to be converted to a 1d array of data points to be placed in memory. This means that when you access data in a 1d array it just has to take the memory location of the first data point in the array, and add the offset to get the location of the data point you requested.

However for the 3d array, it has to take the location of the first point, multiply the 3 offsets you have provided together to get the 1d memory offset and then access that point in memory. This adds extra overhead. It's not much 8ms (or even 200ms) over 1000000 items is very very very small. I would assume the foreach makes the difference more pronounced because it now has to figure out the offsets for each dimension of the array as well as converting the offsets down to the 1d memory locations. If .net multidimensional arrays are implemented as arrays of arrays that will mean the foreach has to do quite a bit of work in processing the enumerator for each dimension of the array.

[Disclaimer: This isn't fact, it's just a theoretical guess based on knowledge of memory and how it would be accessed.]

(Don't worry about this too much, just use the 3d array if it makes sense for your data. The difference in access times is so small you will be better off making the code maintainable and readable than trying to mess around with squeezing 3d data into a 1d array just for a few ms of performance)

Answer 2

The CLR supports two different array-like types: vectors and arrays. Vectors are single-dimensional and are zero-based - so accessing an element is just a case of doing:

ptr = arrayStart + elementSize * elementIndex

and performing a very simple boundary check: 0 <= elementIndex < arraySize

Arrays (in CLR terminology) can be multi-dimensional and have different lower bounds - so accessing them takes a lot more effort. For example, for a two-dimensional array:

ptr = arrayStart + ((elementIndex1 - lowerBound1) * arraySize2
                    + (elementIndex2 - loundBound2)) * elementSize

and with a boundary check of rank == 2 && lowerBound1 <= elementIndex1 < upperBound1 && lowerBound2 <= elementIndex2 < upperBound2. Obviously this is considerably slower than the simple case.

Basically it's optimised for the common one-dimensional zero-base case, but with support for multi-dimensional arrays for the cases where they genuinely make things better.