Why is Python so slow ?- revisited.

[Thomas Wouters]

On Wed, Jun 21, 2000 at 11:45:56AM +0000, Martijn Faassen wrote:

> > So, we have to check if range is still the same function. Which means we
> > have to look it up and compare identity -- and we've already lost any
> > advantage the cache could give us. Or we could place a marker on the
> > __builtin__ module, and invalidate the cached entry of 'range' whenver
> > 'range' is changed. But then we also have to add a marker to the global
> > namespace, because something can *add* a range there.

> You could do some analysis of local and global namespace, and see 
> that it is possible that 'range' is altered. If such a possibility
> exists at all (assignment to the name, or by from import), then range
> is simply never cached at all.

But how do you see, at compiletime, that *a user* of the code we are busy
compiling, will or wont change the global dictionary ? For instance:

import spam
def myrange(x):
    # insert funcky new range() for the purpose of debugging or such here
spam.range = myrange

You'd have to check at each compile which namespaces are assigned to, and
make sure, at runtime, those namespaces are not somehow optimized.

> If 'from module import *' is used, the user deserves what they
> asked for and *nothing* in that module is cached. I'm not sure
> how 'exec' can be used to screw things up, but let's say we can apply
> the same rule to that. Though that is possibly more tricky..

Take a look at the current translation from (LOAD|DELETE|STORE)_NAME
bytecodes to *_FAST and *_GLOBAL bytecodes. If the current namespace isn't
being changed dynamically (which you can determine, at compile time, for
*local* namespaces) the compiler can determine which name-lookups are going
to be local, and which are going to be global (if they do not fail).

However, there are two ways to alter a local namespace (one that isn't
global in some way, in any case): by using 'from <module> import *', and
by using 'exec'. Imagine 'exec "def range(...): ... "'. This adds 'range' to
the local namespace. 

It isn't tricky, though, the code for that is already there :)

> Something along the lines of this approach could work, I think? The
> approach would be to forbid the caching of certain names if it's
> detected certain things could happen to them that would make them
> uncachable.

These trick would work, yes, the question is: will they work enough? Will
they actually be more efficient than just trying the code ? Or will we be
special-casing so much circumstances that we'll end up optimizing a very
small percentage of code, at the cost of a much higher compile time and a
much more complicated compiler ?

> > Also, we need a way to invalidate the cached entry of egg.spam if any of egg or
> > any of its parent up to the one defining 'spam', have something done to
> > their 'spam' attribute.

> If the possibility exist that a method is changed, don't cache that
> method. Of course setattr() will be a major problem; very hard to determine
> whether setattr() won't affect some class at some point. And you won't
> know what class, or what name. Hmm.

Exactly :) Also, don't forget the fact that another module can change stuff
on an object, or an *exec* in another module (!) can change stuff on an
object, as long as that module has in some way access to the object, however
indirectly.

> > And that means than whenever you change an attribute
> > on a class or instance, you need to traverse the entire tree of subclasses
> > and instances (up to one that 'masks' the change) looking for cached entries
> > and invalidating them.

> Far cheaper would be simply to invalidate the entire cache in such
> a case. That is, if class attributes are changed. I'm not sure why
> you'd need to invalidate things when you change something on an instance,
> though? (except the thing that's changed itself)

That's what I meant. I said 'instances' because a single object can have a
lot of subclasses & instances, and *each of those* can have 'cached
entries'. We're not talking about optimizing a single instance, we're
talking about the whole can of worms.

> > And of course, if you do something like:
> 
> >   egg.ham.viking.spam.plate.drop()
> 
> > you have to consider *each lookup* cached ;-P I don't think lookups are
> > *that* expensive. I'm not sure what the penalty for a failed lookup is, I
> > seem to recall something about a successful lookup being relatively cheap,
> > compared to a failed one, and a 2nd lookup is not likely to fail ;)
> 
> I don't seem to understand this bit. What does it mean, considering
> each lookup cached? Could you explain?

The lookup of 'egg' in the local or global namespace, the lookup of 'ham' in
the namespace 'egg', the lookup of 'viking' in the namespace 'ham',
etcetera.

> I think you need the ideas of invalidation. I think you also need the
> idea of "don't ever cache this" (or at least "don't cache this until I
> tell you to"). I think that approach can help with some of the tricky bits.

Oh definately. I'm just not very sure there'll be enough non-tricky bits
left to actually matter ;)

Perhaps-we-should-discuss-this-over-a-beer-somewhere-in-Amsterdam-Martijn'ly
yr's, Thomas

(Though not during Euro2000, please)

-- 
Thomas Wouters <thomas at xs4all.net>

Hi! I'm a .signature virus! copy me into your .signature file to help me spread!