call_at/call_later with Timer cancellation can result in (practically) unbounded memory usage

This patch is intended to fix http://bugs.python.org/issue22448. Option b) was implemented. The measure to indicate that scheduled event filtering (to remove cancelled events) needs to be performed is 1) There are at least 100 events scheduled. This prevents needless reheapifying if there are only a handful of events. 2) More than 50% of scheduled events are cancelled. The use of a percentage ensures that a list of 10,000 events isn't reheaped for some small fixed number of cancelled events. Otherwise 50% was just chosen as it seemed a reasonable measure. Note that _cancel_count is not always completely accurate, nor does it need to be: - It may be possible for events that are _ready to be cancelled, and it may be possible for race conditions to occur if two threads are cancelling the same timer handle at the same time. - Other threads may cancel events while _scheduled events are being rebuilt. Note that I added a condition (events.py) to avoid repeated cancellation messing up the _cancel_count. Once I added that, I thought it would make sense to include the rest of the method in the condition. This has the added benefit of the string representation of the arguments not getting wiped on repeated cancellation. test_base_events.py and test_events.py were both updated to test these changes.

[yselivanov, 2014-09-20 22:42:44]

https://codereview.appspot.com/145220043/diff/110001/asyncio/base_events.py File asyncio/base_events.py (right): https://codereview.appspot.com/145220043/diff/110001/asyncio/base_events.py#n... asyncio/base_events.py:148: self._cancel_count = 0 Maybe we can come up with a bit more descriptive name? https://codereview.appspot.com/145220043/diff/110001/asyncio/base_events.py#n... asyncio/base_events.py:995: if sched_count > 100 and self._cancel_count / sched_count > 0.5: 100 and 0.5 should be constants defined somewhere on top of the file. Also, while I understand what you want to do with the second check (cleanup only when 50% of tasks are cancelled), I'm not sure it's such a good idea. I would just set the threshold to a bit higher number (say 1000) and cleanup the queue every time we hit it. After all, it takes python about 50ms to rebuild a list of 1000000 items.

[chatgris, 2014-09-20 23:00:42]

On 2014/09/20 22:42:44, yselivanov wrote: > https://codereview.appspot.com/145220043/diff/110001/asyncio/base_events.py > File asyncio/base_events.py (right): > > https://codereview.appspot.com/145220043/diff/110001/asyncio/base_events.py#n... > asyncio/base_events.py:148: self._cancel_count = 0 > Maybe we can come up with a bit more descriptive name? self._cancelled_count = 0 ? Anything much more descriptive would be a fairly long name. I haven't thought of anything better, any ideas? > > https://codereview.appspot.com/145220043/diff/110001/asyncio/base_events.py#n... > asyncio/base_events.py:995: if sched_count > 100 and self._cancel_count / > sched_count > 0.5: > 100 and 0.5 should be constants defined somewhere on top of the file. No problem doing this, but will wait until the following is resolved before I do. > > Also, while I understand what you want to do with the second check (cleanup only > when 50% of tasks are cancelled), I'm not sure it's such a good idea. I would > just set the threshold to a bit higher number (say 1000) and cleanup the queue > every time we hit it. After all, it takes python about 50ms to rebuild a list of > 1000000 items. I understand your reasoning, but I strongly disagree. Taking just 1,000,000 - If it takes 50ms to rebuild the 1,000,000 list, which would be built as the result of 500,000 active events and 500,000 cancelled events. i) The current algorithm would take 50ms if there were 500,000 uncancelled events. ii) The proposed change (static of 1000) would take ~ 500 * 25ms == 12.5 seconds!!! Explanation: - Once the system got to a steady state of 500,000 uncancelled events (and 1M == 50ms, 0.5M == 25ms) every time 1000 events were cancelled, a 25ms penalty would be paid. IMO, a core element such as an event scheduler should never be O(N) (which it still is with a static limit).

