sched.cancel() doesn't distinguish equal events and can break order

[serhiy-storchaka]

BPO	19270
Nosy	@rhettinger, @pitrou, @giampaolo, @serhiy-storchaka, @MojoVampire, @bharel, @akulakov
PRs	bpo-19270: Fixed sched.scheduler.cancel to cancel correct event #22729
Files	sched_test_stable.patch

^{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 = <Date 2021-11-22.10:43:52.847>
created_at = <Date 2013-10-16.08:47:32.204>
labels = ['easy', 'type-bug', '3.10', 'docs']
title = "sched.cancel() doesn't distinguish equal events and can break order"
updated_at = <Date 2021-11-22.10:43:52.846>
user = 'https://github.com/serhiy-storchaka'

bugs.python.org fields:

activity = <Date 2021-11-22.10:43:52.846>
actor = 'iritkatriel'
assignee = 'docs@python'
closed = True
closed_date = <Date 2021-11-22.10:43:52.847>
closer = 'iritkatriel'
components = ['Documentation']
creation = <Date 2013-10-16.08:47:32.204>
creator = 'serhiy.storchaka'
dependencies = []
files = ['32142']
hgrepos = []
issue_num = 19270
keywords = ['patch', 'easy']
message_count = 24.0
messages = ['200040', '200048', '200698', '200708', '200711', '200714', '200715', '200717', '200719', '200788', '200798', '200799', '200828', '200830', '200831', '200832', '244346', '327404', '371895', '372139', '372142', '376985', '378930', '398628']
nosy_count = 9.0
nosy_names = ['rhettinger', 'pitrou', 'giampaolo.rodola', 'docs@python', 'serhiy.storchaka', 'josh.r', 'bar.harel', 'wocket', 'andrei.avk']
pr_nums = ['22729']
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'behavior'
url = 'https://bugs.python.org/issue19270'
versions = ['Python 3.10']

[serhiy-storchaka]

sched.cancel() breaks events order if events are scheduled on same time and have same priority.

Patch contains tests which expose this issue.

[serhiy-storchaka]

Actually there are two bugs:

1. sched.cancel() can remove wrong event (because it uses equality instead identity).

2. sched.cancel() change order of equal (by time and priority) events.

[rhettinger]

1. sched.cancel() can remove wrong event
   (because it uses equality instead identity).

I don't think this is a bug. The user should be able to define events that can be compared on equality. It is the user's responsibility to make sure that events are distinct (this is no different than how list.remove() works for example).

2. sched.cancel() change order of equal (by time and priority) events.

That is allowed. We make no stability guarantees. Plus it just makes sense that events with the same time and priority are non-deterministic.

Note, to add stability we would have to store the order that events were added. This would slow down the code.

Add note that Tornado uses heapq in its ioloop in the same way that the schedule module does. It too makes no effort to preserve input order.

I recommend closing this as "not a bug" or as an "further document the existing behaviors".

[serhiy-storchaka]

If the order of events with the same time and priority doesn't matter, we can optimize the queue property more than 10 times by using sort() (see cancel_4.patch in bpo-13451).

[vstinner]

That is allowed. We make no stability guarantees. Plus it just makes sense that events with the same time and priority are non-deterministic.

It would be nice to keep the insertion order. If it is not guaranteed, it must be well documented (big red warning).

Does it occur frequently to schedule two events at exactly the same time? On Linux, clocks have a good precision, even time.monotonic(). On Windows, the precision of time.monotonic() is worse (around 16 ms), so two events at the same time is more likely.

The issue is specific to events scheduled at an absolute time, right? Or does .enter() has a similar issue?

[pitrou]

Does it occur frequently to schedule two events at exactly the same
time? On Linux, clocks have a good precision, even time.monotonic().

It depends how you calculate your timestamps, I'd say :-) It's unlikely
for two calls to time.time() to give the exact same outcome. OTOH, if
you're using a fixed base time and add user-provided timedeltas to it,
collisions are quite possible.

(a special case is using a 0 delay, in order to schedule a call for
the next loop iteration)

[vstinner]

... for two calls to time.time() to give the exact same outcome

sched now uses time.monotonic() since Python 3.3. In Python 2.7, there is no default timer, but I get that users pick time.time(). (Oh, sched has no unit test in Python 2.7.)

[pitrou]

> ... for two calls to time.time() to give the exact same outcome

sched now uses time.monotonic() since Python 3.3.

This seems quite irrelevant:

  >>> len(set(time.monotonic() for i in range(100)))
  100

[vstinner]

Victor: "On Windows, the precision of time.monotonic() is worse (around 16 ms), so two events at the same time is more likely."

Antoine: "This seems quite irrelevant:"

I would be interested of the same test on Windows.

[rhettinger]

This module has been around for a long time and no users have reported any issues with respect to event ordering. The logic is essentially the same as is used in popular event loops like Tornado.

Please don't just make-up a new invariant for this module.

[serhiy-storchaka]

Well. In any case I have no ideas how fix it. Any behavior change will break existing code.

I requalify this issue as documentation enhancement. The documentation should specify that evens scheduled on same tame with same priority considered equal. That cancel() doesn't distinguish equal events and can cancel arbitrary of them. That cancel() doesn't preserve order of equal events.