Speeding up name lookups
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
participants (4)
-
aahz@rahul.net
-
M.-A. Lemburg
-
Oren Tirosh
-
Tim Peters