220 14202 <3ff7fe35-37c6-4f95-8701-1798b0112c10@isocpp.org> article Path: news.gmane.org!not-for-mail From: Gor Nishanov Newsgroups: gmane.comp.lang.c++.isocpp.proposals Subject: Re: comment on n4244 Date: Fri, 24 Oct 2014 09:13:39 -0700 (PDT) Lines: 248 Approved: news@gmane.org Message-ID: <3ff7fe35-37c6-4f95-8701-1798b0112c10@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> <05a08ac6-f9b8-4ebb-9cb8-9a37a6fd4527@isocpp.org> Reply-To: std-proposals@isocpp.org NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: multipart/alternative; boundary="----=_Part_5_514806934.1414167219617" X-Trace: ger.gmane.org 1414167230 3119 80.91.229.3 (24 Oct 2014 16:13:50 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Fri, 24 Oct 2014 16:13:50 +0000 (UTC) To: std-proposals@isocpp.org Original-X-From: std-proposals+bncBC47RF4IW4GRBNHVVGRAKGQEZAVKF6Y@isocpp.org Fri Oct 24 18:13:45 2014 Return-path: Envelope-to: gclcip-std-proposals@m.gmane.org Original-Received: from mail-oi0-f70.google.com ([209.85.218.70]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1XhhUk-0004d1-4V for gclcip-std-proposals@m.gmane.org; Fri, 24 Oct 2014 18:13:42 +0200 Original-Received: by mail-oi0-f70.google.com with SMTP id a141sf5216019oig.9 for ; Fri, 24 Oct 2014 09:13: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=gamjhmVk2E3ntzgn+YzJEfOg23SVSbSJ9EeOuimF7sc=; b=d/m5dcycU3NdKjkt82LBPmBtCqINGKbFyoopbNSBvlyIppc8KTbOA2o00L01zAo38L dlBcXsj+6yHNLCkl9VCy2n0v3SbiNsFM5saj6TMm4onDSDC7nDrJMPlVQradHGZtWqhW QlIiV8ac2g/5wSr3ui1zsYo5oDIWrIRDWJMgNVfFMjpY0S04Lk0+QhERbai0ZjAtEmTX tFcaOfS7l9e5hngBExSs+mqVgNtwKv5uyGtN8+nsTBiMXhRLmiyiB7Xt11+T4fI7dviS 5W9gWwAqAlzrUQ5y+iko6khdXDt5Zsv5Gmae3dm7nX1Scm4uPtpu7yb5BVZMcl151kXO QwIg== 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=gamjhmVk2E3ntzgn+YzJEfOg23SVSbSJ9EeOuimF7sc=; b=RrDpTIwrRuJjYvOXUF22F6i4B2hrxZf+pHKrRnjF+Qh4hsLCVVRWqpZ6XWXpP8HWzA 3EpE1gb0+XuVyeyIpfUZlevjL+pY1W353/ySnlLB4fod/2BFIyuXs6cGuFAyr0rchPsQ 2PfDf0RGV30/aYZJnmiszPdPmcEujD6I+aV45SyFZMDwLDW/NtJfblkbA3vLv1rjvEMw q9LD7JMZ5nvxDLBLUNGzdyeKWnOxZCpxxjmdQ4Fwc6IWYFzC4IwXgcbjTOxncRsXgdIS 3voINHD+6JLd0HjkAsPJJGQGw55PFtC2eLoBewYxw00Htk5KJB0iHSzNukyWUDlrsFSI ly5g== X-Gm-Message-State: ALoCoQksgDBDjnyKUUX3KidRU0dqq8m1S6KSv4+md0NW8pbXrpvyLBnod75YJIDuyrTvfRiEpC9O X-Received: by 10.50.111.170 with SMTP id ij10mr7303631igb.1.1414167221184; Fri, 24 Oct 2014 09:13:41 -0700 (PDT) X-BeenThere: std-proposals@isocpp.org Original-Received: by 10.51.16.66 with SMTP id fu2ls137530igd.0.canary; Fri, 24 Oct 2014 09:13:40 -0700 (PDT) X-Received: by 10.50.43.233 with SMTP id z9mr61590igl.5.1414167220595; Fri, 24 Oct 2014 09:13:40 -0700 (PDT) In-Reply-To: <05a08ac6-f9b8-4ebb-9cb8-9a37a6fd4527@isocpp.org> X-Original-Sender: GorNishanov@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:14202 Archived-At: ------=_Part_5_514806934.1414167219617 Content-Type: text/plain; charset=UTF-8 > > 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? > resursive_generator coroutine type can have an allocator optimized for that pattern, essentially an allocator will implement chained stack with, chunks for K size. Reducing the impact of the allocations. Remember, N4134 is just a language change with appropriate hook ups for library designers go wild. C++17 will only need 3 coroutine types. generator, task and async_generator. Moreover, I hope we will keep coroutines in the wild for a year, before we decide on which generator, which task and which async_generator. STL did not come together with templates. First you got templates and min/max. After some number of years, we got an amazing library utilizing templates. Of course, coroutines are not as fundamental as templates, but, I do not want to rush to standardize generators before I can see what smart people can come up with. I want only the best generator, task and async_generator selected. > 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? > This was a torture test. This is the worst case for stackless, Since we have 1 coroutine frame creation, 1 coroutine frame destruction for every 1 yield. In a real problems where the ration of coroutine creation / destruction is more favorable, stackless will shine. Also, yes. on tail recursion. There are a number of coroutine specific optimizations we are planning and tail yield / await optimization, cross await RVO and many many others. > hum, 41ns per iteration seems a bit high. A stackful coroutine yield > should be around 10 clock cycles: save callee save registers, restore > It is dominated by the context switch. On my box defaul context switch is 35ns. Without floats 28ns. This is Windows, it needs to swap more things than the registers. Exception chain, TLS root, and a few other things. > 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). > Oliver and I are exploring that direction. Expect a proposal in the future if it goes well. > Simple extension of an example from N4244 > | ... > As it is, it couldn't possibly compile. countdown_squared will need to > wrap its result in a box. > Yep. It won't compile. You need to heap allocate the coroutine frame. I went through it before. My original design was lambda* which is the same idea as Chris, generalization of lambda with locals / formals and temporaries of operator() of the lambda included in the lambda state. I explore it for awhile, but did not find too many cases where I did not need to wrap the state and place it in some stationary location. Note, that N4134 allows allocation elision if coroutine lifetime is fully contained within lifetime of a caller. Thus for generator patterns, some async patterns, there will no heap allocations whatsoever. Coroutine will use the frame of its caller. > 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. I only want zero-overhead abstractions in the standard :-). :) ; 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. > I view it as an opposite. N4134 is a syntax sugar on top of unspecified lambda* and provides friendlier way to adopt it to different patterns. Makes lambda* concrete. I chose not to expose lambda* directly to have freedom to do cool optimization and because I did not find a need where lambda* will be better in perf or convenience than N4134. If you have a case in mind, please let me know. My claim is that for any problem solved by N4244, I can solve it with N4134 with simpler code and same or better perf. I need counter examples, so, Chris, and fans of N4244, please bring me some. Tear me down! :-) 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. > I highly recommend to want this presentation on N4134. I explain the Cilk example at 23:47. But, of course, I suggest to start from the beginning to get into the mood :-) http://www.youtube.com/watch?v=KUhSjfSbINE Cheers, Gor -- --- 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_5_514806934.1414167219617 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
Actually right after posting I realized that a sufficiently smart = implementation could do something like that. You would still need to heap a= llocate every step of the recursion depth though, right?

