Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c++ > #67263 > unrolled thread

Why can't I understand what coroutines are?

Back to article view | Back to comp.lang.c++

Contents

  Why can't I understand what coroutines are? Juha Nieminen <nospam@thanks.invalid> - 2019-08-04 09:37 +0000
    Re: Why can't I understand what coroutines are? "Chris M. Thomasson" <invalid_chris_thomasson_invalid@invalid.com> - 2019-08-04 02:58 -0700
      Re: Why can't I understand what coroutines are? Sam <sam@email-scan.com> - 2019-08-04 09:18 -0400
        Re: Why can't I understand what coroutines are? "Chris M. Thomasson" <invalid_chris_thomasson_invalid@invalid.com> - 2019-08-04 11:15 -0700
    Re: Why can't I understand what coroutines are? Louis Krupp <lkrupp@nospam.pssw.com.invalid> - 2019-08-04 04:58 -0600
      Re: Why can't I understand what coroutines are? Juha Nieminen <nospam@thanks.invalid> - 2019-08-05 08:31 +0000
        Re: Why can't I understand what coroutines are? Martijn van Buul <pino@dohd.org> - 2019-08-05 09:51 +0000
          Re: Why can't I understand what coroutines are? "Chris M. Thomasson" <invalid_chris_thomasson_invalid@invalid.com> - 2019-08-05 14:44 -0700
    Re: Why can't I understand what coroutines are? Chris Vine <chris@cvine--nospam--.freeserve.co.uk> - 2019-08-04 14:08 +0100
      Re: Why can't I understand what coroutines are? Sam <sam@email-scan.com> - 2019-08-04 09:23 -0400
        Re: Why can't I understand what coroutines are? Chris Vine <chris@cvine--nospam--.freeserve.co.uk> - 2019-08-04 14:36 +0100
          Re: Why can't I understand what coroutines are? Sam <sam@email-scan.com> - 2019-08-04 10:31 -0400
            Re: Why can't I understand what coroutines are? Chris Vine <chris@cvine--nospam--.freeserve.co.uk> - 2019-08-04 16:42 +0100
              Re: Why can't I understand what coroutines are? Sam <sam@email-scan.com> - 2019-08-04 16:43 -0400
                Re: Why can't I understand what coroutines are? "Chris M. Thomasson" <invalid_chris_thomasson_invalid@invalid.com> - 2019-08-04 13:58 -0700
                  Re: Why can't I understand what coroutines are? Sam <sam@email-scan.com> - 2019-08-04 17:36 -0400
                    Re: Why can't I understand what coroutines are? Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2019-08-04 22:43 +0100
                    Re: Why can't I understand what coroutines are? Chris Vine <chris@cvine--nospam--.freeserve.co.uk> - 2019-08-04 22:52 +0100
                      Re: Why can't I understand what coroutines are? Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2019-08-04 23:10 +0100
                      Re: Why can't I understand what coroutines are? Sam <sam@email-scan.com> - 2019-08-04 21:32 -0400
                        Re: Why can't I understand what coroutines are? Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2019-08-05 18:32 +0100
                          Re: Why can't I understand what coroutines are? scott@slp53.sl.home (Scott Lurndal) - 2019-08-05 17:48 +0000
                            Re: Why can't I understand what coroutines are? Sam <sam@email-scan.com> - 2019-08-05 20:14 -0400
                            Re: Why can't I understand what coroutines are? leigh.v.johnston@googlemail.com - 2019-08-06 04:13 -0700
                              Re: Why can't I understand what coroutines are? leigh.v.johnston@googlemail.com - 2019-08-06 04:23 -0700
                                Re: Why can't I understand what coroutines are? Chris Vine <chris@cvine--nospam--.freeserve.co.uk> - 2019-08-06 22:19 +0100
                                  Re: Why can't I understand what coroutines are? "Chris M. Thomasson" <invalid_chris_thomasson_invalid@invalid.com> - 2019-08-06 15:19 -0700
                                    Re: Why can't I understand what coroutines are? Chris Vine <chris@cvine--nospam--.freeserve.co.uk> - 2019-08-07 00:01 +0100
                                      Re: Why can't I understand what coroutines are? scott@slp53.sl.home (Scott Lurndal) - 2019-08-06 23:52 +0000
                                      Re: Why can't I understand what coroutines are? Öö Tiib <ootiib@hot.ee> - 2019-08-06 16:57 -0700
                                        Re: Why can't I understand what coroutines are? scott@slp53.sl.home (Scott Lurndal) - 2019-08-07 14:41 +0000
                                          Re: Why can't I understand what coroutines are? Öö Tiib <ootiib@hot.ee> - 2019-08-08 07:10 -0700
                                    Re: Why can't I understand what coroutines are? scott@slp53.sl.home (Scott Lurndal) - 2019-08-06 23:49 +0000
                    Re: Why can't I understand what coroutines are? Robert Wessel <robertwessel2@yahoo.com> - 2019-08-04 22:04 -0500
                    Re: Why can't I understand what coroutines are? "Chris M. Thomasson" <invalid_chris_thomasson_invalid@invalid.com> - 2019-08-04 20:10 -0700
          Re: Why can't I understand what coroutines are? "Chris M. Thomasson" <invalid_chris_thomasson_invalid@invalid.com> - 2019-08-04 11:20 -0700
            Re: Why can't I understand what coroutines are? Chris Vine <chris@cvine--nospam--.freeserve.co.uk> - 2019-08-04 20:30 +0100
              Re: Why can't I understand what coroutines are? "Chris M. Thomasson" <invalid_chris_thomasson_invalid@invalid.com> - 2019-08-04 14:03 -0700
              Re: Why can't I understand what coroutines are? Paavo Helde <myfirstname@osa.pri.ee> - 2019-08-05 09:36 +0300
                Re: Why can't I understand what coroutines are? "Chris M. Thomasson" <invalid_chris_thomasson_invalid@invalid.com> - 2019-08-05 14:34 -0700
          Re: Why can't I understand what coroutines are? scott@slp53.sl.home (Scott Lurndal) - 2019-08-04 19:46 +0000
        Re: Why can't I understand what coroutines are? Juha Nieminen <nospam@thanks.invalid> - 2019-08-05 08:37 +0000
          Re: Why can't I understand what coroutines are? David Brown <david.brown@hesbynett.no> - 2019-08-05 12:06 +0200
            Re: Why can't I understand what coroutines are? Juha Nieminen <nospam@thanks.invalid> - 2019-08-05 12:20 +0000
              Re: Why can't I understand what coroutines are? David Brown <david.brown@hesbynett.no> - 2019-08-06 15:06 +0200
                Re: Why can't I understand what coroutines are? David Brown <david.brown@hesbynett.no> - 2019-08-06 15:18 +0200
            Re: Why can't I understand what coroutines are? Bonita Montero <Bonita.Montero@gmail.com> - 2019-08-06 13:58 +0200
    Re: Why can't I understand what coroutines are? Sam <sam@email-scan.com> - 2019-08-04 09:17 -0400
    Re: Why can't I understand what coroutines are? Robert Wessel <robertwessel2@yahoo.com> - 2019-08-04 10:12 -0500
      Re: Why can't I understand what coroutines are? Juha Nieminen <nospam@thanks.invalid> - 2019-08-05 08:42 +0000
        Re: Why can't I understand what coroutines are? Chris Vine <chris@cvine--nospam--.freeserve.co.uk> - 2019-08-05 13:35 +0100
        Re: Why can't I understand what coroutines are? Bart <bc@freeuk.com> - 2019-08-05 20:19 +0100
        Re: Why can't I understand what coroutines are? Christian Gollwitzer <auriocus@gmx.de> - 2019-08-05 22:26 +0200
          Re: Why can't I understand what coroutines are? "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2019-08-05 23:09 +0200
            Re: Why can't I understand what coroutines are? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-08-09 19:49 -0700
              Re: Why can't I understand what coroutines are? "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2019-08-10 05:13 +0200
            Re: Why can't I understand what coroutines are? Christian Gollwitzer <auriocus@gmx.de> - 2019-08-10 08:23 +0200
              Re: Why can't I understand what coroutines are? "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2019-08-10 10:43 +0200
                Re: Why can't I understand what coroutines are? Christian Gollwitzer <auriocus@gmx.de> - 2019-08-11 22:19 +0200
                  Re: Why can't I understand what coroutines are? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-08-14 08:25 -0700
          Re: Why can't I understand what coroutines are? "Chris M. Thomasson" <invalid_chris_thomasson_invalid@invalid.com> - 2019-08-10 00:19 -0700
          Re: Why can't I understand what coroutines are? Juha Nieminen <nospam@thanks.invalid> - 2019-08-11 21:16 +0000
        Re: Why can't I understand what coroutines are? "Chris M. Thomasson" <invalid_chris_thomasson_invalid@invalid.com> - 2019-08-05 23:43 -0700
        Re: Why can't I understand what coroutines are? Bonita Montero <Bonita.Montero@gmail.com> - 2019-08-10 10:50 +0200
    Re: Why can't I understand what coroutines are? Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2019-08-04 17:57 +0100
    Re: Why can't I understand what coroutines are? "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2019-08-05 01:11 +0200
      Re: Why can't I understand what coroutines are? Juha Nieminen <nospam@thanks.invalid> - 2019-08-05 08:50 +0000
        Re: Why can't I understand what coroutines are? "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2019-08-05 16:59 +0200
      Re: Why can't I understand what coroutines are? Manfred <noname@add.invalid> - 2019-08-06 16:24 +0200
      Re: Why can't I understand what coroutines are? "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2019-08-07 00:52 +0200
        Re: Why can't I understand what coroutines are? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-08-09 18:11 -0700
    Re: Why can't I understand what coroutines are? Martijn van Buul <pino@dohd.org> - 2019-08-05 07:46 +0000

