On Fri, Nov 6, 2009 at 3:00 PM, Benjamin Peterson <benjamin@python.org> wrote:

2009/11/6 Brian Quinlan <brian@sweetapp.com>:

...

Hey all,

I'd like to propose adding a module/package to Python that makes it easy to parallelize arbitrary function calls.

Your package is less than a year old. It's at version 0.1. We do not normally accept packages into the stdlib until they are considered mature and best of breed in the community. And then only if we feel a need for its functionality in the stdlib.

In Brian's defense, Brett Cannon referred him here (wearing his PEP editor hat -- and I stood by and watched :-). But yeah, it's probably a little early to start proposing this as a stdlib addition. Maybe python-ideas? I do think that having a standard API for this kind of stuff makes some kind of sense. (And no, I don't have any experiencing using Brian's code either. :-) -- --Guido van Rossum (python.org/~guido)

I'm +1 adding something which provides this functionality to the standard library, in fact it's been on my todo list since adding multiprocessing. I actually suggested something like this in private discussions around possible additions to jython for additional concurrency constructs.

That being said, I'll try to carve time off soon to dig into the pep and the implementation.

Have you thought at looking at Twisted and Deferred objects? What's the point of starting from scratch when an existing project has a well-known and well-established API?

Le vendredi 06 novembre 2009 à 19:09 -0500, Jesse Noller a écrit :

...

Have you thought at looking at Twisted and Deferred objects? What's the point of starting from scratch when an existing project has a well-known and well-established API?

Personally; I have. I don't prefer them, but that's my personal taste.

The Twisted Deferred object is a quasi-standard when doing asynchronous programming in Python. The only seriously competing approach AFAICT is generator-based syntaxes (which Twisted also provides on top of Deferreds by the way). Inventing a third idiom just for taste reasons doesn't sound very reasonable. Of course, if the third idiom turns out *really* better in terms of expressiveness then why not.

I'd gladly add this API (or some flavor of it) into multiprocessing, as I do see it as a logical extension to the API itself. Just like multiprocessing has pool/etc

I agree that it can make sense as an additional facility to run parallel tasks (like the shortcut functions in the subprocess or commands modules). It should probably stay minimal then. Regards Antoine.

Looking at the code dist; processing.py is 338 lines, _base.py is 558 and thread.py is 153; it really is a light API on top of threading/multiprocessing. I think most of the line count are doc strings. It's very clean/simple at first glance. Ah this probably answers my question, Jython would just support the

On Fri, Nov 6, 2009 at 7:41 PM, Jesse Noller <jnoller@gmail.com> wrote: threading side. -Frank

On Nov 7, 2009, at 11:43 AM, Frank Wierzbicki wrote:

On Fri, Nov 6, 2009 at 7:41 PM, Jesse Noller <jnoller@gmail.com> wrote:

...

Looking at the code dist; processing.py is 338 lines, _base.py is 558 and thread.py is 153; it really is a light API on top of threading/multiprocessing. I think most of the line count are doc strings. It's very clean/simple at first glance. Ah this probably answers my question, Jython would just support the threading side.

Consolidating the interfaces between threading and multiprocessing was a secondary design goal. Right now multiprocessing is ahead of threading in terms of features. Pool.map() in particular is a pretty powerful idiom that has no equivalent in threading. The Executor ABC provides a consistent interface to both (with .map() :-)). Cheers, Brian

This is the area where I am most worried. Though multiprocessing is a drop in replacement for threading, threading is not currently a drop in replacement for multiprocessing. If multiprocessing doesn't make sense for Jython and we need to tell our users that they should just use threading, threading needs to do everything that multiprocessing does...

Well, feel free to propose a patch for threading.py. I'm not sure this has anything to do with the discussion about futures anyway. Regards Antoine.

