[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:
> > > On 6/10/07, Josiah Carlson <jcarlson at uci.edu> wrote:
> > > 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
> >
> >
> I think you missed what I said - I said that the functionality should
> probably not be exported to Python - as Python has little to gain from
> it (it would have to getattr a C method just to request the exported
> item -- which will nullify the speed benefit).
> 
> It is the C code which can suddenly do direct access to access the
> exported dict items - not Python code.

Maybe my exposure to C extensions is limited, but I haven't seen a whole
lot of C doing the equivalent of obj.attrname outside of the Python
standard library. And even then, it's not "I'm going to access attribute
Y of object X a million times", it's "I'm going to access some
attributes on some objects".  The only exception that I've seen happen
really at all is when someone converts their pure Python library that
interacts with other libraries into Pyrex.  But even then, repeated
access is generally uncommon except in wxPython uses; wx.<attrname>
(which I've never seen converted to Pyrex), and in those cases, repeated
access is generally rare.

I'm curious as to what kind of C code you are seeing in which these
cached lookups will help in a substantial way.


> > 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.
> 
> That is true, I acknowledged that. It is even true also that access to
> X[key] even when key is not exported is slower.  When I have a few
> spare moments, I'll try and benchmark how much slower it is.

I await your benchmarks.


> > > 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.
> 
> I may have oversimplified a bit for the sake of explaining.  I was
> referring to the operations that are taken by LOAD_ATTR, as an
> example.
> Lets analyze the LOAD_ATTR bytecode instruction:
>  * Calls PyObject_GetAttr for the requested attribute name on the
> request object.
>  * PyObject_GetAttr redirects it to the type's tp_getattr[o].
>  * When tp_getattr[o] is not overridden, this calls PyObject_GenericGetAttr.
>  * PyObject_GenericGetAttr first looks for a method descriptor in
> dicts of every class in the entire __mro__. If it found a
> getter/setter descriptor, it uses that. If it didn't, it tries the
> instance dict, and then uses the class descriptor/attr.
> 
> I believe this implementation to be very wasteful (specifically the
> last step) and I have posted a separate post about this in python-dev.

Due to the lack of support on the issue in python-dev (it would break
currently existing code, and the time for Python 3.0 PEPs is past), I
doubt you are going to get any changes in this area unless the resulting
semantics are unchanged.


> Since a "static lookup" costs a dereference and a conditional, and a
> dynamic lookup entails at least 4 C function calls (including C stack
> setup/unwinds), a few C assignments and C conditionals, I believe it
> is likely that this will pay off as a serious improvement in Python's
> performance, when combined with a psyco-like system (not an
> architecture-dependent ones).

It's really only useful if you are accessing fixed attributes of a fixed
object many times.  The only case I can think of where this kind of
thing would be useful (sufficient accesses to make a positive difference)
is in the case of module globals, but in that case, we can merely change
how module globals are implemented (more or less like self.__dict__ = ...
in the module's __init__ method).


> > 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).
> 
> As I explained above, there is room for improvement in normal
> attribute lookups, however that improvement requires a psyco-like
> system in order to be able to deduce which dicts are going to be
> accessed by the GetAttr mechanism and then using static lookups to
> access them directly.

Insights into a practical method of such optimizations are not leaping
forth from my brain (aside from using a probabilistic tracking mechanism
to minimize overhead), though my experience with JIT compilers is
limited.  Maybe someone else has a good method (though I suspect that
this particular problem is hard enough to make it not practical to make
it into Python).


> With access to globals and builtins, this optimization is indeed
> easier, and your description is correct, I can be a little more
> specific:
> * Each code object can contain a "co_globals_dict_items" and
> "co_builtins_dict_items" attributes that refer to the
> exported-dict-items for that literal name in both the globals and
> builtins dict.
>
> * Each access to a literal name in the globals/builtins namespace, at
> the compilation stage, will request the globals dict and builtins dict
> to create an exported item for that literal name. This exported item
> will be put into the co_globals_dict_items/co_builtins_dict_items in
> the code object.
> 
> * LOAD_GLOBAL will not be used when literal name are accessed.
> Instead, a new bytecode instruction "LOAD_LITERAL_GLOBAL" with an
> index to the "co_globals_dict_items/co_builtins_dict_items" tuples in
> the code object.

You may want to change the name.  "Literal" implies a constant, like 1
or "hello", as in 'x = "hello"'.  LOAD_GLOBAL_FAST would seem to make
more sense to me, considering that is what it intends to do.


 - Josiah