[Mono-dev] List<T> Optimisations

[Michael Poole]

Alan McGovern writes:

> I was just browsing through the List<T> implementation and made a few speed
> optimisations. I'm not sure if changing from foreach(blah) to for(int i=0; i<
> blah, i++) is ok or not, but it does offer a large speed increase. So let me
> know if that's ok or not.
>
> Optimised Methods:
> RemoveAll - from 0x up to 50x faster
>
> (The reason for the huge speed increase is that if you have a list<int>
> containing entirely the number 5, removing from the end will be much more
> efficient than removing from the start as you won't have to shift the entire
> array over and over. Removing from the end will *always* be faster than
> removing from the start, but the exact speed increase is highly dependant on
> the number of matches).

You can avoid any duplicate shifting by keeping one additional
variable.  I have not looked at the rest of the class, so this may not
be quite right, but should capture the rough idea of always-linear
behavior:

  int ii, jj;

  // Scan past the non-matching prefix of the list.
  for (ii = 0; ii < _size; ++ii)
  {
    if (match(_items[ii]))
      break;
  }

  // Could optimize away the repeated call to match(_items[ii]) here.
  // The speedup of doing so is questionable.

  // Do in-place removal for the remaining items.
  for (jj = ii; ii < _size; ++ii)
  {
    if (!match(_items[ii]))
      _items[jj++] = _items[ii];
  }

  // dispose of _items[jj] through _items[_size] here
  _size = jj;

Michael Poole