On the other hand, possibly pushing futures into a concurrent.* namespace within the standard library means that you could have concurrent.futures, concurrent.map, concurrent.apply and so on, and pull the things which multiprocessing does and threading can as well into that concurrent package. I really like the idea of a concurrent package over adding these

On Sat, Nov 7, 2009 at 10:05 AM, Jesse Noller <jnoller@gmail.com> wrote: things to multiprocessing - I might even be able to get it implemented before CPython since I have some obvious implementation advantages ;) -Frank

2009/11/7 Antoine Pitrou <solipsis@pitrou.net>:

I'm not sure this has anything to do with the discussion about futures anyway.

It's not - unless the suggestion that futures get added into multiprocessing was serious. Personally, I like the idea of a "concurrent" namespace - concurrent.futures seems like an ideal place for the module. Paul.

On Sat, Nov 7, 2009 at 9:42 AM, Frank Wierzbicki <fwierzbicki@gmail.com> wrote:

On Sat, Nov 7, 2009 at 12:29 AM, Brian Quinlan <brian@sweetapp.com> wrote:

...

Right now multiprocessing is ahead of threading in terms of features. Pool.map() in particular is a pretty powerful idiom that has no equivalent in threading. This is the area where I am most worried. Though multiprocessing is a drop in replacement for threading, threading is not currently a drop in replacement for multiprocessing. If multiprocessing doesn't make sense for Jython and we need to tell our users that they should just use threading, threading needs to do everything that multiprocessing does... or maybe there needs to be a higher level package?

The only reason in my view that this is not the case is because no one has submitted a patch, myself included, it's been on my wish list for some time. There is nothing blocking that, AFAIK.

On Nov 7, 2009, at 10:59 AM, Antoine Pitrou wrote:

...

I'm +1 adding something which provides this functionality to the standard library, in fact it's been on my todo list since adding multiprocessing. I actually suggested something like this in private discussions around possible additions to jython for additional concurrency constructs.

That being said, I'll try to carve time off soon to dig into the pep and the implementation.

Have you thought at looking at Twisted and Deferred objects? What's the point of starting from scratch when an existing project has a well-known and well-established API?

Hey Antoine, I'm not an expert in Twisted but I think that Deferreds are looking to solve a slightly different problem. I'm trying to solve the problem of easily parallelizing *synchronous* tasks (using threads of processes). My original use case looked something like this: for source_path in source_paths: for destination_path in destination_paths: DoBlockingNetworkCopy(source_path, destination_path) Which, in my proposed package, could be written as: copies = [] for source_path in source_paths: for destination_path in destination_paths: copies.append(partial(DoBlockingNetworkCopy, source_path, destination_path)) with ThreadPoolExecutor(20) as e: e.run_to_futures(copies, return_when=FIRST_EXCEPTION) Twisted Deferreds represent a fundamentally *asynchronous* operation (e.g. non-blocking I/O). Cheers, Brian

On Fri, Nov 6, 2009 at 8:42 PM, Brian Quinlan <brian@sweetapp.com> wrote:

On Nov 7, 2009, at 10:00 AM, Benjamin Peterson wrote:

...

2009/11/6 Brian Quinlan <brian@sweetapp.com>:

...

Hey all,

I'd like to propose adding a module/package to Python that makes it easy to parallelize arbitrary function calls.

Your package is less than a year old. It's at version 0.1. We do not normally accept packages into the stdlib until they are considered mature and best of breed in the community. And then only if we feel a need for its functionality in the stdlib.

Hey Benjamin,

You were probably looking at an old version - the latest official release is 1.0. But that is, of course, totally arbitrary :-)

I think that building a community around this package would be fairly hard because it is fairly easy to replicate its functionality to solve particular problems.

I don't think that should be a barrier for inclusion of new utility modules though. Consider urlparse, StringIO, etc. They are very useful but I doubt that they would have had much usage if they had been released as third-party modules - everyone would have simply coded the sub-set of the functionality that they needed to address the problem at hand.

