Optimistic Concurrency

Is optimistic concurrency http://en.wikipedia.org/wiki/Optimistic_concurrency_control a possible option for removing the GIL in Python? Skip

skip@pobox.com wrote:
Is optimistic concurrency
http://en.wikipedia.org/wiki/Optimistic concurrency_control
This is designed for humans using client programs to edit records in shared databases with a low collision rate at the record level.
a possible option for removing the GIL in Python?
It does not strike me as practical for Python. 1. It starts with copying data. Clients accessing a database server already do this. Threads accessing *shared* data normally do not. 2. Any edit (change) may be discarded in part or in whole. Human operators, informed of the rejection, must (and 'somehow' do) decide what to do. Wrapping every assignment to shared data with a pre-programmed RejectionException handler would usually be a huge burden on the programmer.

On Tue, Oct 14, 2008 at 1:38 PM, Terry Reedy <tjreedy@udel.edu> wrote:
It does not strike me as practical for Python.
Probably true, but let's see....
1. It starts with copying data. Clients accessing a database server already do this. Threads accessing *shared* data normally do not.
Agreed, but if I want them to, they should (and I should be able to tell that to python concisely, and have python understand what that means for concurrency).
It would be a huge burden, but perhaps it could be an option for the especially ambitious programmer. Might there be a way to tell the interpreter, "hey buddy, I've written all the RejectionException handlers, why don't you just let go of the GIL for now and use this other thing instead"? I could see this becoming very difficult if there were some kind of on/off switch you could trigger from inside python (what happens when _that_ has a race condition? O_o), but if you could have it on a per-program-run basis, it might be useful. Certainly, you could then go and exec() an program that does this, and break it that way, but hopefully, if you understand enough to use the switch in the first place, you'd understand how bad of an idea this would be. For a long time, I've wanted to see a strong guarantee of concurrency-invariance in python, especially when dealing with swigged modules, which have a tendency to blunder right on past the GIL. I think having a secondary mode that allows this might be the slow, gentle path we need. After all, I nearly dropped python altogether when I discovered Erlang (before I discovered its syntax, of course), for just this reason. -- Cheers, Leif

Leif Walsh wrote:
You persuaded me to rethink this...
Suppose shared data consists of mutable collections. Let the program units that share the date follow this protocol (discipline) for editing members of a collection. old_id = id(member) edit_copy = collection.member # or collection[index/key] or whatever edit edit_copy done = False while not done: atomically: if id(edit_copy) == old_id: collection.member = copy # by reference copy, not data copy done = True if done: break recover(edit_copy) 'Atomically' could be by a very short term lock or perhaps a builtin C API function if such can run 'atomically' (I just don't know). I believe this will work if all editors edit at the same level of granularity. Certainly, mixing levels can easily lead to data loss.
Or the program might ask a human user, which was the use-case for this idea.

On Thu, Oct 16, 2008 at 9:03 PM, Terry Reedy <tjreedy@udel.edu> wrote:
It feels like, if a new syntax element 'atomically' is added, it would need to know what variable or collection is meant to be atomic. This poses a problem for objects with other references elsewhere, but I think (and I don't know the internal structures of python very well, so this may be way off the mark), the lock could be applied at the data level, not the pointer level, to alleviate this issue.
I believe this will work if all editors edit at the same level of granularity. Certainly, mixing levels can easily lead to data loss.
Again, I think we can fix this by applying the lock to the data. For example (since we talked about this in a class I had today), think about the vfs in linux: Say we have one file with many hardlinks. If we apply a lock to the dentry for the file, and then the user tries to modify our file from a different dentry, the lock won't function. If we apply the lock to the inode, however, it locks it against changes from all hardlinks. Hopefully python has a similar opportunity.
Or the program might ask a human user, which was the use-case for this idea.
I don't think I understood the use case. Can you explain it? -- Cheers, Leif

Leif Walsh wrote:
For example (since we talked about this in a class I had today), think about the vfs in linux:
Out of my knowledge range.
Or the program might ask a human user, which was the use-case for this idea.
I don't think I understood the use case. Can you explain it?
Near the bottom of the original article this thread is based on. Casual users requesting html forms, maybe submitting then, maybe not, with low collision rate, and ability to adjust to collisions. tjr

On Sat, Oct 18, 2008 at 2:00 PM, Terry Reedy <tjreedy@udel.edu> wrote:
Out of my knowledge range.
Well, don't worry, it's mostly still out of mine as well. Thinking about the problem more, I can't come up with a reasonable way to do the locking needed for that last bit of conflict resolution. Maybe someone else can.
I see that now, but wasn't the original post about removing the GIL? That seems to imply that the users would be different threads in a program, with high speed and possibly high collision rate. If we are talking about users communicating over http, this seems like something you'd write a program in python to do (like wikipedia says Rails does), and it doesn't seem to merit discussion in the development of python itself. -- Cheers, Leif

Leif Walsh wrote:
When I said 'impractical', I was thinking about this sort of situation. 'Optimistic Concurrency' is optimistic about not colliding ;-). Else the recovery overhead makes it worse than locking.
Servers have several threads, each communicating with and representing to the rest of the system one user. When those several threads all edit shared data, should they have to acquire GIL, local locks, or none at all? The point of the article is that 'no lock' is desirable when many locks would be left to expire unused and often also possible. tjr

