[Python-ideas] Fast global cacheless lookup

[Eyal Lotem]

Hey, I had a very similar idea and implementation back in June (that
also passed all regression tests):
http://mail.python.org/pipermail/python-ideas/2007-June/000902.html

When I read Neil's mail I almost thought it was my old mail :-)

Unfortunately, when I posted my optimization, it pretty much got
ignored. Maybe I have not worded it properly.

The main difference between our implementations, if I understand
Neil's explanation correctly, is that you use direct ptrs into the
dict and notify the ptr holders of relocations.

I used a different method, where you call a new PyDict_ExportKey
method and it creates a mediating element.  The mediating element has
a fixed position so it can be dereferenced directly.  Direct access to
it is just as fast, but it may be slightly affecting dict performance.

I think a hybrid approach similar to Neil's, but with a mediating
object to represent the access to the dict and do the observing for
its user could be nicer (hell, Neil might already be doing this).

P.S: I also had a more ambitious plan, after eliminating
globals/builtins dict lookups, to use mro caches more aggressively
with this optimization and type-specialization on code objects, to
also eliminate class-side dict lookups. The user can also eliminate
instance-side dict lookupts via __slots__ - effectively allowing the
conversion of virtually _all_ namespace dict lookups in pure Python
code to be direct memory dereferences, isn't that exciting? :-)

Eyal

On Nov 22, 2007 7:07 PM, Guido van Rossum <guido at python.org> wrote:
> [Quick] The best way to post a patch is to put it in the bug tracker
> at bugs.python.org, and post a link to the issue here. The best way to
> create a patch is svn diff, assuming you started out with an anonymous
> svn checkout (see python.org/dev/) and not just with a distro
> download.
>
> Looking forward to it!
>
> --Guido
>
>
> On Nov 22, 2007 8:42 AM, Neil Toronto <ntoronto at cs.byu.edu> wrote:
> > Guido van Rossum wrote:
> > > Cool! Are you willing to show the code yet (bugs and all)?
> >
> > Sure! I stayed up all night doing it and today is Thanksgiving, so I'll
> > probably not get to it for a little while. (I know making a patch
> > shouldn't take long, but I've never done it before.) Should I post the
> > patch here or somewhere else?
> >
> > > Some questions:
> > >
> > > - what's the space & time impact for a dict with no watchers?
> >
> > I think it's almost negligible.
> >
> > Space: There are four bytes extra on every dict for a pointer to the
> > observer list. It may actually be zero or eight or more depending on
> > alignment and malloc block size - I haven't looked.
> >
> > Time: On dicts with no observers, dealloc, delitem, pop, popitem, clear,
> > and resize pass through an "if (mp->ma_entryobs_list != NULL)".
> > PyDict_New sets mp->ma_entryobs_list to NULL. Nothing else is affected.
> >
> > > - does this do anything for builtins?
> >
> > It does right now well enough to get them quickly, but setting or
> > deleting them elsewhere won't show up yet in the frame. And it doesn't
> > handle the case where __builtins__ is replaced. That'll take a little
> > doing, but just mentally - it shouldn't affect performance much.
> >
> > Anyway, that part will work properly when I'm done.
> >
> > > - could this be made to work for instance variables?
> >
> > If my brain were thinking in straight lines, maybe I'd come up with
> > something. :) I've got this fuzzy idea that it just might work. The hard
> > part may be distinguishing LOAD_ATTR applied to self from LOAD_ATTR
> > applied to something else. Hmm...
> >
> > Something to digest while I'm digesting the Real Other White Meat. :)
> >
> > > - what about exec(src, ns) where ns is a mapping but not a dict?
> >
> > Good question - I don't know, but I think it should work, at least as
> > well as it did before. If there's no observer attached to a frame, it'll
> > default to its previous behavior. Another hmm...
> >
> > Thanks for the prompt reply.
> >
> > Neil
> >
> > P.S. By the way, I'm very pleased with how clean and workable the
> > codebase is. I actually cheered at the lack of warnings. My wife
> > probably thinks I'm nuts. :D
> >
> >
> > _______________________________________________
> > Python-ideas mailing list
> > Python-ideas at python.org
> > http://mail.python.org/mailman/listinfo/python-ideas
> >
>
>
>
> --
> --Guido van Rossum (home page: http://www.python.org/~guido/)
> _______________________________________________
>
> Python-ideas mailing list
> Python-ideas at python.org
> http://mail.python.org/mailman/listinfo/python-ideas
>