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 10:17 AM, wrote:

Is optimistic concurrency

http://en.wikipedia.org/wiki/Optimistic_concurrency_control

a possible option for removing the GIL in Python?

Safethread's use of monitors eliminates data contention. The bigger problem is refcounting, which optimistic concurrency doesn't help. -- Adam Olsen, aka Rhamphoryncus

On Tue, Oct 14, 2008 at 2:13 PM, wrote:

...

...

...

...

...

"Adam" == Adam Olsen 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?

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 Thu, Oct 16, 2008 at 9:03 PM, Terry Reedy wrote:

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).

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

On Sat, Oct 18, 2008 at 2:00 PM, Terry Reedy 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.

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.

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

On Sat, Oct 18, 2008 at 6:23 PM, Terry Reedy 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.

I see now.

...

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.

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.

I'm still not convinced that this should be an implementation concern, rather than a language concern, but that's probably okay. -- Cheers, Leif

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 Sun, Oct 19, 2008 at 10:05 PM, wrote:

I'm curious about the assertion of "possibly high collision rate". Do you have measurements to support that?

Nope. :-)

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.

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.

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.

Yeah, side-effects make this nasty. -- Cheers, Leif

On Mon, Oct 20, 2008 at 8:31 AM, wrote:

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?

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 Mon, Oct 20, 2008 at 2:33 PM, Leonardo Santagada wrote:

On Oct 20, 2008, at 6:12 PM, Adam Olsen wrote:

...

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

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.

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 Mon, Oct 20, 2008 at 8:11 PM, Dillon Collins wrote:

On Monday 20 October 2008, Adam Olsen wrote:

...

Stepping back a bit, there's two distinct problems to solve: 1) Making threading easier 2) Removing the GIL

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 ;).

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