Performance Quiz #7 -- Generics Improvements and Costs

Article
08/25/2005

Time for another quiz for you all, this is just a micro-benchmark so we want to be careful not to conclude too much but it's useful for understanding the costs and their origins. Consider the two snippets shown below:

// choice #1, using Generics

int total = 0;

List<int> li = new List<int>();

for (i = 0; i < 20; i++)
li.Add(i);

// start timer

for (i = 0; i < 10000000; i++)
foreach (int el in li)
total += el;

// end timer

// choice #2, using ArrayList

ArrayList al = new ArrayList();

for (i = 0; i < 20; i++)
al.Add(i);

// start timer

for (i = 0; i < 10000000; i++)
foreach (int el in al)
total += el;

// end timer

Now try to answer these question (no peeking at the comments until you've done your work :))

Q1: Which is faster?

Q2: How much faster?

Q3: Why is it faster?

Q4: What price do we pay for this speed? Quantify it if you can.

Answers and discussion soon :)

Comments

Anonymous
August 25, 2005
The comment has been removed
Anonymous
August 25, 2005
The comment has been removed
Anonymous
August 25, 2005
Rico just posted a new&nbsp;performance quiz where he compares performance of List&lt;T&gt; and ArrayList...
Anonymous
August 25, 2005
It appears that you are comparing a number of things:

1) IEnumerable<int> struct implementation of List<int> versus IEnumerable class implementation of ArrayList. The first is a direct and fast pattern invocation while the second makes slower interface calls.

2) Allocated objects versus unallocated objects. The generic version allocates no additional memory in the loop while the second allocates a new enumerator object one million times.

3) Int copying of List<int> versus Int unboxing and typechecking of ArrayList. Int unboxing is not as costly as boxing, but there is still the null-check and the type-check that needs to be performed.

There may also be additional virtual calls in the ArrayList version not present in the generic List version--such as calls to GetEnumerator.

I thought that this may be a trick question... especially since object references are just as efficient for computers to manipulate as are integers, but the disadvantages that I pointed out earlier lead me to believe the List<int> implementation performs fast.
Anonymous
August 25, 2005
Well, at least on my machine the generics implementation performed a little over 105% faster than an array list implementation.
Anonymous
August 25, 2005
Wesner Moise seems to think that I have many things on my mind with this example. Could it be true? :)

Kudos for spotting some of the hidden details!
Anonymous
August 25, 2005
C# performance quiz time.
Anonymous
August 25, 2005
Rico just posted a new&nbsp;performance quiz where he compares performance of List&lt;T&gt; and ArrayList...
Anonymous
August 25, 2005
The Quiz:
&nbsp;
Recently Ricom posted a performance quiz on his blog asking about the performance...
Anonymous
August 25, 2005
Hey Rico,

As a dev on the F1 Profiler team, I figured that I would take a wack at using our tool to profile this performance quiz. I posted my findings to my blog in an entry here. I ended up finding out some of the issue that have already been mentioned above.

http://blogs.msdn.com/ianhu/archive/2005/08/25/456531.aspx

I also linked it in my comment URL.
Anonymous
August 25, 2005
<P>Ian's chimed in with a very detailed post (thank you Ian). Lots of good numbers there but have we come to the right conclusion? Do we know why this is happening? </P>
<P>Is it really all those allocations? And if so, why? Is foreach inherently bad? Will I ever make a quiz with a straighforward answer? :) :)</P>
Anonymous
August 25, 2005
Q1) The generic version is faster.

Q2) I'd say #2 takes about 50% longer.

Q3) Unboxing imposes a small cost, but it is large compared to the work being done with the result. Boxing is not an issue.

Q4) Larger start-up cost: instantiating the generic type, possibly JITting (vs. NGEN'ed base classes?) Some memory overhead.

The extra start-up cost is large (by orders of magnitude) compared to the gain for a single inner loop, but still only of the order of milliseconds.

On reading the other comments: creating a new IEnumerator 10 million times will have a significant impact as well... probably the biggest impact. Add another 50%. (Good find, Wes!)

Hidden allocations inside loops are a major source of performance degradation. Some languages do a really good job of hiding them. :o)

I don't think there are virtual calls on a struct implementing an interface. All Current and MoveNext() calls on the ArrayList will be virtual, however. (Add another few %)

Both versions would still benefit from using a simple for loop and indexing. For #1 and #2, this removes the bookkeeping overhead of the enumerator. For #2, this removes allocations.
Anonymous
August 25, 2005
Hidden allocations and memory leaks in loops in languagues like C++ are a real problem. I wouldn't want my app to allocate and leak 280MB while it runs.

But in .NET, is this really an issue? Is the 280MB really all allocated and "held," or was the same small memory block just reused a million times? Or was the memory allocated and set aside for the GC to come along later?
Anonymous
August 25, 2005
One other comment: List<int>.Enumerator may be instantiated at the beginning of the foreach loop in which case there would be additional start-up cost for the JIT compilation to occur at the beginning of the test.

In this case, the performance of the generic list will probably be significantly improved if we have an additional foreach loop before performing the timing tests, thereby moving the instantiation costs out of the tests.

I doubt that this occurs, because I believe that the mscorlib already contains an instantiation of List<int>.
Anonymous
August 25, 2005
The comment has been removed
Anonymous
August 25, 2005
The comment has been removed
Anonymous
August 26, 2005
Q1: List<>
Q2: 3:1 advantage when I tested
Q3: Boxing
Q4: Not sure. I posted before reading the comments, so hopefully someone else answered this for me ;)
Anonymous
August 26, 2005
The comment has been removed
Anonymous
August 26, 2005
Ian Griffiths writes:

>>You're starting the stopwatch after creating your collection objects, so there are a whole load of costs you're not even measuring!

I don't think I could measure the difference even if I moved the stopwatch. We do twenty adds to the collection then we do two hundred million read operations. Those adds would have to be pretty hefty indeed to make a difference :)
Anonymous
August 26, 2005
Rico> it is not the collector.

With only a few objects allocated, the GC wouldn't have much work, even if it's invoked 100's of times per second.

However, you're running through a large chunk of memory a few hundred times. My money for the main culprit would be on loss of locality, with tons of cache misses and expensive RAM accesses as a result.
Anonymous
August 26, 2005
Believe it or not I actually spend a good amount of time thinking about my little quizzes hoping to come...
Anonymous
August 26, 2005
>>My money for the main culprit would be on loss of locality, with tons of cache misses and expensive RAM accesses as a result

That was a very good thought. When I started doing the quiz I expected the costs to be more evenly divided between the extra virtuals and the memory allocation. The measurement seems to indicate otherwise though.
Anonymous
August 30, 2005
The comment has been removed
Anonymous
September 15, 2005
Due to my upbringing in C/C++ somehow I feel uneasy whenever I see some likevar a = 5;
I guess this...
Anonymous
September 16, 2005
Due to my upbringing in C/C++ somehow I feel uneasy whenever I see some likevar a = 5;
I guess this...
Anonymous
June 25, 2006
PingBack from http://www.philosophicalgeek.com/2005/09/02/list-vs-arraylist/
Anonymous
January 23, 2007
Believe it or not I actually spend a good amount of time thinking about my little quizzes hoping to come

Share via

Performance Quiz #7 -- Generics Improvements and Costs

Comments

Additional resources