Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Simpler mechanisms for asynchronous processing (thoughts) #1380

Open
dhalbert opened this issue Dec 6, 2018 · 31 comments

Comments

Projects
None yet
10 participants
@dhalbert
Copy link
Collaborator

commented Dec 6, 2018

These are some strawman thoughts about how to provide handling of asynchronous events in a simple way in CircuitPython. This was also discussed at some length in our weekly audio chat on Nov 12, 2018, starting at 1:05:36: https://youtu.be/FPqeLzMAFvA?t=3936.

Every time I look at the existing solutions I despair:

  • asyncio: it's complicated, has confusing syntax, and pretty low level. Event loops are not inherent in the syntax, but are part of the API.
  • interrupt handlers: MicroPython has them, but they have severe restrictions: should be quick, can't create objects.
  • callbacks: A generalization of interrupt handlers, and would have similar restrictions.
  • threads: Really hard to reason about.

I don't think any of these are simple enough to expose to our target customers.

But I think there's a higher-level mechanism that would suit our needs and could be easily comprehensible to most users, and that's

Message Queues
A message queue is just a sequence of objects, usually first-in-first-out. (There could be fancier variations, like priority queues.)

When an asynchronous event happens, the event handler (written in C) adds a message to a message queue when. The Python main program, which could be an event loop, processes these as it has time. It can check one or more queues for new messages, and pop messages off to process them. NO Python code ever runs asynchronously.

Examples:

  • Pin interrupt handler: Add a timestamp to a queue of timestamps, recording when the interrupt happened.
  • Button presses: Add a bitmask of currently pressed buttons to the queue.
  • UART input: Add a byte to the queue.
  • I2CSlave: Post an I2C message to a queue of messages.
  • Ethernet interface: Adds a received packet to a queue of packets.

When you want to process asynchronous events from some builtin object, you attach it to a message queue. That's all you have to do.

There are even already some Queue classes in regular Python that could serve as models: https://docs.python.org/3/library/queue.html

Some example strawman code is below. The method names are descriptive -- we'd have to do more thinking about the API and its names.

timestamp_queue = MessageQueue()        // This is actually too simple: see below.
d_in = digitalio.DigitalIn(board.D0)
d_in.send_interrupts_to_queue(timestamp_queue, trigger=RISE)

while True:
    timestamp = timestamp_queue.get(block=False, timeout=None) // Or could check for empty (see UART below)
     if timestamp:    // Strawman API: regular Python Queues actually throw an exception if nothing is read.
        // Got an interrupt, do something.
        continue
        // Do something else.
```

Or, for network packets:
```
packet_queue = MessageQueue()
eth = network.Ethernet()
eth.send_packets_to_queue(packet_queue)
...
```

For UART input:
```
uart_queue = MessageQueue()
uart = busio.UART(...)
uart.send_bytes_to_queue(uart_queue)
while True:
    if not uart_queue.is_empty:
        char = uart_queue.pop()
```

Unpleasant details about queues and storage allocation:

It would be great if queues could just be potentially unbounded queues of arbitrary objects. But right now the MicroPython heap allocator is not re-entrant, so an interrupt handler or packet receiver, or some other async thing can't allocate the object it want to push on the queue. (That's why MicroPython has those restrictions on interrupt handlers.) The way around that is pre-allocate the queue storage, which also makes it bounded. Making it bounded also prevents queue overflow: if too many events happen before they're processed, events just get dropped (say either oldest or newest). So the queue creation would really be something like:
```
// Use a list as a queue (or an array.array?)
timestamp_queue = MessageQueue([0, 0, 0, 0])
// Use a bytearray as a queue
uart_queue = MessageQueue(bytearray(64))

