[Python-Dev] Speeding up name lookups

[Oren Tirosh]

Step 1.  Define name type

The type 'name' looks and behaves just like a string.  Internally, it 
contains a reference to a string, a pointer to a dictionary (nm_dict) and 
an integer (nm_index).  The field nm_dict points to a dictionary where this
name is used as a key. nm_index is the index into the hash table of the
specific dictentry where this name is a key.  The validity of this cached 
data is verified before using it.


Step 2. Convert co_names to names

When initializing a code object the co_names tuple is converted from strings
to names.  A new name object is always allocated for each item in co_names 
even if the string it contains was already interned somewhere else.


Step 3. PyDict_GetItem_ByName

This function should be used instead of PyDict_GetItem where lookups are 
guaranteed to be performed with name objects as keys and performance is 
critical: LOAD_NAME and LOAD_GLOBAL in eval_frame.  It may be inlined.

PyObject *
PyDict_GetItem_ByName(PyObject *op, PyObject *key)
{
	dictobject *mp = (dictobject *)op;
        nameobject *nm = (nameobject *)key;
	dictentry *ep;

        if (nm->nm_dict == mp) {
		ep = &(op->ma_table[nm->nm_index & op->ma_mask ]);
		if (ep->me_key == key)
			return ep->me_value;
	}
        return PyDict_GetItem(op,key);
}

Step 4. modify PyDict_GetItem 

The above function takes care of cache hits.  When a cache miss occurs the 
regular PyDict_GetItem should check whether the key is a name and 
initialize nm_dict and nm_index for subsequent lookups.


Step 5. PyDict_SetItem_ByName

Similar to PyDict_GetItem_ByName.  A cache hit means that the key was 
already in the dictionary and only the associated value is modified.
Creating new keys and other cache misses are handled by PyDict_SetItem.
Should be used in STORE_NAME and STORE_GLOBAL.


Step 6. modify PyDict_SetItem

Initialize cache inside name objects for fast lookups by name.


This appears to be a low-risk modification because it affects only a small
part of the code and the cache validity is always verified.  

It has a slight performance impact on the speed of the regular GetItem and 
SetItem because they need to check if their key is a name and initialize the 
cache inside the name object.  This should be more than offset by the 
improvement in name lookup speed.  This may be corrected by adding a third 
lookup method in addition to lookdict and lookdict_string.

It is possible to speed up PyDict_GetItem_ByName even further by caching the
value instead of the hash table index:

PyObject *
PyDict_GetItem_ByName(PyObject *op, PyObject *key)
{
        nameobject *nm = (nameobject *)key;
        if (nm->nm_dict == op) 
	   return nm->nm_value;
	else
          return PyDict_GetItem(op,key);
}

The penalty is that GetItem and SetItem will need to carefully invalidate or 
update the cached values inside name objects because the fast lookup function
cannot verify validity.  This also doesn't handle SetItem so the table index 
will need to be stored inside the name object as well.


I'd like to hear what you think about this proposal.  I believe it should
address many of the issues that PEP 266 and PEP 267 were trying to solve.

In which cases will the cached values be thrashed by two dictionaries that
use the same name as a key?  

	Oren Tirosh