PEP: XXX Title: Interpreter support for concurrent programming Version: $Revision$ Last-Modified: $Date$ Author: Mike Meyer <mike@mired.org> Status: Draft Type: Informational Content-Type: text/x-rst Created: 11-Nov-2011 Post-History: Abstract ======== The purpose of this PEP is to explore strategies for making concurrent programming in Python easier by allowing the interpreter to detect and notify the user about possible bugs in concurrent access. The reason for doing so is that "Errors should never pass silently". Such bugs are caused by allowing objects to be accessed simultaneously from another thread of execution while they are being modified. Currently, python systems provide no support for such bugs, falling back on the underlying platform facilities and some tools built on top of those. While these tools allow prevention of such modification if the programmer is aware of the need for them, there are no facilities to detect that such a need might exist and warn the programmer of it. The goal is not to prevent such bugs, as that depends on the programmer getting the logic of the interactions correct, which the interpreter can't judge. Nor is the goal to warn the programmer about any such modifications - the goal is to catch standard idioms making unsafe modifications. If the programmer starts tinkering with Python's internals, it's assumed they are aware of these issues. Rationale ========= Concurrency bugs are among the hardest bugs to locate and fix. They result in corrupt data being generated or used in a computation. Like most such bugs, the corruption may not become evident until much later and far away in the program. Minor changes in the code can cause the bugs to fail to manifest. They may even fail to manifest from run to run, depending on external factors beyond the control of the programmer. Therefore any help in locating and dealing with such bugs is valuable. If the interpreter is to provide such help, it must be aware of when things are safe to modify and when they are not. This means it will almost certainly cause incompatible changes in Python, and may impose costs so high for non-concurrent operations as to make it untenable. As such, the final options discussed are destined for Python version 4 or later, and may never be implemented in any mainstream implementation of Python. Terminology =========== The word "thread" is used throughout to mean "concurrent thread of execution". Nominally, this means a platform thread. However, it is intended to include any threading mechanism that allows the interpreter to change threads between or in the middle of a statement without the programmer specifically allowing this to happen. Similarly, the word "interpreter" means any system that processes and executes Python language files. While this normally means cPython, the changes discussed here should be amenable to other implementations. Concept ======= Locking object -------------- The idea is that the interpreter should indicate an error anytime an unlocked object is mutated. For mutable types, this would mean changing the value of the type. For Python class instances, this would mean changing the binding of an attribute. Mutating an object bound to such an attribute isn't a change in the object the attribute belongs to, and so wouldn't indicate an error unless the object bound to the attribute was unlocked. Locking by name --------------- It's also been suggested that locking "names" would be useful. That is, to prevent a specific attribute of an object from being rebound, or a key/index entry in a mapping object. This provides a finer grained locking than just locking the object, as you could lock a specific attribute or set of attributes of an object, without locking all of them. Unfortunately, this isn't sufficient: a set may need to be locked to prevent deletions for some period, or a dictionary to prevent adding a key, or a list to prevent changing a slice, etc. So some other locking mechanism is required. If that needs to specify objects, some way of distinguishing between locking a name and locking the object bound to the name needs to be invented, or there needs to be two different locking mechanisms. It's not clear that the finer grained locking is worth adding yet another language mechanism. Alternatives ============ Explicit locking ---------------- These alternatives requires that the programmer explicitly name anything that is going to be changed to lock it before changing it. This lets the interpreter gets involved, but makes a number of errors possible based on the order that locks are applied. Platform locks '''''''''''''' The current tool set uses platform locks via a C extension. The problem with these is that the interpreter has no knowledge of them, and so can't do anything about detecting the mutation of unlocked objects. A ``locking`` keyword ''''''''''''''''''''' Adding a statement to tell the interpreter to lock objects for the attached suite would let the interpreter know which objects are locked. To help prevent deadlocks, such a keyword needs to imply an order for locking objects, such that two objects locked by the a locking statement will lock the two objects in the same order during a single execution of the program. This can be achieved by sorting objects by the ``id`` of the object, since the requirements for ``id`` are sufficient for this. While the locking order requirement is sufficient to prevent deadlocks from non-nested locking statements, it's not sufficient if locking statements are allowed to nest. So either nested locking statements need to be disallowed, or the outer statement must lock everything that's going to need to be locked. Either requirement is sufficiently onerous that alternatives need to be considered. Implicit locking ---------------- In this alternative, the interpter uses one or more heuristics to decide when things should need locking. Software Transactional Memory (STM) ''''''''''''''''''''''''''''''''''' STM is a relatively new technology being experimented with in newer languages, and in a number of 3rd party libraries (both Peak [#Peak]_ and Kamaelia [#Kamaelia]_ provide STM facilities). A suite is marked as a `transaction`, and then when an unlocked object is modified, instead of indicating an error, a locked copy of it is created to be used through the rest of the transaction. If any of the originals are modified during the execution of the suite, the suite is rerun from the beginning. If it completes, the locked copies are copied back to the originals in an atomic manner. This causes the changes seen by any threads not running the transaction to be atomic. If two threads are updating the same object in transactions, the one that finishes second will be restarted with values set by the one that finished first. The advantage of an STM is that the programmer doesn't have to worry about what is locked, and there's no overhead for using locked objects (after locking them, of course). The disadvantage is that any code in a transaction must be safe to run multiple times. This forbids any kind of I/O. Compiler support '''''''''''''''' Since the point is to get the interpreter involved, we might as well let it be involved in figuring out which things are safe and don't need to be locked. This could potentially eliminate a lot of locking. Each object - whether a Python class instance or builtin type - is created with no way to access it until it is bound. So it is inherently safe to modify. Being bound to a local (or nonlocal?) variable doesn't change this. Being bound to a global, class or instance variable or stored in a container does change this, as the object may now be accessed from other threads via the module or container. Since this analysis is being done at compile time, being passed to another function - including methods of the object - makes it unsafe. Likewise, yielding an object makes it unsafe for future use. Returning it doesn't change anything, since our execution is over and we lose access to the object. Unfortunately, objects returned from functions must be treated as unsafe. Interpreter support ''''''''''''''''''' If we instead track whether or not objects require locking in the interpreter, then we can improve the analsysis. The only thing that definitely makes an object unsafe is binding to a global variable or a variable known to be unsafe. Passing objects to C routines exposes them to concurrent modification, since there's no way to know what will happen inside the C routine. Adding some way of marking C routines - or possibly the objects passed to them - as not exposing things to concurrent modification would help with this, allowing C modules to be called without requiring locking everything passed to them. Binding to class and instance variables, or adding them to a container, is an interesting issue. If the object in question is safe, then anything added to it is also safe. However, this would mean that when an object is flagged as unsafe, all objects accessible through it would also have to be flagged as unsafe. This type of tracking also means that objects effectively have three states: locked, unlocked, and safe. Both locked and safe objects can safely be modified without a problem. Locking and unlocking safe objects is a nop. Interpreter threading --------------------- One alternative is replacing the current threading tools - which are wrappers around the OS-provided threading - with threading support in the interpreter. This would allow the interpreter to control whether or not objects are shared between threads, which isn't possible today. The full implications of this approach have as yet to be worked out. Mixed solutions --------------- Most likely, any real implementation would use a number of the techniques above, since all of them have serious shortcomings. For instance, combining STM with explicit locking would allow explicit locking when IO was required, but complex multi-object changes could be handled by STM, thus avoiding the nested locking issues. Likewise, interpreter or compiler support could be mixed with most other solutions to relax the requirement of locking for part of the objects used in a program. The implications of mixing these things together also needs to be explored more thoroughly. Change proposal =============== This is 'strawman' proposal to provide a starting point for discussion. The proposal is to add an STM support to the python interpreter. A new suite type - the ``transaction`` will be added to the language. The suite will have the semantics discussed above: modifying an object in the suite will trigger creation of a thread-local shallow copy to be used in the Transaction. Further modifications of the original will cause all existing copies to be discarded and the transaction to be restarted. At the end of the transaction, the originals of all the copies are locked and then updated to the state of the copy. Further work ============ Requiring further investigation: - The interpreter providing it's own threading. - How various solutions interact when mixed. There are also a couple tools that might be useful to build, or at least investigate building: - A static concurrency safety analyzer, that handled the AST of a function to determine which variables are safe. - A dynamic concurrency safety analyzer, similar to coverage [#coverage]_. Implementation Notes ==================== Not significantly impacting the performance of single-threaded code must be of paramount importance to any implementation. One implementation technique arose that could help with this. Instead of keeping track of the objects state and having methods check that state and modify their behavior based on it, change the methods as the object changes state. So in safe or locked mode, the objects methods could freely modify the object without having to check it's mode. In unlocked mode, an attempt to do so would raise an error or warning. Unfortunately, this doesn't work if some global or thread state must be checked instead of just object-local state. References ========== .. [#Peak] "Peak, the Python Enterprise Application Kit", http://peak.telecommunity.com/ .. [#Kamaelia] "Kamaelia - Concurrency made useful, fun", http://www.kamaelia.org/ .. [#coverage] "Code coverage measurement for Python", http://pypi.python.org/pypi/coverage Copyright ========= This document has been placed in the public domain.  .. Local Variables: mode: indented-text indent-tabs-mode: nil sentence-end-double-space: t fill-column: 70 coding: utf-8 End: