[Python-ideas] Ordered storage of keyword arguments (original) (raw)
Raymond Hettinger raymond.hettinger at gmail.com
Thu Oct 28 20:10:24 CEST 2010
- Previous message: [Python-ideas] Ordered storage of keyword arguments
- Next message: [Python-ideas] Ordered storage of keyword arguments
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
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
- Previous message: [Python-ideas] Ordered storage of keyword arguments
- Next message: [Python-ideas] Ordered storage of keyword arguments
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]