[Python-Dev] Compact dict implementations (was: PEP 468

[INADA Naoki]

Now I fixed failing tests (some tests relying to underlying layout).

Before posting it to bugs.python.org, I want to confirm I have chance to
it merged.


First big problem is language spec.

If builtin dict in both of PyPy and CPython is ordered, many people
will relying it.
It will force other Python implementations to implement it for compatibility.
In other words, it may be de-facto "Python Language", even if Python
Language spec
say it's an implementation detail.

Is it OK?


Second problem is performance.

Quick benchmark on my laptop (Sorry, I don't have dedicated hardware
for long running stable
benchmarking), It reduces 3% memory usage and increase 3% cpu time.
I'll run longer benchmark in next week.
I think I can't avoid the penalty because index hashtable and (hash,
key, value) is not in
same cacheline.  (I hope my thought is wrong and there is way to optimize more.)

pybench: https://gist.github.com/methane/cfad1427d87ceff9310350e78a214880
benchmark: https://gist.github.com/methane/5eb11fdd93863813b222e795ca0bfc1f

Is it acceptable?

I have some other minor problems (e.g. How I can use 2byte integer?
Using int16_t in stdint.h
is OK?).  I'll discuss them in core-mentor ML or bugs.python.org.

Thanks
-- 
INADA Naoki  <songofacandy at gmail.com>