Leif> I see that now, but wasn't the original post about removing the Leif> GIL? That seems to imply that the users would be different Leif> threads in a program, with high speed and possibly high collision Leif> rate. Yes, it was. (I'm the OP.) I'm curious about the assertion of "possibly high collision rate". Do you have measurements to support that? If the collision rate is high enough you'd be replaying operations all the time. OTOH, if the actual collision rate is quite low the replay operation, even if it is onerous, can be tolerated. Someone else mentioned the problem with side effects in non-functional languages. That would indeed seem to be a problem with C (the level I see this operating at.) I have no desire to add further load to the Python programmer. Programming with multiple threads is already hard enough. Clearly the GIL is too coarse a level of locking because it eliminates all possible parallelism. Is it possible that some finer grained locking (but still coarser than complete free threading) can give you back some of the possible parallelism? Maybe reqire all mutable types to support a GIL of their own? Skip

On Oct 20, 2008, at 12:05 AM, skip@pobox.com wrote:
This is the idea that they are planing to do in PyPy. Another idea that maybe have a chance of working is implementing Software Transactional Memory on the interpreter level and use it to implement threading... and maybe have an application (that is, able to be used inside a python program) level STM to make programs more easily parallel (so no need to use locking, semaphores and monitors). I think that trying to do all that in CPython is nearly impossible, as removing refcount, move to finer grained locking and testing all in the current CPython would be a lot of work to do and take a lot of time, to then having to resync with the modifications that are bound to happen during that time in CPython. Also keeping compatibility with the CPython external API would be very hard (but doable, there is even some people trying to do it for running numpy on ironpython). Just my 0,02 cents []'s -- Leonardo Santagada santagada at gmail.com

Leonardo> Another idea that maybe have a chance of working is Leonardo> implementing Software Transactional Memory on the interpreter Leonardo> level and use it to implement threading... That's the term I was looking for, but couldn't remember it. I saw an article on STM a couple months ago and thought that might work for Python. Aren't "optimistic concurrency" and "software transactional memory" very similar concepts? Skip

On Mon, Oct 20, 2008 at 8:31 AM, <skip@pobox.com> wrote:
They're essentially the same. Optimistic concurrency is one of the tools used by STS. To counter Terry's example, I believe it should look like this: transaction: edit collection.member # or collection[index/key] or whatever IOW, the collection container should automatically create a view when you touch it, adding it to the current transaction. When the transaction block completes, the language attempts to atomically commit all the views, restarting if there's a conflict. This has substantial problems if you mix a very long transaction with many short ones. Various ways of prioritizing restarted transactions are possible, at the risk of locking everybody out if the long transaction takes too long (or never completes). Also note that this doesn't require optimistic concurrency. It's just as valid to raise an exception when editing if another commit has invalidated your transaction. In fact, since views are added lazily, this is more-or-less required. Stepping back a bit, there's two distinct problems to solve: 1) Making threading easier 2) Removing the GIL #1 can be done by things like monitors and transactions (the two are complementary). #2 at its core is about refcounting, and transactions are irrelevant there — you need to switch to a tracing-based GC implementation -- Adam Olsen, aka Rhamphoryncus

