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 (1)

  1. Sheva says:

    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

Skip to main content