[Mono-dev] [PATCH] Optimization to System.Collections.Generic.List

[Laurent Debacker]

Oops yeah I saw the problem with my while, and thank you for the
explaination about structs.

List.patch1 includes the optimization with a for loop.
List.patch2 includes the above patch plus a little optimization to the
enumerator.

If you want exact results on an Intel P3 Mobile 750Mhz running MS .NET
2.0 (20000 iterations with 10000 elements)
MS's List.ForEach: 5.61 secs
Mono's List.ForEach: 15.20 secs
My List.ForEach: 4.63 secs

MS's foreach loop: 7.24 secs
Mono's foreach loop: 11.24 secs
My foreach loop: 10.74 secs

Laurent.

On 11/12/05, Ben Maurer <bmaurer at ximian.com> wrote:
> On Sat, 2005-11-12 at 19:13 +0100, Laurent Debacker wrote:
> > Hi!
> >
> > The file is a modified version of
> > mcs/class/corlib/System.Collections.Generic/List.cs revision 52947.
> >
> > I've modified the ForEach method so that it no longer uses the
> > enumerator. This avoids a lot of method calls to Enumerator (and the
> > creation of yet another Enumerator object).
>
> The Enumerator is a struct, it is allocated on the stack. So, your patch
> just inlines the methods. With our current jit, this is probably faster,
> first we aren't doing inlining, second even if we did inline, the struct
> would always be on the stack, with int variables, we can keep it in a
> register. We'd need something to decompose the struct into variables so
> that we could do register allocation on it. I'd rather focus on making
> foreach () on a List<T> be nearly as fast as manual iteration than
> replacing things with manual loops blindly.
>
> However, it looks like that is besides the point. MSFT does not do
> failfast behavior (ie, it doesn't error out on modifications to the
> list), as you commented in the method. I believe this is a bug (we
> should file it with them), because modifying the collection will make
> the enumeration meaningless. However, we should emulate the behavior for
> now.
>
> Please rewrite using a for loop rather than a while loop and submit a
> patch (svn diff).
>
> -- Ben
>
>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: List.path1
Type: application/octet-stream
Size: 1421 bytes
Desc: not available
Url : http://lists.ximian.com/pipermail/mono-devel-list/attachments/20051112/6d940201/attachment.obj 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: List.path2
Type: application/octet-stream
Size: 2324 bytes
Desc: not available
Url : http://lists.ximian.com/pipermail/mono-devel-list/attachments/20051112/6d940201/attachment-0001.obj