Page 3 of 4 — ← Prev page 1 2 [3] 4  Next page →

#67280

Chris Vine <chris@cvine--nospam--.freeserve.co.uk> writes:
>On Sun, 04 Aug 2019 09:23:52 -0400
>Sam <sam@email-scan.com> wrote:
>> Chris Vine writes:
>> 
>> > Asynchronous programming with callbacks normally works so that when a
>> > i/o operation might block because the resource in question (read or
>> > write) is unavailable, instead of blocking the function returns
>> > immediately and registers a callback with the program's event loop
>> > (usually based on select() or poll()), representing the i/o operation's
>> > continuation when the resource becomes available.  Programming this way
>> > using callbacks in the style of, say, Node.js is troublesome because it
>> > gives rise to what is sometimes called inversion of control, aka
>> > "callback hell".  In particular, control flow ceases to appear as a
>> > sequential series of i/o operations which can easily be reasoned about.
>> 
>> This problem was solved a long time ago. It is called "threads".
>> 
>> The funniest thing about this is that Gnome is most extreme case of this.  
>> The entire Gnome stack is just one event dispatching main loop. Everything  
>> is callbacks. But since Gnome is C code, none of this will help it, that's  
>> the funny part.
>
>Threads are very definitely not the answer.  Threads work well with
>cpu-bound workloads.  They are hopeless with i/o-bound workloads, which
>is why co-operative (possibly single-threaded) multi-tasking using
>coroutines has become popular.

I disagree.  So do the Open Data Plane (ODP) folks.   Threads work very
well with I/O bound workloads when used properly.  Last time I found a
coroutine useful was in PDP-11 assembler (JMS @(SP)+).

