as_completed() calls _create_and_install_waiters() over all given Futures, even if some (or all) of the Futures have already completed.

The following fragment of the as_completed code (from 3.3.3):

with _AcquireFutures(fs):
        finished = set(
                f for f in fs
                if f._state in [CANCELLED_AND_NOTIFIED, FINISHED])
        pending = set(fs) - finished
        waiter = _create_and_install_waiters(fs, _AS_COMPLETED)

installs waiters into Futures contained in fs, rather than pending. 

A more efficient approach might be to only install waiters on the pending subset if necessary. This would be faster and would also result in less dwell time with all of the Future conditions locked via the _AcquireFutures context manager.

Also: waiters are appended with the Future condition lock acquired, but are removed (at the conclusion of as_completed) without the _AcquireFutures condition lock. Is this correct?

See also http://bugs.python.org/issue20319

Uploading proposed new version of as_completed() for review. Note the following changes:

- does not install waiters for Futures which are completed
- locks only one Future at a time to improve concurrency (rather than locking all Futures at once); traverses Futures in the order given, as no need to sort into a canonical order
- immediately yields each completed Future, without waiting to lock and examine other Futures
- fixes locking bug in waiter removal

I attached Glenn's function as a patch.

Comments on as_completed_proposed.patch:

- _create_and_install_waiters() doesn't remove duplicates using set(), so you change the behaving of as_completed(). I don't think that it is correct. as_completed([f, f]) should yield f twice, but I didn't check the current behaviour. Future._waiters is a list and so accept duplicated waiters.

- you replaced the _AcquireFutures context manager on all futures with an individual lock. In my opinion, it should be changed in a different patch. I don't know which option is better, but if it is changed, it should be changed in the whole file.

@Glenn: You should take a look at the Python Developer's Guide to learn how to write a patch and how to contribute to Python ;-)
http://docs.python.org/devguide/

Comments on @Victor's comments - I will have a look at the dev guide.  :-)

I think you have identified another bug in the current code. 

"Future._waiters is a list and so accept duplicated waiters." What this means is that the following code is broken, because it attempts to remove the Future twice from the pending set.

for future in finished:
     yield future
     pending.remove(future)  ## KeyError triggered on as_completed( [f,f] )

See attached test which demonstrates the breakage.

Also, the behaviour of as_completed([f,f]) and wait([f,f], return_when=ALL_COMPLETED) is currently different. wait will only yield f once.

> I think you have identified another bug in the current code.

Please open a separated issue in this case.

> - you replaced the _AcquireFutures context manager on all futures with an >individual lock. In my opinion, it should be changed in a different patch. I >don't know which option is better, but if it is changed, it should be changed >in the whole file.

I can pursue the replacement of _AcquireFutures in a different patch, however I don't necessarily agree that it should be changed in the whole file. as_completed() is different than wait(), since wait() is obligated to return done and notdone Futures, which might require a different implementation. Initially, it may be better to only change as_completed(), where there is a clear concurrency win.