[GvR, 2014-09-21 02:30:59]

Thanks, this is a good start. Some remarks in addition to Yuri's review: - You are effectively adding a new interface to the event loop class. It is legal to implement a new event loop that derives from AbstractEventLoop but not from BaseEventLoop. So you either have to add _handle_cancelled to AbstractEventLoop (so people know that they have to implement it), or you have to check whether it exists before calling it. - The _scheduled list can only contain TimerHandle instances; I think the _handle_cancelled call should be made in that class's cancel() method, so you don't count cancellations of immediate callbacks. - I'm in agreement with you that we should avoid O(N) behavior and I like your current approach to rebuild at a fixed percentage. I'm not sure how to tune the percentage at which we decide to rebuild. Note that the heapify() call contributes way more than the list comprehension. - You are overcounting cancelled events -- calling cancel() after the callback has already run is common, e.g. sleep() does this. But I'm not sure of the best way to avoid this. Setting _cancelled when the callback is run feels wrong (it affects the repr) and Handle objects may be run multiple times (when used as I/O callbacks). Maybe a separate flag that only TimerHandle instances have. But you could still overcount, as the TimerHandle is transferred from _scheduled to _ready once it is due, but it may still be cancelled before it gets run. Perhaps none of this matters.

[chatgris, 2014-09-21 18:57:29]

On 2014/09/21 02:30:59, GvR wrote: > Thanks, this is a good start. Some remarks in addition to Yuri's review: On the topic of Yuri's review: Constants were defined at the top of the file. Renaming has become less of a concern since I have pulled the scheduled logic into a separate class (details below), and all names are now relative to that class. > > - You are effectively adding a new interface to the event loop class. It is > legal to implement a new event loop that derives from AbstractEventLoop but not > from BaseEventLoop. So you either have to add _handle_cancelled to > AbstractEventLoop (so people know that they have to implement it), or you have > to check whether it exists before calling it. I have added the cancelled callback to AbstractEventLoop. > > - The _scheduled list can only contain TimerHandle instances; I think the > _handle_cancelled call should be made in that class's cancel() method, so you > don't count cancellations of immediate callbacks. Done. Additionally, I have renamed the method to _timer_handle_cancelled > > - I'm in agreement with you that we should avoid O(N) behavior and I like your > current approach to rebuild at a fixed percentage. I'm not sure how to tune the > percentage at which we decide to rebuild. Note that the heapify() call > contributes way more than the list comprehension. No ideas on how to tune the percentage. 50% was chosen simply on the heuristic "If there are more cancelled events than non-cancelled events, it's probably time to clean". > > - You are overcounting cancelled events -- calling cancel() after the callback > has already run is common, e.g. sleep() does this. But I'm not sure of the best > way to avoid this. Setting _cancelled when the callback is run feels wrong (it > affects the repr) and Handle objects may be run multiple times (when used as I/O > callbacks). Maybe a separate flag that only TimerHandle instances have. But > you could still overcount, as the TimerHandle is transferred from _scheduled to > _ready once it is due, but it may still be cancelled before it gets run. > Perhaps none of this matters. The algorithm will still function correctly if the count was off, but it will affect performance especially with the cancel semantics of sleep. It could be handled by tracking whether the TimerHandle is in the _scheduled list or not. If we can track that, then on cancellation if the handle is in _scheduled we alter the count, otherwise we ignore the cancellation. I made a fairly major change to the code, to include two different ways we could track that. Additionally, since in some cases it resulted in keeping 3 variables in sync, I made separate SchedBy* classes. (This was a bit of a pain since the unit tests expect direct access to a list when testing, but I made it work at least for the purposes of demonstration. We could always pull all variables back into BaseEventLoop and discard the classes if that is preferred, or we could alter the tests and get rid of a lot of the methods in the SchedBy* classes that are marked "for testing purposes only"). You can flip between the two types by editing lines 301 and 302 in base_events.py. SchedByFlag uses a _scheduled flag in TimerHandle that it modifies to track whether it is in the _scheduled list or not. SchedBySet uses a set to keep track of what exists in the _scheduled list and what does not. Note that _scheduled would be removed from TimerHandle if this algorithm was chosen as it is not needed. Finally, note it is very likely these SchedBy* classes are buggy. No testing has been done yet, they exist merely for demonstration of the concept. And I would probably rename the classes too if we decide to use a separate class and one was deleted. Looking forward to feedback.

