adafruit / Adafruit_CircuitPython_asyncio

CIrcuitPython subset of CPython asyncio library
MIT License
28 stars 16 forks source link

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

Open imnotjames opened 1 year ago

imnotjames commented 1 year ago

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 commented 1 year ago

Code snippet of a first pass of implementation:

```python 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 commented 1 year ago

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 commented 1 year ago

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: https://github.com/micropython/micropython/pull/5332 https://github.com/micropython/micropython/pull/5332#issuecomment-571133960 (choice of queue implementation) https://github.com/micropython/micropython/pull/5332#issuecomment-598173856 (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 commented 1 year ago

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 commented 1 year ago

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.