[Mono-list] List.FindAll method implementation

[Miguel de Icaza]

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