[Python-Dev] A new dictionary implementation

[Mark Shannon]

Hi,

Version 2 is now available.

Version 2 makes as few changes to tunable constants as possible, and 
generally does not change iteration order (so repr() is unchanged).
All tests pass (the only changes to tests are for sys.getsizeof() ).

Repository: https://bitbucket.org/markshannon/cpython_new_dict
Issue http://bugs.python.org/issue13903

Performance changes are basically zero for non-OO code.
Average -0.5% speed change on 2n3 benchamrks, a few benchmarks show
a small reduction in memory use. (see notes below)

GCbench uses 47% less memory and is 12% faster.
2to3, which seems to be the only "realistic" benchmark that runs on Py3,
shows no change in speed and uses 10% less memory.

All benchmarks and tests performed on old, slow 32bit machine
with linux.
Do please try it on your machine(s).

If accepted, the new dict implementation will allow a useful 
optimisation of the LOAD_GLOBAL (and possibly LOAD_ATTR) bytecode:
By testing to see if the (immutable) keys-tables is the expected table,
the value can accessed directly by index, rather than by name.

Cheers,
Mark.


Notes:
All benchmarks from http://hg.python.org/benchmarks/
using the -m flag to get memory usage data.

I've ignored the json benchmarks which shows unstable behaviour
on my machine.
Tiny changes to the dict being serialized or to the random seed can 
change the relative speed of my implementation vs CPython from -25% to +10%.