resursive_generator coroutine type can have an al= locator optimized for that pattern, essentially an allocator will implement= chained stack with, chunks for K size. Reducing the impact of the allocati= ons. Remember, N4134 is just a language change with appropriate hook ups fo= r library designers go wild.

C++17 will only need = 3 coroutine types. generator, task and async_generator. Moreover, I hope we= will keep coroutines in the wild for a year, before we decide on which gen= erator, which task and which async_generator. STL did not come together wit= h templates. First you got templates and min/max. After some number of year= s, we got an amazing library utilizing templates.

= Of course, coroutines are not as fundamental as templates, but, I do not wa= nt to rush to standardize generators before I can see what smart people can= come up with. I want only the best generator, task and async_generator sel= ected.
 
this is 'tail' recursive though; a full tree visit= wouldn't benefit from it. Does it make a difference with your implementati= on? Does it allocate a frame every iteration or the compiler can reuse the = frame it was going to deallocate?

This was a torture test. This is the worst case for stackless, Since we = have 1 coroutine frame creation, 1 coroutine frame destruction for every 1 = yield. In a real problems where the ration of coroutine creation / destruct= ion is more favorable, stackless will shine.

Also,= yes. on tail recursion. There are a number of coroutine specific optimizat= ions we are planning and tail yield / await optimization, cross await RVO a= nd many many others. 
 