[chatgris, 2014-09-21 18:59:03]

Note: Apologies for the terrible formatting of my last post, I didn't realize it automatically breaks lines.

[GvR, 2014-09-22 18:14:30]

On 2014/09/21 18:59:03, chatgris wrote: > Note: Apologies for the terrible formatting of my last post, I didn't realize it > automatically breaks lines. Well, if you *do* want to break lines, break them around 72 chars, then you'll be safe. :-) Anyway, let's look at the various proposed solutions: (A) over-count cancellations when cancel() happens to a handle that's not scheduled, like in your original proposal (B) track whether a handle is in the scheduled queue (B1) using a flag in each timer handle (B2) using a separate set of scheduled timer handles I don't think B2 is needed -- the TimerHandle class is ours to modify, and having an extra field in every instance takes up less space than the space required for the set, *unless* the percentage of cancelled timer handles is under 25% or so. (Back-of-the-envelop calculation after observing that the memory taken by a set of N elements is around 32 bytes per element, i.e. 4 pointers -- the extra slot only costs one pointer per timer handle.) The set version is also always slower and takes more code. So IMO the contest is between (A) and (B1). Your current version of B1 looks pretty clunky -- perhaps you can inline it? There are really only very few choke points -- timer handles are only placed in the scheduled queue by call_at() and _add_callback(), and only removed by _run_once() (inn two different places). (Plus, I think _add_callback() should never be called with a TimerHandle argument. There's a test for this, but it's an internal method and none of the call sites should ever create a TimerHandle. I think these things are all relics from earlier designs.) I'll refrain from more in-detail review until you've got a new version up. FWIW, we've now missed the 3.4.2 release candidate and I think this is too much new stuff to sneak into a release at the last moment, so there's less time pressure.

[chatgris, 2014-09-23 16:32:23]

On 2014/09/22 18:14:30, GvR wrote: > On 2014/09/21 18:59:03, chatgris wrote: > > Note: Apologies for the terrible formatting of my last post, I didn't realize > it > > automatically breaks lines. > > Well, if you *do* want to break lines, break them around 72 chars, then you'll > be safe. :-) > > Anyway, let's look at the various proposed solutions: > > (A) over-count cancellations when cancel() happens to a handle that's not > scheduled, like in your original proposal > (B) track whether a handle is in the scheduled queue > (B1) using a flag in each timer handle > (B2) using a separate set of scheduled timer handles > > I don't think B2 is needed -- the TimerHandle class is ours to modify, and > having an extra field in every instance takes up less space than the space > required for the set, *unless* the percentage of cancelled timer handles is > under 25% or so. (Back-of-the-envelop calculation after observing that the > memory taken by a set of N elements is around 32 bytes per element, i.e. 4 > pointers -- the extra slot only costs one pointer per timer handle.) The set > version is also always slower and takes more code. > > So IMO the contest is between (A) and (B1). We could tune the % cleanup to be 25% to keep memory usage down for (B2). IMO, the contest is between (B1) and (B2), because if (B2) is being rejected due to performance, then (A) should be rejected as well (due to the increased frequency of heapq.heapify). > Your current version of B1 looks > pretty clunky -- perhaps you can inline it? There are really only very few > choke points -- timer handles are only placed in the scheduled queue by > call_at() and _add_callback(), and only removed by _run_once() (inn two > different places). (B1) has been inlined in the latest patch set. > > (Plus, I think _add_callback() should never be called with a TimerHandle > argument. There's a test for this, but it's an internal method and none of the > call sites should ever create a TimerHandle. I think these things are all relics > from earlier designs.) Well, I'm happy to remove the "if isinstance(handle, events.TimerHandle):" block if you'd like me to from _add_callback(). Based on your reasoning it appears that it is redundant.

