[Python-ideas] Ordered storage of keyword arguments

[geremy condra]

On Thu, Oct 28, 2010 at 11:10 AM, Raymond Hettinger
<raymond.hettinger at gmail.com> wrote:
>
> 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

Is this available somewhere? I'd like to play around with this for a bit.

Geremy Condra