AA dsource project

[dsimcha]

== Quote from Moritz Warning (moritzwarning at web.de)'s article
> On Wed, 04 Nov 2009 20:53:20 +0000, dsimcha wrote:
> > A few weeks ago I mentioned that I was going to create some kind of
> > forum for people to post candidate associative array implementations to
> > replace the current, much-despised implementation as the new "builtin"
> > AA for D.  It's now up at http://dsource.org/projects/aa/wiki/WikiStart
> > .  SVN write access should work for all registered dsource users.  If
> > you have an associative array implementation that you feel is a
> > significant improvement over the current builtin and are able/willing to
> > license it under the Boost license, please post it for comment.
> >
> > Also, if you have a good benchmark for AAs, please create a benchmarks/
> > directory and submit it.
> I've committed a port of Pythons dictionary implementation.
> Here is my announcement along with some benchmark figures:
> http://digitalmars.com/d/archives/digitalmars/D/
> Python_dictionary_inspired_hash_table_implementation_73176.html

Nice job.  I ported your code to D2, (quick and dirty, doesn't work right with
const and all, just enough to be able to test it), and uploaded that version for
D2 users.  I had in the back of my mind that this was to be D2-centric, but I
guess D1 could easily get better AAs, too, since it wouldn't affect the spec.

I couldn't find your benchmarks, but here are my results:

Builtin:
Start Benchmark.
1 x 10000000 iterations
inserts:  394601/s (25.342000s)
lookups: 9813542/s (1.019000s)

PyDict:
Start Benchmark.
1 x 10000000 iterations
inserts:  2044153/s (4.892000s)
lookups: 3401360/s (2.940000s)

This pretty much confirms my suspicion that the builtin AAs are optimized for
lookup speed at the expense of insertion speed/GC overhead to an absurd degree.

Also, regarding the license for Python's dictionary, apparently the Python License
doesn't allow removing of copyright notices from stuff distributed in binary form.
 This might prove problematic if this were to be integrated into druntime.