[Patches] [ python-Patches-1739789 ] Accelerate attr dict lookups

[SourceForge.net]

Patches item #1739789, was opened at 2007-06-19 17:05
Message generated for change (Comment added) made by pitrou
You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=305470&aid=1739789&group_id=5470

Please note that this message will contain a full copy of the comment thread,
including the initial issue submission, for this request,
not just the latest update.
Category: Core (C code)
Group: Python 2.6
Status: Open
Resolution: None
Priority: 5
Private: No
Submitted By: Eyal Lotem (peaker)
Assigned to: Nobody/Anonymous (nobody)
Summary: Accelerate attr dict lookups

Initial Comment:
* 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.


----------------------------------------------------------------------

Comment By: Antoine Pitrou (pitrou)
Date: 2007-06-24 22:17

Message:
Logged In: YES 
user_id=133955
Originator: NO

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).



----------------------------------------------------------------------

Comment By: Eyal Lotem (peaker)
Date: 2007-06-19 17:06

Message:
Logged In: YES 
user_id=231480
Originator: YES

File Added: words.py

----------------------------------------------------------------------

You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=305470&aid=1739789&group_id=5470