VB.NET: 2-dimensional list is almost 1000x slower than 1-dimensional list?

Question

Consider the following code:

    Dim arr1 As New List(Of Double)
    Dim arr2 As New List(Of Object)

    Dim timeStart As DateTime = Now

    For x As Integer = 0 To 1000000
        arr1.Add(3.14159)
    Next

    Dim timeEnd As DateTime = Now

    MsgBox(((timeEnd - timeStart).Seconds).ToString())

    timeStart = Now

    arr2.Add(New List(Of Double))

    For x As Integer = 0 To 1000000
        arr2(0).add(3.14159)
    Next

    timeEnd = Now

    MsgBox(((timeEnd - timeStart).Seconds).ToString())

It involves 2 lists. The first one is 1-dimensional, the second one is 2-dimensional.

The first routine (which operates on the first list) completes in about .015 seconds. The second routine (which operates on the second list), however, takes almost 10 seconds. The only difference is that the second list is 2-dimensional.

Am I missing something here? Is there a way to speed this up or am I doing something wrong? I have a program that requires several 2-dimensional arrays and it's running extremely slow right now. How can I speed it up so I get the same feedback that I'd get if the lists were 1-dimensional?

Solution

The problem lies with one line of code.

Make arr2 strongly typed and it'll be much, much faster...

Dim arr2 As New List(Of List(Of Double))

I ran a quick test and it went from about 7 seconds on my computer to 17 ms with this one change.

As CodeInChaos correctly pointed out, the reason for the slowness has more to do with the .Add() method being dynamically dispatched than anything.

EDIT: Writing VB.NET with Option Strict On is one way to avoid this kind of problem in the future. By doing this, you would've seen a compile-time error that says "Option Strict On disallows late binding."

Comments

[topepo]

boxing/unboxing means converting a value type to and from object. List<double> is not a value type. This is simply type conversion (casting), which indeed is slow.

[CodesInChaos]

I don't think boxing/casting is the issue here. I don't know VB.net very well, but it looks like the add to the second list is dynamically dispatched.

[Steve Wortham]

@CodeInChaos - I noticed that when I was reviewing the code a few minutes ago. That's also why .add was all lowercase. If it had been strongly typed Visual Studio would have automatically fixed the case.

[Steve Wortham]

@CodeInChaos - You're exactly right. I changed the arr2 instantiation back to the way it was as a list of objects. Then I changed the line inside the loop to this DirectCast(arr2(0), List(Of Double)).Add(3.14159) and that also runs in 17 ms.

[Cody Gray]

@Steve: That's a great find. I was wondering the same thing as Laurent; there was actually no boxing going on in the original code, but I didn't have time to post a more complete answer than yours. The weird thing that remains, though, is why VB.NET didn't autocorrect add to Add. Considering it's case-insensitive, the Intellisense usually fixes this type of thing up on its own as you type. Not if you copy and paste in the text, but it should have when the OP wrote his code.

[Steve Wortham]

@Cody - With Option Strict Off, you can throw anything at the end of an Object and it'll attempt to late bind at runtime. So in fact Visual Studio didn't fix the capitalization because it didn't recognize .add as a member of Object. Turn Option Strict On, of course, and you'll get a message saying "Option Strict On disallows late binding", preventing you from making this mistake to begin with. That's one reason a lot of people recommend writing VB.NET with Option Strict On.

[Mark Hurd]

re where the slowness comes from: I haven't confirmed what Dim fAdd As Action(Of Double) = AddressOf obj.LatBound actually does, but either it "dynamically" looks up LateBound for every call or the "dispatching" itself (i.e. the marshalling at runtime) is the slow thing because I get 00.032, 24.97, 25.38 where the last time removes arr2(0).Add from the loop.