Stories from the Perf lab: Part I

During the past year, we’ve found and fixed a lot of perf issues in Expression and WPF.  I’d like to relate a few of them, not so much because you’ll have the exact same problems, but that the pattern of finding and resolving the bugs may be helpful experiences.  To start:

Expression uses a tree data structure to keep track of the XAML source code.  Each node in the tree has a property called Children that returns a List of all its child nodes. For leaf nodes this collection was always empty, but even so a new collection object was always allocated. In some scenarios, this resulted in megabytes of allocations.  To fix this, we implemented a singleton EmptyList class.  Leaf nodes always return the same instance of this collection, removing all the allocation costs. 

There are two implementation patterns here.  The simplest is to have a static EmptyList, like this:

public static List<Node> EmptyList = new List<Node>();

and just always return that.  This will get you most of the performance you want.  We went a little further and implemented a whole class, giving us greater correctness and even slightly better perf.  Here for example is the implementation of the ICollection members on EmptyList:

            public void Add(T item)

            {

                  throw new NotSupportedException();

            }

            public void Clear()

            {

            }

            public bool Contains(T item)

            {

                  return false;

            }

            public void CopyTo(T[] array, int arrayIndex)

            {

            }

            public int Count

            {

                  get { return 0; }

            }

            public bool IsReadOnly

            {

            get { return true; }

            }

            public bool Remove(T item)

            {

                  return false;

            }

In general, collection classes are a good place for teams to look at optimization: Expression, WPF and other Microsoft teams have all implemented specialized collections for degenerate cases and other cases where the BCL collections are overly general or expensive.

Comments

• Anonymous
  September 08, 2006
  Hi, John, could you please elaborate a litte bit about how good performance can be achieved by creating a dedicated empty collection?In my understanding, when the collection is kept empty, it won't occupy too much memory.Sheva