I believe that it is possible to add a useful feature to dicts, that will enable some interesting performance features in the future.
Dict lookups are in general supposed to be O(1) and they are indeed very fast. However, there are several drawbacks: A. O(1) is not always achieved, collisions may still occur B. Some lookups use static "literal" keys, and could benefit from accessing a dict item directly (very fast O(1) _worst_ case, without even a function call when done from the C side). C. B is especially true when dicts are used to hold attributes - in that case literal attribute names, in conjunction with psyco-like type specialization, can help avoid many dict lookups. I won't delve into this in this mail - but this is actually the use-case that I'm after optimizing.
There is a possible implementation that can allow a dict to export items with minimal impact on its other performance.
Create a new type of PyObject, a PyDictItemObject that will contain a key, value pair. (This will NOT exist for each hash table entry, but only for specifically exported items).
Add a bitmap to dicts that has a single bit for every hash table entry. If the entry is marked in the bitmap, then its PyObject* "value" is not a reference to the value object, but to a PyDictItemObject.
A new dict method "PyDict_ExportItem" that takes a single argument: key will create a PyDictItemObject, and assign the dict's key to it, and mark that hash-table entry in the bitmap. If PyDict_ExportItem is called when the item is already exported, it will return another reference to the same PyDictItemObject. The value in PyDictItemObject will initially be set to NULL (which means "key not mapped"). Both the PyDictItemObject and PyDict_exportitem should probably not be exported to the Python-side, but PyDictItemObject should probably be a PyObject for refcounting purposes.
All the dict methods to get/set values, once they found the correct entry, check the bitmap to see if the entry is marked, and if it is - access the value in the PyDictItemObject instead of the value itself. In addition, if that value is NULL, it represents the key not actually being in the dict (__getitem__ can raise a KeyError there, for example, and __setitem__ can simply use Py_XDECREF and overwrite value with the value).
Alternatively to the bitmap, the hash table entry can contain another boolean int -- I am not sure which is preferable in terms of cache-locality, but the bitmap is definitely cheaper, space-wise.
This would allow dict users to create an exported item for a key once, and then access that key in real O(1) without function calls. As mentioned before, this can also serve in the future, as the basis for avoiding dict lookups for attribute searches.