classification
Title: asyncio as_completed() thrashes adding and removing callbacks
Type: performance Stage:
Components: Library (Lib) Versions: Python 3.5, Python 3.4
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: Nosy List: glangford, gvanrossum, haypo, pitrou, python-dev, yselivanov
Priority: normal Keywords:

Created on 2014-02-08 20:18 by glangford, last changed 2014-03-17 06:30 by python-dev. This issue is now closed.

Files
File name Uploaded Description Edit
test_thrash.py glangford, 2014-02-08 20:30 Test code
output.txt glangford, 2014-02-08 20:31 Test output (with instrumented code in _wait()
Messages (9)
msg210679 - (view) Author: Glenn Langford (glangford) * Date: 2014-02-08 20:18
In asyncio, tasks.py as_completed() appears to trigger adding and removing callbacks multiple times for the pending set of futures, each time a single future completes. 

For example, to wait for 5 futures which complete at different times:
- as_completed() uses _wait()
- _wait() will add 5 callbacks, one for each future
- when one future completes, a callback is triggered and all 5 callbacks are removed; this is because _wait() was called with FIRST_COMPLETED
- for the 4 remaining futures - 4 callbacks have to be added back again
- when the next future completes, the 4 callbacks are removed
etc…

The worst case is if as_completed() is called to wait for all of a larger number of futures, which complete at different times. For example, with 100 futures worst case, ~10,000 callback adds and removes would be performed.

(I am very new to the asyncio code, so I don't have a patch to offer at this point).
msg210680 - (view) Author: Guido van Rossum (gvanrossum) * (Python committer) Date: 2014-02-08 21:16
Yup, I remember feeling a bit guilty doing it this way, but at least the semantics are correctly, and there were bigger fish to fry. Thanks for the test code that proves the issue!

I assume it can be fixed by not using _wait() but some custom approach. If we get this done by RC2, fine, otherwise we'll just have to documented that this is O(N**2) and not to use it for large numbers of tasks until the fix lands, perhaps in 3.4.1. (Usually there's a solution that avoids as_completed() altogether.)

I've created upstream bug http://code.google.com/p/tulip/issues/detail?id=127 to track this.
msg210683 - (view) Author: Guido van Rossum (gvanrossum) * (Python committer) Date: 2014-02-08 21:41
BTW, just curious: Glenn, what led you to discover this?
msg210690 - (view) Author: Glenn Langford (glangford) * Date: 2014-02-08 22:02
> Glenn, what led you to discover this?

It was found by code inspection. I recently started looking at concurrent.futures, really just curious as to how futures were implemented. Because one of the concurrent.futures bugs I raised also applied to asyncio, I started poking into the source for it as well.
msg210709 - (view) Author: Guido van Rossum (gvanrossum) * (Python committer) Date: 2014-02-09 01:17
I'm looking into a solution for this. The idea is pretty straightforward: http://codereview.appspot.com/61210043.

This needs more code to support the optional timeout feature, and it now returns Futures instead of coroutines (which I think is fine).

But to my surprise, test_as_completed_reverse_wait() failed. After nearly an hour of debugging my own code I realized that this test specifically verifies the following weird behavior: if you get two values (futures/coroutines) out of as_completed() without waiting for either, and then wait for the *second* one, it will wait for the *first* result. I guess this is defensible because it is the first one you wait for, but I find it hard to believe that this is desirable behavior -- even though I wrote the code and the test! (http://code.google.com/p/tulip/source/detail?r=674355412f33.)

So I'd like permission to just change these semantics. They aren't clear from the docs or from PEP 3156, and concurrent.futures.as_completed() doesn't have the same issue (there, __next__() on the iterator blocks until the result is ready).
msg211054 - (view) Author: Guido van Rossum (gvanrossum) * (Python committer) Date: 2014-02-12 04:31
Everyone interested, I plan to push the latest version on view in Rietveld tomorrow: http://codereview.appspot.com/61210043

It's not as drastic a rewrite as my original attempt; Glenn's idea of using a Queue worked out great!
msg211055 - (view) Author: Guido van Rossum (gvanrossum) * (Python committer) Date: 2014-02-12 04:35
Note: The new version does *not* change the semantics as mentioned in msg210709. Nobody should depend on those semantics anyway.
msg211122 - (view) Author: Roundup Robot (python-dev) Date: 2014-02-13 01:58
New changeset 6e04027ed53e by Guido van Rossum in branch 'default':
asyncio: Change as_completed() to use a Queue, to avoid O(N**2) behavior. Fixes issue #20566.
http://hg.python.org/cpython/rev/6e04027ed53e
msg213801 - (view) Author: Roundup Robot (python-dev) Date: 2014-03-17 06:30
New changeset b52113fb58a5 by Guido van Rossum in branch '3.4':
asyncio: Change as_completed() to use a Queue, to avoid O(N**2) behavior. Fixes issue #20566.
http://hg.python.org/cpython/rev/b52113fb58a5
History
Date User Action Args
2014-03-17 06:30:46python-devsetmessages: + msg213801
2014-02-13 01:58:53gvanrossumsetstatus: open -> closed
resolution: fixed
2014-02-13 01:58:31python-devsetnosy: + python-dev
messages: + msg211122
2014-02-12 04:35:18gvanrossumsetmessages: + msg211055
2014-02-12 04:32:25gvanrossumsetmessages: - msg210765
2014-02-12 04:32:07gvanrossumsetmessages: - msg210715
2014-02-12 04:31:46gvanrossumsetmessages: + msg211054
2014-02-09 13:53:54glangfordsetmessages: + msg210765
2014-02-09 03:55:11gvanrossumsetmessages: + msg210715
2014-02-09 01:17:23gvanrossumsetmessages: + msg210709
2014-02-08 22:02:36glangfordsetmessages: + msg210690
2014-02-08 21:41:22gvanrossumsetmessages: + msg210683
2014-02-08 21:27:23yselivanovsetnosy: + yselivanov
2014-02-08 21:16:59gvanrossumsetmessages: + msg210680
2014-02-08 20:31:10glangfordsetfiles: + output.txt
2014-02-08 20:30:01glangfordsetfiles: + test_thrash.py
2014-02-08 20:18:14glangfordcreate