// Queue up to three network packets.
packet_queue = MessageQueue([bytearray(1500) for _ in range(3)], discard_policy=DISCARD_NEWEST)
```

-----------------------------

The whole idea here is that event processing takes place synchronously, in regular Python code, probably in some kind of event loop. But the queues take care of a lot of the event-loop bookkeeping.

If and when we have some kind of multiprocessing (threads or whatever), then we can have multiple event loops.

@dhalbert dhalbert added the enhancement label Dec 6, 2018

@dhalbert dhalbert added this to the Long term milestone Dec 6, 2018

@dhalbert

This comment has been minimized.

Copy link
Collaborator Author

commented Dec 6, 2018

For a different and interesting approach to asynchronous processing, see @bboser's https://github.com/bboser/eventio for a highly constrained way of using async / await, especially the README and https://github.com/bboser/eventio/tree/master/doc. Perhaps some combination of these makes sense.

@brennen

This comment has been minimized.

Copy link

commented Dec 6, 2018

I'm unqualified at this point to talk about implementation, but from an end user perspective I like the idea of this abstraction quite a bit. It feels both like a way to shortcut some ad hoc polling loop logic that I suspect people duplicate a lot (and often badly), and also something that could be relatively friendly to people who came up on high-level languages in other contexts.

People aren't going to stop wanting interrupts / parallelism, but this answers a lot of practical use cases.

@deshipu

This comment has been minimized.

Copy link

commented Dec 6, 2018

I like event queues and I agree they are quite easy to understand and use, however, I'd like to point out a couple of down sides for them, so that we have more to discuss.

  1. Queues need memory to store the events. Depending on how large the event objects are, how often they get added and how often you check them, this can be a lot of memory. Since events are getting created and added from a callback, that has to be pre-allocated memory. And I don't know of a good way of signalling and handling overflows in this case — depending on use case, you might want to have an error, drop old events, drop new events, etc. To save memory you might want to have an elaborate filtering scheme, and that gets complex really fast.
  2. Queues encourage a way of writing code that introduces unpredictable latency. The way your code usually would flow, you would do your work for the given frame, then you would go through the content of all the event queues and act on them, then you would wait for the next frame. In many cases that is perfectly fine, but in some you would rather want to react to the event as soon as possible.
  3. Every new kind of queue will need a new class and its own C code for the callback and handling of the data. So if you have a sensor that signals availability of new data with an interrupt pin, you will need custom C code that will get called, read the sensor readings and put them on the queue. That means that all async drivers would need to be built-in.
  4. Sometimes a decision needs to be done while the event is being created, and can't wait. For example, in the case of the I2C slave, you need to ACK or NACK the data, and you have to hold the bus in a clock-stretch until you do.

That's all I can think of at the moment.

@framlin

This comment has been minimized.

Copy link

commented Dec 19, 2018

Hm, I do not fully understand, why such a MessageQueue model should be easier to understand than callbacks. Maybe it's, because I am used to callbacks ;-)
What is so special with your target customers, that you think, they do not understand callbacks?

I think, you have to invest much more brain in managing a couple of MessageQueues for different types of events (ethernet, i2c, timer, exceptions, spi, .....) or one MessageQueue, where you have to distinguish between different types of events, than in implementing one callback for each type of event ant pass it to a built in callback-handler.

def byte_reader(byte):
      deal_with_the(byte)

uart = busio.UART(board.TX, board.RX, baudrate=115200, byte_reader)
@siddacious

This comment has been minimized.

Copy link
Collaborator

commented Dec 19, 2018

I like the idea of message queues but I'm not convinced that they're any easier to understand than interrupt handers. Rather I think that conceptually interrupt handlers/callbacks are relatively easy to understand but understanding how to work with their constraints is where it gets a bit more challenging. Message queues are a good way of implementing the "get the operable data out of the hander and work on it in the main loop" solution to the constraints of interrupt handlers but as @deshipu pointed out, there are still good reasons to need to put some logic in the handler. Maybe both?

Similarly I like how eventio works but I think it's even more confusing than understanding and learning to work with the constraints of interrupt handlers. That in mind, it's tackling concurrency in a way that I think might be more relatable to someone who came to concurrency from the "why can't I blink two leds at once" angle.

One thing I was wondering about is what a bouncy button would do to a message queue. Ironically I think overflow might actually be somewhat useful in this case as if the queue was short enough you'd possibly lose the events for a number of bounces (but not all of them unless your queue was len=1. I'll have to ponder this one further). With a longer queue you could easily write a debouncer by looking for a time delta between events above a threshold.

No matter how you slice it, concurrency is a step beyond the basics of programming and I don't think any particular approach is going to allow us to avoid that. It seems to me that we're being a bit focused choosing a solution to a set of requirements that we don't have a firm grasp on yet. I think it's worth taking the time to understand who the users of this solution are and what their requirements are.

@notro

This comment has been minimized.

Copy link
Collaborator

commented Dec 20, 2018

See #1415 for an async/await example.

@deshipu

This comment has been minimized.

Copy link

commented Dec 21, 2018

What is so special with your target customers, that you think, they do not understand callbacks?

The problem is not with the callback mechanism itself, but in the constraint that MicroPython has that you can't allocate memory inside a callback. This is made much more complex than necessary by the fact that Python is a high level language with automatic memory management, that lets you forget about memory allocation most of the time, so it's not really obvious what operations can be used in a callback, and how to work around the ones that can't.

@notro

This comment has been minimized.

Copy link
Collaborator

commented Dec 22, 2018

One solution would be to enable MICROPY_ENABLE_SCHEDULER and only allow soft IRQ's, running the callback inline with the VM. This would prevent people from shooting themselves in the foot.

Refs:

@bboser

This comment has been minimized.

Copy link

commented Dec 22, 2018

@dhalbert

This comment has been minimized.

Copy link
Collaborator Author

commented Dec 26, 2018

Thank you all for your thoughts and trials on this. I'll follow up in the near future but am deep in Bluetooth at the moment. The soft interrupts idea and the simplified event loop / async / await stuff is very interesting. I think we can make some progress on this.

@dhalbert dhalbert changed the title Using message queues for asynchronous processing (thoughts) SImpler mechanisms for asynchronous processing (thoughts) Jan 8, 2019

@dhalbert dhalbert changed the title SImpler mechanisms for asynchronous processing (thoughts) Simpler mechanisms for asynchronous processing (thoughts) Jan 8, 2019

@pvanallen

This comment has been minimized.

Copy link

commented Apr 3, 2019

From my experience with what I think is the CircuitPython audience (I teach technology to designers), I don't think message queues are easier to understand than other approaches, and are probably harder in many cases. As @siddacious says, concurrency takes a while for newcomers to wrap their heads around no matter what the method.

I also think it's important to distinguish between event driven needs and parallelism. In my experience, the most common need amongst my students is doing multiple things at once, e.g. fading two LEDs at different rates, and perhaps doing this while polling a distance sensor. This requirement is different from the straw man example above.

Some possible directions:

@dhalbert

This comment has been minimized.

Copy link
Collaborator Author

commented Apr 8, 2019

I have done some more thinking and studying on this topic. In particular, I've read (well, read the front part; skimmed a lot more) Using Asyncio in Python 3, and I've read about curio and trio (github), which is even simpler than curio, started by @njsmith. Trio emphasizes "structured concurrency". I also re-reviewed @bboser 's https://github.com/bboser/eventio, and @notro 's example of a simple async/await system in #1415. This is also reminiscent of MakeCode's multiple top-level loops.

Also I had some thoughts about some very simple syntax for an event-loop system I thought might be called when. Here are some strawman doodlings, which are a lot like eventio or @notro's proposal. I am not thinking about doing asynchronous stream or network I/O here, but about handling timed events in a clean way, and about handling interrupts or other async events. Not shown below could be some kind of event queue handler, which would be similar to the interrupt handler.

Maybe the functions below need to be async? Not sure; I need to understand things further. I'm more interested in the style than the details right now.

Note that that when.interval() subsumes even doing await time.sleep(1.0) or similar: it's built in to the kind of when.

I am pretty excited about this when/eventio/notro-event-loop/trio/MakeCode model, as opposed to asyncio, which is very complex. asyncio started from a goal of handling tons of network I/O, and is also partly a toolkit for writing concurrency packages, as Caleb Hattingh (author of the asyncio book above) points out.

# A cute name
import when

import board, digitalio

d1 = digitalio.DigitalInOut(board.D1)
d1.switch_to_output()

d2 = digitalio.DigitalInOut(board.D2)
d2.switch_to_output()

d3_interrupt = digitalio.Interrupt(board.D3, change=digitalio.Interrupt.RISIING)

#################################
# Decorator style of using `when`

#Starts at 0.0 seconds, runs every 1.0 seconds
@when.interval(d1, interval=1.0)
def blink1(pin):
     pin.value = not pin.value

# Starts at 0.5 seconds, runs every 1.0 seconds
@when.interval(d2, interval=1.0, start_at=0.5)
def blink2(pin):
     pin.value = not pin.value

# This is a soft interrupt. The actual interrupt will set a flag or queue an event.
@when.interrupt(d3_interupt)
def d3_interrupt_handler(interrupt):
    print("interrupted")

# Start an event loop with all the decorated functions above.
when.run()

####################################
# Programmatic style of using `when`

def toggle_d1():
     d1.value = not d1.value

def toggle_d1():
     d2.value = not d2.value

when.interval(toggle_d1, interval=1.0)
when.interval(toggle_d2, interval=1.0, start_at=0.5)

def d3_interrupt_handler():
    print("interrupted")

when.interrupt(d3_interrupt_handler, d3_interupt)

when.run()
@dhalbert

This comment has been minimized.

Copy link
Collaborator Author

commented Apr 8, 2019

@deshipu

This comment has been minimized.

Copy link

commented Apr 8, 2019

For comparison, here is how you would do it with some kind of async framework (let's call it "suddenly"):

import suddenly
import digitalio

async def blink1(pin):
    pin.switch_to_output()
    while True:
        pin.value = not pin.value
        await suddenly.sleep(1)

async def blink2(pin):
    await suddenly.sleep(0.5)
    await blink1(pin)

async def interrupt(pin):
    while True:
        await pin.change(digitalio.Interrupt.RISING)
        print("interrupted")

suddenly.start(blink1(digitalio.DigitalInOut(board.D1)))
suddenly.start(blink2(digitalio.DigitalInOut(board.D2)))
suddenly.start(interrupt(digitalio.DigitalInOut(board.D3)))
suddenly.run()

or a shorter:

suddenly.run(
    blink1(digitalio.DigitalInOut(board.D1)),
    blink2(digitalio.DigitalInOut(board.D2)),
    interrupt(digitalio.DigitalInOut(board.D3)),
)
@dhalbert

This comment has been minimized.

Copy link
Collaborator Author

commented Apr 8, 2019

@deshipu Right, right, yes, we're talking about the same thing! I left out the asyncs and awaits, or propose they might be hidden by the when mechanism. I'm trying to come up with strawman pseudocode before getting into the details. I freely admit there may be mistakes in my thinking here, but I'm trying not to get sucked into the details of an existing paradigm yet.

trio and curio use async with as a style. I'll doodle with the same style:

import when

# similar defs as in previous comment ...
# ...

# I am deliberately leaving out the `async`s because I want to understand we actually need them and when we don't. How much can we hide in the library?
with when.loop() as loop:
    loop.interval(blink1, 1.0)
    loop.interval(blink2, 1.0, start_at=0.5)
    loop.interrupt(some_function)
    loop.event(event_handler, queue=some_event_queue)
    loop.done_after(60.0)         # stop loop after 60 seconds
    loop.done(some_predicate_function)

# ^^ Runs the loop until done.

    # in general:
    # loop.something(function_name_or_lambda, args=(), more args if necessary)
@deshipu

This comment has been minimized.

Copy link

commented Apr 8, 2019

It's not possible to "hide" the async keyword in the library, because then you create a function that is being invoked when you "call" it. With async, "call" will simply produce an iterator object, which the library can then exhaust in its main loop, handling any Futures it gets from it along the way.

I think that syntax makes a very big difference for beginners, and that the "callback" style that you propose is very difficult to grasp for people not used to it. With the async style syntax, you basically write each function as if it was the only function in your program (you can test it as the only function), and then add the async to it and await to all parts that block, and it just works.

@dhalbert

This comment has been minimized.

Copy link
Collaborator Author

commented Apr 8, 2019

@deshipu Thank you for the enlightenment. I'll rework the examples with async. I think we still might be able to avoid explicit awaits in some cases. I like the interval() style, which pushes the timing into when instead of making it part of the function. But maybe that is too much of a toy example.

@dhalbert

This comment has been minimized.

Copy link
Collaborator Author

commented Apr 8, 2019

@deshipu But I am seeing trio use what you call the "callback" style:
https://trio.readthedocs.io/en/latest/tutorial.html#okay-let-s-see-something-cool-already
Notice child1, not child1(), below, etc.
There are other examples where the args are separated from the function, e.g. start(fn, arg).

Do you have an example of an await/async library that uses your style?

Trimmed example from link above:

async def child1():
    # ...

async def child2():
    # ...

async def parent():
    print("parent: started!")
    async with trio.open_nursery() as nursery:
        nursery.start_soon(child1)
        nursery.start_soon(child2)

trio.run(parent)
@deshipu

This comment has been minimized.

Copy link

commented Apr 8, 2019

Here is a very simple implementatin of such an async framwork, that can only await on a sleep function:

import time


TASKS = []


class Task:
    def __init__(self, when, coro):
        self.coro = coro
        self.when = when


def sleep(seconds):
    return [seconds]


def start(*awaitables, delay=0):
    now = time.monotonic()
    for awaitable in awaitables:
        TASKS.append(Task(now + delay, awaitable))


def run(*awaitables):
    start(*awaitables)
    while TASKS:
        now = time.monotonic()
        for task in TASKS:
            if now >= task.when:
                try:
                    seconds = next(task.coro)
                except StopIteration:
                    TASKS.remove(task)
                else:
                    task.when = now + seconds


# async def test():
def test1():
    for i in range(10):
        print(i)
        # await sleep(1)
        yield from sleep(1)

def test2():
    yield from sleep(0.5)
    yield from test1()

run(test1(), test2())
@deshipu

This comment has been minimized.

Copy link

commented Apr 8, 2019

This presentation explains the trampoline trick that it uses:
https://www.youtube.com/watch?v=MCs5OvhV9S4

@deshipu

This comment has been minimized.

Copy link

commented Apr 8, 2019

As for examples, asyncio uses that style: https://docs.python.org/3/library/asyncio.html

@deshipu

This comment has been minimized.

Copy link

commented Apr 8, 2019

Of course in a proper implementation you would use a priority queue for tasks that are delayed, and a select() (with a timeout equal to the time for the next item in the priority queue) for tasks that are blocked on input/output, such as interrupts, reading, or writing.

@deshipu

This comment has been minimized.

Copy link

commented Apr 8, 2019

I mocked up a simple framework that lets you sleep and wait for a pin change (uses polling internally): https://github.com/deshipu/meanwhile

@pvanallen

This comment has been minimized.

Copy link

commented Apr 8, 2019

@dhalbert I think your "when" proposal has promise. I like the simplicity of it. And compared to other approaches, I think moving the interval outside the def is better because it makes the method more reusable and cleaner. From my perspective, the use of "callbacks" is not that hard for people to understand, whereas the use of await/yield requires explaining cooperative multitasking etc.

I'm interested to hear how your approach would handle terminating an interval. And did you consider giving an interval an optional number of repeats? E.g.

when.interval(toggle_d2, interval=1.0, start_at=0.5, repeats=20)
@deshipu

This comment has been minimized.

Copy link

commented Apr 8, 2019

Since with async the interval is just a loop with a delay, you can easily control the number of repeats:

async def blink1(pin, interval, start_at,  repeats):
    await meanwhile.sleep(start_at)
    for repeat in range(repeats):
        pin.value = not pin.value
        await meanwhile.sleep(interval)

meanwhile.run(blink1(pin_d2, 1.0, 0.5, 20))
@deshipu

This comment has been minimized.

Copy link

commented Apr 8, 2019

I added a mock of a hypothetical implementation of an async framework if we had the select call available (just for file operations for now, but for sercoms or interrupts it would be similar): https://github.com/deshipu/meanwhile/blob/master/meanwhile_select.py

@pvanallen

This comment has been minimized.

Copy link

commented Apr 15, 2019

@deshipu

Since with async the interval is just a loop with a delay, you can easily control the number of repeats

Sure, but for beginning coders, I think keeping the common aspects of these intervals out of the function definitions makes them simpler to write and understand. E.g. this is boiled down to the essence of the task:

def toggle_d1():
     d1.value = not d1.value

and leaves all the bookkeeping for delay, start time, and repeats to the library. For my students, this simplification would be very helpful in their gaining confidence and trying out new things like cooperative multitasking. Over time, they'll then develop a greater understanding and be able to add more complex features.

I would like to have arguments, and I wonder if @dhalbert's when approach will permit it? E.g.:

def toggle(pin):
     pin.value = not pin.value

when.interval(toggle(pin), interval=1.0, start_at=0.5, repeats=20)
@deshipu

This comment has been minimized.

Copy link

commented Apr 15, 2019

@pvanallen in my limited experience, it's really difficult to teach people this style of programming (where the inside of the loop is in a separate function from the rest of the code), and it results in code that is difficult to follow. You can of course do it with async if you really hate yourself:

def blink_inner(pin):
    pin.value = not pin.value

async def blink1(pin, interval, start_at,  repeats, func=blink_inner):
    await meanwhile.sleep(start_at)
    for repeat in range(repeats):
        func(pin)
        await meanwhile.sleep(interval)

meanwhile.run(blink1(pin_d2, 1.0, 0.5, 20, blink_inner))
@deshipu

This comment has been minimized.

Copy link

commented Apr 15, 2019

Come to think of it, it should be trivial to make a decorator function that would add what blink1 does in the above example to any function.

@zencuke

This comment has been minimized.

Copy link

commented Apr 30, 2019

Sorry to come to this late. As context I am a long time embedded control developer who has written a couple of low level preemptive tasker/schedulers (easier than you might guess) and I've least read several versions of UNIX/Linux schedulers. I used to be up on current theory, including studying how an OS scheduler problem (priority inversion) killed the Pathfinder Mars lander, but that was a while ago. I just wanted to add one thing. Usually concurrency is implemented with a small number of core tools (message queue, resource locks, semaphores ... choose one) then more complex abstractions are built on top of them. I suggest breaking the problem into two parts, 1) a basic core abstraction for internal implementation, and 2) User visible interfaces (API) which use the core abstraction to do the heavy lifting. A good choice of core abstraction gives you a simple reliable building block to implement different user interfaces. It doesn't have to be simple to understand. It may be that only developers see it. It just has to be reliable. Simplicity is the job of the user API.

@skoslowski

This comment has been minimized.

Copy link

commented May 5, 2019

This issue came up in a discussion with @tannewt during PyCon19. Only skimmed the comments here, it looks like no one has mentioned the simple scheduler/event loop that is part of the CPython standard library and may be of interest for this:

https://docs.python.org/3/library/sched.html

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.