[yselivanov, 2014-09-23 16:56:05]

The patch is getting better and better! I'm +1 for B1 strategy you guys have decided upon. Below are some nits and suggestions. https://codereview.appspot.com/145220043/diff/150001/asyncio/base_events.py File asyncio/base_events.py (right): https://codereview.appspot.com/145220043/diff/150001/asyncio/base_events.py#n... asyncio/base_events.py:45: _MIN_SCHEDULED_HANDLES = 100 I'd prefer to see TIMER word in these names too. https://codereview.appspot.com/145220043/diff/150001/asyncio/base_events.py#n... asyncio/base_events.py:155: self._cancelled_count = 0 How about _timer_cancelled_count? https://codereview.appspot.com/145220043/diff/150001/asyncio/base_events.py#n... asyncio/base_events.py:1002: heapq.heappop(self._scheduled)._scheduled = False I'd split this line in two. https://codereview.appspot.com/145220043/diff/150001/asyncio/base_events.py#n... asyncio/base_events.py:1007: and self._cancelled_count / sched_count > _MIN_CANCELLED_HANDLES_PCT): This indent looks shaggy... https://codereview.appspot.com/145220043/diff/150001/asyncio/base_events.py#n... asyncio/base_events.py:1056: handle._scheduled = False Maybe we should add a method to TimerHandle for True/False flips? scheduled()/unscheduled()? https://codereview.appspot.com/145220043/diff/150001/asyncio/events.py File asyncio/events.py (right): https://codereview.appspot.com/145220043/diff/150001/asyncio/events.py#newcod... asyncio/events.py:249: def _timer_handle_cancelled(self, handle): A docstring here would be nice. https://codereview.appspot.com/145220043/diff/150001/tests/test_base_events.py File tests/test_base_events.py (right): https://codereview.appspot.com/145220043/diff/150001/tests/test_base_events.p... tests/test_base_events.py:321: for x in range(50): It would also be great if you can tie your tests logic to the new constants you have defined (as somebody may go and tweak them later), not numbers.

[GvR, 2014-09-23 17:07:04]

I'm with Yuri's comments (except where I explicitly disagree :-). Here are some nits. https://codereview.appspot.com/145220043/diff/150001/asyncio/base_events.py File asyncio/base_events.py (right): https://codereview.appspot.com/145220043/diff/150001/asyncio/base_events.py#n... asyncio/base_events.py:49: _MIN_CANCELLED_HANDLES_PCT = 0.5 It is not a percentage (that would be 50), it's a fraction. https://codereview.appspot.com/145220043/diff/150001/asyncio/base_events.py#n... asyncio/base_events.py:976: if isinstance(handle, events.TimerHandle): Fine to replace this with assert not isinstance(handle, events.TimerHandle). You also have to delete the one test that tests this. https://codereview.appspot.com/145220043/diff/150001/asyncio/base_events.py#n... asyncio/base_events.py:1004: # Remove delayed calls that were cancelled if their number is too high I suggest move this before the preceding while-loop. In the case where we decide to re-heapify, any effort spent on popping cancelled items from the front is wasted. https://codereview.appspot.com/145220043/diff/150001/asyncio/base_events.py#n... asyncio/base_events.py:1056: handle._scheduled = False On 2014/09/23 16:56:04, yselivanov wrote: > Maybe we should add a method to TimerHandle for True/False flips? > scheduled()/unscheduled()? I don't think so. The event loop already reaches into *Handle instances; the only public method is cancel() which is for the app, not for internal use. https://codereview.appspot.com/145220043/diff/150001/asyncio/events.py File asyncio/events.py (right): https://codereview.appspot.com/145220043/diff/150001/asyncio/events.py#newcod... asyncio/events.py:188: You don't need this blank line. https://codereview.appspot.com/145220043/diff/150001/tests/test_events.py File tests/test_events.py (right): https://codereview.appspot.com/145220043/diff/150001/tests/test_events.py#new... tests/test_events.py:1900: '<Handle cancelled noop(1, 2) at %s:%s created at %s:%s>' This line is too long.