[toc] | [prev] | [next] | [standalone]

#67299

Sam <sam@email-scan.com> wrote:
> This problem was solved a long time ago. It is called "threads".

I think that with "threads" you are implying pre-emptive multitasking.
Doesn't that introduce lots of problems relating to mutual exclusion?
Quite a significant portion of bugs out there are related to
multithreading problems.

[toc] | [prev] | [next] | [standalone]

#67304

On 05/08/2019 10:37, Juha Nieminen wrote:
> Sam <sam@email-scan.com> wrote:
>> This problem was solved a long time ago. It is called "threads".
> 
> I think that with "threads" you are implying pre-emptive multitasking.
> Doesn't that introduce lots of problems relating to mutual exclusion?
> Quite a significant portion of bugs out there are related to
> multithreading problems.
> 

Yes, it certainly does.

One way to think about coroutines is like threads, but cooperatively 
multitasking instead of preemptive multitasking.  You, the programmer, 
have full control over which coroutine is running at a time, and when it 
can be blocked.  This has disadvantages, of course - it means more 
manual control, and it cannot take advantage of multiple cores (you need 
to run your coroutines from different threads for that).  But it has the 
advantage of being simpler and lighter (not every system is a multi-core 
multi-GHz monster), and you don't need to worry about locking, 
synchronisation, atomic accesses, races, contention, or anything like that.

I am looking forward to coroutines for my sub-GHz single core embedded 
systems.

[toc] | [prev] | [next] | [standalone]

#67308

David Brown <david.brown@hesbynett.no> wrote:
> One way to think about coroutines is like threads, but cooperatively 
> multitasking instead of preemptive multitasking.

From another forum I got the impression that C++20 coroutines are stackless.
Meaning that they don't have their own stack that's separate from the one
used by main(). Which means that you can't have a chain of function calls
in a coroutine, have one of those functions "yield", and then later return
back to that point and resume execution as normal. (Basically, and if I
understand correctly, only the coroutine function itself can "yield",
not any of the functions it might call in the normal way.)

This would make coroutines rather different from threads. Actual threads
have each their own stack that they use for function call parameters etc,
and which is independent from other threads.

In other words, it sounds to me like coroutines are, essentially,
lambda functions, or stateful functor objects, with a jump at the
beginning of the function to the position in the code that last yielded.

[toc] | [prev] | [next] | [standalone]

#67332

On 05/08/2019 14:20, Juha Nieminen wrote:
> David Brown <david.brown@hesbynett.no> wrote:
>> One way to think about coroutines is like threads, but cooperatively 
>> multitasking instead of preemptive multitasking.
> 
> From another forum I got the impression that C++20 coroutines are stackless.
> Meaning that they don't have their own stack that's separate from the one
> used by main(). Which means that you can't have a chain of function calls
> in a coroutine, have one of those functions "yield", and then later return
> back to that point and resume execution as normal. (Basically, and if I
> understand correctly, only the coroutine function itself can "yield",
> not any of the functions it might call in the normal way.)
> 
> This would make coroutines rather different from threads. Actual threads
> have each their own stack that they use for function call parameters etc,
> and which is independent from other threads.
> 
> In other words, it sounds to me like coroutines are, essentially,
> lambda functions, or stateful functor objects, with a jump at the
> beginning of the function to the position in the code that last yielded.
> 

The explanation here calls them "stackless":

<https://en.cppreference.com/w/cpp/language/coroutines>

But really, they are only "stackless" in the sense that C++ does not
actually need a stack.  They have a local state - you can have normal
local variables, and a normal call chain of normal functions.  This will
typically end up on a heap somewhere, but is effectively a local stack
for the coroutine execution state.  It is entirely possible, given
simple enough coroutines and smart enough compilers, for this all to be
boiled down to a single allocatable block.

[toc] | [prev] | [next] | [standalone]

#67333

On 06/08/2019 15:06, David Brown wrote:
> On 05/08/2019 14:20, Juha Nieminen wrote:
>> David Brown <david.brown@hesbynett.no> wrote:
>>> One way to think about coroutines is like threads, but cooperatively 
>>> multitasking instead of preemptive multitasking.
>>
>> From another forum I got the impression that C++20 coroutines are stackless.
>> Meaning that they don't have their own stack that's separate from the one
>> used by main(). Which means that you can't have a chain of function calls
>> in a coroutine, have one of those functions "yield", and then later return
>> back to that point and resume execution as normal. (Basically, and if I
>> understand correctly, only the coroutine function itself can "yield",
>> not any of the functions it might call in the normal way.)
>>
>> This would make coroutines rather different from threads. Actual threads
>> have each their own stack that they use for function call parameters etc,
>> and which is independent from other threads.
>>
>> In other words, it sounds to me like coroutines are, essentially,
>> lambda functions, or stateful functor objects, with a jump at the
>> beginning of the function to the position in the code that last yielded.
>>
> 
> The explanation here calls them "stackless":
> 
> <https://en.cppreference.com/w/cpp/language/coroutines>
> 
> But really, they are only "stackless" in the sense that C++ does not
> actually need a stack.  They have a local state - you can have normal
> local variables, and a normal call chain of normal functions.  This will
> typically end up on a heap somewhere, but is effectively a local stack
> for the coroutine execution state.  It is entirely possible, given
> simple enough coroutines and smart enough compilers, for this all to be
> boiled down to a single allocatable block.
> 

After reading some of Alf's posts in this thread, it looks like I was
wrong here and C++ coroutines will be more restricted than general
coroutines.  If they can only yield from within the coroutine function
itself, not arbitrary external functions, then the compiler can figure
out the size of the local stack frame needed and generate it as a single
block, thus avoiding any variable sized stack.


