This issue tracker has been migrated to GitHub, and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

classification
Title: fast dictionary lookup by name
Type: Stage:
Components: Build Versions:
process
Status: closed Resolution: out of date
Dependencies: Superseder:
Assigned To: gvanrossum Nosy List: gvanrossum, orenti, rhettinger
Priority: low Keywords: patch

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

Files
File name Uploaded Description Edit
fastnames5.patch orenti, 2002-09-07 18:36
fastnames5a.patch gvanrossum, 2002-12-30 22:42 GvR's version for current CVS as of 12/30/02
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) * (Python committer) 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) * (Python committer) 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) * (Python committer) 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) * (Python committer) 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.
History
Date User Action Args
2022-04-10 16:05:39adminsetgithub: 37144
2002-09-07 18:36:54orenticreate