[chatgris, 2014-09-23 18:14:25]

Added new patch set to fix nits, will reply to a few specific issues in two replies. On 2014/09/23 16:56:05, yselivanov wrote: > https://codereview.appspot.com/145220043/diff/150001/asyncio/base_events.py#n... > asyncio/base_events.py:1007: and self._cancelled_count / sched_count > > _MIN_CANCELLED_HANDLES_PCT): > This indent looks shaggy... prefixing the and was my attempt to resolve this issue in pep8 "When the conditional part of an if-statement is long enough to require that it be written across multiple lines, it's worth noting that the combination of a two character keyword (i.e. if), plus a single space, plus an opening parenthesis creates a natural 4-space indent for the subsequent lines of the multiline conditional. This can produce a visual conflict with the indented suite of code nested inside the if-statement, which would also naturally be indented to 4 spaces. " However, it has been changed as your request. > https://codereview.appspot.com/145220043/diff/150001/tests/test_base_events.p... > tests/test_base_events.py:321: for x in range(50): > It would also be great if you can tie your tests logic to the new constants you > have defined (as somebody may go and tweak them later), not numbers. This is done. Note on line 303 I added # This test is invalid if _MIN_SCHEDULED_TIMER_HANDLES is too low self.assertLessEqual(cancelled_count + not_cancelled_count, base_events._MIN_SCHEDULED_TIMER_HANDLES) Since unittest doesn't have assertInconclusive, and I wanted at least 2 of each type to ensure that looping was performed (as opposed to a single removal) I have effectively added a lower limit of 5 to base_events._MIN_SCHEDULED_TIMER_HANDLES for the purposes of the test.

[chatgris, 2014-09-23 18:16:54]

> https://codereview.appspot.com/145220043/diff/150001/asyncio/base_events.py#n... > asyncio/base_events.py:1004: # Remove delayed calls that were cancelled if their > number is too high > I suggest move this before the preceding while-loop. In the case where we decide > to re-heapify, any effort spent on popping cancelled items from the front is > wasted. Additionally, I have moved it to the else portion of the if statement, as if the statement had already run, it should not be possible to have a cancelled event at the head of the queue. > https://codereview.appspot.com/145220043/diff/150001/tests/test_events.py#new... > tests/test_events.py:1900: '<Handle cancelled noop(1, 2) at %s:%s created at > %s:%s>' > This line is too long. I have also fixed the previous statement I copied it from for consistency.

[chatgris, 2014-09-23 18:43:27]

I just realized that the tests I changed to tie into the new constants is incorrect. Please hold while I fix them.

[chatgris, 2014-09-23 19:20:40]

On 2014/09/23 18:43:27, chatgris wrote: > I just realized that the tests I changed to tie into the new constants is > incorrect. Please hold while I fix them. This should now be fixed.

[yselivanov, 2014-09-23 19:41:02]

