[Mono-dev] List<T> Optimisations

[Alan McGovern]

Hi,

Thats a brilliant idea. It'll be much faster than the current shifting.

I'll test it out now.

Thanks,
Alan.

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
> 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
> _______________________________________________
> Mono-devel-list mailing list
> Mono-devel-list at lists.ximian.com
> http://lists.ximian.com/mailman/listinfo/mono-devel-list
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.ximian.com/pipermail/mono-devel-list/attachments/20070326/ae9f8c61/attachment.html