[Python-ideas] Exporting dict Items for direct lookups of specific keys

[Eyal Lotem]

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.