List<> vs type[]

is there any speed difference for using generic list verse a type array . for example

will

List<point3d> evaluate faster than point3d[]

or the other way around. i am just wondering for future development projects.

Replies to This Discussion

Permalink Reply by David Rutten on May 16, 2010 at 7:15am

Hi Robert,

it depends a bit on where you use it. A lot of Rhino SDK functions will work faster with arrays than with list (which is why we added the RhinoList class to RhinoCommon, which gives us the speed of arrays and gives you the flexibility of lists), but Grasshopper itself uses mostly Lists so it doesn't really matter there.

If you are using Lists, then you can often improve your performance by properly sizing the list prior to using it. This will prevent the list from having to automatically resize as you fill it up.

On a somewhat unrelated note, I've found that it is practically impossible to predict where the bottlenecks in code are going to be. The only proper way to speed up a program is to:

A) Write it without any optimisations
B) Profile it to find bottlenecks
C) Optimize the bottlenecks
D) Profile again to make sure you didn't make things worse
E) Goto (B) and repeat

--
David Rutten
david@mcneel.com
London, UK

Permalink Reply by robert cervellione on May 16, 2010 at 7:30am

Excellency! i did notice the rhinolist class and i think they work great especially for point3d lists. will grasshopper now that is on the new sdk be able to accept arrays as outputs in .6 version it did not like arrays. also for things like double arrays can there be a built in converter to trees. something like

GH_Structure ghs = GH_Structure.fromArray(myPointarray[][]);

Permalink Reply by David Rutten on May 16, 2010 at 8:01am

How would you define the paths for each subarray?

--
David Rutten
david@mcneel.com
London, UK

Permalink Reply by robert cervellione on May 16, 2010 at 8:07am

this is how i do it now. the code would just be a built in function of gh_structure without having to loop through it (i guess a foreach() would be better)

GH_Structure ghs = new GH_Structure();

for (int i = 0; i < Vres; i++)
{

List ghpList = new List();

for (int j = 0; j < Ures; j++)
{
ghpList.Add(new GH_Point(pList[i][j]));
}

ghs.AppendRange(ghpList, new GH_Path(i));
}

Permalink Reply by Giulio Piacentino on May 16, 2010 at 9:42am

Hi Robert,

you could try running some benchmarks using this implementation for an array and two lists, the first one where the final size is known in advance, the second one where it is not. This would be by no means a general benchmark of all arrays and lists, but it would give an idea of where List<T> and where T[] might be more appropriate.

Here is how you could set this up: on my PC, with 1'000'000 arrays/lists constructions and 50 inner loops on each, "arrays vs. list" has about 1:2 speed relationship, and "array vs. unknown length list" 1:9. You can test on your system and change the tests, too. If you do, remember to build in release mode and "Run without debugging".

- Giulio
____________________
giulio@mcneel.com
McNeel Europe, Barcelona

Attachments:

Benchmarks.zip, 6 KB

Permalink Reply by robert cervellione on May 16, 2010 at 2:28pm

nice test Giulio, so if i read you test right a generic list will run 9x slower than an initialized array. if so, that is a huge difference. i will try your test out for myself soon. thanks for the info

Permalink Reply by David Rutten on May 16, 2010 at 3:30pm

No, it's only ~10 times slower if you do no properly initialize the List ahead of time. You'd get the same penalty if you were to increase the length of the array inside a loop.

Arrays will be faster than Lists, but they are so much harder to use that it only makes sense to revert to 'old-skool' arrays in performance critical code.

--
David Rutten
david@mcneel.com
London, UK

Permalink Reply by dima on May 16, 2010 at 3:49pm

David,
What do you exactly mean by "properly initialize the List ahead of time"?
Thanks,
Dima

Permalink Reply by robert cervellione on May 16, 2010 at 4:28pm

this means to set its size as in

List plist(point3d> = new List(point3d>(50);

this tell the list that it will be of type point 3d and have only 50 items in it, there for it will only allocate memory for the 50 objects.

ps. i cannot type <> with text, it disappears when i go to post it

Permalink Reply by dima on May 16, 2010 at 5:02pm

so, variable size lists are WAY slower that fixed size ones?

Permalink Reply by David Rutten on May 17, 2010 at 1:19am

There are no fixed size lists.

You basically have two options:



Dim listTest As New List(Of Boolean)

For i As Int32 = 0 To 999999

listTest.Add(True)

Next



Dim listTest As New List(Of Boolean)(1000000)

For i As Int32 = 0 To 999999

listTest.Add(True)

Next

In the first case the list has an initial capacity of 4, meaning it can contain 4 items without having to resize. When you try to add the fifth item, it will double the size of the internal array, which involves declaring a new array of 8 items and performing a copy on the existing 4 items. Then again, as you try to add the ninth item, it will have to double again to 16, and so on and so forth.

The constructor of the List class allows you to override the default capacity, so if you know (even vaguely) how many items you will need to store, you should always set the initial capacity to that number.

--
David Rutten
david@mcneel.com
London, UK

Permalink Reply by dima on May 18, 2010 at 7:39pm

thanks, David