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

[Josiah Carlson]

"Eyal Lotem" <eyal.lotem at gmail.com> wrote:
> On 6/10/07, Josiah Carlson <jcarlson at uci.edu> wrote:
> > "Eyal Lotem" <eyal.lotem at gmail.com> wrote:
> > > 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).
> >
> > [snip]
> >
> > What you are proposing is to add a level of indirection between some
> > pointer in the dictionary to some special PyDictItem object. This will
> > slow Python execution when such a thing is used.  Why? The extra level
> > of indirection requires another pointer following, as well as a
> > necessary check on the bitmap you are proposing, nevermind the
> > additional memory overhead of having the item (generally doubling the
> > size of dictionary objects that use such 'exported' items).
> >
> > You don't mention what algorithm/structure will allow for the accessing
> > of your dictionary items in O(1) time, only that after you have this
> > bitmap and dictioanry item thingy that it will be O(1) time (where
> > dictionaries weren't already fast enough natively). I don't believe you
> > have fully thought through this, but feel free to post C or Python
> > source that describes your algorithm in detail to prove me wrong.
> 
> Only access of exported items is O(1) time (when accessed via your
> PyDictItem_obj->value), other items must be accessed normally and they
> take just as much time (or as I explained and you reiterated, a tad
> longer, as it requires a bitmap check and in the case of exported
> items another dereference).

But you still don't explain *how* these exported keys are going to be
accessed.  Walk me through the steps required to improve access times in
the following case:

def foo(obj):
    return obj.foo


> > You should note that Python's dictionary implementation has been tuned
> > to work *quite well* for the object attribute/namespace case, and I
> > would be quite surprised if anyone managed to improve upon Raymond's
> > work (without writing platform-specific assembly).
> 
> Ofcourse - the idea is not to improve dict's performance with the
> normal way it is accessed, but to change the way it is accessed for
> the specific use-case of accessing static values in a static dict -
> which can be faster than even a fast dict lookup.

If I have a dictionary X, and X has exported keys, then whenever I
access exported values in the dictionary via X[key], your proposed
indirection will necessarily be slower than the current implementation.


> The dict lookups in globals, builtins are all looking for literal
> static keys in a literal static dict. In this specific case, it is
> better to outdo the existing dict performance, by adding a special way
> to access such static keys in dicts - which insignificantly slows down
> access to the dict, but significantly speeds up this very common use
> pattern.

Please benchmark before you claim "insignificant" performance
degredation in the general case. I claim that adding a level of
indirection and the accessing of a bit array (which in C is technically
a char array with every bit getting a full char, unless you use masks
and shifts, which will be slower still) is necessarily slower than the
access characteristics of current dictionaries.  We can see this as a
combination of an increase in the number of operations necessary to do
arbitrary dictionary lookups, increased cache overhad of those lookups,
as well as the delay and cache overhead of accessing the bit array.


> Attribute lookups in the class dict are all literal/static key lookups
> in a static dict (though in order for a code object to know that it is
> a static dict, a psyco-like system is required. If such a system is
> used, all of those dict lookups can be made faster as well).

No, attribute lookups are not all literal/static key lookups.  See
getattr/setattr/delattr, operations on cls.__dict__, obj.__dict__, etc.

From what I can gather (please describe the algorithm now that I have
asked twice), the only place where there exists improvement potential is
in the case of global lookups in a module.  That is to say, if a
function/method in module foo is accessing some global variable bar, the
compiler can replace LOAD_GLOBAL/STORE_GLOBAL/DEL_GLOBAL with an opcode
to access a special PyDictItem object that sits in the function/method
cell variables, rather than having to look in the globals dictionary
(that is attached to every function and method).


 - Josiah