Collections too slow? When to write your own basic types


As usual there isn’t really one set of rules that will always guide you to making the right decisions but I’d like to offer some approximately correct guidance to help you to decide when you should decline the standard menu and instead cook up your own basic types.

Rule #1:  Don’t do it

Seriously, who needs the aggravation?  If you create your own basic types (a collection, an event source, an enumerator, a string buffer, etc.) you’ll automatically start at a penalty.  The built-in class is bound to be used in your application, either directly or indirectly. Even if you could substitute your class for the built-in class it’s likely that the new class doesn’t do everything the standard version does – in fact that may be the very reason you created your own class.  So now your program will have to load (at least) two classes that do approximately the same job.  Likewise your developers will have to keep (at least) two classes in their head and know how to choose between them.  And of course you’ll have to service the extra class yourself – no handy security fixes from your pals at Microsoft in the event of boo-boos, you’ll have to do your own patches. You do have a site like windowsupdate.com in your release plan right?  No?  Hmmm… you might be needing one.  Lastly, and perhaps most compellingly, it just doesn’t scale – if everyone creates their own version of some basic class that’s approximately but not quite the same as the one offered by default then the total redundancy that end users (like my mom) get in their applications will be staggering.

So, seriously, just don’t. 

OK, you still really want to?  Or better yet you really don’t want to but you’re pretty sure you have to.  Here are some of the more common reasons why it becomes necessary.

Rule #2: Do it if data volume demands specialization

Our base classes are designed to be broadly applicable and so they provide a broad spectrum of services and a nice high quality of service.  However this can work against you:  Suppose your application needs say a million hash tables…  Yikes!  Do you really want our full service hash tables for that?  Maybe not.  How many entries in these hash tables?  If there’s a million of them maybe not too many.  What’s the overhead per hash table going to be?  There could be very big savings on the table for a specialized class.  Maybe enough savings to let you target a lower class of consumer hardware and still be functional.  That kind of flexibility might be enough to justify the extra work.

Rule #3: Do it if call volume demands specialization

Again, our base classes are designed to be easy to use in a variety of situations and provide robust error reporting.  However if (e.g.) collections are critical to your performance scenario and your call volume (number of calls) is such that every cycle counts you may need to have your own specialized collection.  I’m picking on the collections here because everyone knows them, but the same phenomenon can happen in pretty much any low-level class.  Sometimes the cost of the nice parameter checking (and we’d be slammed if we didn’t do good parameter checking) is comparable to the whole job at hand.  Sometimes the cost of polymorphism (the virtual function calls) for plugability is comparable to the cost of the full job of the API.  Consider poor ArrayList – we need to do argument validation on even the simple methods or else developers will be faced with very difficult to decode exceptions internal to the class.  So we put in extra checks to help developers get rich messages and be more productive.  However, if an ArrayList collection was the cornerstone of your application, creating a specialized class might be just what you need meet throughput goals on more modest hardware (and hence win valuable contracts).

Rule #4:  Do it if exotic threading disciplines are required for scale

Many of our lowest level classes offer little guarantee in the way of multi-threaded services.  We tend to write them so that you provide your own locking mechanism and we stay the heck out of the locking business.  That’s a good position to take in my opinion because low level classes like hashtables don’t really understand the context in which they are being used, so they would tend to take locks at the wrong granularity to be useful if you try to make them natively multithreaded.  This is all fine and well but if the objects are fundamentally single threaded (and hence need to be protected by locks) but you can’t afford to take those locks (because it would kill your scale-up on a multi-processor machines) then you might need a specialized collection, enumerator, or whatever, that is multi-processor aware and (very carefully!) uses volatile storage and maybe interlocked operations to provide some useful multi-threaded support in a lock-free manner.  This might be what it takes to get good value for the dollar on (e.g.) an 8, or 32 processor box. 

Rule #5: Do it if strict control over memory or exceptions is critical

The final case is probably the rarest by far.  However there are cases where users are trying to create classes that will be used in a near-real-time scenario (such as video playback).  In that case you might want to use only a set of classes that carefully control the lifetime of the objects allocated (e.g. via recycling) so as to have garbage collections happen in a much more predictable fashion.  This is not an easy undertaking but it is possible and even important in some cases where managed code is being used in (e.g.) a kiosk.