On Oct 20, 2008, at 6:12 PM, Adam Olsen wrote:
PyPy has a real GC and doesn't depend on refcount already. So that is not the only thing needed to accomplish #2, you need to lock mutable data containers so concurrent threads don't leave them in a broken state. This is the part not ready on PyPy yet. But it is probably easier to fix on PyPy than on CPython. []'s -- Leonardo Santagada santagada at gmail.com

On Mon, Oct 20, 2008 at 2:33 PM, Leonardo Santagada <santagada@gmail.com> wrote:
Although #2 does depend on it, providing sane and safe semantics for the datastructures is the domain of #1. Keep in mind that very little in python actually needs implicit concurrent mutation (class and module dicts do). Implicit thread interaction is the fundamental problem of the current threading models, for all the reasons spelled out in the zen. -- Adam Olsen, aka Rhamphoryncus

On Monday 20 October 2008, Adam Olsen wrote:
As I've not seen it mentioned in this thread, I feel that it's worth pointing out that 2.6's new multiprocessing module allows for programs to use more than one CPU, thus eventually eliminating the GIL: http://docs.python.org/dev/2.6/library/multiprocessing.html In light of this I doubt we'll see the GIL removed from CPython pretty much ever. The GIL does have the benefit of speeding up CPython fairly significantly by removing lock overhead, and simplifies the code. It can also be released by C libs for things that will take a long time (which are often best in C for that reason anyway). So, while removing the GIL is fun from an intellectual perspective, it's practical value is now somewhat limited. Sure, multiprocessing isn't perfect, but it is the first thing to bypass the GIL that's been accepted ;).

On Mon, Oct 20, 2008 at 8:11 PM, Dillon Collins <dillonco@comcast.net> wrote:
The GIL won't be removed from CPython, but that's because it'd be a near-total-rewrite to do effectively. multiprocessing is useful when there's a limited amount of shared data. Problems that involve large amounts of shared data will still require threading. You can gain scalability by moving the logic into C, but as the number of CPUs increases so does the amount that must be in C. Eventually you reach a point where using python is counterproductive. As far as I'm concerned we can already solve this: safethread defines the semantics (#1) and other implementations like PyPy can handle the scalability (#2). What we lack is a significant number of people that *need* this solved. -- Adam Olsen, aka Rhamphoryncus

Adam> What we lack is a significant number of people that *need* this Adam> solved. Most people *think* they need this solved though. ;-) Skip

On Sun, Oct 19, 2008 at 10:05 PM, <skip@pobox.com> wrote:
I'm curious about the assertion of "possibly high collision rate". Do you have measurements to support that?
Nope. :-)
This is why I suggested that there should be some kind of mode switch available, so I can decide when it's worth it to switch.
Yeah, side-effects make this nasty. -- Cheers, Leif

"Adam" == Adam Olsen <rhamph@gmail.com> writes:
Adam> Safethread's use of monitors eliminates data contention. The Adam> bigger problem is refcounting, which optimistic concurrency Adam> doesn't help. Thanks. I see Safethread hasn't had a release in awhile. Is it still up-to-date w.r.t. Subversion trunk? Skip

On Tue, Oct 14, 2008 at 2:13 PM, <skip@pobox.com> wrote:
Development has stalled due to lack of interest. It's not up-to-date, but the current plan is to strip the GIL removal changes out of it (leaving them in a separate branch), which should make it much easier to update. -- Adam Olsen, aka Rhamphoryncus

On Tue, Oct 14, 2008 at 9:17 AM, <skip@pobox.com> wrote:
Not really. Automatically retrying generic operations when there's a conflict more-or-less requires a pure functional language, since you want to absolutely minimize side-effects when you're replaying the failed operation. See the implementation of STM in Haskell's GHC compiler for more. Collin Winter