Cheers, Brian

I obviously tend to agree with Brian; I know I've personally had to implement things like this plenty of times, it's relatively simple once you do it once or twice. This is a nice bit of syntactic sugar on top of the threading/multiprocessing modules. jesse

On 7 Nov 2009, at 22:06, Paul Moore wrote:

2009/11/7 Jesse Noller <jnoller@gmail.com>:

...

I obviously tend to agree with Brian; I know I've personally had to implement things like this plenty of times, it's relatively simple once you do it once or twice. This is a nice bit of syntactic sugar on top of the threading/multiprocessing modules.

I agree. I've implemented futures a few times, and I'd be very glad not to have to again. I'll certainly check out the package, but I'd like to see the functionality in the stdlib.

I'm not convinced it should go in multiprocessing, though. After all, it uses threading rather than multiple processes.

Actually, you can choose weather to use threads or processes. The current implementation includes a ThreadPoolExecutor and a ProcessPoolExecutor (which is an argument to making it a separate package) and should be abstract enough to accommodate other strategies in the future. Java, for example, Cheers, Brian

On Nov 7, 2009, at 9:03 AM, Paul Moore <p.f.moore@gmail.com> wrote:

2009/11/7 Brian Quinlan <brian@sweetapp.com>:

...

On 7 Nov 2009, at 22:06, Paul Moore wrote:

...

I'm not convinced it should go in multiprocessing, though. After all, it uses threading rather than multiple processes.

Actually, you can choose weather to use threads or processes. The current implementation includes a ThreadPoolExecutor and a ProcessPoolExecutor (which is an argument to making it a separate package) and should be abstract enough to accommodate other strategies in the future.

That's my point. Multiprocessing is about just that - multiprocessing. I wouldn't use it (or even think of looking in it) if I wanted to write a single-process multithreaded program (which is what I usually do on Windows). I was responding to the suggestion that your futures module would work as a component of the multiprocessing package.

Actually, it's a pity that things like the Pool class only exist in multiprocessing. A threaded version of that would be very useful to me as well.

Paul. ______________________________

It's an easily rectified pity. Also, your not the only use case addressed by multiprocessing, which is why stuff you wouldn't use is in there. Jesse

On Sat, Nov 7, 2009 at 9:48 AM, Paul Moore <p.f.moore@gmail.com> wrote:

2009/11/7 Jesse Noller <jnoller@gmail.com>:

...

...

Actually, it's a pity that things like the Pool class only exist in multiprocessing. A threaded version of that would be very useful to me as well.

It's an easily rectified pity. Also, your not the only use case addressed by multiprocessing, which is why stuff you wouldn't use is in there.

I'm not quite sure what you mean there. Are you suggesting that there could be a threading.Pool which mirrors multiprocessing.Pool? If so, then yes I agree - but of course, it wouldn't be available till 2.7/3.2.

What I suppose I was thinking of as a "pity" was that it wasn't already added to threading. I thought multiprocessing was "just" the threading API using multiple processes - but it looks like it's more than that.

See my response to frank: There's nothing blocking this except for: 1> A patch 2> Tests 3> Docs It's been on my wish list for ~2 years now, I might get it done in the next decade. Also, multiprocessing has never been "just" the threading API on top of processes. Part of the PEP for it's inclusion was that it had other items in it of value. jesse

On Nov 7, 2009, at 11:44 AM, Jesse Noller wrote:

On Fri, Nov 6, 2009 at 5:35 PM, Brian Quinlan <brian@sweetapp.com> wrote:

...

Hey all,

I'd like to propose adding a module/package to Python that makes it easy to parallelize arbitrary function calls. I recently wrote a solution for the use case of parallelizing network copies and RPC using threads without forcing the user to explicitly creating thread pools, work queues, etc. I have a concrete implementation that I'll describe below but I'd be happy to hear about other strategies! The basic idea is to implement an asynchronous execution method patterned heavily on java.util.concurrent (but less lame because Python has functions as first-class objects). Here is a fairly advanced example: import futures import functools import urllib.request

