Issue 606098: fast dictionary lookup by name (original) (raw)

This issue has been migrated to GitHub: https://github.com/python/cpython/issues/37144

classification

process

Created on 2002-09-07 18:36 by orenti, last changed 2022-04-10 16:05 by admin. This issue is now closed.

Messages (6)
msg41113 - (view)	Author: Oren Tirosh (orenti)	Date: 2002-09-07 18:36
This patch speeds up dictionary lookup when the key is an interned string. Test results (Guido's tar from patch #597907) Before: builtin 2.01 global 1.57 local 1.87 fastlocal 1.02 After: builtin 1.78 global 1.63 local 1.51 fastlocal 1.06 Not as impressive as the last patch because this version doesn't use the inline macro yet. A dummy/negative entry is now defined as me_key != NULL and me_value == NULL. A dummy entry also has me_hash set to -1 to shave a few more cycles in the search. Management of negative entries and the interaction with table resizing still needs more work. If there is not enough room for a new negative entry it is simply ignored. The bottlneck appears to be the first negative lookup. It starts with a fast search that fails and then falls back to a slow search and inserts a negative entry. This path is significantly slower than without the patch. Subsequent lookups will be much faster but many objects are created where attributes or methods are looked up just once. The solution I am considering is to change lookdict_string to lookdict_interned. A dictionary in this state has only interned string keys so the fast search is guaranteed to produce the correct result if the lookup key is also an interned string with no fallback required. This should also make it easier to speed up PyDict_SetItem.
msg41114 - (view)	Author: Guido van Rossum (gvanrossum) *	Date: 2002-11-15 16:55
Logged In: YES user_id=6380 Assigned to me because it may relate to patch 597907. But I have no time to sort through this, and it seems Oren's priorities lie elsewhere. If someone can help out, please do!
msg41115 - (view)	Author: Guido van Rossum (gvanrossum) *	Date: 2002-12-30 20:59
Logged In: YES user_id=6380 I don't see any improvement with pystone. That doesn't mean much, but it means I'm not going to do this before releasing 2.3a1.
msg41116 - (view)	Author: Oren Tirosh (orenti)	Date: 2002-12-30 22:05
Logged In: YES user_id=562624 According to my instrumented version pystone was something like 97.8% fastlocal lookups. I'm afraid I won't be able to continue my work on this patch any time soon. If anyone wants to take over I'll be happy to help.
msg41117 - (view)	Author: Guido van Rossum (gvanrossum) *	Date: 2002-12-30 22:42
Logged In: YES user_id=6380 New version of the patch, for current CVS.
msg41118 - (view)	Author: Raymond Hettinger (rhettinger) *	Date: 2004-12-20 03:22
Logged In: YES user_id=80475 Most of the benefits of this patch were already obtained by the newer dict resizing scheme (quarupling size instead of doubling) which made both successful and unsuccessful lookups go faster. Closing this until new research efforts show that additional improvements are possible.