How does asyncio.sleep work with negative values?

Question

I decided to implement sleep sort (https://rosettacode.org/wiki/Sorting_algorithms/Sleep_sort) using Python's asyncio when I made a strange discovery: it works with negative values (and returns immediately with 0)!

Here is the code (you can run it here https://repl.it/DYTZ):

import asyncio import random async def sleepy(value): return await asyncio.sleep(value, result=value) async def main(input_values): result = [] for sleeper in asyncio.as_completed(map(sleepy, input_values)): result.append(await sleeper) print(result) if __name__ == '__main__': loop = asyncio.get_event_loop() input_values = list(range(-5, 6)) random.shuffle(input_values) loop.run_until_complete(main(input_values))

The code takes 5 seconds to execute, as expected, but the result is always [0, -5, -4, -3, -2, -1, 1, 2, 3, 4, 5]. I can understand 0 returning immediately, but how are the negative values coming back in the right order?

A heapq is used to sort the callbacks using their scheduled time, which means your sleep sort is actually a heapsort — Vincent
– Vincent, Commented Sep 8, 2016 at 19:48

Vivian · Accepted Answer · 2016-09-08 20:25:02Z

Well, looking at the source:

delay == 0 is special-cased to return immediately, it doesn't even try to sleep.
Non-zero delay calls events.get_event_loop(). Since there are no calls to events.set_event_loop_policy(policy) in asyncio.tasks, it would seem to fall back on the default unless it's already been set somewhere else, and the default is asyncio.DefaultEventLoopPolicy.
This is not defined in events.py, because it's different on Windows from on UNIX.
Either way, sleep calls loop.create_future(). That's defined a few inheritances back, over in base_events.BaseEventLoop. It's just a simple call to the Future() constructor, no significant logic.

From the instance of Future it delegates back to the loop, as follows:

future._loop.call_later(delay, futures._set_result_unless_cancelled, future, result)

That one is also in BaseEventLoop, and still doesn't directly handle the delay number: it calls self.call_at, adding the current time to the delay.
call_at schedules and returns an events.TimerHandle, and the callback is to tell the Future it's done. The return value is only relevant if the task is to be cancelled, which it is automatically at the end for cleanup. The scheduling is the important bit.
_scheduled is sorted via heapq - everything goes on there in sorted order, and timers sort by their _when. This is key.
Every time it checks, it strips out all cancelled scheduled things, then runs all remaining scheduled callbacks, in order, until it hits one that's not ready.

TL;DR:

Sleeping with asyncio for a negative duration schedules tasks to be "ready" in the past. This means that they go to the top of the list of scheduled tasks, and are run as soon as the event loop checks. Effectively, 0 comes first because it doesn't even schedule, but everything else registers to the scheduler as "running late" and is handled immediately in order of how late it is.

Wow, this is really detailed. Thanks for digging into the source.

dirn · Accepted Answer · 2016-09-08 19:45:52Z

If you take a look at the asyncio source, sleep special cases 0 and returns immediately.

if delay == 0: yield return result

If you continue through the source, you'll see that any other value gets passed through to the event loop's call_later method. Looking at how call_later is implemented for the default loop (BaseEventLoop), you'll see that call_later passes a time to call_at.

self.call_at(self.time() + delay, callback, *args)

The reason the values are turned in order is that the times created with negative delays occur before those with positive delays.

Gah - took too long tracing source and getting it all written out, and you beat me to it.
Yeah, but you went all the way to the heap, so you've got that on me.
Up to you. I took longer, and speed is a kind of quality too. /shrugs
I think I will because it has more material for future reference. Thanks to you both!

Collectives™ on Stack Overflow

How does asyncio.sleep work with negative values?

2 Answers 2

1 Comment

5 Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

5 Comments

Related