[Python-Dev] Temporary Constantification

[Guido van Rossum]

On 6/25/06, Eric Sumner <kd5bjo at gmail.com> wrote:
> It seems to me that the main reason to provide constantification (in a
> switch statement or anywhere else) is to be able to optimize execution
> by caching the result locally for later use.  The problem comes from
> trying to determine exactly when and how a value gets calculated, as
> most values in Python are subject to change.

Actually, most values tend *not* to change -- it's just hard for the
compiler to prove this to so that it can use that fact.

For example, in practice, builtins don't change. Imported objects
(modules, and things you import from modules like constants, functions
and classes) don't change. Defined functions and classes don't change.
Manifest constants don't change. (*In practice*, you should add in all
cases.)

> If, however, there was a mechanism by which a cache could be
> invalidated when its value changes, the only remaining difference
> between cached and non-cached values becomes their execution speed and
> memory usage (and possibly impact on the execution speed of other
> code).  Thus, I propose a 'cached' keyword much like the static and
> const proposed keywords.

In all (or nearly all) the use cases that were considered so far, the
problem is more that the programmer knows that a certain expression
isn't going to change, but the compiler doesn't.

The problem is more that we'd like to be told (preferably at compile
time -- but runtime is better than not at all) if we assume that
something is a constant where in fact it is subject to change.

> In general, a cached value can be used (rather than re-evaluating the
> expression) if:
>   - The expression has no side effects,
>   - The result of all operations is deterministic, and
>   - None of the expression parameters have changed since the cached
> value was generated
>
> The first two can be determined at compile-time without too much
> difficulty (except possibly function calls, I'll get to those in a
> minute).  The hard issue here is knowing when parameters have changed.
>  These fall into two different categories: literals and name lookups.
> Immutable literals don't cause a problem, and mutable literals always
> have a side-effect of generating a new object.  There are two ways to
> determine if name lookups have changed:
>   1) Cache all the parameters, and check them against the current values, or
>   2) Be notified whenever one of the parameters changes.
>
> The first option requires a bunch of name lookups whenever the cached
> value is considered, which is exactly the problem that caching is
> supposed to fix.  To implement the second, each name in each namespace
> needs a list of caches that depend on the name, and all name binding
> operations need to check the list and mark all dependent caches
> invalid.  This is a small performance penalty whenever any name is
> rebound, and a large penalty whenever a watched name is rebound.
>
> Function calls can safely be considered volatile, but this would
> invalidate many of the uses for caching.  Instead, each function has
> an immutable property of being either volatile or deterministic.  Each
> deterministic function call maintains its own cache which is
> invalidated if  the name to which the associated function (or any of
> its parameters) is rebound.  Thus, if a function is rebound to
> something volatile, it does not force continual re-evaluation of other
> sub-expressions.  Functions should be assumed to be volatile unless
> specified otherwise (probably via a decorator).
>
> I'm not particularly familiar with the internals of Python, so I'm not
> able to actually assess the feasability or performance implications of
> this proposal, but I think it basically covers the problem.

Unfortunately, a mechanism that would let you register a callback for
when a particular variable or attribute used in a cached expression is
used, is pretty hard to implement without affecting the performance of
code that doesn't use it. I'm afraid this is not a very likely path
towards a solution.

-- 
--Guido van Rossum (home page: http://www.python.org/~guido/)