[Mono-list] List.FindAll method implementation
Juan C. Olivares
juancri at gmail.com
Mon Mar 19 20:27:28 EDT 2007
Nice idea but..
Some results:
100 elements:
old method: 00:00:00.0126610 (26x)
stackalloc bit method: 00:00:00.0004750 (1x)
array bit method: 00:00:00.0010700 (2x)
heap bit method: 00:00:00.0038830 (8x)
1,000 elements:
old method: 00:00:00.0139250 (24x)
stackalloc bit method: 00:00:00.0005670 (1x)
array bit method: 00:00:00.0010890 (2x)
heap bit method: 00:00:00.0034920 (6x)
10,000 elements:
old method: 00:00:00.0136110 (12x)
stackalloc bit method: 00:00:00.0011240 (1x)
array bit method: 00:00:00.0016450 (1.4x)
heap bit method: 00:00:00.0043110 (3x)
50,000 elements:
old method: 00:00:00.0175970 (3x)
stackalloc bit method: 00:00:00.0085630 (1.5x)
array bit method: 00:00:00.0055010 (1x)
heap bit method: 00:00:00.0099590 (1.8x)
100,000 elements:
old method: 00:00:00.0210330 (2x)
array bit method: 00:00:00.0100430 (1x)
heap bit method: 00:00:00.0154150 (1.5x)
1,000,000 elements:
old method: 00:00:00.1243730 (1.2x)
array bit method: 00:00:00.0973110 (1x)
heap bit method: 00:00:00.1285650 (1.3x)
10,000,000 elements:
old method: 00:00:00.9252570 (1x)
array bit method: 00:00:00.9632300 (1.05x)
heap bit method: 00:00:01.1098490 (1.20x)
I think the "heap bit" method is not that good :)
JCO
On 3/19/07, Miguel de Icaza <miguel at novell.com> wrote:
>
> Hey!
>
> > is that really better than user a uint[] array? I have thinked in
> > other solutions... I will test them later.
>
> Well, basically you could use the same code path FindAllStackBits, but
> you would have to change it like this:
>
> List <T> FindAllStackBits (uint *bits, Predicate <T> match)
>
> And you would have to pre-allocate bits in the caller:
>
> if (size < 8*8*1024)
> bits = stackalloc uint [n];
> else
> bits = (uint *) Marshal.AllocHGlobal (...);
>
> That way it always uses a fast path, the only difference is that for
> large memory blocks we use memory on the heap instead of using stack
> memory.
>
> Miguel
> > JCO
> >
> > On 3/19/07, Miguel de Icaza < miguel at novell.com> wrote:
> > Hello Juan,
> >
> > > Because there's no way to know the size of the stack in any
> > moment in
> > > time, Miguel suggested me to limit this new method to use
> > only 8KB of
> > > the stack... so it will be useful for list with 8 * 1024 * 8
> > elements
> > > or less. Bigger lists will use the old algorithm.
> >
> > I just had an idea: if the memory to be allocated is too
> > large, instead
> > of using stackalloc, you could use:
> >
> > using System.Runtime.InteropServices ;
> >
> > IntPtr Marshal.AllocHGlobal (size);
> >
> > and release it with:
> >
> > Marshal.FreeHGGlobal (IntPtr p);
> >
> > That way we could always use the fast mechanisms.
> >
> > > It also includes few testcases.
> > >
> > > Juan C. Olivares
> > > www.juancri.com
> > >
> > > On 3/18/07, Juan C. Olivares < juancri at gmail.com> wrote:
> > > I'll check...
> > >
> > > Juan Cristóbal Olivares
> > >
> > > www.juancri.com
> > >
> > > On 3/18/07, Miguel de Icaza <miguel at novell.com>
> > wrote:
> > > Hello,
> > >
> > > I feel a bit strange that the bools are
> > allocated
> > > using
> > > numbers.Count but the loop uses this._items.
> > I
> > > rather keep them in
> > > parallel.
> > >
> > > Also, another idea might be to use three
> > code
> > > paths depending on the
> > > number of items:
> > >
> > > * [0,N] use bools.
> > > * [N,M] use bitbools.
> > > * [M,infinity] use the old method.
> > >
> > > Thread stacks could not be very large,
> > and you
> > > would like to avoid a
> > > crash in that condition. Actually, I
> > wonder if
> > > stackalloc returns a
> > > null if the requested size is larger than
> > the
> > > available stack.
> > >
> > > Miguel.
> > >
> > > > Attached.
> > > >
> > > > Juan C. Olivares
> > > > www.juancri.com
> > > >
> > > > On 3/18/07, Miguel de Icaza <
> > miguel at novell.com>
> > > wrote:
> > > > Hello,
> > > >
> > > > >
> > > > > Do you have any comment?. I
> > could send a
> > > patch...
> > > >
> > > > These numbers look fantastic. We
> > would
> > > love to see a patch.
> > > >
> > > > > best regards
> > > > >
> > > > > Juan C. Olivares
> > > > > www.juancri.com
> > > > >
> > > > >
> > > > >
> > > > >
> > >
> > _______________________________________________
> > > > > Mono-list
> > > maillist - Mono-list at lists.ximian.com
> > > > >
> > >
> > http://lists.ximian.com/mailman/listinfo/mono-list
> > > >
> > > >
> > > >
> > _______________________________________________
> > > > Mono-list maillist -
> > Mono-list at lists.ximian.com
> > > >
> > http://lists.ximian.com/mailman/listinfo/mono-list
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> >
> >
> >
> >
> > --
> > Juan Cristóbal Olivares
>
>
--
Juan Cristóbal Olivares
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.ximian.com/pipermail/mono-list/attachments/20070319/d5dc1e6f/attachment-0001.html
More information about the Mono-list
mailing list