220 14197 <05a08ac6-f9b8-4ebb-9cb8-9a37a6fd4527@isocpp.org> article Path: news.gmane.org!not-for-mail From: Giovanni Piero Deretta Newsgroups: gmane.comp.lang.c++.isocpp.proposals Subject: Re: comment on n4244 Date: Fri, 24 Oct 2014 07:46:40 -0700 (PDT) Lines: 366 Approved: news@gmane.org Message-ID: <05a08ac6-f9b8-4ebb-9cb8-9a37a6fd4527@isocpp.org> References: <5d78c59b-4d67-45f6-9d99-8c4beeeac055@isocpp.org> <5344687e-e1de-4205-885c-b5c2f9580129@isocpp.org> <187da710-8adc-4516-bf64-263951503bc7@isocpp.org> <42ddf641-27c7-42a5-ab1c-772667797e5b@isocpp.org> Reply-To: std-proposals@isocpp.org NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: multipart/alternative; boundary="----=_Part_1862_770612441.1414162000188" X-Trace: ger.gmane.org 1414162012 10838 80.91.229.3 (24 Oct 2014 14:46:52 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Fri, 24 Oct 2014 14:46:52 +0000 (UTC) To: std-proposals@isocpp.org Original-X-From: std-proposals+bncBDEP3I7TGEINBTFJUICRUBBQ4T4CK@isocpp.org Fri Oct 24 16:46:42 2014 Return-path: Envelope-to: gclcip-std-proposals@m.gmane.org Original-Received: from mail-ig0-f200.google.com ([209.85.213.200]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1Xhg8Y-00012k-0j for gclcip-std-proposals@m.gmane.org; Fri, 24 Oct 2014 16:46:42 +0200 Original-Received: by mail-ig0-f200.google.com with SMTP id h3sf4409515igd.3 for ; Fri, 24 Oct 2014 07:46:41 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=date:from:to:message-id:in-reply-to:references:subject:mime-version :x-original-sender:reply-to:precedence:mailing-list:list-id :list-post:list-help:list-archive:list-subscribe:list-unsubscribe :content-type; bh=m4giYSh8AmS+Q8WVbl6Va1ViiWHOOd9ILv9/0da3e8k=; b=q8x/mxIPVSDuxLrz/Se9tq9RjWKIkaEpFcNyNlWuNckjqBqP6aZvl8KfawOE9ma6vZ fPM2LUqRcFcWpgMY6Zms9I7QCsidDs+9cl8AzFGPe2p0tH7W6lMkZ7Wh2eBa1uEU/UlD e4P0QAjB1BW/vpf6bWcxnHGsVAHyZ6WU7d3m5HlLtddCtwb1Yu2GoSPAy8LaOEi/xi/4 8186Q0p2CE7oqj5nN/pnCII6MFnDpRy91GeRMcgc3hjm9mJwI+RfDvK5SC8mdfYnsWJW CPoa+G7pe3UsT3FFP+g7UhY+5CTXTzWPIQoZRHGociZ+PPPsOyY28KC42A8he1KOXeOH qTwA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:date:from:to:message-id:in-reply-to:references :subject:mime-version:x-original-sender:reply-to:precedence :mailing-list:list-id:list-post:list-help:list-archive :list-subscribe:list-unsubscribe:content-type; bh=m4giYSh8AmS+Q8WVbl6Va1ViiWHOOd9ILv9/0da3e8k=; b=COhfVOohWOYekGvmkIE5Fn8sbg6Bl56044HYtCl8sKqm1nRDenbyy0uIjbueBHuKzv IMn6bmjrbBF4s2vOVPjnI20ufUWDbg+p86gr7M5PAla2Tf9iuXFKQSR2AL3AZWAcHaG0 qicWeHoJZfgtr8YyTxB1iVuTOcGgSbRa89ycKFLJ1kHPdTMFsMsevp9Fd8KqLBPOVh+z NhCpOGdUB9Xt5CJSH8LfoOdIfFpL2zyPjK9+68cquUOCpDSmHSPFAfNocWMsGInzXNI9 i/sS2Hyc/ST88JfEg6D7UnDe9M6do5Np1onWFXxEFv31e9zK/d2/h1NvCWA3eLCAx5Ac VTuw== X-Gm-Message-State: ALoCoQkmBWDbDXtiOnL6w28wgsXZtMLcaaeDIDWIk0+SYtgnvfzMSHaDTtMbnVsHlSqdjVmF8xgB X-Received: by 10.42.200.206 with SMTP id ex14mr12776679icb.4.1414162001348; Fri, 24 Oct 2014 07:46:41 -0700 (PDT) X-BeenThere: std-proposals@isocpp.org Original-Received: by 10.140.42.56 with SMTP id b53ls1726254qga.89.gmail; Fri, 24 Oct 2014 07:46:40 -0700 (PDT) X-Received: by 10.140.105.34 with SMTP id b31mr9511qgf.31.1414162000684; Fri, 24 Oct 2014 07:46:40 -0700 (PDT) In-Reply-To: X-Original-Sender: gpderetta@gmail.com Precedence: list Mailing-list: list std-proposals@isocpp.org; contact std-proposals+owners@isocpp.org List-ID: X-Google-Group-Id: 399137483710 List-Post: , List-Help: , List-Archive: List-Subscribe: , List-Unsubscribe: , Xref: news.gmane.org gmane.comp.lang.c++.isocpp.proposals:14197 Archived-At: ------=_Part_1862_770612441.1414162000188 Content-Type: text/plain; charset=UTF-8 On Friday, October 24, 2014 2:44:04 PM UTC+1, Gor Nishanov wrote: > > Hi Giovanni: > > >> "Same Fringe" requires stackfull coroutines to be implemented efficiently >> (it needs to yield deep inside a recursive tree visit). With stackless >> generators (like those of python, C# and those proposed for C++ other than >> Oliver&Nat proposal), you would need to yield at every stack level but it >> would in practice make yielding an O(log n) operation, >> > > I don't think so. It depends how you implement yield a generator. In a > generators, supported by N4134, when you yield not a value but another > generator, it treats it as await until that generator is finished, thus it > is always the very top generator that keeps yielding values to the user, > and when the user pulls the value from the generator it goes straight back > to the very top one. It does not walk the generator "stack" to do that. > Actually right after posting I realized that a sufficiently smart implementation could do something like that. You would still need to heap allocate every step of the recursion depth though, right? > > Stackful do have cheaper recursive invocations because they have normal > stack, but it is compensated by more expensive context switch, thus making > each yield more expensive. > > Quick test using boost::context vs N4134 (note we did not implement yet > any coroutine specific optimizations and our ventual codegen will be much > better. Remember when Stephanov did STL it was not zero-overhead on any > existing compiler). > > Anyway: > > This is what is being tested: > > generator GoDeep(int depth) { > yield depth; > if (depth > 0) yield GoDeep(depth-1); > } > this is 'tail' recursive though; a full tree visit wouldn't benefit from it. Does it make a difference with your implementation? Does it allocate a frame every iteration or the compiler can reuse the frame it was going to deallocate? > compared to: > [...] > Stackful: 0.417057 secs: yields 10000000 values 41.705700ns per each > > Stackless: 0.517368 secs: yields 10000001 values 51.736836ns per each > hum, 41ns per iteration seems a bit high. A stackful coroutine yield should be around 10 clock cycles: save callee save registers, restore callee save registers (saving and restoring can be done in parallel), pop return address and jump (perfectly predictable in this case). In this specific case even the return is perfectly predicted (which is > Again, with better codegen we will be beating stackful on recursive > problems when higher recursive call overhead of stackless is less than > higher yield cost on stackful. > Possibly. Note that also the stackful version could benefit from compiler support like only saving clobbered registers and saving by moving to unused registers instead of the stack (which takes advantage of "free" register renames). Of course it will always be much easier for the compiler to inline the callee of a stackless generator than for a stackfull implementation (pretty much requiring a full CPS conversion). > >> frames to support arbitrary recursion depth (in practice reifying the >> call stack), but I might be wrong here. >> > > Yeah. I really want Chris to chime in, and hopefully provide a full > implementation for GoDeep() > > Simple extension of an example from N4244 auto countdown_squared(int n) { return [n]() resumable { std::cout << "Counting down from " << n << "\n"; while (n > 0) { yield n; yield from countdown_squared(n -1); n -= 1; } }; } As it is, it couldn't possibly compile. countdown_squared will need to wrap its result in a box. > Personally I would like to see both styles in the standard: full >> Oliver&Nat coroutines for the general case and 0-overhead Chris' style >> generators for iteration >> > > I think stackless can take the coroutine niche. I showed about that > stackles can match stackful in the problem domain when stackful is king. > > However, I do believe that machinery powering N9835 (aka boost::context / > fibers) is valuable as it can serve as a foundation for cooperative user > mode threads in C++ / fibers > the advantage of the stackful aproaches is that they interoperate with existing code which is a huge win. No need to convert everything in the call stack. For example, any function that takes an STL-style output iterator can be trivially non-intrusively converted to a generator. It has a cost of course. > >> and async continuations that do not require keeping around the full >> stack. Because of the simplicity I think Chris' work has more chances to >> get into the standard. >> > > :-) As you can guess, I hold different opinion on this particular point. > :) ; As far as I can see N4244 is a strict superset of N4134 (that is, additional functionality can be built on top), so in the interest of generality I would prefer the former to the latter. > > >> There is at least another use case for coroutines/generators: Cilk style >> parent stealing; I think that can also be implemented with 4244, without >> additional compiler support. >> > > Have you seen parent stealing example from N4134? > > spawnable fib(int n) { > if (n < 2) return n; > return await(fib(n - 1) + fib(n - 2)); > } > I didn't. Very nice. The problem with this is that the obvious implementation would eagerly convert the parent to a continuation, while an important optimization of a Cilk style implementation is to lazily perform the conversion (which includes heap allocating the task and marking the variables as requiring synchronization) only on a steal. Of course a Sufficiently Smart Compiler could remove the boxing, but as the continuation pointer escapes into the (global) work stealing scheduler itself, I have a feeling it would require an heroic effort unless the compiler had intimate knowledge of the scheduler. A N4244 based design would have the parent continuation still reified as an object, but sitting on the parent stack by default. The stealer would copy/move it explicitly to the heap/its own stack on a steal. Anyway, in whatever form, I'm really looking forward to see generators or coroutines in the standard. Good work guys! -- gpd -- --- You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group. To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org. To post to this group, send email to std-proposals@isocpp.org. Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/. ------=_Part_1862_770612441.1414162000188 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
On Friday, October 24, 2014 2:44:04 PM UTC+1, Gor Nishanov= wrote:
Hi Gio= vanni:
 
"Same Fringe" = requires stackfull coroutines to be implemented efficiently (it needs to yi= eld deep inside a recursive tree visit). With stackless generators (like th= ose of python, C# and those proposed for C++ other than Oliver&Nat prop= osal), you would need to yield at every stack level but it would in practic= e make yielding an O(log n) operation,

I don't think so. It depends how you implement yield a generator. In a g= enerators, supported by N4134, when you yield not a value but another gener= ator, it treats it as await until that generator is finished, thus it is al= ways the very top generator that keeps yielding values to the user, and whe= n the user pulls the value from the generator it goes straight back to the = very top one. It does not walk the generator "stack" to do that.

Actually right after posting I realized that a suffi= ciently smart implementation could do something like that. You would still = need to heap allocate every step of the recursion depth though, right?
&= nbsp;

Stackful do have cheaper recursive invocations because th= ey have normal stack, but it is compensated by more expensive context switc= h, thus making each yield more expensive.

Quick te= st using boost::context vs N4134 (note we did not implement yet any corouti= ne specific optimizations and our ventual codegen will be much better. Reme= mber when Stephanov did STL it was not zero-overhead on any existing compil= er).

Anyway:

This is what= is being tested:

generator<int> GoDeep(int depth) {
   yield depth;
   <= /font>if (depth > 0) yield GoDeep(depth-1);}

this is 'tail' recursive though; a full tree visit wouldn't ben= efit from it. Does it make a difference with your implementation? Does it a= llocate a frame every iteration or the compiler can reuse the frame it was = going to deallocate?

 

com= pared to:

[...]
Stackful: 0.= 417057 secs: yields 10000000 values 41.705700ns per each

Stackless: 0.517368 secs: yields 10000001 values 51.73= 6836ns per each

hum, 41ns per i= teration seems a bit high. A stackful coroutine yield should be around 10 c= lock cycles: save callee save registers, restore callee save registers (sav= ing and restoring can be done in parallel), pop return address and jump (pe= rfectly predictable in this case). In this specific case even the return is= perfectly predicted (which is
 
Again, with better codegen we will b= e beating stackful on recursive problems when higher recursive call overhea= d of stackless is less than higher yield cost on stackful.

Possibly. Note that also the stackful version could benefi= t from compiler support like only saving clobbered registers and saving by = moving to unused registers instead of the stack (which takes advantage of "= free" register renames).

Of course it will always be much easier for= the compiler to inline the callee of a stackless generator than for a sta= ckfull implementation (pretty much requiring a full CPS conversion).
&= nbsp;
frames to support arbitrary re= cursion depth (in practice reifying the call stack), but I might be wrong h= ere.

Yeah. I really want Chris to= chime in, and hopefully provide a full implementation for GoDeep()
 

Simple extension of an example f= rom N4244

auto countdown_squared(int  n) 
{ 
=         return [n]() resumable          { 
   &= nbsp;            std= ::cout << "Counting down from " << n << "\n"; 
&= nbsp;           &nbs= p;   while  (n  >  0) 
  &nb= sp;            = { 
          &n= bsp;            = ; yield n;
          &= nbsp;           &nbs= p; yield from countdown_squared(n -1);
     &nb= sp;            =       n  -=3D  1; 
  =             &nb= sp; } 
        }; 
}&n= bsp;

As it is, it couldn't possibly compile. countdown_squared will= need to wrap its result in a box.
 
Pers= onally I would like to see both styles in the standard: full Oliver&Nat= coroutines for the general case and 0-overhead Chris' style generators for= iteration

I think stackless can tak= e the coroutine niche. I showed about that stackles can match stackful in t= he problem domain when stackful is king.

However, = I do believe that machinery powering N9835 (aka boost::context / fibers) is= valuable as it can serve as a foundation for cooperative user mode threads= in C++ / fibers

the advantage of the stac= kful aproaches is that they interoperate with existing code  which is = a huge win. No need to convert everything in the call stack. For example, a= ny function that takes an STL-style output iterator can be trivially non-in= trusively converted to a generator. It has a cost of course.

<= blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8ex;bord= er-left: 1px #ccc solid;padding-left: 1ex;">
 
and async continuations that do not re= quire keeping around the full stack. Because of the simplicity I think Chri= s' work has more chances to get into the standard.

:-) As you can guess, I hold different opinion on this pa= rticular point.

 :) ; As far as I can= see N4244 is a strict superset of N4134 (that is, additional functionality= can be built on top), so in the interest of generality I would prefer the = former to the latter.
 
 
= There is at least another use case for coroutines/generators: Cilk style pa= rent stealing; I think that can also be implemented with 4244, without addi= tional compiler support.

Have you seen paren= t stealing example from N4134?

sp= awnable<int> fib(int n) {
       if (n < 2) return n;
       return <= span style=3D"color:blue">await(fib(n - 1) + fib(n - 2));
} 

I didn't. Very nice= .. The problem with this is that the obvious implementation would eagerly co= nvert the parent to a continuation, while an important optimization of a Ci= lk style implementation is to lazily perform the conversion (which includes= heap allocating the task and marking the variables as requiring synchroniz= ation) only on a steal. Of course a Sufficiently Smart Compiler could remov= e the boxing, but as the continuation pointer escapes into the (global) wor= k stealing scheduler itself, I have a feeling it would require an heroic ef= fort unless the compiler had intimate knowledge of the scheduler.

A = N4244 based design would have the parent continuation still reified as an o= bject, but sitting on the parent stack by default. The stealer would copy/m= ove it explicitly to the heap/its own stack on a steal. 
Anyway, in whatever form, I'm really looking forward to see generators or = coroutines in the standard. Good work guys!

-- gpd

--

---
You received this message because you are subscribed to the Google Groups &= quot;ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an e= mail to std-proposa= ls+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/<= /a>.
------=_Part_1862_770612441.1414162000188-- .