hum, 41ns per iteration seems a bi= t high. A stackful coroutine yield should be around 10 clock cycles: save c= allee save registers, restore

I= t is dominated by the context switch. On my box defaul context switch is 35= ns. Without floats 28ns. This is Windows, it needs to swap more things than= the registers. Exception chain, TLS root, and a few other things.
 
Possibly. Note that also the stackful version could benefit from comp= iler support like only saving clobbered registers and saving by moving to u= nused registers instead of the stack (which takes advantage of "free" regis= ter renames).

Oliver and I are = exploring that direction. Expect a proposal in the future if it goes well.&= nbsp;
 
Simple extension of an example from N4244
| ... 
As it is, it couldn't possibly comp= ile. countdown_squared will need to wrap its result in a box.

Yep. It won't compile. You need to heap = allocate the coroutine frame.

I went through it be= fore. My original design was lambda* which is the same idea as Chris, gener= alization of lambda with locals / formals and temporaries of operator() of = the lambda included in the lambda state.

I explore= it for awhile, but did not find too many cases where I did not need to wra= p the state and place it in some stationary location.

<= div>Note, that N4134 allows allocation elision if coroutine lifetime is ful= ly contained within lifetime of a caller. Thus for generator patterns, some= async patterns, there will no heap allocations whatsoever. Coroutine will = use the frame of its caller.

 > 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= ..

I only want zero-overhead abstractions in the st= andard :-).

 :) ; As far as I can see N4244 is a strict su= perset 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.

I view it as an opposite. N4134 is= a syntax sugar on top of unspecified lambda* and provides friendlier way t= o adopt it to different patterns.
Makes lambda* concrete. I chose= not to expose lambda* directly to have freedom to do cool optimization and= because I did not find a need where lambda* will be better in perf or conv= enience than N4134.

If you have a case in mind, pl= ease let me know.

My claim is that for any problem= solved by N4244, I can solve it with N4134 with simpler code and same or b= etter perf.
I need counter examples, so, Chris, and fans of N4244= , please bring me some. Tear me down! :-)

I didn't. Very nice. = The problem with this is that the obvious implementation would eagerly conv= ert the parent to a continuation, while an important optimization of a Cilk= style implementation is to lazily perform the conversion (which includes h= eap allocating the task and marking the variables as requiring synchronizat= ion) only on a steal.

I highly = recommend to want this presentation on N4134. I explain the Cilk example at= 23:47. But, of course, I suggest to start from the beginning to get into t= he mood :-)

http://www.youtube.com/watch?v=3DKUhSj= fSbINE

Cheers,
Gor

--

---
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_5_514806934.1414167219617-- .