[Python-ideas] Ordered storage of keyword arguments
raymond.hettinger at gmail.com
Thu Oct 28 20:10:24 CEST 2010
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
* 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).
More information about the Python-ideas