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.

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!

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.

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. 
 

Logged In: YES 
user_id=6380

New version of the patch, for current CVS.

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.