Could `TaskQueue` be implemented without `Task` being in C?

[imnotjames]

I have a hypothesis that the big reason why Task and TaskQueue are implemented in C are because the task queue's pairing heap implementation in C is far more performant than implementing it in native python.

Because the entire TaskQueue is in C, with the way it's written it needs to reference the tasks themselves - so then the Task class has to be written in C as well. This leads to troubles when - for example - we want to reference other errors, make changes to the Task class, etc. (Okay, so maybe it's just me that has been feeling this pain!)

Something I was poking at is rewriting the TaskQueue to use the heapq implementation. The big question I have and why I opened this issue is to ask "Is this a path forward?"

Another alternative would be to abstract the Task piece so it no longer stores its own ph_key / etc and include the task within the pairing heap wrapped. There's two places where Task's ph_key is checked outside of the task queue - once by the task itself during cancellation (this could be done by somehow getting when a task is scheduled from the currently running loop?) - and once by the running loop which could just be asking the task queue when the next Task is going to be at during the peek.

[imnotjames]

Code snippet of a first pass of implementation:

from heapq import heappush, heappop


class TaskQueue:
    def __init__(self):
        self._heap = []
        self._entries = {}
        self._counter = 0

    def peek(self):
        while self._heap:
            task = self._heap[0][-1]
            if task is not None:
                return task
            heappop(self._heap)

        return None

    def push(self, task: Task, key=None):
        if key is None:
            key = core.ticks()

        task.ph_key = key
        task.data = None
        self._counter += 1

        entry = [
            key,
            self._counter,
            task
        ]

        self._entries[task] = entry
        heappush(self._heap, entry)

    def pop(self):
        while self._heap:
            key, _, task = heappop(self._heap)

            if task is not None:
                del self._entries[task]
                return task

        return None

    def remove(self, task: Task):
        # Find the task and tombstone it
        if not task in self._entries:
            return

        entry = self._entries.pop(task)
        entry[-1] = None

    # Compatibility aliases, remove after they are no longer used
    push_head = push
    push_sorted = push
    pop_head = pop

[imnotjames]

Checking out the additional bin size when enabling heapq it seems smaller than the change introduced by adding _asyncio. However, I'm not sure on if this is comparable during runtime to the pairing heap implementation.

What should I be measuring during runtime? Memory usage? CPU time? How would I measure these kinds of things?

[dhalbert]

We have not turned on heapq for CircuitPython, but it probably works

You can see a discussion in the MicroPython PR about a revamp of uasyncio:
micropython/micropython#5332
micropython/micropython#5332 (comment) (choice of queue implementation)
micropython/micropython#5332 (comment) (addition of _uasyncio)

Damien tends to be quite thorough and thoughtful about these kinds of things, so I would not be inclined to second-guess him about the queue implementation. uheapq has been around for a long time and I think he would have used it if it seemed worthwhile. But I have not asked him this specifically.

[dhalbert]

We are trying not to stray too far from MicroPython on core things, and also would like to contribute things back. So if we can do that without a complete revamp, they are more likely to take it back.

[imnotjames]

We have not turned on heapq for CircuitPython, but it probably works

You can see a discussion in the MicroPython PR about a revamp of uasyncio: micropython/micropython#5332 micropython/micropython#5332 (comment) (choice of queue implementation) micropython/micropython#5332 (comment) (addition of _uasyncio)

Damien tends to be quite thorough and thoughtful about these kinds of things, so I would not be inclined to second-guess him about the queue implementation. uheapq has been around for a long time and I think he would have used it if it seemed worthwhile. But I have not asked him this specifically.

This is some perfect context, I'll spend some time reading through that thread. I was looking at heapq just because it was an alternative - definitely not because it'd be the best alternative or even a "good" alternative.