[Mono-list] List.FindAll method implementation

[Paolo Molaro]

On 03/19/07 Juan C. Olivares wrote:
> 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.

As a rule, stackalloc must not be used in the class libraries.
Exceptions are possible if the size is small and if it provides a
significant performance speedup for a common operation.
8 KB of stack space is definitely too much to use and it is also,
as your numbers show, in an area where an heap-allocated array would be
faster. 1 KB of stack-allocated memory would be on the high-side
already.

That said, if the existing code is slow, we need to understand why,
because that is what we need to fix first: the existing code just uses
List<T>.Add (T val) and this is a very basic operation. If that is slow,
it needs to be improved and FindAll() will become faster as a
consequence.

As a data point, the older code was significantly slower because
it used an iterator.
As another data point, the new code is sometimes slightly slower and sometimes
slightly faster for the attached benchmark (depending on things like the value 
of mod, ie how many results we return): I just changed 0x1000 to 1 in the
FindAll if so that the stackalloc func was not called.

So I'd like to see the code you used to generate your numbers, because
as things look right now, I see no reason to use the stackalloc codepath
at all (given its risks) and it should be removed.
Thanks!

lupus

-- 
-----------------------------------------------------------------
lupus at debian.org                                     debian/rules
lupus at ximian.com                             Monkeys do it better
-------------- next part --------------
using System;
using System.Collections.Generic;

class T {
	static int size = 10;
	static int count = 1000000;
	static int mod = 10;

	static Predicate<string> match = delegate (string v) {
		return v == "hello";
		//return false;
	};

	static List<string> Setup ()
	{
		List<string> l = new List<string> ();
		int start, end;
		start = Environment.TickCount;
		for (int i = 0; i < size; ++i) {
			if ((i % mod) == 0)
				l.Add ("hello");
			else
				l.Add ("world");
		}
		end = Environment.TickCount;
		Console.WriteLine ("size: {0}, loops: {1}, setup time: {2}", size, count, end-start);
		return l;
	}

	static void Run (List<string> l)
	{
		int start, end;
		List<string> res;
		start = Environment.TickCount;
		for (int i = 0; i < count; ++i) {
			res = l.FindAll (match);
		}
		end = Environment.TickCount;
		Console.WriteLine ("size: {0}, loops: {1}, time: {2}", size, count, end-start);
	}

	static void Main (string[] args) {
		if (args.Length > 0)
			size = int.Parse (args [0]);
		if (args.Length > 1)
			count = int.Parse (args [1]);
		if (args.Length > 2)
			mod = int.Parse (args [2]);
		List<string> res;
		while (count >= 10) {
			res = Setup ();
			Run (res);
			size *= 10;
			count /= 10;
		}
	}
}