A simple and lightweight version of this has been in use in embedded
systems in C for long time.  For those that think Duff's device is cool,
macros are a joy, and the non-structured nature of "switch" is a great
idea, have a look at this:

<https://en.wikipedia.org/wiki/Protothread>
<http://dunkels.com/adam/pt/>

[toc] | [prev] | [next] | [standalone]

#67329

> One way to think about coroutines is like threads, but
> cooperatively  multitasking instead of preemptive multitasking.

It's not really multitasking since the corutine-context can only
live as long as the calling function. With cooperative multitasking
like with fibers in Windows, a fiber can end without stopping other
contexts.

[toc] | [prev] | [next] | [standalone]

#67268

[Multipart message — attachments visible in raw view] — view raw

Juha Nieminen writes:

> This tells me nothing. I don't get it.

You are not alone. I had the same reaction.

After reading all the available documentation on it, I believe that  
coroutines are a solution in search of a problem.

[toc] | [prev] | [next] | [standalone]

#67273

On Sun, 4 Aug 2019 09:37:39 -0000 (UTC), Juha Nieminen
<nospam@thanks.invalid> wrote:

>C++20 will introduce support for coroutines. To this day, for reasons
>that are completely mysterious even to me, I have *absolutely no idea*
>what they are. I just don't get it.
>
>I go to the Wikipedia page "Coroutine"... and it tells me nothing.
>
>"Coroutines are computer program components that generalize subroutines
>for non-preemptive multitasking, by allowing execution to be suspended
>and resumed. Coroutines are well-suited for implementing familiar program
>components such as cooperative tasks, exceptions, event loops, iterators,
>infinite lists and pipes."
>
>This tells me nothing. I don't get it.
>
>"By contrast, coroutines can exit by calling other coroutines, which may
>later return to the point where they were invoked in the original
>coroutine; from the coroutine's point of view, it is not exiting but
>calling another coroutine."
>
>Can exit by calling other coroutines... And then the execution later
>resumes from that calling point. This is not "exiting" but "yielding",
>whatever that's supposed to mean.
>
>Sounds like a normal function call to me, but what do I know? I can't
>understand what this is saying. It's like it's speaking in legible
>English, yet it somehow is complete gibberish at the same time. I don't
>get it.
>
>It then gives a pseudocode example of coroutines... that look exactly
>like a function calling another (which then just returns to the
>original caller).
>
>==========================================
>var q := new queue
>
>coroutine produce
>    loop
>        while q is not full
>            create some new items
>            add the items to q
>        yield to consume
>
>coroutine consume
>    loop
>        while q is not empty
>            remove some items from q
>            use the items
>        yield to produce
>==========================================
>
>This looks to me exactly like
>
>==========================================
>var q := new queue
>
>coroutine produce
>    loop
>        while q is not full
>            create some new items
>            add the items to q
>        call consume
>
>coroutine consume
>    while q is not empty
>        remove some items from q
>        use the items
>    return
>==========================================
>
>But what do I know? I don't get it.
>
>Ok, Wikipedia is just a generic article about coroutines. Maybe
>https://en.cppreference.com/w/cpp/language/coroutines has a better
>explanation. It's done from the perspective of C++ in particular,
>after all.
>
>"A coroutine is a function that can suspend execution to be resumed
>later. Coroutines are stackless: they suspend execution by returning
>to the caller. This allows for sequential code that executes
>asynchronously (e.g. to handle non-blocking I/O without explicit
>callbacks), and also supports algorithms on lazy-computed infinite
>sequences and other uses."
>
>A function that can suspend execution to be resumed later...
>Yeah, I don't get it. Allows sequential code that executes
>asynchronously... What? Supports algorithms on lazy-computed infinite
>sequences... Ok, but what does this all mean? I don't get it.
>
>The examples given are complete gibberish. I have *absolutely no
>idea* what something like this is supposed to mean:
>
>    co_await async_write(socket, buffer(data, n));
>
>co_await? What?
>
>It seems that everybody else is awaiting (hah!) and praising coroutines
>like the second coming of Christ. Yet I just can't understand what they
>are, or how exactly they are used or useful. All web pages I can find
>are legible English that still somehow manages to be completely meaningless
>gibberish that tells me nothing.


The problem is that this is a bit oversimplified:

var q := new queue

coroutine produce
    loop
        while q is not full
            create some new items
            add the items to q
        yield to consume

coroutine consume
    loop
        while q is not empty
            remove some items from q
            use the items
        yield to produce

It's not wrong, but rather it's been reduced to so simple a form that
coroutines are not a great help.  That's one of the classic "problems"
with coroutines - there's not a trivial example of why you'd want
them.

Consider instead:
var z := ...

coroutine produce
    loop
        ...code...
        loop
            ...code...
            create z
            yield to consume
            ...code...
        endloop
        ...code...
    endloop

coroutine consume
    loop
        ...code...
        loop
            ...code...
            yield to produce
            process z
            ...code...
        endloop
        ...code...
    endloop

Now try unwinding those into a simple subroutine call.

The point is that the producer can generate the output at any
convenient point (that's not different from having the producer call
the consumer at a point convenient for the producer), but also the
*consumer* can acquire the item at a point convenient for the
*consumer*.

