Cycling through a SortedList - Why is this faster?

Question

List1 in the following example is a SortedList(Of MyClass) and contains 251 members.

The first two codeblocks execute in 15.5 seconds.

 For cnt As Integer = 1 To 1000000
        For Each TempDE In List1
            Dim F As String = TempDE.Key
            TempDE.Value.x1 = 444
        Next
    Next

 

    For cnt As Integer = 1 To 1000000
        For Each TempDE As KeyValuePair(Of String, phatob) In List2
            Dim F As String = TempDE.Key
            TempDE.Value.x1 = 444
        Next
    Next

This one executes in 5.6 seconds.

    For cnt As Integer = 0 To 999999
        For cnt2 As Integer = 0 To 250
            Dim F As String = List1.Keys(cnt2)
            List1.Values(cnt2).x1 = 444
        Next

    Next

Why are the first two codeblocks so much slower?

Answer 1

The SortedList extends a Collection by implementing IComparer to provide the sort functionality. Internally, it implements 2 arrays to store the elements of the list - one array for the key and one for the values. The .NET Array is optimised for fast in-order and fast random access.

My suspicion why the first 2 are slow is because the foreach statement in a SortedList is a wrapper around the Enumerator. Calling foreach will query for the enumerator, call MoveNext and Current. In addition, going though the generic list can potentially involve boxing and unboxing as you traverse the list, and can create performance overhead that you would not normally get by accessing by Index.