# HG changeset patch # User Paul Boddie # Date 1255132347 -7200 # Node ID d395dfacb98db11a36333041ab6ab2a193602357 # Parent 5ad00ae3d24d9a15dc6df49161f505fd5e18bdb6 Moved optimisation discussions into the appropriate document. Added more general introductory documentation. diff -r 5ad00ae3d24d -r d395dfacb98d README.txt --- a/README.txt Wed Sep 30 00:53:07 2009 +0200 +++ b/README.txt Sat Oct 10 01:52:27 2009 +0200 @@ -1,227 +1,51 @@ -Optimisations -============= - -Some optimisations around constant objects might be possible; these depend on -the following: - - * Reliable tracking of assignments: where assignment operations occur, the - target of the assignment should be determined if any hope of optimisation - is to be maintained. Where no guarantees can be made about the target of - an assignment, no assignment-related information should be written to - potential targets. - - * Objects acting as "containers" of attributes must be regarded as "safe": - where assignments are recorded as occurring on an attribute, it must be - guaranteed that no other unforeseen ways exist to assign to such - attributes. - -The discussion below presents certain rules which must be imposed to uphold -the above requirements. - -Safe Containers ---------------- +Introduction +------------ -Where attributes of modules, classes and instances are only set once and are -effectively constant, it should be possible to circumvent the attribute lookup -mechanism and to directly reference the attribute value. This technique may -only be considered applicable for the following "container" objects, subject -to the noted constraints: - - 1. For modules, "safety" is enforced by ensuring that assignments to module - attributes are only permitted within the module itself either at the - top-level or via names declared as globals. Thus, the following would not - be permitted: - - another_module.this_module.attr = value - - In the above, this_module is a reference to the current module. - - 2. For classes, "safety" is enforced by ensuring that assignments to class - attributes are only permitted within the class definition, outside - methods. This would mean that classes would be "sealed" at definition time - (like functions). - -Unlike the property of function locals that they may only sensibly be accessed -within the function in which they reside, these cases demand additional -controls or assumptions on or about access to the stored data. Meanwhile, it -would be difficult to detect eligible attributes on arbitrary instances due to -the need for some kind of type inference or abstract execution. - -Constant Attributes -------------------- +Micropython is a language environment incorporating a compiler for a +simplified version of the Python programming language which targets a simple +instruction set supported by a virtual machine known as RSVP (a Really Simple +Virtual Processor). -When accessed via "safe containers", as described above, any attribute with -only one recorded assignment on it can be considered a constant attribute and -this eligible for optimisation, the consequence of which would be the -replacement of a LoadAttrIndex instruction (which needs to look up an -attribute using the run-time details of the "container" and the compile-time -details of the attribute) with a LoadAttr instruction. - -However, some restrictions exist on assignment operations which may be -regarded to cause only one assignment in the lifetime of a program: - - 1. For module attributes, only assignments at the top-level outside loop - statements can be reliably assumed to cause only a single assignment. +The RSVP instruction set is intended to map relatively closely to instructions +employed by real processors, with only a few "macroinstructions" which would +probably be implemented as short macros or library routines in programs +translated to the instruction set of a real target processor. - 2. For class attributes, only assignments at the top-level within class - definitions and outside loop statements can be reliably assumed to cause - only a single assignment. - -All assignments satisfying the "safe container" requirements, but not the -requirements immediately above, should each be recorded as causing at least -one assignment. - -Additional Controls -------------------- - -For the above cases for "container" objects, the following controls would need -to apply: +Quick Start +----------- - 1. Modules would need to be immutable after initialisation. However, during - initialisation, there remains a possibility of another module attempting - to access the original module. For example, if ppp/__init__.py contained - the following... - - x = 1 - import ppp.qqq - print x - - ...and if ppp/qqq.py contained the following... - - import ppp - ppp.x = 2 +Currently, the test.py program is the principal means of compiling and running +code. For example, to inspect the logical.py test program... - ...then the value 2 would be printed. Since modules are objects which are - registered globally in a program, it would be possible to set attributes - in the above way. + python -i test.py tests/logical.py -m - 2. Classes would need to be immutable after initialisation. However, since - classes are objects, any reference to a class after initialisation could - be used to set attributes on the class. - -Solutions: - - 1. Insist on global scope for module attribute assignments. - - 2. Insist on local scope within classes. +...will provide a number of objects which can then be inspected, notably the +rm (RSVP machine) object which provides the following methods: -Both of the above measures need to be enforced at run-time, since an arbitrary -attribute assignment could be attempted on any kind of object, yet to uphold -the properties of "safe containers", attempts to change attributes of such -objects should be denied. Since foreseen attribute assignment operations have -certain properties detectable at compile-time, it could be appropriate to -generate special instructions (or modified instructions) during the -initialisation of modules and classes for such foreseen assignments, whilst -employing normal attribute assignment operations in all other cases. Indeed, -the StoreAttr instruction, which is used to set attributes in "safe -containers" would be used exclusively for this purpose; the StoreAttrIndex -instruction would be used exclusively for all other attribute assignments. - -To ensure the "sealing" of modules and classes, entries in the attribute -lookup table would encode whether a class or module is being accessed, so -that the StoreAttrIndex instruction could reject such accesses. - -Constant Attribute Values -------------------------- - -Where an attribute value is itself regarded as constant, is a "safe container" -and is used in an operation accessing its own attributes, the value can be -directly inspected for optimisations or employed in the generated code. For -the attribute values themselves, only objects of a constant nature may be -considered suitable for this particular optimisation: + * show - reveals the contents of the machine's memory + * run - starts execution of the code in the memory + * step - steps through the code one instruction at a time + * dump - shows the machine's registers - * Classes - * Modules - * Instances defined as constant literals +To run a test and check the output, specify the -t option: -This is because arbitrary objects (such as most instances) have no -well-defined form before run-time and cannot be investigated further at -compile-time or have a representation inserted into the generated code. - -Class Attributes and Access via Instances ------------------------------------------ - -Unlike module attributes, class attributes can be accessed in a number of -different ways: + python test.py tests/logical.py -t - * Using the class itself: - - C.x = 123 - cls = C; cls.x = 234 - - * Using a subclass of the class (for reading attributes): +To run all tests, use the test_all.py program: - class D(C): - pass - D.x # setting D.x would populate D, not C - - * Using instances of the class or a subclass of the class (for reading - attributes): - - c = C() - c.x # setting c.x would populate c, not C + python test_all.py -Since assignments are only achieved using direct references to the class, and -since class attributes should be defined only within the class initialisation -process, the properties of class attributes should be consistent with those -desired. - -Method Access via Instances ---------------------------- - -It is desirable to optimise method access, even though most method calls are -likely to occur via instances. It is possible, given the properties of methods -as class attributes to investigate the kind of instance that the self -parameter/local refers to within each method: it should be an instance either -of the class in which the method is defined or a compatible class, although -situations exist where this might not be the case: - - * Explicit invocation of a method: - - d = D() # D is not related to C - C.f(d) # calling f(self) in C - -If blatant usage of incompatible instances were somehow disallowed, it would -still be necessary to investigate the properties of an instance's class and -its relationship with other classes. Consider the following example: - - class A: - def f(self): ... - - class B: - def f(self): ... - def g(self): - self.f() +Both programs support optimisations either using the -o flag immediately +followed (no space or separator) by a comma-separated list of options (defined +in the docs/optimisations.txt document) or by specifying -omax to apply all +possible optimisations. - class C(A, B): - pass - -Here, instances of B passed into the method B.g could be assumed to provide -access to B.f when self.f is resolved at compile-time. However, instances of C -passed into B.g would instead provide access to A.f when self.f is resolved at -compile-time (since the method resolution order is C, A, B instead of just B). +Contact, Copyright and Licence Information +------------------------------------------ -One solution might be to specialise methods for each instance type, but this -could be costly. Another less ambitious solution might only involve the -optimisation of such internal method calls if an unambiguous target can be -resolved. - -Narrowing Type Candidates using Attribute Names ------------------------------------------------ +The current Web page for micropython at the time of release is: -Within functions, it might be useful to record attribute accesses on local -names and to collect the names in order to help resolve targets in the -generated code. For example: +http://www.boddie.org.uk/python/micropython.html - def f(x, y): - x.method(y) - if x.something: - ... - return x.attr - -Here, the object referenced via x should have "method", "something" and "attr" -as attributes. We could impose a test for a type providing these attributes at -the earliest opportunity and then specialise the attribute accesses, perhaps -also invocations, in the generated code. AttributeError occurrences would need -to be considered, however, potentially disqualifying certain attributes from -any optimisations, and control flow would also need to be considered. +Copyright and licence information can be found in the docs directory - see +docs/COPYING.txt and docs/gpl-3.0.txt for more information. diff -r 5ad00ae3d24d -r d395dfacb98d docs/optimisations.txt --- a/docs/optimisations.txt Wed Sep 30 00:53:07 2009 +0200 +++ b/docs/optimisations.txt Sat Oct 10 01:52:27 2009 +0200 @@ -1,3 +1,234 @@ +Optimisations +============= + +Some optimisations around constant objects might be possible; these depend on +the following: + + * Reliable tracking of assignments: where assignment operations occur, the + target of the assignment should be determined if any hope of optimisation + is to be maintained. Where no guarantees can be made about the target of + an assignment, no assignment-related information should be written to + potential targets. + + * Objects acting as "containers" of attributes must be regarded as "safe": + where assignments are recorded as occurring on an attribute, it must be + guaranteed that no other unforeseen ways exist to assign to such + attributes. + +The discussion below presents certain rules which must be imposed to uphold +the above requirements. + +Safe Containers +--------------- + +Where attributes of modules, classes and instances are only set once and are +effectively constant, it should be possible to circumvent the attribute lookup +mechanism and to directly reference the attribute value. This technique may +only be considered applicable for the following "container" objects, subject +to the noted constraints: + + 1. For modules, "safety" is enforced by ensuring that assignments to module + attributes are only permitted within the module itself either at the + top-level or via names declared as globals. Thus, the following would not + be permitted: + + another_module.this_module.attr = value + + In the above, this_module is a reference to the current module. + + 2. For classes, "safety" is enforced by ensuring that assignments to class + attributes are only permitted within the class definition, outside + methods. This would mean that classes would be "sealed" at definition time + (like functions). + +Unlike the property of function locals that they may only sensibly be accessed +within the function in which they reside, these cases demand additional +controls or assumptions on or about access to the stored data. Meanwhile, it +would be difficult to detect eligible attributes on arbitrary instances due to +the need for some kind of type inference or abstract execution. + +Constant Attributes +------------------- + +When accessed via "safe containers", as described above, any attribute with +only one recorded assignment on it can be considered a constant attribute and +this eligible for optimisation, the consequence of which would be the +replacement of a LoadAttrIndex instruction (which needs to look up an +attribute using the run-time details of the "container" and the compile-time +details of the attribute) with a LoadAttr instruction. + +However, some restrictions exist on assignment operations which may be +regarded to cause only one assignment in the lifetime of a program: + + 1. For module attributes, only assignments at the top-level outside loop + statements can be reliably assumed to cause only a single assignment. + + 2. For class attributes, only assignments at the top-level within class + definitions and outside loop statements can be reliably assumed to cause + only a single assignment. + +All assignments satisfying the "safe container" requirements, but not the +requirements immediately above, should each be recorded as causing at least +one assignment. + +Additional Controls +------------------- + +For the above cases for "container" objects, the following controls would need +to apply: + + 1. Modules would need to be immutable after initialisation. However, during + initialisation, there remains a possibility of another module attempting + to access the original module. For example, if ppp/__init__.py contained + the following... + + x = 1 + import ppp.qqq + print x + + ...and if ppp/qqq.py contained the following... + + import ppp + ppp.x = 2 + + ...then the value 2 would be printed. Since modules are objects which are + registered globally in a program, it would be possible to set attributes + in the above way. + + 2. Classes would need to be immutable after initialisation. However, since + classes are objects, any reference to a class after initialisation could + be used to set attributes on the class. + +Solutions: + + 1. Insist on global scope for module attribute assignments. + + 2. Insist on local scope within classes. + +Both of the above measures need to be enforced at run-time, since an arbitrary +attribute assignment could be attempted on any kind of object, yet to uphold +the properties of "safe containers", attempts to change attributes of such +objects should be denied. Since foreseen attribute assignment operations have +certain properties detectable at compile-time, it could be appropriate to +generate special instructions (or modified instructions) during the +initialisation of modules and classes for such foreseen assignments, whilst +employing normal attribute assignment operations in all other cases. Indeed, +the StoreAttr instruction, which is used to set attributes in "safe +containers" would be used exclusively for this purpose; the StoreAttrIndex +instruction would be used exclusively for all other attribute assignments. + +To ensure the "sealing" of modules and classes, entries in the attribute +lookup table would encode whether a class or module is being accessed, so +that the StoreAttrIndex instruction could reject such accesses. + +Constant Attribute Values +------------------------- + +Where an attribute value is itself regarded as constant, is a "safe container" +and is used in an operation accessing its own attributes, the value can be +directly inspected for optimisations or employed in the generated code. For +the attribute values themselves, only objects of a constant nature may be +considered suitable for this particular optimisation: + + * Classes + * Modules + * Instances defined as constant literals + +This is because arbitrary objects (such as most instances) have no +well-defined form before run-time and cannot be investigated further at +compile-time or have a representation inserted into the generated code. + +Class Attributes and Access via Instances +----------------------------------------- + +Unlike module attributes, class attributes can be accessed in a number of +different ways: + + * Using the class itself: + + C.x = 123 + cls = C; cls.x = 234 + + * Using a subclass of the class (for reading attributes): + + class D(C): + pass + D.x # setting D.x would populate D, not C + + * Using instances of the class or a subclass of the class (for reading + attributes): + + c = C() + c.x # setting c.x would populate c, not C + +Since assignments are only achieved using direct references to the class, and +since class attributes should be defined only within the class initialisation +process, the properties of class attributes should be consistent with those +desired. + +Method Access via Instances +--------------------------- + +It is desirable to optimise method access, even though most method calls are +likely to occur via instances. It is possible, given the properties of methods +as class attributes to investigate the kind of instance that the self +parameter/local refers to within each method: it should be an instance either +of the class in which the method is defined or a compatible class, although +situations exist where this might not be the case: + + * Explicit invocation of a method: + + d = D() # D is not related to C + C.f(d) # calling f(self) in C + +If blatant usage of incompatible instances were somehow disallowed, it would +still be necessary to investigate the properties of an instance's class and +its relationship with other classes. Consider the following example: + + class A: + def f(self): ... + + class B: + def f(self): ... + def g(self): + self.f() + + class C(A, B): + pass + +Here, instances of B passed into the method B.g could be assumed to provide +access to B.f when self.f is resolved at compile-time. However, instances of C +passed into B.g would instead provide access to A.f when self.f is resolved at +compile-time (since the method resolution order is C, A, B instead of just B). + +One solution might be to specialise methods for each instance type, but this +could be costly. Another less ambitious solution might only involve the +optimisation of such internal method calls if an unambiguous target can be +resolved. + +Narrowing Type Candidates using Attribute Names +----------------------------------------------- + +Within functions, it might be useful to record attribute accesses on local +names and to collect the names in order to help resolve targets in the +generated code. For example: + + def f(x, y): + x.method(y) + if x.something: + ... + return x.attr + +Here, the object referenced via x should have "method", "something" and "attr" +as attributes. We could impose a test for a type providing these attributes at +the earliest opportunity and then specialise the attribute accesses, perhaps +also invocations, in the generated code. AttributeError occurrences would need +to be considered, however, potentially disqualifying certain attributes from +any optimisations, and control flow would also need to be considered. + +Implemented Optimisation Types +============================== + Optimisation Prerequisites and Effect ------------ ------------------------