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