The current approach taken in as_completed() and wait() is to immediately lock the entire set of given Futures simultaneously. This limits concurrency, particularly when the number of futures is large, and also requires the complete set of Futures to be known up front.

A different approach is to lock Futures one at a time, as they are given. In the case of as_completed(), completed futures can be yielded immediately. For completed futures, a waiter also does not have to be installed (whereas the current implementation installs waiters for all given Futures, regardless of state).

A demonstration patch is attached which 
- locks Futures one at a time for as_completed() and all variations of wait()
- reduces the overhead in tracking the state of each Future
- makes it easier to add other user APIs if desired later
- consolidates the machinery into a new internal class, reducing the amount of code

Thanks for the patch. This will have to wait for 3.5, since 3.4 is currently in feature freeze stage.

Just a quick comment on the patch: in as_completed(), if the future is cancelled or finished, control is yielded back to the caller with the condition's lock held.
As a general rule, libraries should not yield control to the caller with a lock held, because depending on what the client does, this can lead to a deadlock. 
For example, Future.__repr__() acquires the future's lock: since the current implementation uses a reentrant lock, it won't cause a deadlock if called from the same thread, but it could deadlock e.g. if another thread called a similar method which acquires this lock.
Also, more generally, when you hold an object's lock it's to make sure that it's always seen in a consistent state, and yielding control to the user means that it can potentially see it in an inconsistent state.

See e.g. the excellent "Java Concurrency in Practice", or "Effective Java" for more details.

> if the future is cancelled or finished, control is yielded back to the caller with the condition's lock held.

Hmmm...I don't agree. I assume you are looking at this code:

with f._condition: # Lock the Future; yield if completed or add our Waiter
                if f._state in [CANCELLED_AND_NOTIFIED, FINISHED]:
                    yield f

Note that the context manager will be called in this case to release the lock before f is yielded to the caller.

class MiniContext():
    def __init__(self):
        pass

    def __enter__(self):
        print('Hello')

    def __exit__(self, *args):
        print('Goodbye')

def gen():
	with MiniContext():
		yield 1

print(next(gen()))

prints:

Hello
Goodbye
1

> Note that the context manager will be called in this case to release the
lock before f is yielded to the caller.
>
> class MiniContext():
>     def __init__(self):
>         pass
>
>     def __enter__(self):
>         print('Hello')
>
>     def __exit__(self, *args):
>         print('Goodbye')
>
> def gen():
>         with MiniContext():
>                 yield 1
>
> print(next(gen()))
>
> prints:
>
> Hello
> Goodbye
> 1

Actually, I think what you're seeing here is the context manager being
garbage collected right after the call to next(), and therefore before the
call to print(), because no reference to it is kept. So __exit__() is
called right away.

But if you rewrite it like this:

"""
for e in gen():
    print(e)
"""

You see:
"""
Hello
1
Goodbye
"""

It would be suprising if __exit__() got called before exit of the syntactic
block, just imagine what would happen with the following code:
"""
def read_file(path):
    with open(path) as f:
        for line in f:
            yield line
"""

if the file was closed before yielding.

> Actually, I think what you're seeing here is the context manager being
garbage collected

Yes indeed, I am with you now. Thanks for identifying the problem, and for your explanation. The future should not be yielded while locked.

Updated patch: Fixed bug where quick yield in as_completed() did not release lock on future.

Glenn, are you willing to update your patch to address the review comments?
(I'm assuming you have been notified of them... if not, you can access the code review tool by clicking the "review" links near your patch)

I'm not sure that Glenn receives this, he is not in the nosy list.

2014-07-18 16:45:36	glangford	set	nosy: - glangford

Woops. Thanks for noticing, Claudiu. I guess someone can take over the patch and finish the work, then :-)