ControlCollection

5/6/03

The following is a general description of how the ControlCollection is implemented in the System.Windows.Forms.Control. Specifically, it concerns performance of the code underneath so that you can take it into consideration when adding and removing controls is a performance issue.

First of all, one would assume that calling AddRange() and passing an array of controls would be faster than looping through all the control and calling Add(). The reverse however, is true. You can achieve roughly the same performance using the following code (assume that controls is your array of controls to be added):

  this.SuspendLayout()

  foreach(Control ctrl in controls)
  {
    this.Controls.Add(ctrl)
  }

  this.ResumeLayout()

This is in fact, exactly how AddRange() appears to work (except that it throws an ArgumentNullException if you pass a null array of Controls.

Now, why is that bad? Well, the way Add() works is to allocate an initial array for the controls with room for 4 controls. Each time you add a control beyond what the control collection is currently allocated for, it doubles the allocation, so the 5th control re-allocates for 8 controls then copies all the old controls over, and then adds the 5th control.

Wouldn't it make more sense for AddRange to say, "Hey, we're adding 20 controls. Let's re-allocate the array for at least 20 more control," instead of having multiple re-allocations? Granted, since it doubles the number of slots with each allocation, the number of reallocations drops off quickly, but still, multiple allocations could be removed entirely for an AddRange() call.

There's currently no "legal" way to override this implementation of AddRange, because the internal array of controls is private to the ControlCollection class. However, I believe there is a way to side-step this using reflection. I will try to do that over the next week or so and post it here.

Now, on the remove side, we also find some interesting stuff. I originally thought that RemoveAt() would have better performance than Remove(). Again, this is not the case. RemoveAt() actually calls get_Item (the indexer, really) which checks that the value is within the range of valid values (else throws an exception), and then calls Remove() with the actual control. So, clearly, calling Remove() directly is the best thing to do, in terms of performance.

Also, as an additional note, it turns out that Remove() will be much more efficient if you remove the controls in LIFO (Last In, First Out) order. The reason is that in the Remove(), a call is made to Array.Copy() to shift all of the items to the right of the item removed, left one location. So, clearly, if you're removing a bunch of controls in the same order that you added them, there's going to be a lot of shifting in the array. Far better to remove them in the reverse order (i.e. from the end of the array towards the front), if possible.

It's worth noting that Clear() takes advantage of this by removing the items in reverse order. Unfortunately, Clear() also calls RemoveAt() instead of Remove which as mentioned before, is sub-optimal. The implementation of clear looks something like this:

  while(items.Count > 0)
    RemoveAt(items.Count - 1);

Alternatively, it could be implemented more efficiently as:

  while(items.Count > 0)
    Remove(items[items.Count - 1]);

I would have thought that a more efficient method could be found for handling all of this, and maybe there is, but maybe it also depends on the situation. Maybe this provides better performance on average. However, when large numbers of controls are contained, that is really when performance becomes critical.

The IndexOf() method takes a control as a parameter and returns the index into the internal array of controls. This is used to allow calls to RemoveAt() and the indexer. IndexOf() is a O(n) algorithm. Meaning, it basically searches through the array, one item at a time, to find the control's index. In other words, not fast. The indexer itself simply does a bounds check on the index (throwing an ArgumentOutOfRangeException if the value passed is out of range) and then returns the indexed item from the array (item[index]). About as optimal as they come.