[Mono-dev] List<T> Optimisations
mdpoole at troilus.org
Mon Mar 26 13:57:51 EDT 2007
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
int ii, jj;
// Scan past the non-matching prefix of the list.
for (ii = 0; ii < _size; ++ii)
// 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)
_items[jj++] = _items[ii];
// dispose of _items[jj] through _items[_size] here
_size = jj;
More information about the Mono-devel-list