[Python-Dev] Temporary Constantification
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. 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 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. -- Eric Sumner ___ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [Python-Dev] Temporary Constantification
On Sun, Jun 25, 2006, Eric Sumner wrote: 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). Except for properties. So you'd have to allow only bare names, no attributes. You'd also have to restrict values to immutable ones. -- Aahz ([EMAIL PROTECTED]) * http://www.pythoncraft.com/ I saw `cout' being shifted Hello world times to the left and stopped right there. --Steve Gonedes ___ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [Python-Dev] Temporary Constantification
On 6/25/06, Eric Sumner [EMAIL PROTECTED] 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/) ___ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [Python-Dev] Temporary Constantification
On 6/25/06, Guido van Rossum [EMAIL PROTECTED] wrote: 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. I could make a strong argument that it is actually impossible to implement without affecting the performance of other code; the only issue is whether or not the impact is acceptable. I may be wrong, but I think that this particular scheme minimizes the impact: - There is a bit more data to store in every namespace - There is no change to dereferencing names; no test is required, no callback is generated - Binding to a name that currently has no binding simply requires allocating the extra memory and clearing it. - Binding to a name that is bound and does have callbacks is slow, but those are supposed to be constant *in practice* anyway. - Binding to a name that is already bound, but has no callbacks requires a test on a single variable against a constant. Without knowing more about the internals of Python (such as how long a check of a single variable takes relative to binding a new value to a name), I can't properly evaluate how much of a problem this would be. -- Eric Sumner ___ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [Python-Dev] Temporary Constantification
On 6/25/06, Eric Sumner [EMAIL PROTECTED] wrote: On 6/25/06, Guido van Rossum [EMAIL PROTECTED] wrote: 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. I could make a strong argument that it is actually impossible to implement without affecting the performance of other code; the only issue is whether or not the impact is acceptable. I may be wrong, but I think that this particular scheme minimizes the impact: - There is a bit more data to store in every namespace - There is no change to dereferencing names; no test is required, no callback is generated - Binding to a name that currently has no binding simply requires allocating the extra memory and clearing it. - Binding to a name that is bound and does have callbacks is slow, but those are supposed to be constant *in practice* anyway. - Binding to a name that is already bound, but has no callbacks requires a test on a single variable against a constant. Without knowing more about the internals of Python (such as how long a check of a single variable takes relative to binding a new value to a name), I can't properly evaluate how much of a problem this would be. Your proposal would require a change to the dict type to set a callback to be called when a particular key is modified (not a generic callback when any key is modified). That seems pretty tricky to do with no impact, given how highly dicts are optimized. Also, allowing attribute references is a whole new can of worms, since attributes aren't necessarily implemented as standard namespaces implemented by dictionaries. Aahz already pointed this out. -- --Guido van Rossum (home page: http://www.python.org/~guido/) ___ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
