>> (C) That scheduler is non-preemptive. A single greedy generator can >> starve all the others. Antoine> Instead of looking at this as a problem, you could look at it Antoine> as a feature. Apple looked at it as a feature for years. Not anymore. <wink> Skip

On 9/30/05, Antoine Pitrou wrote:

Le vendredi 30 septembre 2005 à 08:32 -0500, skip@pobox.com a écrit :

...

>> (C) That scheduler is non-preemptive. A single greedy generator can >> starve all the others.

Antoine> Instead of looking at this as a problem, you could look at it Antoine> as a feature.

Apple looked at it as a feature for years. Not anymore. <wink>

You are missing the context: - at the OS level, it is not good to have cooperative MT because any badly-written app (there are lots of ;-)) can cause lack of responsiveness for the whole machine - at the application level, cooperative MT can be good to enforce robust semantics without disrupting other apps

The latter is what we are discussing AFAIK: a different concurrency scheme inside a single application - not accross the whole OS or desktop.

I like this analysis.

Actually, I think different concurrency schemes must be chosen and mixed depending on the semantics. For example, when you have a networked GUI app, it can be good to have the network in one preemptive thread (using e.g. Twisted) and the GUI in another preemptive thread (using GTK, wx...). This is because GUI and network have different latency characteristics and requirements. (of course, you can replace "preemptive thread" with "process" in the above description)

I'm skeptical of this. I think a traditional GUI+network app can combine the network and UI tasks in one process -- usually they interact somewhat and that's where the bugs show up. Also note that this is not an application area where MP is very interesting -- most of the time you're blocked waiting for the user or for a socket (or likely both :) so a single CPU is all you need. I've never heard someone complain that the GIL is in the way for these types of apps.

So whatever innovatice concurrency scheme Python may come out, it should still be mixable with more traditional concurrency schemes, because required properties vary wildly even inside a single app.

I don't think you've proved that yet. -- --Guido van Rossum (home page: http://www.python.org/~guido/)

On Fri, 30 Sep 2005 17:26:27 +0200, Antoine Pitrou wrote:

Hi,

...

I've never heard someone complain that the GIL is in the way for these types of apps.

I've never said so either. I was just saying that it can be useful to mix cooperative threading and preemptive threading in the same app, i.e. have different domains of cooperative threading which are preemptively scheduled by the OS. That has nothing to do with the GIL, I think (but I don't know much in Python internals).

For instance the mix between Twisted and GUI event loops is a very common topic on the twisted mailing-list, because people have trouble getting it right inside a single system thread. The Twisted people have started advocating something called the ThreadedSelectReactor, which I haven't looked at but whose name suggests that some operations are performed in a helper system thread.

"Advocating" might be putting it too strongly :) "Experimenting with" describes the current state of things most accurately. The problem it aims to solve is integration with cooperative threading systems which don't work very well. An example of such a loop is the wx event loop. Whenever a modal dialog is displayed or a menu is activated, wx's loop stops cooerating. The only way we've found thus far to avoid this is to run wx in a separate thread, so even when it stops cooperating, network code can still get scheduled. Jp

On Fri, 2005-09-30 at 18:33 +0200, Antoine Pitrou wrote:

Hi Jp,

Le vendredi 30 septembre 2005 à 12:20 -0400, Jp Calderone a écrit :

...

"Advocating" might be putting it too strongly :) "Experimenting with" describes the current state of things most accurately.

Ok :)

...

The problem it aims to solve is integration with cooperative threading systems which don't work very well. An example of such a loop is the wx event loop.

Whenever a modal dialog is displayed or a menu is activated, wx's loop stops cooerating.

That is wx's problem. Try PyGTK some day; I hear it's really good! ;-)

This specific problem hides the more general problem, which is that GUI and network activities have different typical latencies. As I explained on the twisted ML, a GUI needs very good response times to feel friendly (typically below 20 or even 10 ms.), whereas some network protocols have non-trivial calculations which can go above 100 ms.

