[Python-ideas] Ordered storage of keyword arguments

[Raymond Hettinger]

On Oct 28, 2010, at 4:52 AM, M.-A. Lemburg wrote:

> Antoine Pitrou wrote:
>> On Thu, 28 Oct 2010 11:19:36 +0200
>> spir <denis.spir at gmail.com> wrote:
>>> On Thu, 28 Oct 2010 10:13:09 +0200
>>> "M.-A. Lemburg" <mal at egenix.com> wrote:
>>> 
>>>> Ordered dicts are a lot slower than normal dictionaries. I don't
>>>> think that we can make such a change unless we want to make
>>>> Python a lot slower at the same time.
>>> 
>>> Ruby has ordered hashes since 1.9 with apparently no relevant
>>> performance loss
>> 
>> Performance would probably not suffer on micro-benchmarks (with
>> everything fitting in the CPU's L1 cache), but making dicts bigger
>> (by 66%: 5 pointer-sized fields per hash entry instead of 3) could
>> be detrimental in real life workloads.
> 
> For function calls, yes. For class creation, I doubt that a few
> extra bytes would make much difference in real life - classes typically
> don't have thousands of methods or attributes :-)

Last year, I experimented with this design (changing the dict implementation
to be ordered by adding two fields for links).   The effects are:

* The expected 66% increase in size was unavoidable for large dicts.

* For smaller dicts the link fields used indices instead of pointers
   and those indices were smaller than the existing fields (i.e. 8 bits
   per entry for tables under 256 rows, 16 bits per entry for tables under
   65k rows).

* Iteration speed improved for smaller dicts because we don't have 
   to examine empty slots (we also get to eliminate the "search
   finger" hack).  For larger dicts, results were mixed (because of the
   loss of locality of access).


Raymond