Consider a program that processes an input stream - it would normally
call getc() (or whatever) at various places, probably several nested
subroutines and/or loops deep.  Consider how much more convoluted the
code would be if instead the OS called main() with every character
(and yes, that's the model many event driven GUIs use).

The point of a coroutine is that it can "suspend" at some arbitrary
point in its logic (say a dozens subroutine calls and loops deep, plus
a bunch of state from local variables), and then continue from that
point (still those dozen subroutine calls and loops deep, with state
intact), rather than at the beginning of the routine again.

[toc] | [prev] | [next] | [standalone]

#67300

Robert Wessel <robertwessel2@yahoo.com> wrote:
> The point of a coroutine is that it can "suspend" at some arbitrary
> point in its logic (say a dozens subroutine calls and loops deep, plus
> a bunch of state from local variables), and then continue from that
> point (still those dozen subroutine calls and loops deep, with state
> intact), rather than at the beginning of the routine again.

From all the text and discussion out there I'm getting the picture that
coroutines are a bit like lambda functions (ie. essentially stateful
functors), with the difference that the coroutine can be "called" again
in such a manner that it continues from where it "returned" last time,
rather than always from the beginning (which would happen with lambdas).

Is that correct?

Is there a simple example of a situation where this is significantly
beneficial compared to a lambda or an explicitly written functor
(ie. a class with member variables and an operator())?

[toc] | [prev] | [next] | [standalone]

#67309

On Mon, 5 Aug 2019 08:42:48 -0000 (UTC)
Juha Nieminen <nospam@thanks.invalid> wrote:
> Robert Wessel <robertwessel2@yahoo.com> wrote:
> > The point of a coroutine is that it can "suspend" at some arbitrary
> > point in its logic (say a dozens subroutine calls and loops deep, plus
> > a bunch of state from local variables), and then continue from that
> > point (still those dozen subroutine calls and loops deep, with state
> > intact), rather than at the beginning of the routine again.
> 
> From all the text and discussion out there I'm getting the picture that
> coroutines are a bit like lambda functions (ie. essentially stateful
> functors), with the difference that the coroutine can be "called" again
> in such a manner that it continues from where it "returned" last time,
> rather than always from the beginning (which would happen with lambdas).
> 
> Is that correct?
> 
> Is there a simple example of a situation where this is significantly
> beneficial compared to a lambda or an explicitly written functor
> (ie. a class with member variables and an operator())?

This is essentially correct although in speaking of lambda functions
with closures you are moving from the concept ("what is a coroutine?")
to one possible implementation.

Asymmetric coroutines (ones which can only suspend to the caller) are
indeed like ordinary functions (not necessarily lambda functions) except
that they can emit an enhanced return statement at some point in the
function's execution and, by some arrangement to be implemented, return
to that point later.  Symmetric coroutines don't "return" in quite this
way - instead they yield to some other coroutine, which need not be the
same as the one that last resumed them.

One possible but fragile implementation of a coroutine is a stateful
functor built by hand along the lines you describe.  For example, for an
asymmetric coroutine you could construct a functor whose operator() has
three return statements as possible exit points.  The functor object
could have an enum as member data which describes what point the
function has at present reached.  When the functor is to "yield" it
sets the enum to the correct point, saves its local variables to the
functor's data variables and then returns.  When invoked again
("resumed") it first examines the enum and jumps to the correct part of
the operator() function where it is to resume, and if necessary
re-establishes its local state.  Note also that C has setjmp() and
longjmp() as primitives which are similar to delimited continuations
(but not recommended for use in C++ because longjumps give undefined
behaviour if non-trivial objects are in scope).

In addition to symmetric and asymmetric coroutines, you can also have
stackfull and stackless coroutines.  "Stackless" is a bit misleading:
it means that the coroutine does not need a stack while it is suspended
(clearly it needs one when resumed), allowing the stack to be reused
in the meantime.

[toc] | [prev] | [next] | [standalone]

#67318

On 05/08/2019 09:42, Juha Nieminen wrote:
> Robert Wessel <robertwessel2@yahoo.com> wrote:
>> The point of a coroutine is that it can "suspend" at some arbitrary
>> point in its logic (say a dozens subroutine calls and loops deep, plus
>> a bunch of state from local variables), and then continue from that
>> point (still those dozen subroutine calls and loops deep, with state
>> intact), rather than at the beginning of the routine again.
> 
>  From all the text and discussion out there I'm getting the picture that
> coroutines are a bit like lambda functions (ie. essentially stateful
> functors), with the difference that the coroutine can be "called" again
> in such a manner that it continues from where it "returned" last time,
> rather than always from the beginning (which would happen with lambdas).
> 
> Is that correct?
> 
> Is there a simple example of a situation where this is significantly
> beneficial compared to a lambda or an explicitly written functor
> (ie. a class with member variables and an operator())?

I don't get coroutines either. Since I have also implemented languages, 
I sometimes put in features I've heard of which sound neat, although 
that's often just for box-ticking as I then never use the feature again.

But coroutines, I wouldn't even bother ticking a box for.

However.... with 'generators', I do understand how they can be useful, 
and which are something I've been thinking about adding. And generators, 
I understand, can be implemented with coroutines.

(Although I would just create whatever I can see will be necessary. If I 
end up inventing something like a coroutine, then that would be cool 
too, even if I couldn't tell you what they are.)

Anyway, 'generators' might be one easy-to-understand application of 
'coroutines'.

[toc] | [prev] | [next] | [standalone]

#67319

Am 05.08.19 um 10:42 schrieb Juha Nieminen:
>  From all the text and discussion out there I'm getting the picture that
> coroutines are a bit like lambda functions (ie. essentially stateful
> functors), with the difference that the coroutine can be "called" again
> in such a manner that it continues from where it "returned" last time,
> rather than always from the beginning (which would happen with lambdas).
> 
> Is that correct?

Similar to my understanding of it.
> 
> Is there a simple example of a situation where this is significantly
> beneficial compared to a lambda or an explicitly written functor
> (ie. a class with member variables and an operator())?
> 

When you yield() from inside a loop. With coroutines, you can implement 
generators - a functor which returns a value from a set, one at a time - 
similar to iterators. You can write your code *as if* the yielding would 
be a simple function call.

For example, consider a function which prints the time as hours:minutes 
from midnight to midnight:

void printtime() {
   for (int hour=0; hour<24; hour++) {
     for (int min=0; min<60; min++) {
        std::cout<<hour<<":"<<min<<std::endl;
      }
    }
}

Now you want a functor that returns the formatted string, one at a time, 
for each call. Coroutine solution:*

void printtime() {
   for (int hour=0; hour<24; hour++) {
     for (int min=0; min<60; min++) {
        std::ostringstream os;
        os<<hour<<":"<<min;
        co_yield(os.str());
      }
    }
}


The only significant change is print -> yield. If you had to write this 
thing manually, you would need to unroll the loops and correctly switch 
the state when the minutes surpass 60.

With two for loops, that is still practically doable, albeit 
inconvenient - but now consider to implement an iterator for 
breadth-first traversal of a tree. Trivial algorithm for printing:

void bftraverse(Tree* root) {
    std::cout<<root->content;
    if (root->left) bftraverse(root->left);
    if (root->right) bftraverse(root->right);
}

Now please unroll this into a functor which produces one value at a 
time. Good luck getting this right at the first time, basically that 
would be reinventing an iterative algorithm from TAOCP.

Coroutine solution:

void bftraverse(Tree* root) {
    co_yield(root->content);
    if (root->left) bftraverse(root->left);
    if (root->right) bftraverse(root->right);
}

voilá.

If you're patient, search for videos from Gor Nishanov, he has provided 
some examples in C++ (tree traversal is one of them).

	Christian


(*) I haven't tried C++ coroutines, so the syntax may be off. I'm using 
them in Python and Tcl only

[toc] | [prev] | [next] | [standalone]

#67320

On 05.08.2019 22:26, Christian Gollwitzer wrote:
> [snip]
> When you yield() from inside a loop. With coroutines, you can implement 
> generators - a functor which returns a value from a set, one at a time - 
> similar to iterators. You can write your code *as if* the yielding would 
> be a simple function call.
> 
> For example, consider a function which prints the time as hours:minutes 
> from midnight to midnight:
> 
> void printtime() {
>    for (int hour=0; hour<24; hour++) {
>      for (int min=0; min<60; min++) {
>         std::cout<<hour<<":"<<min<<std::endl;
>       }
>     }
> }
> 
> Now you want a functor that returns the formatted string, one at a time, 
> for each call. Coroutine solution:*
> 
> void printtime() {
>    for (int hour=0; hour<24; hour++) {
>      for (int min=0; min<60; min++) {
>         std::ostringstream os;
>         os<<hour<<":"<<min;
>         co_yield(os.str());
>       }
>     }
> }
> 
> 
> The only significant change is print -> yield. If you had to write this 
> thing manually, you would need to unroll the loops and correctly switch 
> the state when the minutes surpass 60.
> 
> With two for loops, that is still practically doable, albeit 
> inconvenient - but now consider to implement an iterator for 
> breadth-first traversal of a tree. Trivial algorithm for printing:
> 
> void bftraverse(Tree* root) {
>     std::cout<<root->content;
>     if (root->left) bftraverse(root->left);
>     if (root->right) bftraverse(root->right);
> }
> 
> Now please unroll this into a functor which produces one value at a 
> time. Good luck getting this right at the first time, basically that 
> would be reinventing an iterative algorithm from TAOCP.
> 
> Coroutine solution:
> 
> void bftraverse(Tree* root) {
>     co_yield(root->content);
>     if (root->left) bftraverse(root->left);
>     if (root->right) bftraverse(root->right);
> }
> 
> voilá.

As I understand it this generates a new coroutine instance, with 
dynamically allocated state, for each call.

It needs to do that (modulo optimization) to represent the call stack 
for the recursive calls.

Thus it's convenient, but possibly/probably inefficient.


> If you're patient, search for videos from Gor Nishanov, he has provided 
> some examples in C++ (tree traversal is one of them).
> 
>      Christian
> 
> 
> (*) I haven't tried C++ coroutines, so the syntax may be off. I'm using 
> them in Python and Tcl only

Same for me, except I'm only using my head. That's not intelligent, 
because the C++20 coroutines are modeled on the Visual C++ coroutines, 
except they've changed the keywords to more unreadable and tried to make 
the documentation like impenetrable machine code. I wish I was more 
intelligent, at least enough to just use the VC compiler I have...

Anyway, to avoid the dynamic allocation inefficiency I'd probably do 
something like this:


auto bftraverse( Node* root )
     -> optional<Data>
{
     stack<Node*> nodes;
     nodes.push( root );
     while( not nodes.empty() ) {
         const auto p = nodes.top();
         nodes.pop();
         if( p == nullptr ) {
             co_return {};
         }
         co_yield p->data;
         if( p->right ) { nodes.push( p->right ); }
         if( p>left )   { nodes.push( p->left ); }
     }
}


Except that from cppreference's page it seems that the trailing return 
type syntax isn't supported for coroutines. If so then that's an 
inconsistency that will probably be fixed later.

I guess that at some point someone is going to publish a guideline, 
"Recursive coroutines considered harmful". For efficiency. Then someone 
else is going to counter that with ""Recursive coroutines considered 
harmful" considered harmful", for convenience and development time. And 
then there will maybe be some discussion. In forums of the mainly 
willfully ignorant those who post either naturally recursive or 
unnaturally iterative coroutines will sometimes get blasts of anonymous 
downvotes. For not following the perceived best practice. And so on. :)


Cheers!,

- Alf

[toc] | [prev] | [next] | [standalone]

#67509

"Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> writes:

>> [...]
>
> Anyway, to avoid [a recursive coroutine] I'd probably do
> something like this:
>
>
> auto bftraverse( Node* root )
>     -> optional<Data>
> {
>     stack<Node*> nodes;
>     nodes.push( root );
>     while( not nodes.empty() ) {
>         const auto p = nodes.top();
>         nodes.pop();
>         if( p == nullptr ) {
>             co_return {};
>         }
>         co_yield p->data;
>         if( p->right ) { nodes.push( p->right ); }
>         if( p>left )   { nodes.push( p->left ); }
>     }
> }

The function body can be simplified thus:

    stack<Node*> nodes;
    nodes.push( root );
    while( not nodes.empty() ) {
        const auto p = nodes.top();
        nodes.pop();
        if( !p )  continue;
        co_yield p->data;
        nodes.push( p->right );
        nodes.push( p->left );
    }

[toc] | [prev] | [next] | [standalone]

#67510

On 10.08.2019 04:49, Tim Rentsch wrote:
> "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> writes:
> 
>>> [...]
>>
>> Anyway, to avoid [a recursive coroutine] I'd probably do
>> something like this:
>>
>>
>> auto bftraverse( Node* root )
>>      -> optional<Data>
>> {
>>      stack<Node*> nodes;
>>      nodes.push( root );
>>      while( not nodes.empty() ) {
>>          const auto p = nodes.top();
>>          nodes.pop();
>>          if( p == nullptr ) {
>>              co_return {};
>>          }
>>          co_yield p->data;
>>          if( p->right ) { nodes.push( p->right ); }
>>          if( p>left )   { nodes.push( p->left ); }
>>      }
>> }
> 
> The function body can be simplified thus:
> 
>      stack<Node*> nodes;
>      nodes.push( root );
>      while( not nodes.empty() ) {
>          const auto p = nodes.top();
>          nodes.pop();
>          if( !p )  continue;
>          co_yield p->data;
>          nodes.push( p->right );
>          nodes.push( p->left );
>      }

Thanks.

Don't know why I wrote that so complicated, with no nullpointers pushed 
except possibly the root. But I guess I was just transforming the 
original code, which had those conditional pushes.


Cheers!,

- Alf

[toc] | [prev] | [next] | [standalone]

#67511

Am 05.08.19 um 23:09 schrieb Alf P. Steinbach:
> On 05.08.2019 22:26, Christian Gollwitzer wrote:
>> Coroutine solution:
>>
>> void bftraverse(Tree* root) {
>>     co_yield(root->content);
>>     if (root->left) bftraverse(root->left);
>>     if (root->right) bftraverse(root->right);
>> }
>>
>> voilá.
> 
> As I understand it this generates a new coroutine instance, with 
> dynamically allocated state, for each call.

yes, of course.

> It needs to do that (modulo optimization) to represent the call stack 
> for the recursive calls.
> 
> Thus it's convenient, but possibly/probably inefficient.
> 

> 
> auto bftraverse( Node* root )
>      -> optional<Data>
> {
>      stack<Node*> nodes;
>      nodes.push( root );
>      while( not nodes.empty() ) {
>          const auto p = nodes.top();
>          nodes.pop();
>          if( p == nullptr ) {
>              co_return {};
>          }
>          co_yield p->data;
>          if( p->right ) { nodes.push( p->right ); }
>          if( p>left )   { nodes.push( p->left ); }
>      }
> }
> 

This code now manages the stack manually and is half-way to the 
transformation into the iterative versino which you need to write 
*without* coroutines.

I'm not sure my message was received, I try again. So consider, you 
decide to go from breadth-first traversal to in-order traversal.

Coroutine:

void bftraverse(Tree* root) {
      if (root->left) [<-] bftraverse(root->left);
      co_yield(root->content);
      if (root->right) [<-] bftraverse(root->right);
}

The only thing that has changed, is the order of the yield instructions. 
(plus I added the forgotten [<-] thing as shown in the TR paper, which 
means the same as "yield from" in Python)


How to transform your unfolded code? Let's replace:

 >          co_yield p->data;
 >          if( p->right ) { nodes.push( p->right ); }
 >          if( p>left )   { nodes.push( p->left ); }

by

 >          if( p->right ) { nodes.push( p->right ); }
 >          co_yield p->data;
 >          if( p>left )   { nodes.push( p->left ); }

and surprisingly, it is still doing breadth-first search. Transforming 
this correctly means either a different stack management, or a special 
algorithm invented by geniuses which can walks along the tree leafs-

The point of coroutines is not to maximize efficieny, but to write code 
*as if* it were the original simple, clear algorithm, but resulting in a 
state machine. For some cases this can actually improve efficiency, e.g 
for asynchronous network code, because the manual async thing is so 
complex that noone would do it.

The price to pay is actually not that high. Your stack uses one node* 
for the coroutine state. The compiler-generated version uses all local 
variables (just Node*) plus an instruction pointer, so yes it is more, 
but not that much. Gor Nishanov actually claimed in his talk, that VC++ 
coroutines are efficient enough for asynchronous access to *main memory*

https://www.youtube.com/watch?v=j9tlJAqMV7U

	Christian

[toc] | [prev] | [next] | [standalone]

#67515

On 10.08.2019 08:23, Christian Gollwitzer wrote:
> Am 05.08.19 um 23:09 schrieb Alf P. Steinbach:
>> On 05.08.2019 22:26, Christian Gollwitzer wrote:
>>> Coroutine solution:
>>>
>>> void bftraverse(Tree* root) {
>>>     co_yield(root->content);
>>>     if (root->left) bftraverse(root->left);
>>>     if (root->right) bftraverse(root->right);
>>> }
>>>
>>> voilá.
>>
>> As I understand it this generates a new coroutine instance, with 
>> dynamically allocated state, for each call.
> 
> yes, of course.
> 
>> It needs to do that (modulo optimization) to represent the call stack 
>> for the recursive calls.
>>
>> Thus it's convenient, but possibly/probably inefficient.
>>
> 
>>
>> auto bftraverse( Node* root )
>>      -> optional<Data>
>> {
>>      stack<Node*> nodes;
>>      nodes.push( root );
>>      while( not nodes.empty() ) {
>>          const auto p = nodes.top();
>>          nodes.pop();
>>          if( p == nullptr ) {
>>              co_return {};
>>          }
>>          co_yield p->data;
>>          if( p->right ) { nodes.push( p->right ); }
>>          if( p>left )   { nodes.push( p->left ); }
>>      }
>> }
>>
> 
> This code now manages the stack manually and is half-way to the 
> transformation into the iterative versino which you need to write 
> *without* coroutines.
> 
> I'm not sure my message was received, I try again. So consider, you 
> decide to go from breadth-first traversal to in-order traversal.

I think you mean go from pre-order to in-order.


> Coroutine:
> 
> void bftraverse(Tree* root) {
>       if (root->left) [<-] bftraverse(root->left);
>       co_yield(root->content);
>       if (root->right) [<-] bftraverse(root->right);
> }
> 
> The only thing that has changed, is the order of the yield instructions. 
> (plus I added the forgotten [<-] thing as shown in the TR paper, which 
> means the same as "yield from" in Python)

I haven't yet stumbled upon that notation, so I think it must be 
something that once was proposed but has been rejected?

Anyway, I'm now aware that for C++20 coroutines one needs a return type 
that implements a lot of stuff. With Visual C++ that's apparently 
provided by `std::future`. I don't know about the standard.


> How to transform your unfolded code? Let's replace:
> 
>  >          co_yield p->data;
>  >          if( p->right ) { nodes.push( p->right ); }
>  >          if( p>left )   { nodes.push( p->left ); }
> 
> by
> 
>  >          if( p->right ) { nodes.push( p->right ); }
>  >          co_yield p->data;
>  >          if( p>left )   { nodes.push( p->left ); }
> 
> and surprisingly, it is still doing breadth-first search. Transforming 
> this correctly means either a different stack management, or a special 
> algorithm invented by geniuses which can walks along the tree leafs-

Iterative in-order isn't that hard.

After having output (or whatever) the left subtree of node N, one 
outputs N.data and registers a sufficient subset of nodes in the right 
subtree in the data structure, which can be a stack, so that the same 
general process of popping out a node, displaying it, and registering 
some more, can work.

What's necessary then is just that the first node popped out and thus 
next output, should be the leftmost leaf of the right subtree. To do 
that it's necessary to register all the nodes down to that left. I.e., a 
loop, to register (push) the nodes down the chain to that leaf node.

     void process_tree_node( const Node& node )
     {
         cout << node.data;
     }

     void process_tree_nodes_inorder( const Type_<const Node*> p_root )
     {
         stack<const Node*> nodes;
         const Node* p_current = p_root;
         for( ;; ) {
             while( p_current ) {
                 nodes.push( p_current );
                 p_current = p_current->left;
             }
             if( is_empty( nodes ) ) {
                 break;
             }
             p_current = popped_top( nodes );
             process_tree_node( *p_current );
             p_current = p_current->right;
         }
     }


> The point of coroutines is not to maximize efficieny, but to write code 
> *as if* it were the original simple, clear algorithm, but resulting in a 
> state machine. For some cases this can actually improve efficiency, e.g 
> for asynchronous network code, because the manual async thing is so 
> complex that noone would do it.
> 
> The price to pay is actually not that high. Your stack uses one node* 
> for the coroutine state. The compiler-generated version uses all local 
> variables (just Node*) plus an instruction pointer, so yes it is more, 
> but not that much. Gor Nishanov actually claimed in his talk, that VC++ 
> coroutines are efficient enough for asynchronous access to *main memory*
> 
> https://www.youtube.com/watch?v=j9tlJAqMV7U


Cheers!,

- Alf

[toc] | [prev] | [next] | [standalone]

#67571

Am 10.08.19 um 10:43 schrieb Alf P. Steinbach:
> On 10.08.2019 08:23, Christian Gollwitzer wrote:
>> and surprisingly, it is still doing breadth-first search. Transforming 
>> this correctly means either a different stack management, or a special 
>> algorithm invented by geniuses which can walks along the tree leafs-
> 
> Iterative in-order isn't that hard.
> 

By the algorithm "invented by geniuses" for this particular case I was 
referring to Morris traversal, which walks a tree in in-order sequence 
with O(1) space and time. See e.g. 
https://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion-and-without-stack/ 


It modifies the tree along its way, but restores it when you do the full 
traversal. That would be the most efficient method, at the expense of 
head-scratching and that you can't stop it in the middle without ruining 
your data structure.

	Christian

[toc] | [prev] | [next] | [standalone]

#67652

Christian Gollwitzer <auriocus@gmx.de> writes:

> Am 10.08.19 um 10:43 schrieb Alf P. Steinbach:
>
>> On 10.08.2019 08:23, Christian Gollwitzer wrote:
>>
>>> and surprisingly, it is still doing breadth-first
>>> search.  Transforming this correctly means either a different stack
>>> management, or a special algorithm invented by geniuses which can
>>> walks along the tree leafs-
>>
>> Iterative in-order isn't that hard.
>
> By the algorithm "invented by geniuses" for this particular case I was
> referring to Morris traversal, which walks a tree in in-order sequence
> with O(1) space and time. [...]

Of course you meant to say O(1) space and O(n) time.

[toc] | [prev] | [next] | [standalone]

Page 3 of 4 — ← Prev page 1 2 [3] 4  Next page →

Back to top | Article view | comp.lang.c++

csiph-web