Looks good, aside from just couple of really small notes. I also like how you refactored your unittest, now it's much easier to follow. https://codereview.appspot.com/145220043/diff/160005/asyncio/base_events.py File asyncio/base_events.py (right): https://codereview.appspot.com/145220043/diff/160005/asyncio/base_events.py#n... asyncio/base_events.py:44: # cancelled handles is performed Please add '.' at the end of the sentence. https://codereview.appspot.com/145220043/diff/160005/asyncio/events.py File asyncio/events.py (right): https://codereview.appspot.com/145220043/diff/160005/asyncio/events.py#newcod... asyncio/events.py:188: super().cancel() I'd move super call out of the 'if' statement. https://codereview.appspot.com/145220043/diff/160005/asyncio/events.py#newcod... asyncio/events.py:249: raise NotImplementedError We need a docstring here. https://codereview.appspot.com/145220043/diff/160005/tests/test_base_events.py File tests/test_base_events.py (right): https://codereview.appspot.com/145220043/diff/160005/tests/test_base_events.p... tests/test_base_events.py:310: self.loop._process_events = mock.Mock() Please move this line to the top of the test, so it's immediately obvious how we patch self.loop here. https://codereview.appspot.com/145220043/diff/160005/tests/test_base_events.p... tests/test_base_events.py:323: 0 < base_events._MIN_CANCELLED_TIMER_HANDLES_FRACTION < 1.0) This check also should be on top of the test.

[chatgris, 2014-09-23 20:04:10]

On 2014/09/23 19:41:02, yselivanov wrote: > https://codereview.appspot.com/145220043/diff/160005/asyncio/base_events.py#n... > asyncio/base_events.py:44: # cancelled handles is performed > Please add '.' at the end of the sentence. I also did this on line 48 for consistency.

[yselivanov, 2014-09-24 00:13:00]

Looks good now.

[GvR, 2014-09-25 01:50:23]

Yuri, if you're happy with it, I have no further comments. Can you commit this for Joshua?

[yselivanov, 2014-09-25 02:55:48]

I was in the middle of committing the patch when I saw one more thing I'd like us to discuss. Please see the comment below. https://codereview.appspot.com/145220043/diff/200001/asyncio/base_events.py File asyncio/base_events.py (right): https://codereview.appspot.com/145220043/diff/200001/asyncio/base_events.py#n... asyncio/base_events.py:1006: self._scheduled = [x for x in self._scheduled if not x._cancelled] Just noticed that we have a double iteration over what might be a huge list potentially, and _run_once() is a central part of asyncio. Let's think about combining this list comprehension and the above loop in one thing, like this: new_scheduled = [] for handle in self._scheduled: if handle._cancelled: handle._scheduled = False else: new_scheduled.append(handle) self._scheduled = heapify(new_scheduled) Or should we use deque for new_scheduled? Can you test if there are any performance benefits in rewriting this piece?

[GvR, 2014-09-25 03:16:59]

On 2014/09/25 02:55:48, yselivanov wrote: > I was in the middle of committing the patch when I saw one more thing I'd like > us to discuss. Please see the comment below. > > https://codereview.appspot.com/145220043/diff/200001/asyncio/base_events.py > File asyncio/base_events.py (right): > > https://codereview.appspot.com/145220043/diff/200001/asyncio/base_events.py#n... > asyncio/base_events.py:1006: self._scheduled = [x for x in self._scheduled if > not x._cancelled] > Just noticed that we have a double iteration over what might be a huge list > potentially, and _run_once() is a central part of asyncio. > > Let's think about combining this list comprehension and the above loop in one > thing, like this: > > new_scheduled = [] > for handle in self._scheduled: > if handle._cancelled: > handle._scheduled = False > else: > new_scheduled.append(handle) > self._scheduled = heapify(new_scheduled) > > Or should we use deque for new_scheduled? Can you test if there are any > performance benefits in rewriting this piece? Heh, I suggested this in an earlier review. I expect it will be only a modest win, since heapify() is O(N) and its constant is much larger. But yeah, good idea to try. Note that heapify() doesn't return anything -- it rearranges the argument in place. So new_scheduled must be a list.

[chatgris, 2014-09-25 15:07:17]

