concurrent.futures.as_completed() installs waiters for already completed Futures

[glangford]

BPO	20297
Nosy	@brianquinlan, @mdickinson, @vstinner
Files	as_completed_proposed.py as_completed_proposed.patch test_dupfuture.py

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = None
closed_at = None
created_at = <Date 2014-01-18.21:19:35.870>
labels = ['library', 'performance']
title = 'concurrent.futures.as_completed() installs waiters for already completed Futures'
updated_at = <Date 2014-07-18.16:46:17.165>
user = 'https://bugs.python.org/glangford'

bugs.python.org fields:

activity = <Date 2014-07-18.16:46:17.165>
actor = 'glangford'
assignee = 'none'
closed = False
closed_date = None
closer = None
components = ['Library (Lib)']
creation = <Date 2014-01-18.21:19:35.870>
creator = 'glangford'
dependencies = []
files = ['33590', '33654', '33657']
hgrepos = []
issue_num = 20297
keywords = ['patch']
message_count = 7.0
messages = ['208418', '208593', '208652', '208921', '208942', '208943', '208974']
nosy_count = 3.0
nosy_names = ['bquinlan', 'mark.dickinson', 'vstinner']
pr_nums = []
priority = 'normal'
resolution = None
stage = None
status = 'open'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue20297'
versions = ['Python 3.3', 'Python 3.4']

[glangford]

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?

[glangford]

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

[glangford]

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

[vstinner]

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/

[glangford]

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.

[vstinner]

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

Please open a separated issue in this case.

[glangford]

• 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.

[iritkatriel]

This issue seems to have been abandoned 8 years ago. Shall we close it or is someone planning to work on it?

cc @glangford