Six Questions about Generics and Performance
Here are some comments from a recent discussion on Generics that I thought were generally useful. The comments have been edited so that they fit better with the general format of a Q&A session. The origin of this discussion was some commentary on the cost associated with creating instances of generic types where the type parameter is a value-type -- that case is interesting because the code for those classes cannot be shared like it can for reference types, so there can be considerable cost associated with their use.
As always many of these questions would require whole tomes to answer fully, so I'm giving an answer that's brief but only approximately correct. For additional information on Generics please see these links:
And the Q&A:
Q1: It seems like you save on boxing/unboxing [by using Generics] in the exact same scenarios [value types] as you lose on working set – in other words, as far as I can tell, you only lose on memory when you’re going to gain on boxing. Is that the case?
Generally speaking that's correct but of course nothing is ever simple in the performance world.
You may or may not save on boxing by using generics just as you may or may not save on boxing by using arrays of value types. It depends on the whole life-cycle of those objects.
Sometimes you're trading transient object use for full-time static code, that can be a bad trade. Other times you really are eliminating tons of boxing which is a huge win.
It's important to remember that generics can and do share implementation between reference types but they can't share implementation between value types (well a sufficiently advanced JIT might be able to do some sharing but none is happening at the moment).
Q2: Why exactly is space king in WinFX? I’ve always though wall-clock-time was king. Are we telling app developers to focus on space as well or is it just a platform issue?
Library code runs in a variety of contexts, it is imperative that you remember that you will be sharing the machine and indeed your library is not the main thing running, it's a utility being used by the main thing running. Your job is to use the fewest possible resources so there is as much possible left over for other things. Like a bigger disk cache.
If your code is big enough that it pushes the machine into paging -- which can happen when targetting more modest machines -- then you're really in a world of hurt. But it's not just paging that is your enemy. Every bit of memory you touch pushes something out of the processors L2 cache, so if your code causes 25% more cache faults while its running that's a real cost. It's a sneaky cost too because it’s a cost that is paid (again) after your code is finished running (reheating the cache so that the main algorithm can continue).
Space is king because space *IS* speed. Only when you are very lucky and very careful can you trade space for speed -- the general rule is that smaller is faster. The size of your classes will directly limit the customers that can use them, on big machines and small.
Q3: Why don’t we have exposed reference types to wrap value types so I can do List<Int32Wrapper> if I’m ok with the boxing/unboxing CPU loss because the working set cost is more important to me? Why must people with needs for collections of value types be forced into a choice that hurts their working set?
You can make a generic (reference) class Box<VT> in a heartbeat… course it'll cost you a few K. But then you can do Dict<Box<VT>, Box<OtherVT>> on the cheap. That might not be totally stupid for your application.
I feel like Sting here but -- "Every choice you make, every type you fake, know it's costing you…"
I preach these huge warnings about generics because unlike a lot of things you can take a huge, non-sharable, static hit with a small number of characters typed. You can blow a lot of memory (a lot more!) by making big ArrayLists but nobody is surprised that their 1,000,000 entry array list is large. People can be shocked when they find what the price tag was for using some other more suble features that look innocuous like XML, Reflection, and Generics. It's so easy to use them but "easy" doesn't always mean "free", and certainly doesn't (always) mean "prudent."
Q4: How are we actually recommending people measure?
It's always about giving your customers good value for the byte in the scenarios in which they will be using your system.
See http://blogs.msdn.com/ricom/archive/2004/09/07/226315.aspx for some ideas there.
There's a whole chapter on modelling in http://msdn.microsoft.com/perf
Here's another useful one on planning http://blogs.msdn.com/ricom/archive/2004/04/22/118422.aspx
And some cautions about the basic collections too (I have a caution for all occasions, it's my job)http://blogs.msdn.com/ricom/archive/2004/04/29/123126.aspx
Q5: List<T> brings more than just compile-time type safety of course, it’s the ability to RemoveAll / FindAll / etc. that makes it much more productive to use in my code – how do we recommend people factor in API usability, compile-time type safety, etc. while they’re considering which collections to go with? "We lost 0.06% perf, but the gains in productivity and maintainability were worth it" seems like something customers should be able to conclude. How are we enabling that?
Time to market is a very real consideration for us and for many of our customers. Not to mention bug count and long term servicability. All of these are factors to be considered. However it's no use getting to market with a solution that's fundamentally unusable by a large number of your customers. That's why its vitally important to understand your system as your customer is going to be using it and then make quantitative choices about what you can afford. That's what engineering is all about. There are many cases where with only 2 seconds of thought you can conclude that the "easy way" is plenty fast enough and in those cases you shouldn't spend more than those 2 seconds. However, for library writers it is rarely that easy.
As library writers it often falls to us to do things the hard way so that our customers have it easy.
Q6: If people could choose to either List<T> or List<Box<T>> for T : struct, are there still scenarios where ArrayList is better than List<T>?
It's hard to think of a reason not to use say List<Object> over ArrayList -- the List implementation is just better in a variety of ways.
The main reason not to use List<Object> would be that you might not want to put it in your public API and you might want to run on downlevel versions of the CLR.