On 2014/09/25 03:16:59, GvR wrote: > On 2014/09/25 02:55:48, yselivanov wrote: > > I was in the middle of committing the patch when I saw one more thing I'd like > > us to discuss. Please see the comment below. > > > > https://codereview.appspot.com/145220043/diff/200001/asyncio/base_events.py > > File asyncio/base_events.py (right): > > > > > https://codereview.appspot.com/145220043/diff/200001/asyncio/base_events.py#n... > > asyncio/base_events.py:1006: self._scheduled = [x for x in self._scheduled if > > not x._cancelled] > > Just noticed that we have a double iteration over what might be a huge list > > potentially, and _run_once() is a central part of asyncio. > > > > Let's think about combining this list comprehension and the above loop in one > > thing, like this: > > > > new_scheduled = [] > > for handle in self._scheduled: > > if handle._cancelled: > > handle._scheduled = False > > else: > > new_scheduled.append(handle) > > self._scheduled = heapify(new_scheduled) > > > > Or should we use deque for new_scheduled? Can you test if there are any > > performance benefits in rewriting this piece? > > Heh, I suggested this in an earlier review. I expect it will be only a modest > win, since heapify() is O(N) and its constant is much larger. But yeah, good > idea to try. Sorry, I don't recall seeing this in an earlier review. It was something I briefly thought about but my internal heuristic thought that calling append would be slower than the list comprehension since in my experience python function calls have a lot of overhead. However, in the interests of completeness, below is a program I ran to test this (it is included inline at the end of this message). Based on that program, over the course of 5 runs: Option A took between 12.25 and 12.4 seconds. Option B took between 13.2 and 14.4. Option C took around 17s (NOTE: Option C is not correct, after the first iteration it will be running on a list half the size (and since it's slower I didn't go to the effort to create an apples to apples comparison). But I thought I'd try an in-place method as well.) It appears that choosing the option that uses the least python/most C code is the winning option. And that appears to be what is already in the patch. Note that the above timing is the elapsed time the program prints out which excludes creation of the list. ==================== import asyncio import time loop = asyncio.get_event_loop() def cb(self): pass for x in range(1000000): th = loop.call_later(3600, cb) if x % 2 == 1: th.cancel() start = time.time() orig_data = loop._scheduled for x in range(100): loop._scheduled = orig_data """Option A for handle in loop._scheduled: if handle._cancelled: handle._scheduled = False loop._scheduled = [x for x in loop._scheduled if not x._cancelled] """ """Option B new_scheduled = [] for handle in loop._scheduled: if handle._cancelled: handle._scheduled = False else: new_scheduled.append(handle) loop._scheduled = new_scheduled """ """Option C This is not correct as it is repeatedly operating on a list half the size offs = 0 for i in range(len(loop._scheduled)): handle = loop._scheduled[i] if handle._cancelled: handle._scheduled = False offs += 1 else: loop._scheduled[i-offs] = handle del loop._scheduled[len(loop._scheduled) - offs:] """ end = time.time() print(end - start)

[yselivanov, 2014-09-25 16:11:54]

Joshua, I've just committed the patch to CPython and tulip: - https://hg.python.org/cpython/rev/2a868c9f8f15 - https://hg.python.org/cpython/rev/a6aaacb2b807 - https://code.google.com/p/tulip/source/detail?r=df3fa0556765e51ed06551af6fc2e... Thank you for the patch and for your patience during the code review!

[gvrpython, 2014-09-25 16:12:31]

