[Mono-list] Tuning Dictionary`2

[Juraj Skripsky]

Hi Miguel,

The List.FindAll patch is svn now.

Speaking of optimizations: The implementation of Dictionary`2 could
benefit immensely from tuning.

See this bug for some information:
http://bugzilla.ximian.com/show_bug.cgi?id=80774

While Hashtable stores its values in an array, Dictionary`2 stores them
in linked lists (see Dictionary`2.Slot class), boxing all values in the
process. The performance advantage of generics is not used at all.

What puzzles me most, is this:
http://msdn2.microsoft.com/en-us/library/ms379571(VS.80).aspx

According to this article, the implementation of Dictionary`2 in MS.NET
employs linked lists as well. Has anybody an idea why? Is the
generational GC in MS.NET so good that Dictionary`2 performs better with
linked lists than with an array?

I think a generic variant of the Hashtable data structure makes much
more sense.

Any ideas or feedback appreciated!

- Juraj


On Tue, 2007-03-20 at 19:55 -0400, Miguel de Icaza wrote:
> Hey!
> 
> > I've just noticed the commit to List.FindAll(). Attached is an (small)
> > optimization for the optimization:
> 
> This is fantastic ;-)
> 
> Please commit ;-)
> 
> If we could only do these kind of tuning everywhere ;-)
> 
> > - the resulting List<T> is built directly as an array which is later on
> > wrapped by a List<T> object. This eliminates the unnecessary overhead of
> > List.Add().
> > - the filling of the result array stops as soon as all found items are
> > processed. If there are no matches at the end of the original list, this
> > will give an small performance win.
> > 
> > The test-run of the resulting code ran fine and it should always be
> > faster than the version in svn.
> > 
> > 
> > May I commit (with a changelog entry of course)?
> > 
> > - Juraj
> > _______________________________________________
> > Mono-list maillist  -  Mono-list at lists.ximian.com
> > http://lists.ximian.com/mailman/listinfo/mono-list
>