With PyGTK a typical solution for this is to use a generator function executing an "idle function", which would make the non-trivial calculations, but yield control back to the main loop periodically, in order to process GUI events. For example, see the last code block in http://www.async.com.br/faq/pygtk/index.py?req=show&file=faq23.020.htp

Moreover, you don't want a sudden flood of network events to block events in the GUI.

Process one event at a time, after each event give back control to the main loop, and give low priority to socket IO events. Problem solved.

This is why even without considering wx's specificities, it is still useful to keep GUI and network activities in separate threads.

You are considering a scenario that seldom happens to design a solution that is far too complicated for most cases. Regards. -- Gustavo J. A. M. Carneiro The universe is always one step beyond logic

On 9/30/05, Antoine Pitrou wrote:

...

(C) That scheduler is non-preemptive. A single greedy generator can starve all the others.

Instead of looking at this as a problem, you could look at it as a feature. Since generators can't be switched at arbitrary places, the programmer has to define his/her synchronization points explicitly.

I use this approach extensively, using tasks which are defined using generators. The scheduler I developed for this can be viewed here: http://metaplay.dyndns.org:82/svn/nanothreads/nanothreads.py Synchronization using yield statements is an important feature, as I use these cooperative threads for game development. These threads are _very_ useful for games, as they have very low overhead, and allow the programmer to exercise more control over their execution. Sw.