skip@pobox.com wrote:
Is optimistic concurrency
http://en.wikipedia.org/wiki/Optimistic concurrency_control
This is designed for humans using client programs to edit records in shared databases with a low collision rate at the record level.
a possible option for removing the GIL in Python?
It does not strike me as practical for Python. 1. It starts with copying data. Clients accessing a database server already do this. Threads accessing *shared* data normally do not. 2. Any edit (change) may be discarded in part or in whole. Human operators, informed of the rejection, must (and 'somehow' do) decide what to do. Wrapping every assignment to shared data with a pre-programmed RejectionException handler would usually be a huge burden on the programmer.

On Tue, Oct 14, 2008 at 1:38 PM, Terry Reedy <tjreedy@udel.edu> wrote:
It does not strike me as practical for Python.
Probably true, but let's see....
1. It starts with copying data. Clients accessing a database server already do this. Threads accessing *shared* data normally do not.
Agreed, but if I want them to, they should (and I should be able to tell that to python concisely, and have python understand what that means for concurrency).
It would be a huge burden, but perhaps it could be an option for the especially ambitious programmer. Might there be a way to tell the interpreter, "hey buddy, I've written all the RejectionException handlers, why don't you just let go of the GIL for now and use this other thing instead"? I could see this becoming very difficult if there were some kind of on/off switch you could trigger from inside python (what happens when _that_ has a race condition? O_o), but if you could have it on a per-program-run basis, it might be useful. Certainly, you could then go and exec() an program that does this, and break it that way, but hopefully, if you understand enough to use the switch in the first place, you'd understand how bad of an idea this would be. For a long time, I've wanted to see a strong guarantee of concurrency-invariance in python, especially when dealing with swigged modules, which have a tendency to blunder right on past the GIL. I think having a secondary mode that allows this might be the slow, gentle path we need. After all, I nearly dropped python altogether when I discovered Erlang (before I discovered its syntax, of course), for just this reason. -- Cheers, Leif

Leif Walsh wrote:
You persuaded me to rethink this...
Suppose shared data consists of mutable collections. Let the program units that share the date follow this protocol (discipline) for editing members of a collection. old_id = id(member) edit_copy = collection.member # or collection[index/key] or whatever edit edit_copy done = False while not done: atomically: if id(edit_copy) == old_id: collection.member = copy # by reference copy, not data copy done = True if done: break recover(edit_copy) 'Atomically' could be by a very short term lock or perhaps a builtin C API function if such can run 'atomically' (I just don't know). I believe this will work if all editors edit at the same level of granularity. Certainly, mixing levels can easily lead to data loss.
Or the program might ask a human user, which was the use-case for this idea.

On Thu, Oct 16, 2008 at 9:03 PM, Terry Reedy <tjreedy@udel.edu> wrote:
It feels like, if a new syntax element 'atomically' is added, it would need to know what variable or collection is meant to be atomic. This poses a problem for objects with other references elsewhere, but I think (and I don't know the internal structures of python very well, so this may be way off the mark), the lock could be applied at the data level, not the pointer level, to alleviate this issue.
I believe this will work if all editors edit at the same level of granularity. Certainly, mixing levels can easily lead to data loss.
Again, I think we can fix this by applying the lock to the data. For example (since we talked about this in a class I had today), think about the vfs in linux: Say we have one file with many hardlinks. If we apply a lock to the dentry for the file, and then the user tries to modify our file from a different dentry, the lock won't function. If we apply the lock to the inode, however, it locks it against changes from all hardlinks. Hopefully python has a similar opportunity.
Or the program might ask a human user, which was the use-case for this idea.
I don't think I understood the use case. Can you explain it? -- Cheers, Leif

Leif Walsh wrote:
For example (since we talked about this in a class I had today), think about the vfs in linux:
Out of my knowledge range.
Or the program might ask a human user, which was the use-case for this idea.
I don't think I understood the use case. Can you explain it?
Near the bottom of the original article this thread is based on. Casual users requesting html forms, maybe submitting then, maybe not, with low collision rate, and ability to adjust to collisions. tjr

On Sat, Oct 18, 2008 at 2:00 PM, Terry Reedy <tjreedy@udel.edu> wrote:
Out of my knowledge range.
Well, don't worry, it's mostly still out of mine as well. Thinking about the problem more, I can't come up with a reasonable way to do the locking needed for that last bit of conflict resolution. Maybe someone else can.
I see that now, but wasn't the original post about removing the GIL? That seems to imply that the users would be different threads in a program, with high speed and possibly high collision rate. If we are talking about users communicating over http, this seems like something you'd write a program in python to do (like wikipedia says Rails does), and it doesn't seem to merit discussion in the development of python itself. -- Cheers, Leif

Leif Walsh wrote:
When I said 'impractical', I was thinking about this sort of situation. 'Optimistic Concurrency' is optimistic about not colliding ;-). Else the recovery overhead makes it worse than locking.
Servers have several threads, each communicating with and representing to the rest of the system one user. When those several threads all edit shared data, should they have to acquire GIL, local locks, or none at all? The point of the article is that 'no lock' is desirable when many locks would be left to expire unused and often also possible. tjr

