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

Groups > comp.lang.c++ > #67515

Re: Why can't I understand what coroutines are?

From "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com>
Newsgroups comp.lang.c++
Subject Re: Why can't I understand what coroutines are?
Date 2019-08-10 10:43 +0200
Organization A noiseless patient Spider
Message-ID <qim043$jbj$1@dont-email.me> (permalink)
References (1 earlier) <0qqdkep3adsd1m07tp0gnsn21pkvds12kk@4ax.com> <qi8q65$6hs$1@adenine.netfront.net> <qia3ec$gm8$1@dont-email.me> <qia5v7$ui7$1@dont-email.me> <qilnsg$e9a$1@dont-email.me>

Show all headers | View raw

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

Back to comp.lang.c++ | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

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