Hi. I hear a confusion that is annoying me a bit in some of the discussions on concurrency, and I thought I'd flush my thoughts here to help me clarify some of that stuff, because some people on the list appear to discuss generators as a concurrency scheme, and as far as I know (and please correct me if I'm wrong) they really are not adressing that at all (full explanation below). Before I go on, I must say that I am not in any way an authority on concurrent programming, I'm just a guy who happens to have done a fair amount of threaded programming, so if any of the smart people on the list notice something completely stupid and off the mark that I might be saying here, please feel free to bang on it with the thousand-pound hammer of your hacker-fu and put me to shame (I love to learn). As far as I understand, generators are just a convenient way to program apparently "independent" control flows (which are not the same as "concurrent" control flows) in a constrained, structured way, a way that is more powerful than what is allowed by using a stack. By giving up using the stack concept as a fast way to allocate local function variables, it becomes possible to exit and enter chunks of code multiple times, at specific points, within an automatically restored local context (i.e. the local variables, stored on the heap). Generators make it more convenient to do just that: enter and re-enter some code that is expressed as if it would be running in a single execution flow (with explicit points of exit/re-entry, "yields"). The full monty version of that, is what you get when you write assembly code (*memories of adolescent assembly programming on the C=64 abound here now*): you can JMP anywhere anytime, and a chunk of code (a function) can be reentered anywhere anytime as well, maybe even reentered somewhere else than where it left off. The price to pay for this is one of complexity: in assembly you have to manage restoring the local context yourself (i.e in assembly code this just means restoring the values of some registers which are assumed set and used by the code, like the local variables of a function), and there is no clear grouping of the local scope that is saved. Generators give you that for free: they automatically organize all that local context as belonging to the generator object, and it expresses clear points of exit/re-entry with the yield calls. They are really just a fancy goto, with some convenient assumptions about how control should flow. This happens to be good enough for simplifying a whole class of problems and I suppose the Python and Ruby communities are all learning to love them and use them more and more. (I think the more fundamental consequence of generators is to raise questions about the definition of what "a function" is: if I have a single chunk of code in which different parts uses two disjoint sets of variables, and it can be entered via a few entry/exit points, is it really one or two or multiple "functions"? What if different parts share some of the local scope only? Where does the function begin and end? And more importantly, is there a more complex yet stull manageable abstraction that would allow even more flexible control flow than generators allow, straddling the boundaries of what a function is?) You could easily implement something very similar to generators by encapsulating the local scope explicitly in the form of a class, with instance attributes, and having an normal method "step()" that would be careful about saving state in the object's attributes everytime it returns and restoring state from those attributes everytime it gets called. This is what iterators do. Whenever you want to "schedule" your object to be running, you call the step() method. So just in that sense generators really aren't all that exciting or "new". The main problem that generators solve is that they make this save/restore mechanism automatic, thus allowing you to write a single flow of execution as a normal function with explicit exit points (yield). It's much nicer having that in the language than having to write code that can be restored (especially when you have to write a loop with complex conditions/flow which must run and return only one iteration every time they become runnable). Therefore, as far as I understand it, generators themselves DO NOT implement any form of concurrency. I feel that where generators and concurrency come together is often met with confusion in the discussions I see about them, but maybe that's just me. I see two aspects that allow generators to participate in the elaboration of a concurrency scheme: 1. The convenience of expression of a single execution flow (with explicit interruption points) makes it easy to implement pseudo-concurrency IF AND ONLY IF you consider a generator as an independent unit of control flow (i.e. a task). Whether those generators can run asynchronously is yet undefined and depends on who calls them. 2. In a more advanced framework/language, perhaps some generators could be considered to always be possible to run asynchronously, ruled by a system of true concurrency with some kind of scheduling algorithm that oversees that process. Whether this has been implemented by many is still a mystery to me, but I can see how a low-level library that provides asynchronously running execution vehicles for each CPU could be used to manage and run a pool of shared generator objects in a way that is better (for a specific application) than the relatively uninformed scheduling provided by the threads abstraction (more at the end). Pseudo or cooperative concurrency is not the same as true asynchronous concurrency. You can ONLY avoid having to deal with issues of mutual exclusion if you DO NOT have true asynchronous concurrency (i.e. two real CPUs running at the same time)--unless you have some special scheduling system that implements very specific assumptions about data access vs the code that it schedules, in which case that scheduling algorithm itself will have to deal with potential mutual exclusion problems: YOU DON'T GET OUT OF IT, if you have two real, concurrent processing units making calculations, you have to deal with the way that they might access some same piece of data at the same time. I suppose that the essence of what I want to say with this diatribe is that everyone who talks about generators as a way to avoid the hard problems of concurrent programming should really explicitly frame the discussion in the context of a single process cooperative scheme that runs on a single processor (at any one time). It does not hold outside of that context, outside of that context you HAVE to deal with mutex issues, and that's always where it gets messy (even with generators). Now, IMO where it gets interesting is when you consider that what you're doing when you are executing multiple asynchronous control flows with explicit code in your process, is that you're essentially bringing "up" the scheduler from the kernel layer into your own code. This is very cool. This may allow you specialize that scheduler with assumptions which may ultimately simplify the implementation of your independent control flows. For example, if you have two sets of generators that access disjoint sets of data, and two processing units, your scheduler could make sure that no two generators from the same set get scheduled at the same time. If you do that then you might not have to lock access to your data structures at all. You can imagine more complex variants on this theme. One of the problems that you have with using generators like this, is that automatic "yield" on resource access does not occur automatically, like it does in threading. With threads, the kernel is invoked when access to a low-level resource is requested, and may decide to put your process in the wait queue when it judges necessary. I don't know how you would do that with generators. To implement that explicitly, you would need an asynchronous version of all the functions that may block on resources (e.g. file open, socket write, etc.), in order to be able to insert a yield statement at that point, after the async call, and there should be a way for the scheduler to check if the resource is "ready" to be able to put your generator back in the runnable queue. (A question comes to mind here: Twisted must be doing something like this with their "deferred objects", no? I figure they would need to do something like this too. I will have to check.) Any comment welcome. cheers,

On Saturday 01 October 2005 22:50, Martin Blais wrote: ...

because some people on the list appear to discuss generators as a concurrency scheme, and as far as I know they really are not addressing that at all.

