Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c++ > #67511
| From | Christian Gollwitzer <auriocus@gmx.de> |
|---|---|
| Newsgroups | comp.lang.c++ |
| Subject | Re: Why can't I understand what coroutines are? |
| Date | 2019-08-10 08:23 +0200 |
| Organization | A noiseless patient Spider |
| Message-ID | <qilnsg$e9a$1@dont-email.me> (permalink) |
| References | <qi6910$1eht$1@adenine.netfront.net> <0qqdkep3adsd1m07tp0gnsn21pkvds12kk@4ax.com> <qi8q65$6hs$1@adenine.netfront.net> <qia3ec$gm8$1@dont-email.me> <qia5v7$ui7$1@dont-email.me> |
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
Back to comp.lang.c++ | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
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
csiph-web