URLS = [ 'http://www.foxnews.com/', 'http://www.cnn.com/', 'http://europe.wsj.com/', 'http://www.bbc.co.uk/', 'http://some-made-up-domain.com/']

def load_url(url, timeout): return urllib.request.urlopen(url, timeout=timeout).read()

# Use a thread pool with 5 threads to download the URLs. Using a pool # of processes would involve changing the initialization to: # with futures.ProcessPoolExecutor(max_processes=5) as executor with futures.ThreadPoolExecutor(max_threads=5) as executor: future_list = executor.run_to_futures( [functools.partial(load_url, url, 30) for url in URLS])

# Check the results of each future. for url, future in zip(URLS, future_list): if future.exception() is not None: print('%r generated an exception: %s' % (url, future.exception())) else: print('%r page is %d bytes' % (url, len(future.result())))

In this example, executor.run_to_futures() returns only when every url has been retrieved but it is possible to return immediately, on the first completion or on the first failure depending on the desired work pattern.

The complete docs are here: http://sweetapp.com/futures/

A draft PEP is here: http://code.google.com/p/pythonfutures/source/browse/trunk/PEP.txt

And the code is here: http://pypi.python.org/pypi/futures3/

All feedback appreciated!

Cheers, Brian _______________________________________________ stdlib-sig mailing list stdlib-sig@python.org http://mail.python.org/mailman/listinfo/stdlib-sig

Hey brian; a few things - I think the code looks good, and your docs are really good so far;

Cool, thanks.

but I'd personally like to see tests

The tests live here: http://code.google.com/p/pythonfutures/source/browse/trunk/python3/test_futu... Last time I measured, there was 100% test coverage (it's a crappy metric but an easy one) but I'm not completely happy with them because they use time.sleep() in several places to try to provoke deadlock.

and more examples within the docs. I obviously like the concept/idea, but tests are a must, and more examples in the docs would make it a lot better.

More examples in the docs sound good, I'll work on that. Cheers, Brian

To Antoine's Twisted comment, I don't see a direct comparison. From my understanding Twisted's Deferred objects are ways to have callbacks executed once an async event occurs, not to help execute code concurrently.

Well, waiting for concurrently executing code to terminate *is* a case of waiting for an async event to happen. Deferred objects are a generic mechanism to chain reactions to termination or failure of code. Whether the event your Deferred reacts to is "async" or not is really a matter of how you use it (and of how you define "async" -- perhaps you meant "I/O" but Deferreds are not specialized for I/O). Regards Antoine.

Hello,

They do seem specialized for continuation-passing style programming though. As far as I can tell from the docs (http://python.net/crew/mwh/apidocs/twisted.internet.defer.Deferred.html ), the only way to process the results of a Deferred is my installing a callback.

Yes, but the last callback in the chain could trigger an Event, a Queue or any other synchronization object to which you could wait on, if you want something "synchronous" (despite the title of your original message: "asynchronous execution" :-)).

with ThreadedDeferredMaker(max_threads=5) as dm deferreds = [] for url in URLS: deferred = dm.defer(load_url, url) deferred. addCallbacks(print_success, print_failure, url=url) deferred.unpause() deferreds.append(deferred)

If you have a bunch of deferreds and want your callback to trigger when all deferreds are finished/failed, you can use a DeferredList. A DeferredList is itself a Deferred so you can add callbacks to it (including one which makes things synchronous as explained above). http://twistedmatrix.com/documents/8.1.0/api/twisted.internet.defer.Deferred... (note that, as the doc says, "that you can still use a Deferred after putting it in a DeferredList". That is, you can react individually to each result to implement e.g. a progress indicator, and also react to the completion of all deferreds) Of course an all-synchronous API is still simpler to use for the use cases it is meant for. Regards Antoine.

