Accelerate attr dict lookups

[peaker]

BPO	1739789
Nosy	@rhettinger, @pitrou
Files	dictexport.patch: The patch itself. words.py: A small benchmark based on http://www.webfast.com/~skip/python/fastpython.html

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = None
closed_at = <Date 2010-09-17.18:44:27.819>
created_at = <Date 2007-06-19.15:05:35.000>
labels = ['interpreter-core', 'performance']
title = 'Accelerate attr dict lookups'
updated_at = <Date 2010-09-17.18:44:27.818>
user = 'https://bugs.python.org/peaker'

bugs.python.org fields:

activity = <Date 2010-09-17.18:44:27.818>
actor = 'rhettinger'
assignee = 'none'
closed = True
closed_date = <Date 2010-09-17.18:44:27.819>
closer = 'rhettinger'
components = ['Interpreter Core']
creation = <Date 2007-06-19.15:05:35.000>
creator = 'peaker'
dependencies = []
files = ['8059', '8060']
hgrepos = []
issue_num = 1739789
keywords = ['patch']
message_count = 6.0
messages = ['52787', '52788', '52789', '52790', '116694', '116706']
nosy_count = 6.0
nosy_names = ['collinwinter', 'rhettinger', 'pitrou', 'peaker', 'jyasskin', 'BreamoreBoy']
pr_nums = []
priority = 'low'
resolution = 'out of date'
stage = None
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue1739789'
versions = ['Python 3.1', 'Python 2.7']

[peaker]

• Added a PyDict_ExportKey feature to dictionaries, that creates a PyObject that holds the value of the item.

• The hash table entries' top hash bit was abused to mean "is an exported entry", in which case the "value" refers to a PyDictItemObject, rather than an actual dictionary value.

• PyDict_ExportKey can then be used to access certain dictionary keys with direct access/dereference, and not by dictionary lookups.

• Slowdowns: All hash results are masked to remove the top bit, and the entries' hashes are also masked for comparison purposes. When the keys are found in the dict, the top hash bit is also consulted to see how to treat the value.

• Speedups: The LOAD_GLOBAL/STORE_GLOBAL opcodes use direct access to read/write from the globals/builtins dicts, for the keys associated with the relevant co_names.

• Results:

  • 40% speedup on the direct performance of LOAD_GLOBAL/STORE_GLOBAL instructions.
  • 5% speedup of pystones.
  • 5% speedup of a custom benchmark (attached, and based on http://www.webfast.com/~skip/python/fastpython.html)
  • 4.5% slowdown on the time it takes to run the regression tests.

• Potential future speedups enabled by this patch: Ordinary attribute lookups can be converted to a type-check (ptr comparison) followed by direct access to the type's dict (or if an mro cache dict is added for each type, to that dict), rather than a dict lookup.

Problems:

• PyDict_Clear can now fail on a memory error. Before it could only
  fail on a PyDict_Check and was a void return value. Its signature may
  have to change to reflect the newly possible memory error (and the
  dict_check error that already existed).
• I currently use co_names to determine which keys to export from the globals/builtins of the function object. co_names also includes attribute names, and not just globals, so I am wasting a bit of memory here, which may also affect caches/performance (the results may be better still).
• I do not use a freelist for the PyDictItemObject's so their
  allocation/freeing may be slower than usual.
• I no longer store a full 32-bit hash in the dict hashtable entries
  (only the low 31 bits, as I abuse the top bit), so the dict iterator
  that also yielded the hashes, used by set, now needs to recall the
  hash computation to yield those hashes. This makes the set-tests that
  count the number of hash calls fail (All other regression tests pass
  successfully).

The "Vision": Replace virtually all dict lookups for attributes with exported key direct accesses by combining the above approaches with __slots__ or per-instance specialization.

[peaker]

File Added: words.py

[pitrou]

Hi,

I'm not in a position to review the patch, but a small design suggestion: if you need to abuse a bit in the hash structure, wouldn't it be simpler to abuse the least significant bit of the (PyObject*) pointer to the value stored in the dictentry? It seems to me that on today's architectures, pointers are at least 2-byte aligned (if not 4-byte).

[peaker]

Thanks for the suggestion. I decided not to manipulate the pointer though, because it seems more dangerous, portability-wise.

Also, I have discovered a small problem with the patch (curse the build system for not rebuilding properly when things change :-) but I see no use posting it and continuing work on this patch, as it seems to generate so little interest.

[BreamoreBoy]

Is there any interest in this or can it be closed as implied in msg52790?

[rhettinger]

This was an interesting idea. Essentially, it created cell-style objects for entries in a global dict so that functions using load_global could access and update the values directly.

All dicts paid a price for this, but only module dicts would benefit. A more refined approach would be to create a custom dict type just for module globals.

Mark, you're right. The patch appears to have been abandoned and not generated interest.