[Patches] [ python-Patches-606098 ] fast dictionary lookup by name

[noreply@sourceforge.net]

Patches item #606098, was opened at 2002-09-07 14:36
You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=305470&aid=606098&group_id=5470

Category: Build
Group: None
Status: Open
Resolution: None
Priority: 3
Submitted By: Oren Tirosh (orenti)
Assigned to: Guido van Rossum (gvanrossum)
Summary: fast dictionary lookup by name

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


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

>Comment By: Guido van Rossum (gvanrossum)
Date: 2002-12-30 17:42

Message:
Logged In: YES 
user_id=6380

New version of the patch, for current CVS.

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

Comment By: Oren Tirosh (orenti)
Date: 2002-12-30 17:05

Message:
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. 
 

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

Comment By: Guido van Rossum (gvanrossum)
Date: 2002-12-30 15:59

Message:
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.


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

Comment By: Guido van Rossum (gvanrossum)
Date: 2002-11-15 11:55

Message:
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!


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

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