Sounds good to me. It's possible that the difference between A and B is due to the lookup of the append method -- list comprehensions use append too, but they don't have to look it up each time. On Thu, Sep 25, 2014 at 8:07 AM, <chatgris@gmail.com> wrote: > On 2014/09/25 03:16:59, GvR wrote: > >> On 2014/09/25 02:55:48, yselivanov wrote: >> > I was in the middle of committing the patch when I saw one more >> > thing I'd like > >> > us to discuss. Please see the comment below. >> > >> > >> > https://codereview.appspot.com/145220043/diff/200001/ > asyncio/base_events.py > >> > File asyncio/base_events.py (right): >> > >> > >> > > https://codereview.appspot.com/145220043/diff/200001/ > asyncio/base_events.py#newcode1006 > >> > asyncio/base_events.py:1006: self._scheduled = [x for x in >> > self._scheduled if > >> > not x._cancelled] >> > Just noticed that we have a double iteration over what might be a >> > huge list > >> > potentially, and _run_once() is a central part of asyncio. >> > >> > Let's think about combining this list comprehension and the above >> > loop in one > >> > thing, like this: >> > >> > new_scheduled = [] >> > for handle in self._scheduled: >> > if handle._cancelled: >> > handle._scheduled = False >> > else: >> > new_scheduled.append(handle) >> > self._scheduled = heapify(new_scheduled) >> > >> > Or should we use deque for new_scheduled? Can you test if there are >> > any > >> > performance benefits in rewriting this piece? >> > > Heh, I suggested this in an earlier review. I expect it will be only a >> > modest > >> win, since heapify() is O(N) and its constant is much larger. But >> > yeah, good > >> idea to try. >> > > Sorry, I don't recall seeing this in an earlier review. It was something > I briefly thought about but my internal heuristic thought that calling > append would be slower than the list comprehension since in my > experience python function calls have a lot of overhead. > > However, in the interests of completeness, below is a program I ran to > test this (it is included inline at the end of this message). > > Based on that program, over the course of 5 runs: > > Option A took between 12.25 and 12.4 seconds. > Option B took between 13.2 and 14.4. > Option C took around 17s (NOTE: Option C is not correct, after the first > iteration it will be running on a list half the size (and since it's > slower I didn't go to the effort to create an apples to apples > comparison). But I thought I'd try an in-place method as well.) > > It appears that choosing the option that uses the least python/most C > code is the winning option. And that appears to be what is already in > the patch. > > Note that the above timing is the elapsed time the program prints out > which excludes creation of the list. > > ==================== > > import asyncio > import time > > loop = asyncio.get_event_loop() > > def cb(self): > pass > > for x in range(1000000): > th = loop.call_later(3600, cb) > if x % 2 == 1: > th.cancel() > > start = time.time() > > orig_data = loop._scheduled > > for x in range(100): > loop._scheduled = orig_data > > """Option A > for handle in loop._scheduled: > if handle._cancelled: > handle._scheduled = False > > loop._scheduled = [x for x in loop._scheduled if not x._cancelled] > """ > > """Option B > new_scheduled = [] > for handle in loop._scheduled: > if handle._cancelled: > handle._scheduled = False > else: > new_scheduled.append(handle) > > loop._scheduled = new_scheduled > """ > > """Option C > This is not correct as it is repeatedly operating on a list half the > size > offs = 0 > for i in range(len(loop._scheduled)): > handle = loop._scheduled[i] > if handle._cancelled: > handle._scheduled = False > offs += 1 > else: > loop._scheduled[i-offs] = handle > > del loop._scheduled[len(loop._scheduled) - offs:] > """ > > end = time.time() > > print(end - start) > > > > https://codereview.appspot.com/145220043/ > -- --Guido van Rossum (python.org/~guido) 

[gvrpython, 2014-09-25 16:28:00]

Thanks Yuri and Joshua!! This was a very useful exercise. On Thu, Sep 25, 2014 at 9:11 AM, <yselivanov@gmail.com> wrote: > Joshua, I've just committed the patch to CPython and tulip: > > - https://hg.python.org/cpython/rev/2a868c9f8f15 > - https://hg.python.org/cpython/rev/a6aaacb2b807 > - > https://code.google.com/p/tulip/source/detail?r= > df3fa0556765e51ed06551af6fc2e1f1e0ec18a0 > > Thank you for the patch and for your patience during the code review! > > https://codereview.appspot.com/145220043/ > -- --Guido van Rossum (python.org/~guido)