Leif> I see that now, but wasn't the original post about removing the Leif> GIL? That seems to imply that the users would be different Leif> threads in a program, with high speed and possibly high collision Leif> rate. Yes, it was. (I'm the OP.) I'm curious about the assertion of "possibly high collision rate". Do you have measurements to support that? If the collision rate is high enough you'd be replaying operations all the time. OTOH, if the actual collision rate is quite low the replay operation, even if it is onerous, can be tolerated. Someone else mentioned the problem with side effects in non-functional languages. That would indeed seem to be a problem with C (the level I see this operating at.) I have no desire to add further load to the Python programmer. Programming with multiple threads is already hard enough. Clearly the GIL is too coarse a level of locking because it eliminates all possible parallelism. Is it possible that some finer grained locking (but still coarser than complete free threading) can give you back some of the possible parallelism? Maybe reqire all mutable types to support a GIL of their own? Skip

On Oct 20, 2008, at 12:05 AM, skip@pobox.com wrote:
This is the idea that they are planing to do in PyPy. Another idea that maybe have a chance of working is implementing Software Transactional Memory on the interpreter level and use it to implement threading... and maybe have an application (that is, able to be used inside a python program) level STM to make programs more easily parallel (so no need to use locking, semaphores and monitors). I think that trying to do all that in CPython is nearly impossible, as removing refcount, move to finer grained locking and testing all in the current CPython would be a lot of work to do and take a lot of time, to then having to resync with the modifications that are bound to happen during that time in CPython. Also keeping compatibility with the CPython external API would be very hard (but doable, there is even some people trying to do it for running numpy on ironpython). Just my 0,02 cents []'s -- Leonardo Santagada santagada at gmail.com

Leonardo> Another idea that maybe have a chance of working is Leonardo> implementing Software Transactional Memory on the interpreter Leonardo> level and use it to implement threading... That's the term I was looking for, but couldn't remember it. I saw an article on STM a couple months ago and thought that might work for Python. Aren't "optimistic concurrency" and "software transactional memory" very similar concepts? Skip

On Mon, Oct 20, 2008 at 8:31 AM, <skip@pobox.com> wrote:
They're essentially the same. Optimistic concurrency is one of the tools used by STS. To counter Terry's example, I believe it should look like this: transaction: edit collection.member # or collection[index/key] or whatever IOW, the collection container should automatically create a view when you touch it, adding it to the current transaction. When the transaction block completes, the language attempts to atomically commit all the views, restarting if there's a conflict. This has substantial problems if you mix a very long transaction with many short ones. Various ways of prioritizing restarted transactions are possible, at the risk of locking everybody out if the long transaction takes too long (or never completes). Also note that this doesn't require optimistic concurrency. It's just as valid to raise an exception when editing if another commit has invalidated your transaction. In fact, since views are added lazily, this is more-or-less required. Stepping back a bit, there's two distinct problems to solve: 1) Making threading easier 2) Removing the GIL #1 can be done by things like monitors and transactions (the two are complementary). #2 at its core is about refcounting, and transactions are irrelevant there — you need to switch to a tracing-based GC implementation -- Adam Olsen, aka Rhamphoryncus