On Fri, Nov 6, 2009 at 8:12 PM, Brett Cannon <brett@python.org> wrote:

[I am going to be lazy and mass reply to people with a top-post; you can burn an effigy of me later]

In response to Guido, yes, I sent Brian here with my PEP editor hat on. Unfortunately the hat was on rather firmly and I totally forgot to check to see how old the code is. Yet another reason I need to get the Hg conversion done so I can start writing a "Adding to the Stdlib" PEP.

Want to start the skeleton and we can fill in the blanks as needed? :) I vote for "The Getting Your Pony into Python" PEP.

To Antoine's Twisted comment, I don't see a direct comparison. From my understanding Twisted's Deferred objects are ways to have callbacks executed once an async event occurs, not to help execute code concurrently. So I don't see enough similarity to discount the idea Brian is pushing forward.

It's also significantly less code than many existing solutions; it's really light when compared to those as well.

As for Benjamin's one year reminder, since I don't see this happening in time for Python 3.2a1 it isn't a major worry right now. That means this won't land until Python 3.3, which gives everyone time until that alpha which would probably be June 2011. So that would give Brian (and Jesse if he gets involved like it sounds he will) time to work out the API, get public feedback, and get the code checked in. The only way I would feel comfortable letting this in past 3.2a1 would be if it landed before 3.2a4, Jesse personally shuttled it through, and started work in it now and REALLY pushed it. But as he knows from personal experience, rushing a module into the stdlib can bite you in the ass. =)

I don't want to rush it; I think with tests and more examples and a run through the python-ideas and -dev spin cycles, it's small enough (and consumable enough) to get into the 3.2 stream. But just to stress, I'm really not interested in rushing it, I just don't see it as something as "big" and potentially as big a disruption as multiprocessing was. Again, I consider this more akin to the addition of the same API just added to the threading or multiprocessing modules. My pony list for both of those have been built in producer/consumer pools, things like this, more context manager things, etc. Build on the modules to implement common constructs.

But I really do like the idea. With java.util.concurrent and Grand Central Dispatch out there, I think it shows some demand for a way to easily abstract out concurrency management stuff and leave it up to a library.

Making it eas(y)(ier), safer and simple would be nice. There's plenty of tried and true patterns out there that just make sense and that plenty of people implement so frequently that they just sort of scream (to me, I might be in the minority) for inclusion in the relevant modules. Who knows, this could be the start of python.concurrent :) jesse

On Sat, Nov 7, 2009 at 9:53 AM, Antoine Pitrou <solipsis@pitrou.net> wrote:

Le vendredi 06 novembre 2009 à 21:20 -0500, Jesse Noller a écrit :

...

...

But I really do like the idea. With java.util.concurrent and Grand Central Dispatch out there, I think it shows some demand for a way to easily abstract out concurrency management stuff and leave it up to a library.

Making it eas(y)(ier), safer and simple would be nice.

I agree with that. From a quick look at the API it seems it deserves simplifying and polishing.

Regards

Antoine.

Which API? My comment wasn't aimed at the API of the package - in the time I got to scan it last night nothing jumped out at me as overly offensive API-wise.

On Sat, Nov 7, 2009 at 10:21 AM, Antoine Pitrou <solipsis@pitrou.net> wrote:

...

Which API? My comment wasn't aimed at the API of the package - in the time I got to scan it last night nothing jumped out at me as overly offensive API-wise.

Not offensive, but probably too complicated if it's meant to be a simple helper. Anyway, let's wait for the PEP.

The PEP is right here: http://code.google.com/p/pythonfutures/source/browse/trunk/PEP.txt I'm interested in hearing specific complaints about the API in the context of what it's trying to *do*. The only thing which jumped out at me was the number of methods on FutureList; but then again, each one of those makes conceptual sense, even if they are verbose - they're explicit on what's being done. jesse