Rule #6: Report performance issues in the regular classes whenever you can

Take advantage of http://lab.msdn.microsoft.com/ProductFeedback/ (aka Ladybug) to give us a wake-up call if some area of the framework is letting you down.  This is a great way to influence the team’s priorities and believe me we really want to do the most important stuff first.  It’s also a great way to share workarounds and warnings when appropriate.

Summary:  Have careful measurements and clear verifiable goals for success before proceeding

All of the cases I’ve discussed identified a performance problem that was both acute and relevant to the overall success of the product.  Before taking the cost of re-implementing a low level type you’ll want to quantify the costs and benefits of adopting your own and then verify that you are getting those benefits.  E.g. (fictitious example) “Simulations indicated that a lock-free multi-reader version of the hashtable would yield 25% more throughput on 8-way processors and 50% more on 32-way processors for our product.  These gains should result in an extra $1M revenue in the next fiscal year which justifies the expected $100,000 in extra support costs.”

You might start with ideas like “Hmm, I think I could do this with less memory if I roll my own” but I strongly caution you to not stop there.  Have strong data to back your position or chances are you’ll get nothing but aggravation.

Remember, if you are delivering a small component into someone else’s larger system, you probably shouldn’t build your own low level implementations.  But if you are a medium or large team delivering a complete subsystem or application, and you can devote real bodies to the problem, then you might be able to justify the investment.

Comments (7)

  1. Joannes says:

    Btw, is the SortedList implementation going to be fixed in .Net 2.0? In .Net 1.1, the implementation is such that all insertion/deletion operations cost O(n) instead of O(ln(n)) as anyone would expect for such a collection.

  2. Rico Mariani says:

    The thing about collections is they come in a lot of flavors. This particular flavor of SortedList offers this nice function:

    public virtual Object GetByIndex(int index){}

    But in order to offer that service (at constant time) you have to pay a price at insert time.

    Of course there are other implementations of a sorted list that offer faster insertions but have no random access.

  3. Thanks for the nice article, Rico. I really enjoy having resources to help make decisions, not necessarily just on what code to type.

  4. Rico Mariani says:

    It’s funny that you should choose those words. I’ve been trying to explain what it is that an architect at Microsoft does and what I’ve taken to telling people is: "I’m in the decision improvement business"

    Maybe I’m on to something 🙂

    Thanks for the kind words

  5. How about Rule #7? Do if it improves the readability/usability of you API’s.

    We have an application where one of the input parameters is a Hashtable of Hashtables. So the inner Hashtable would be a collection like

    Price["Widget"] = 1.01m

    Price["ThingyBob"]=2.02m

    and there would be a bossman collection that held these:

    Store["Wallmart"] = Price1

    Store["Tiffany"] = Price2

    Now if we had a method like LoadData(System.Collections.IDictionary values) I would have little of no clue as to what this method actually took. What are the keys and what are the values?

    If I defined a custom collection IDictionaryStringKeyDecimalValue and IDictionaryStringKeyIDictionaryStringKeyDecimalValueValue ( i.e. a fake IDictionary<String, IDictionary<String, Decimal> > ), at the risk of aggravating my RSI, I’ve given API consumers ( and myself! ) a pretty clear indication of what my method is expecting. They still probably need to read the docs to get a compete picture ( i.e. what are the valid string values? What exceptions does this thing throw etc) but they are in the right frame of mind before they hit F1. With code generators like CodeSmith, actually creating these things is not that painful anymore.

  6. Ivan Stoev says:

    We definitely prefer #1, but unfortunately forced to do #2. Which wasn’t true with STL for instance. With the presense of generics, what was the problem BCL to expose a low level, highly customizable (via generic type parameters (traits)) collection types (preferable structs) and build current "full service" classes on top of them?

    And if they are supposed to be used only for implementation (i.e. containment and delegation), why they are implemented as classes at all (instead of structs)?

    The point is that in order to be able to follow Rule#1, we need much better BCL, in particular Collections.Generic – the current just brings me back to old VB6 days when we had a "great" choice between array, Collection and Dictionary – doesn’t seem a big step forward?