On Oct 20, 2008, at 6:12 PM, Adam Olsen wrote:
PyPy has a real GC and doesn't depend on refcount already. So that is not the only thing needed to accomplish #2, you need to lock mutable data containers so concurrent threads don't leave them in a broken state. This is the part not ready on PyPy yet. But it is probably easier to fix on PyPy than on CPython. []'s -- Leonardo Santagada santagada at gmail.com

On Mon, Oct 20, 2008 at 2:33 PM, Leonardo Santagada <santagada@gmail.com> wrote:
Although #2 does depend on it, providing sane and safe semantics for the datastructures is the domain of #1. Keep in mind that very little in python actually needs implicit concurrent mutation (class and module dicts do). Implicit thread interaction is the fundamental problem of the current threading models, for all the reasons spelled out in the zen. -- Adam Olsen, aka Rhamphoryncus

On Monday 20 October 2008, Adam Olsen wrote:
As I've not seen it mentioned in this thread, I feel that it's worth pointing out that 2.6's new multiprocessing module allows for programs to use more than one CPU, thus eventually eliminating the GIL: http://docs.python.org/dev/2.6/library/multiprocessing.html In light of this I doubt we'll see the GIL removed from CPython pretty much ever. The GIL does have the benefit of speeding up CPython fairly significantly by removing lock overhead, and simplifies the code. It can also be released by C libs for things that will take a long time (which are often best in C for that reason anyway). So, while removing the GIL is fun from an intellectual perspective, it's practical value is now somewhat limited. Sure, multiprocessing isn't perfect, but it is the first thing to bypass the GIL that's been accepted ;).

On Mon, Oct 20, 2008 at 8:11 PM, Dillon Collins <dillonco@comcast.net> wrote:
The GIL won't be removed from CPython, but that's because it'd be a near-total-rewrite to do effectively. multiprocessing is useful when there's a limited amount of shared data. Problems that involve large amounts of shared data will still require threading. You can gain scalability by moving the logic into C, but as the number of CPUs increases so does the amount that must be in C. Eventually you reach a point where using python is counterproductive. As far as I'm concerned we can already solve this: safethread defines the semantics (#1) and other implementations like PyPy can handle the scalability (#2). What we lack is a significant number of people that *need* this solved. -- Adam Olsen, aka Rhamphoryncus

Adam> What we lack is a significant number of people that *need* this Adam> solved. Most people *think* they need this solved though. ;-) Skip

On Sun, Oct 19, 2008 at 10:05 PM, <skip@pobox.com> wrote:
I'm curious about the assertion of "possibly high collision rate". Do you have measurements to support that?
Nope. :-)
This is why I suggested that there should be some kind of mode switch available, so I can decide when it's worth it to switch.
Yeah, side-effects make this nasty. -- Cheers, Leif

"Adam" == Adam Olsen <rhamph@gmail.com> writes:
Adam> Safethread's use of monitors eliminates data contention. The Adam> bigger problem is refcounting, which optimistic concurrency Adam> doesn't help. Thanks. I see Safethread hasn't had a release in awhile. Is it still up-to-date w.r.t. Subversion trunk? Skip

On Tue, Oct 14, 2008 at 2:13 PM, <skip@pobox.com> wrote:
Development has stalled due to lack of interest. It's not up-to-date, but the current plan is to strip the GIL removal changes out of it (leaving them in a separate branch), which should make it much easier to update. -- Adam Olsen, aka Rhamphoryncus

On Tue, Oct 14, 2008 at 9:17 AM, <skip@pobox.com> wrote:
Not really. Automatically retrying generic operations when there's a conflict more-or-less requires a pure functional language, since you want to absolutely minimize side-effects when you're replaying the failed operation. See the implementation of STM in Haskell's GHC compiler for more. Collin Winter
participants (7)
-
Adam Olsen
-
Collin Winter
-
Dillon Collins
-
Leif Walsh
-
Leonardo Santagada
-
skip@pobox.com
-
Terry Reedy