On 8 Nov 2009, at 03:13, Antoine Pitrou wrote:

...

The PEP is right here:

http://code.google.com/p/pythonfutures/source/browse/trunk/PEP.txt

I'm interested in hearing specific complaints about the API in the context of what it's trying to *do*. The only thing which jumped out at me was the number of methods on FutureList;

Yes that would be the first complaint. Then many of those methods are as (un)trustable as, say, Queue.qsize().

An example : """`done_futures()`

Return an iterator over all `Future` instances that completed or were cancelled."""

First, it claims to return an iterator but the internal container could mutate while iterating (since it can be mutated when a task terminates in another thread). So the API looks broken with respect to what the semantics dictate. It should probably return a distinct container (list or set) instead. Second, by the time the result is processed by the caller, there's no way to know if the information is still valid or not. It's entirely speculative, which makes it potentially deceiving -- and should be mentioned in the doc.

"""`has_done_futures()`

Return `True` if any `Future` in the list has completed or was successfully cancelled."""

Same problem. Please note that it can be removed if `done_futures()` returns a container, since you then just have to do a boolean check on the container (that would remove 5 methods :-)).

Then about the Future API itself. I would argue that if we want it to be a simple helper, it should be as simple to use as a weakref.

That is, rather than :

"""`result(timeout=None)`

Return the value returned by the call. [...]

`exception(timeout=None)`

Return the exception raised by the call."""

Make the object callable, such as `future(timeout=None)` either returns the computed result (if successful), raises an exception (if failed) or raises a TimeoutError.

Then about the Executor API. I don't understand why we have the possibility to wait on a FutureList *and* on the Executor's run_to_results() method. I think all wait-type methods should be folded in to the Future or FutureList API, and the Executor should only generate that Future(List).

Practically, there should be two ways to wait for multiple results, depending on whether you need the results ordered or not. In the web crawling situation given as example, it is silly to wait for the results in order rather than process each result as soon as it gets available. (*)

I don't understand why the Executor seems to be used as a context manager in the examples. Its resources are still alive after the "with" since the tasks are still executin, so it can't possibly have cleaned up anything, has it?

The executor needs to know when no more futures will be scheduled so it can shutdown its thread/process pool after it has finished the current work items. Let me think about your other comments for a while. Cheers, Brian

(*) And, of course, you start to understand why a callback-based API such as Deferreds makes a lot of sense...

Regards

Antoine.

_______________________________________________ stdlib-sig mailing list stdlib-sig@python.org http://mail.python.org/mailman/listinfo/stdlib-sig

On Sat, Nov 7, 2009 at 7:32 AM, Jesse Noller <jnoller@gmail.com> wrote:

On Sat, Nov 7, 2009 at 10:21 AM, Antoine Pitrou <solipsis@pitrou.net> wrote:

...

...

Which API? My comment wasn't aimed at the API of the package - in the time I got to scan it last night nothing jumped out at me as overly offensive API-wise.

Not offensive, but probably too complicated if it's meant to be a simple helper. Anyway, let's wait for the PEP.

The PEP is right here:

http://code.google.com/p/pythonfutures/source/browse/trunk/PEP.txt

I'm interested in hearing specific complaints about the API in the context of what it's trying to *do*. The only thing which jumped out at me was the number of methods on FutureList; but then again, each one of those makes conceptual sense, even if they are verbose - they're explicit on what's being done.

