I followed some instructions from Miguel and here we have this brand new
patch.
It uses the new algorithm bits-on-stack for
System.Collections.Generic.List<T>::FindAll
(Predicate). This algorithm stores a group of uint's in the stack and uses
their bits as flags.
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.
It also includes few testcases.
Juan C. Olivares
www.juancri.com
On 3/18/07, Juan C. Olivares <[EMAIL PROTECTED]> wrote:
I'll check...
Juan Cristóbal Olivares
www.juancri.com
On 3/18/07, Miguel de Icaza < [EMAIL PROTECTED]> 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 < [EMAIL PROTECTED]> 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 - [email protected]
> > > http://lists.ximian.com/mailman/listinfo/mono-list
> >
> >
> > _______________________________________________
> > Mono-list maillist - [email protected]
> > http://lists.ximian.com/mailman/listinfo/mono-list
>
>
Index: class/corlib/System.Collections.Generic/List.cs
===================================================================
--- class/corlib/System.Collections.Generic/List.cs (revision 74587)
+++ class/corlib/System.Collections.Generic/List.cs (working copy)
@@ -212,19 +212,68 @@
throw new ArgumentNullException ("match");
}
- // Maybe we could make this faster. For example, you could
- // make a bit set with stackalloc for which elements to copy
- // then you could size the array correctly.
public List <T> FindAll (Predicate <T> match)
{
- CheckMatch (match);
- List <T> f = new List <T> ();
+ this.CheckMatch (match);
+ if (this._size <= 0x10000) // <= 8 * 1024 * 8 (8k in stack)
+ return this.FindAllStackBits (match);
+ else
+ return this.FindAllList (match);
+ }
+
+ private List <T> FindAllStackBits (Predicate <T> match)
+ {
+ unsafe
+ {
+ uint *bits = stackalloc uint [(this._size / 32) + 1];
+ uint *ptr = bits;
+ int found = 0;
+ uint bitmask = 0x80000000;
+
+ for (int i = 0; i < this._size; i++)
+ {
+ if (match (this._items [i]))
+ {
+ (*ptr) = (*ptr) | bitmask;
+ found++;
+ }
+
+ bitmask = bitmask >> 1;
+ if (bitmask == 0)
+ {
+ ptr++;
+ bitmask = 0x80000000;
+ }
+ }
+
+ List <T> results = new List <T> (found);
+ bitmask = 0x80000000;
+ ptr = bits;
+ for (int i = 0; i < this._size; i++)
+ {
+ if (((*ptr) & bitmask) == bitmask)
+ results.Add (this._items [i]);
+
+ bitmask = bitmask >> 1;
+ if (bitmask == 0)
+ {
+ ptr++;
+ bitmask = 0x80000000;
+ }
+ }
+
+ return results;
+ }
+ }
+
+ private List <T> FindAllList (Predicate <T> match)
+ {
+ List <T> results = new List <T> ();
+ for (int i = 0; i < this._size; i++)
+ if (match (this._items [i]))
+ results.Add (this._items [i]);
- foreach (T t in this)
- if (match (t))
- f.Add (t);
-
- return f;
+ return results;
}
public int FindIndex (Predicate <T> match)
Index: class/corlib/Test/run_test.sh
===================================================================
--- class/corlib/Test/run_test.sh (revision 74587)
+++ class/corlib/Test/run_test.sh (working copy)
@@ -12,7 +12,7 @@
fi
topdir=../../..
-NUNITCONSOLE=$topdir/nunit20/nunit-console.exe
+NUNITCONSOLE=$topdir/class/lib/net_2_0/nunit-console.exe
MONO_PATH=$topdir/nunit20:$topdir/class/lib:.
for i in $@; do
Index: class/corlib/Test/System.Collections.Generic/ListTest.cs
===================================================================
--- class/corlib/Test/System.Collections.Generic/ListTest.cs (revision 74587)
+++ class/corlib/Test/System.Collections.Generic/ListTest.cs (working copy)
@@ -467,7 +467,7 @@
}
[Test]
- public void FindAllTest ()
+ public void FindAllSmallTest ()
{
List <int> findings = _list1.FindAll (FindMultipleOfFour);
Assert.AreEqual (4, findings.Count);
@@ -480,6 +480,42 @@
Assert.IsNotNull (findings);
Assert.AreEqual (0, findings.Count);
}
+
+ [Test]
+ public void FindAllMediumTest ()
+ {
+ List <int> integers = new List <int> (10000);
+ for (int i = 1; i <= 10000; i++)
+ integers.Add (i);
+
+ List <int> results = integers.FindAll (FindMultipleOfFour);
+
+ Assert.IsNotNull (results);
+ Assert.AreEqual (2500, results.Count);
+
+ results = integers.FindAll (FindMultipleOfTwelve);
+
+ Assert.IsNotNull (results);
+ Assert.AreEqual (833, results.Count);
+ }
+
+ [Test]
+ public void FindAllLargeTest ()
+ {
+ List <int> integers = new List <int> (70000);
+ for (int i = 1; i <= 80000; i++)
+ integers.Add (i);
+
+ List <int> results = integers.FindAll (FindMultipleOfFour);
+
+ Assert.IsNotNull (results);
+ Assert.AreEqual (20000, results.Count);
+
+ results = integers.FindAll (FindMultipleOfTwelve);
+
+ Assert.IsNotNull (results);
+ Assert.AreEqual (6666, results.Count);
+ }
[Test, ExpectedException (typeof (ArgumentNullException))]
public void FindAllNullTest ()
_______________________________________________
Mono-list maillist - [email protected]
http://lists.ximian.com/mailman/listinfo/mono-list
