Why is the generic.list slower than array?
Asked
Active
Viewed 1,529 times
3
-
grammar? you question is barely comprehensible as is. – Joel Coehoorn Nov 06 '08 at 17:24
-
Probably need to give slack to non-english speaker. – Lance Roberts Nov 06 '08 at 17:26
-
1How else will one's english get better, if no one tells them when it's especially bad? – Joel Coehoorn Nov 06 '08 at 17:28
-
Good point, I think editing the question to be readable would probably help the most. – Lance Roberts Nov 06 '08 at 17:28
-
Give slack? For using Y? Come on. – Alan Nov 06 '08 at 17:29
-
for the record: there was at least one downvote, but it wasnt' me. – Joel Coehoorn Nov 06 '08 at 17:29
-
@Joel: me neither :) It's a programming site after all. Nevertheless, my willingness to tolerate zero effort input while expecting others to give 100% in their answer is much lower than it used to be... – Alan Nov 06 '08 at 17:34
-
It would really help if you define "slower". There are way too many operations that can be done on both a list and an array for us to interpret what you mean by "slower". – JaredPar Nov 06 '08 at 17:36
-
@Joel, I've learned to never assume who voted which way, since I've been accused of down-voting when I hadn't either (I did upvote your answer though). – Lance Roberts Nov 06 '08 at 17:56
-
1. There is no entity in .NET called "generic.list". Maybe you meant "List
"? 2. What operation are you trying to do? 3. What measurements have you performed to come to your conclusion? – Jay Bazuzi Nov 06 '08 at 18:05
2 Answers
5
A generic list is slightly slower than an array, but not so you'd notice in most cases. Mostly it has to do with the lookup being slightly more complex: List is said to use an array "under the hood", but it's not not guaranteed to keep nodes in adjacent memory in the same way in array is.
However, I saw some benchmarks way back in 2005 (can't find the link now) and difference is very small.
Also, the list has a number of important advantages over an array: mainly that it's trivial to add or remove items. It's much easier to use a list when you don't know how many items you will need, or when that number will vary. In those cases (and honestly, that's most of the time), you probably should not use an array.
Joel Coehoorn
- 399,467
- 113
- 570
- 794
-
good answer, since you have enough points, maybe you could edit the question. – Lance Roberts Nov 06 '08 at 17:28
-
I wasn't sure enough what the original meaning was. Yes, I know that seems odd as I've provided an answer, but providing an potentially incorrect answer wouldn't destroy the question like an edit would. – Joel Coehoorn Nov 06 '08 at 17:31
-
Well, the main data block (the array) will be jut a s contiguous - but agreed: it probably isn't adjacent to the List
instance. – Marc Gravell Nov 06 '08 at 22:02
3
In terms of read performance, there are two factors:
- an extra dereference (i.e. the
List<T>will contain aT[]field, and has to de-reference it) - it can't use some compiler optimisations that that exist for
T[]- such as eliminating bounds checking during loops
However, it is much easier to add to a List<T>, in particular because it retains spare space - i.e. it doesn't have to resize/blit the entire array just to add a single element.
Marc Gravell
- 1,026,079
- 266
- 2,566
- 2,900