[Mono-list] List.FindAll method implementation
Miguel de Icaza
miguel at novell.com
Tue Mar 20 10:24:18 EDT 2007
Hello,
>
> I think the "heap bit" method is not that good :)
But it only becomes slower with ten million elements.
Also, when you run your tests, you might want to run multiple
iterations, so the times are larger (without all the zeros in the
prefix :)
> 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
More information about the Mono-list
mailing list