Performance Quiz #7 -- Generics Improvements and Costs -- Solution

re: Performance Quiz #7 -- Generics Improvements and Costs -- Solution

ricom — Tue, 30 Aug 2005 17:34:40 GMT

>>While List<> enumerator is better than ArrayList it's still non-optimal for enumerating a collection.

I actually measured times that were very similar to the above, I was planning to write something about that when I got back from vacation. I think maybe I still will.

However I still urge caution in interpreting the results of Micro-benchmarks in any kind of broad way. This particular one was designed to magnify enumeration overheads which is why I didn't find it fair comment to say something like foreach is so and so % slower than for.

If you were to dig deeper in this you'd find that the reasons it being slower break down into two categories:

1) It has safety checks to help you if the collection is modified out from under you(generally a good tradeoff)

2) It doesn't get fully inlined (partly due to the above)

With ArrayList the problem, as I've mentioned, is that the implementation choice was not especially good.

In neither case is there any find of "foreach" issue -- it's question of how the enumerator is implemented and what choices were made there. You could even write your own arraylist wrapper value type (no storage overhead) that makes a different choice and get different behavior. You could have the for behavior if you want it.

Interestingly, if you do the same experiment for arrays you'll find (well I found) that the foreach pattern is FASTER with /o+ why? The C# compiler generatates better IL for that pattern and the jit does a better job stripping bounds checks. I tried to rewrite my for loop in such a way as to get rid of every bit of overhead but I couldn't figure out the secret sauce. With foreach I got it without even trying.

This data doesn't support a general conclusion like foreach is always worse on collections. Sometimes foreach is the only choice as far as that goes. High performance collections can and do make difference enumeration design choices that can give great performance. Wrapper classes on our generics can easily make different choices -- ones you like better.

That said it's important to know what choice was made in our own basic collection types and it doesn't happen to be the very fastest one. Although it is much better. Remember the enumeration overhead is very much magnified in this example -- by design.

>>In real life application you have allocations of different kinds of objects not only enumerators. The huge number of allocated enumerators will increase the pressure on the GC.

As you indicated (in context of the quote above) my comments are specific to this benchmark but of course I'm the one whose cautioning not to interpret the results of this analysis too broadly. It is interesting to note that the raw cost of the allocations isn't really the problem, because if it was you would see it even in this benchmark.

The true cost is just as you indicated, if there were other operations you would have side-effects on them (to some extent, you would have to measure to see just how much impact). You would affect the overall locality and age the objects faster than they otherwise would potentially increasing the overall cost of collection.

While allocations are cheap, not allocating at all is still cheaper :)

Locality issues can be, as you say, difficult to find because the tax can be spread about your code. However you would see the enumerators in this case in the CLRProfiler, even though they are short lived. I often go fishing for locality issues by looking at overall allocation volume using CLRProfiler. My LogDump tool (recently posted) is also helpful for this because sometimes the logs get very large.

Good comments, thank you!

allocation/collection cost

Alex — Tue, 30 Aug 2005 02:43:04 GMT

> What about all those allocations, many people noticed that the arraylist version is allocating enumerators like crazy. That must be the problem. 10,000,000 enumerator allocations can't be good right? Surely that's the dominant cost? Well, it turns out it isn't. This guy here JIT_NewFast tells the tale, only 1.87% of the run time was spent in allocations. Now since this guy is single threaded, if any collections happened they would be triggered by that call so the collections are part of that 1.87%. In fact if you look at the performance counters while this program is running you'll see that the average time in the garbage collector is only really about one half of one percent (0.5%) so most of that time is just doing the allocations and not collecting.

This argument is applicable only to microbenchmarks. In real life application you have allocations of different kinds of objects not only enumerators. The huge number of allocated enumerators will increase the pressure on the GC. And GC will spend considerably more time doing collections, and collections will happen more frequently.

The worst thing is that because enumerators are temporary objects the cost of their allocation and collection is very difficult to find in a real life application. You won't see them in the CLR Profiler, because they are short-lived. Yet they contribute to the time spent in GC.

foreach argument

Alex — Tue, 30 Aug 2005 02:21:53 GMT

Here it comes :)

foreach loop:
Generic List: 1.80703441359167 sec
ArrayList: 6.64174133863382 sec

for loop:
Generic List: 0.603019657526306 sec
ArrayList: 2.61797574831438 sec

While List<> enumerator is better than ArrayList it's still non-optimal for enumerating a collection.

re: Performance Quiz #7 -- Generics Improvements and Costs -- Solution

Steven Padfield — Mon, 29 Aug 2005 20:49:45 GMT

What tool did you use to obtain the trace you presented in answer to Q3?

re: Performance Quiz #7 -- Generics Improvements and Costs -- Solution

Michael — Mon, 29 Aug 2005 17:02:44 GMT

Great work, Rico!

Just another reminder that I'll be studying every day for the rest of my life in an attempt to learn a fraction of what I think I need to know (and that's not including what I *want* to know... sigh... ).

re: Performance Quiz #7 -- Generics Improvements and Costs -- Solution

ricom — Sat, 27 Aug 2005 10:29:29 GMT

>>It's disappointing that when discussing performance of the CLR the answer always seems to be don't use virtual functions (and interfaces?).

Well that's a bit of a leap. I am the first to say don't use features you don't need -- that's just being smart but don't use virtuals? No I wouldn't go there.

All we can really conclude here is that the implementation choices in the original ArrayList were pretty unfortunate for raw performance and the advice we now give for how to implement enumerators (which we followed in the List<T> class) is helping a great deal.

I wouldn't conclude anything broad from this micro-benchmark. Comparisons between platforms have been done an notoriously give mixed results.

re: Performance Quiz #7 -- Generics Improvements and Costs -- Solution

Jeffrey Sax — Sat, 27 Aug 2005 07:17:44 GMT

I guess I considerably underestimated the impact of the virtual function calls.

To distinguish this effect from the memory usage, I tested the ArrayList option again, but this time took the enumerator construction out of the loop, and did the enumerating manually using MoveNext and Current.

The result: this code is roughly 10% faster than the foreach version. Relative to the generic version, the allocations cause a slow-down of roughly 30%, much more than the 5% or so from the raw allocations.

In other words, about 1/8 of the difference is caused by the allocations and their side effects - significant, but not dominant.

The rest is due to virtual call overhead, divided roughly 55/45 between dispatch stubs and Current not being inlined.

re: Performance Quiz #7 -- Generics Improvements and Costs -- Solution

Brien — Sat, 27 Aug 2005 02:36:30 GMT

It's disappointing that when discussing performance of the CLR the answer always seems to be don't use virtual functions (and interfaces?).

It would be nice if high performance and polymorphism were not mutually exclusive.

Especially since the Java guys have seemed to figure out how to make this work.