[Mono-dev] List<T> Optimisations
alan.mcgovern at gmail.com
Mon Mar 26 18:51:37 EDT 2007
Thats a brilliant idea. It'll be much faster than the current shifting.
I'll test it out now.
On 3/26/07, Michael Poole <mdpoole at troilus.org> wrote:
> Alan McGovern writes:
> > I was just browsing through the List<T> implementation and made a few
> > 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
> > efficient than removing from the start as you won't have to shift the
> > 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)
> if (match(_items[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)
> if (!match(_items[ii]))
> _items[jj++] = _items[ii];
> // dispose of _items[jj] through _items[_size] here
> _size = jj;
> Michael Poole
> Mono-devel-list mailing list
> Mono-devel-list at lists.ximian.com
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Mono-devel-list