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/