Our project started in the context of dealing with the task of a naturally concurrent environment. Specifically the task is that of dealing with large numbers of concurrent connections to a server. As a result, when I've mentioned concurrency it's been due to coming from that viewpoint. In the past I have worked with systems essentially structured in a similar way to Twisted for this kind of problem, but decided against that style for our current project. (Note some people misunderstand my opinions here due to a badly phrased lightning talk ~16 months ago at Europython 2004 - I think twisted is very much best of breed in python for what it does. I just think there //might// be a nicer way. (might :) ) Since I now work in an R&D dept I wondered what would happen if instead of the basic approach that underlies systems like twisted what would happen if you took a much more CSP-like approach to building such systems, but using generators rather than threads or explicit state machines. A specific goal was to try and make code simpler for people to work with - with the aim actually of simplifying maintenance as the main by-product. I hadn't heard of anyone trying this approach then and hypothesised it *might* achieve that goal. As a result from day 1 it became clear that where an event based system would normally use a reactor/proactor based approach, that you replace that with a scheduler that repeatedly calls a next method on objects given to it to schedule. In terms of concurrency that is clearly a co-operative multitasking system in the same way as a simplistic event based system is. (Both get more complex in reality when you can't avoid blocking forcing the use of threads for some tasks) So when you say this:

explicitly frame the discussion in the context of a single process cooperative scheme that runs on a single processor (at any one time).

This is spot on. However, any generator can be farmed off and run in a thread. Any communications you did with the generator can be wrapped via Queues then - forming a controlled bridge between the threads. Similarly we're currently looking at using non-blocking pipes and pickling to communicate with generators running in a forked environment. As a result if you write your code as generators it can migrate to a threaded or process based environment, and scale across multiple processes (and hence processors) if tools to perform this migration are put in place. We're a little way off doing that, but this looks to be highly reasonable.

As far as I understand, generators are just a convenient way to

They give you code objects that can do a return and continue later. This isn't really the same as the ability to just do a goto into random points in a function. You can only go back to the point the generator yielded at (unless someone has a perverse trick :-).

You could easily implement something very similar to generators by encapsulating the local scope explicitly in the form of a class, with instance attributes, and having an normal method "step()" that would be careful about saving state in the object's attributes everytime it returns and restoring state from those attributes everytime it gets called.

For a more explicit version of this we have a (deliberately naive) C++ version of generators & our core concurrency system. Mechanism is here: http://tinyurl.com/7gaol , example use here: http://tinyurl.com/bgwro That does precisely that. (except we use a next() method there :-)

Therefore, as far as I understand it, generators themselves DO NOT implement any form of concurrency.

By themselves, they don't. They can be used to deal with concurrency though.

2. In a more advanced framework/language, perhaps some generators could be considered to always be possible to run asynchronously, ruled by a system of true concurrency with some kind of scheduling algorithm that oversees that process. Whether this has been implemented by many is still a mystery to me,

This is what we do. Our tutorial we've given to trainees (one of whom have had very little experience of even programming) was able to pick up our approach quickly due to our tutorial. This requires them to implement a mini-version of the framework, which might actually aid the discussion here since it very clearly shows the core of our system. (nb it is however a simplified version) I previously posted a link to it, which is here: http://kamaelia.sourceforge.net/MiniAxon/

but I can see how a low-level library that provides asynchronously running execution vehicles for each CPU could be used to manage and run a pool of shared generator objects in a way that is better (for a specific application) than the relatively uninformed scheduling provided by the threads abstraction (more at the end).

Pseudo or cooperative concurrency is not the same as true asynchronous concurrency.

Correct. I've had discussions with a colleague at work who wants to work on the underlying formal semantics of our system for verification purposes, and he pointed out that the core assumption with a pure generator approach effectively serialises the application, which may hide problems in the true parallel approach (eg only using processes for a CSP-like system). However that statement had an underlying assumption: that the system would be a pure generator system. As soon as you involve multiple systems using network connections, and threads (since we have threaded components as well), and processes (which has always been on the cards, all our desktop machines are dual processor and it just seems a waste to use just one) then the system goes truly asynchronous. As a result we (at least :-) have thought about these problems along the way.

you have to deal with the way that they might access some same piece of data at the same time.

We do. We have both an underlying approach to deal with this and a metaphor that encourages correct usage. The underlying mechanism is based on explicit hand off of data between asynchronous activities. Once you have handed off a piece of data, you no longer own it and can no longer change it. If you are handed a piece of data you can do anything you like with it, for as long as you like until you hand it off or throw it away. The metaphor of old-fashioned paper based inboxes (or in-trays) and outboxes (or out-trays) conceptually reinforces this idea - naturally encouraging safer programming styles. This means that we only ever have a single reader and single writer for any item of data, which eliminates whole swathes of concurrency issues - whether you're pseudo-concurrent (ie threads[*], generators) or truly concurrent (processes on multiple processors). [*] Still only 1 CPU really. Effectively there is no global data. If there is any global data (since we do have a global address space we tend to think of as similar to a linda tuple space), then it has a single owner. Others may read it, but only one may write to it. Because this is python, this is enforced by convention. (But the use is discouraged and rarely needed). The use of generators effectively also hides the local variables from accidental external modification. Which is a secondary layer of protection.

If you do that then you might not have to lock access to your data structures at all.

We don't have to lock data structures at all - this is because we have explicit hand off of data. If we hand off between processes, we do this via Queues that handle the locking issues for us.

To implement that explicitly, you would need an asynchronous version of all the functions that may block on resources (e.g. file open, socket write, etc.)

Or you can create a generator that handles reading from a file and hands off the data on to the next component explicitly. The file reader is given CPU time by the scheduler. This can seem odd unless you've done any shell programming in which case the idea should be obvious: echo `ls *py |while read i; do wc -l $i |cut -d \ -f1; done` | sed -e 's/ /+/g' | bc (yes I know there's better ways of doing this :) So all in all, I'd say "yes" generators aren't really concurrent, but they *are* a very good way (IMHO) of dealing with concurrency in a single thread and map naturally if you're careful in designing your approach early on to map to a thread/process based approach cleanly. If you think I'm talking a load of sphericals (for all I know it's possible I am, though I hope I'm not :-) , please look at our tutorial first, then at our howto for building components [*] and tell me what we're doing wrong. I'd really like to know so we can make the system better, easier for newbies (and hence everyone else), and more trustable. [*] http://tinyurl.com/dp8n7 (This really feels like this more of a comp.lang.python discussion really though, because AFAICT, python already has everything we need for this. I might revisit that thought when we've looked at shared memory issues though. IMHO though that would be largely stuff for the standard library.) Best Regards, Michael. -- Michael Sparks, Senior R&D Engineer, Digital Media Group Michael.Sparks@rd.bbc.co.uk, http://kamaelia.sourceforge.net/ British Broadcasting Corporation, Research and Development Kingswood Warren, Surrey KT20 6NP This e-mail may contain personal views which are not the views of the BBC.

On 9/30/05, Jeremy Maxfield wrote:

Support for multiple interpreters already exists from the C API (mod_python, Java Embedded Python a few other add-ons use them)

I'm aware of that (didn't I mention it in my message - sorry).

But: - it's not possible to create new interpreter instances from within Python.

Yet...

- there's no mechanism for passing information between interpreters.

But one could possibly be added when exposing the functionality to Python.

- interaction with extension modules instances may be a problem.

This is the issue I have heard mentioned before as the problematic one. Unfortunately, I don't know enough about the problems to be able to comment. If it's as simple as saying that any global state maintained by an extension module is part of the "shared state", then I'm OK with that (although it would be nice to encourage extension authors to document their global state a bit more clearly :-)) Actually, it might be necessary to use global extension state (and the fact that it's shared) to implement inter-interpreter communication...

Apart from these points they actually seem to work pretty well and it might be, as you suggest, a "Practical" approach.

Implementing a 'subinterp' module could be interesting...

Indeed. Maybe I'll have a go (in my copious free time :-)) Paul.