Overall, I like the idea of having futures in the standard library, and I like the idea of pulling common bits of multiprocessing and threading into a concurrent.* package. Here's my stream-of-consciousness review of the PEP. I'll try to ** things that really affect the API. The "Interface" section should start with a conceptual description of what Executor, Future, and FutureList are. Something like "An Executor is an object you can hand tasks to, which will run them for you, usually in another thread or process. A Future represents a task that may or may not have completed yet, and which can be waited for and its value or exception queries. A FutureList is ... <haven't read that far>." ** The Executor interface is pretty redundant, and it's missing the most basic call. Fundamentally, all you need is an Executor.execute(callable) method returning None, and all the future-oriented methods can be built on top of that. I'd support using Executor.submit(callable) for the simplest method instead, which returns a Future, but there should be some way for implementers to only implement execute() and get submit either for free or with a 1-line definition. (I'm using method names from http://java.sun.com/javase/6/docs/api/java/util/concurrent/ExecutorService.h... in case I'm unclear about the semantics here.) run_to_futures, run_to_results, and map should be implementable on top of the Future interface, and shouldn't need to be methods on Executor. I'd recommend they be demoted to helper functions in the concurrent.futures module unless there's a reason they need to be methods, and that reason should be documented in the PEP. ** run_to_futures() shouldn't take a return_when argument. It should be possible to wait for those conditions on any list of Futures. (_not_ just a FutureList) The code sample looks like Executor is a context manager. What does its __exit__ do? shutdown()? shutdown&awaitTermination? I prefer waiting in Executor.__exit__, since that makes it easier for users to avoid having tasks run after they've cleaned up data those tasks depend on. But that could be my C++ bias, where we have to be sure to free memory in the right places. Frank, does Java run into any problems with people cleaning things up that an Executor's tasks depend on without awaiting for the Executor first? shutdown should explain why it's important. Specifically, since the Executor controls threads, and those threads hold a reference to the Executor, nothing will get garbage collected without the explicit call. ** What happens when FutureList.wait(FIRST_COMPLETED) is called twice? Does it return immediately the second time? Does it wait for the second task to finish? I'm inclined to think that FutureList should go away and be replaced by functions that just take lists of Futures. In general, I think the has_done_futures(), exception_futures(), etc. are fine even though their results may be out of date by the time you inspect them. That's because any individual Future goes monotonically from not-started->running->(exception|value), so users can take advantage of even an out-of-date done_futures() result. However, it's dangerous to have several query functions, since users may think that running_futures() `union` done_futures() `union` cancelled_futures() covers the whole FutureList, but instead a Future can move between two of the sets between two of those calls. Instead, perhaps an atomic partition() function would be better, which returns a collection of sub-lists that cover the whole original set. I would rename result() to get() (or maybe Antoine's suggestion of __call__) to match Java. I'm not sure exception() needs to exist. --- More general points --- ** Java's Futures made a mistake in not supporting work stealing, and this has caused deadlocks at Google. Specifically, in a bounded-size thread or process pool, when a task in the pool can wait for work running in the same pool, you can fill up the pool with tasks that are waiting for tasks that haven't started running yet. To avoid this, Future.get() should be able to steal the task it's waiting on out of the pool's queue and run it immediately. ** I think both the Future-oriented blocking model and the callback-based model Deferreds support are important for different situations. Futures tend to be easier to program with, while Deferreds use fewer threads and can have more predictable latencies. It should be possible to create a Future from a Deferred or a Deferred from a Future without taking up a thread.

On Thu, Nov 12, 2009 at 9:19 PM, Brian Quinlan <brian@sweetapp.com> wrote:

On Nov 8, 2009, at 6:37 AM, Jeffrey Yasskin wrote:

...

--- More general points ---

** Java's Futures made a mistake in not supporting work stealing, and this has caused deadlocks at Google. Specifically, in a bounded-size thread or process pool, when a task in the pool can wait for work running in the same pool, you can fill up the pool with tasks that are waiting for tasks that haven't started running yet. To avoid this, Future.get() should be able to steal the task it's waiting on out of the pool's queue and run it immediately.

Hey Jeff,

I understand the deadlock possibilities of the executor model, could you explain your proposal would work?

Would it be some sort of flag on the Future.get method e.g. Future.get(timeout=None, immediate_execution=False)?

I don't think a flag is the way to go at first glance, although there could be upsides I haven't thought of. Here's what I had in mind: After I call "fut = executor.submit(task)", the task can be in 3 states: queued, running, and finished. The simplest deadlock happens in a 1-thread pool when the running thread calls fut.result(), and the task is queued on the same pool. So instead of just waiting for the task to finish running, the current thread atomically(checks what state it's in, and if it's queued, marks it as stolen instead) and calls it in the current thread. When a stolen task gets to the front of its queue and starts running, it just acts like a no-op. This can't introduce any new lock-order deadlocks, but it can be observable if the task looks at thread-local variables.

On Thu, Nov 12, 2009 at 10:13 PM, Brian Quinlan <brian@sweetapp.com> wrote:

On Nov 13, 2009, at 4:27 PM, Jeffrey Yasskin wrote:

...

On Thu, Nov 12, 2009 at 9:19 PM, Brian Quinlan <brian@sweetapp.com> wrote:

...

On Nov 8, 2009, at 6:37 AM, Jeffrey Yasskin wrote:

...

--- More general points ---

** Java's Futures made a mistake in not supporting work stealing, and this has caused deadlocks at Google. Specifically, in a bounded-size thread or process pool, when a task in the pool can wait for work running in the same pool, you can fill up the pool with tasks that are waiting for tasks that haven't started running yet. To avoid this, Future.get() should be able to steal the task it's waiting on out of the pool's queue and run it immediately.

Hey Jeff,

I understand the deadlock possibilities of the executor model, could you explain your proposal would work?

Would it be some sort of flag on the Future.get method e.g. Future.get(timeout=None, immediate_execution=False)?

I don't think a flag is the way to go at first glance, although there could be upsides I haven't thought of. Here's what I had in mind:

After I call "fut = executor.submit(task)", the task can be in 3 states: queued, running, and finished. The simplest deadlock happens in a 1-thread pool when the running thread calls fut.result(), and the task is queued on the same pool. So instead of just waiting for the task to finish running, the current thread atomically(checks what state it's in, and if it's queued, marks it as stolen instead) and calls it in the current thread. When a stolen task gets to the front of its queue and starts running, it just acts like a no-op.

This can't introduce any new lock-order deadlocks, but it can be observable if the task looks at thread-local variables.

So you have something like this:

def Future.result(self, timeout=None):  with some_lock:  # would have to think about locking here    do_work_locally =  (threading.current_thread in self._my_executor.threads and        self._my_executor.free_threads == 0 and        timeout is None):

You can deadlock from a cycle between multiple pools, too, so it's probably a bad idea to limit it to only steal if self is one of the pool's threads, and there's no real reason to limit the stealing to when there are exactly 0 waiting threads. Depending on the internal implementation, Future.result() might look something like (untested, sorry if there are obvious bugs): class Future: def __init__(self, f, args, kwargs): self.f, self.args, self.kwargs = f, args, kwargs self.state, self.lock = QUEUED, Executor.Lock() def run(self): with self.lock: if self.state != QUEUED: return self.state = RUNNING self._result = self.f(*self.args, **self.kwargs) with self.lock: self.state = DONE self.notify() def result(self, timeout=None): if timeout is None: # Good catch. self.run() self.wait(timeout) return self._result

That's pretty clever. Some things that I don't like: 1. it might only be applicable to executors using a thread pool so people    shouldn't count on it (but maybe only thread pool executors have this    deadlock problem so it doesn't matter?)

Process pools have the same deadlock problem, unless it's impossible for a task in a process pool to hold a reference to the same pool, or another pool whose tasks have a reference to the first one?

2. it makes the implementation of Future dependent on the executor that     created it - but maybe that's OK too, Future can be an ABC and     executor implementations that need customer Futures can subclass it

It makes some piece dependent on the executor, although not necessarily the whole Future. For example, the run() method above could be wrapped into a Task class that only knows how to mark work stolen and run stuff locally.