digitalmars.D - Stackless resumable functions
- Martin Nowak (7/7) Oct 24 2014 This is so much better than Fibers.
- "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= (8/13) Oct 24 2014 This is how all truly object oriented languages with concurrency
- "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= (10/23) Oct 24 2014 It is worth pointing out that one advantage of taking this
- Sean Kelly (11/18) Oct 24 2014 I'm about halfway through the talk and it's a bit confusing so
- ROOAR (2/2) Oct 24 2014 I really liked this proposal for resumable lambda:
- Andrei Alexandrescu (2/4) Oct 27 2014 Is this related to the video? -- Andrei
- David Nadlinger (8/13) Oct 27 2014 I haven't been following the developments too closely, but I
- ROOAR (3/8) Oct 27 2014 It is a separate proposal, not the one shown in the video
- Martin Nowak (4/9) Oct 28 2014 There is a good sumarry of the current state in
- Sean Kelly (21/21) Oct 24 2014 Alright, done. It's a pretty interesting proposal. They are
- Kagamin (6/6) Oct 28 2014 In my experience with .net, async/await introduce a non-obvious
- Paulo Pinto (5/11) Oct 28 2014 This is why one of the biggest improvements in Visual Studio 2013
- Kagamin (5/5) Oct 28 2014 I think, it's for seamless debugging. The debugger support for
- Andrei Alexandrescu (2/7) Oct 28 2014 Yah, my understanding of async/await is it's all single-threaded. -- And...
- Kagamin (4/4) Oct 29 2014 It's usually single-threaded by default, but this is achieved by
- bitwise (4/11) Feb 20 2015 Just out of curiosity, is anyone planning to implement this?
- CraigDillabaugh (2/14) Feb 20 2015 They are waiting for your pull request :o)
- bitwise (20/21) Feb 21 2015 Welll... I would like to try, but there is good reason behind the
- ketmar (15/16) Feb 21 2015 it seems to me that you can "abuse" delegates for this (i mean the=20
- bitwise (119/144) Feb 22 2015 I'm glad you mentioned "resume address". I guess I don't need a
- ketmar (16/24) Feb 22 2015 you don't need to. if you really need to do that, you're doing something...
- bitwise (120/130) Feb 23 2015 So how do you explain enumerators in C#, or generators in visual
- ketmar (4/4) Feb 21 2015 On Sat, 21 Feb 2015 21:19:32 +0000, bitwise wrote:
This is so much better than Fibers. http://youtu.be/KUhSjfSbINE What I like most about the proposal is that you can adapt await by specializing template functions, similar to how range based foreach works. It also isn't tied to a particular scheduling mechanism and of course consumes much less memory than stack based suspension.
Oct 24 2014
On Friday, 24 October 2014 at 10:33:40 UTC, Martin Nowak wrote:What I like most about the proposal is that you can adapt await by specializing template functions, similar to how range based foreach works. It also isn't tied to a particular scheduling mechanism and of course consumes much less memory than stack based suspension.This is how all truly object oriented languages with concurrency works. Block activation records are conceptually on the heap and there is no difference between an object and a function: Simula67, Beta, Self… It is slower than using a stack though, but if done as in Beta you get a back pointer to the caller (who instantiate the function/object) which can be handy for modelling.
Oct 24 2014
On Friday, 24 October 2014 at 14:50:53 UTC, Ola Fosheim Grøstad wrote:On Friday, 24 October 2014 at 10:33:40 UTC, Martin Nowak wrote:It is worth pointing out that one advantage of taking this uniform view is that you can more easily define a system to persist/migrate a transitive closure of objects/fibers and transfer them to other servers. However, it does not have to be stackless in terms of implementation. A stack is then an optimization, the compiled code can put things on the stack until it at runtime hits a yield (at which point you have to pick it up).What I like most about the proposal is that you can adapt await by specializing template functions, similar to how range based foreach works. It also isn't tied to a particular scheduling mechanism and of course consumes much less memory than stack based suspension.This is how all truly object oriented languages with concurrency works. Block activation records are conceptually on the heap and there is no difference between an object and a function: Simula67, Beta, Self… It is slower than using a stack though, but if done as in Beta you get a back pointer to the caller (who instantiate the function/object) which can be handy for modelling.
Oct 24 2014
On Friday, 24 October 2014 at 10:33:40 UTC, Martin Nowak wrote:This is so much better than Fibers. http://youtu.be/KUhSjfSbINE What I like most about the proposal is that you can adapt await by specializing template functions, similar to how range based foreach works. It also isn't tied to a particular scheduling mechanism and of course consumes much less memory than stack based suspension.I'm about halfway through the talk and it's a bit confusing so far because all of what I'd consider the interesting part seems to be implemented as a compiler extension and so is invisible by looking at the code. He's talking about suspend points in the function but there's no indication from the code that they are present where he says. It seems a bit like these functions are closures and the compiler is figuring this out according to the return type or something. So it's potentially interesting but difficult to see how this directly compares to classic coroutines. I'm hoping all will be clear by the end of the talk.
Oct 24 2014
I really liked this proposal for resumable lambda: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4244.pdf
Oct 24 2014
On 10/24/14 10:51 AM, ROOAR wrote:I really liked this proposal for resumable lambda: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4244.pdfIs this related to the video? -- Andrei
Oct 27 2014
On Tuesday, 28 October 2014 at 02:10:47 UTC, Andrei Alexandrescu wrote:On 10/24/14 10:51 AM, ROOAR wrote:I haven't been following the developments too closely, but I think the talk essentially describes N4134, which supersedes N3977/N3858. Chris Kohlhoff references the latter in his introduction in N4244, but I haven't read that paper in any detail. DavidI really liked this proposal for resumable lambda: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4244.pdfIs this related to the video? -- Andrei
Oct 27 2014
On Tuesday, 28 October 2014 at 02:10:47 UTC, Andrei Alexandrescu wrote:On 10/24/14 10:51 AM, ROOAR wrote:It is a separate proposal, not the one shown in the videoI really liked this proposal for resumable lambda: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4244.pdfIs this related to the video? -- Andrei
Oct 27 2014
On Tuesday, 28 October 2014 at 02:10:47 UTC, Andrei Alexandrescu wrote:On 10/24/14 10:51 AM, ROOAR wrote:There is a good sumarry of the current state in http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2014/n4232.pdf.I really liked this proposal for resumable lambda: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4244.pdfIs this related to the video? -- Andrei
Oct 28 2014
Alright, done. It's a pretty interesting proposal. They are effectively closures with coroutine-like semantics. It seems like the overhead for a complex system might actually be greater than with classic coroutines, as closure data allocations could be happening all over the place, but this is pure speculation. I think a direct comparison could be drawn between their API and ours, as std.concurrency now has a Generator object and one of his early examples is a generator as well. From a use perspective, the two are really pretty similar, though our Generator allocates an entire stack while theirs allocates N function-level context blocks (one per contained awaitable). Overall I see this proposal as being complementary to actors as per std.concurrency. Theirs provides a fairly simple and lightweight model for composing code that doesn't normally compose well (like recursive iterators), which is one traditional use of coroutines. But for high levels of concurrency to be achieved, a scheduler needs to sit behind the await mechanism so other things can happen when execution is suspended waiting for a result. This could integrate well with the Scheduler that is now a part of std.concurrency, as it would be fairly trivial for a context switch to occur whenever an awaitable suspend occurs.
Oct 24 2014
In my experience with .net, async/await introduce a non-obvious multithreading model, which remaining hidden under the hood, can still inflict concurrency issues on your code: race conditions types, D will need to catch concurrent access to data, as it's required by D type system.
Oct 28 2014
On Tuesday, 28 October 2014 at 12:30:22 UTC, Kagamin wrote:In my experience with .net, async/await introduce a non-obvious multithreading model, which remaining hidden under the hood, can still inflict concurrency issues on your code: race shared types, D will need to catch concurrent access to data, as it's required by D type system.This is why one of the biggest improvements in Visual Studio 2013 is async/await debugging. Visual Studio 2014 has a few more improvements, if I am not mistaken.
Oct 28 2014
I think, it's for seamless debugging. The debugger support for async/await is indeed non-trivial, because code is mutated by the compiler a lot, but I don't think it has anything to do with concurrency. Official MS position is async/await has no concurrency problems.
Oct 28 2014
On 10/28/14 8:25 AM, Kagamin wrote:I think, it's for seamless debugging. The debugger support for async/await is indeed non-trivial, because code is mutated by the compiler a lot, but I don't think it has anything to do with concurrency. Official MS position is async/await has no concurrency problems.Yah, my understanding of async/await is it's all single-threaded. -- Andrei
Oct 28 2014
It's usually single-threaded by default, but this is achieved by routing continuation to the original thread through its synchronization context, while in multithreaded mode continuation can be executed in thread pool on any thread.
Oct 29 2014
Just out of curiosity, is anyone planning to implement this? As for why it's not already implemented, is it because of lack of interest, or prohibitive reasons? On Friday, 24 October 2014 at 10:33:40 UTC, Martin Nowak wrote:This is so much better than Fibers. http://youtu.be/KUhSjfSbINE What I like most about the proposal is that you can adapt await by specializing template functions, similar to how range based foreach works. It also isn't tied to a particular scheduling mechanism and of course consumes much less memory than stack based suspension.
Feb 20 2015
On Friday, 20 February 2015 at 17:51:17 UTC, bitwise wrote:Just out of curiosity, is anyone planning to implement this? As for why it's not already implemented, is it because of lack of interest, or prohibitive reasons? On Friday, 24 October 2014 at 10:33:40 UTC, Martin Nowak wrote:They are waiting for your pull request :o)This is so much better than Fibers. http://youtu.be/KUhSjfSbINE What I like most about the proposal is that you can adapt await by specializing template functions, similar to how range based foreach works. It also isn't tied to a particular scheduling mechanism and of course consumes much less memory than stack based suspension.
Feb 20 2015
They are waiting for your pull request :o)Welll... I would like to try, but there is good reason behind the noncommital phrasing of my question :) I experimented with stackful coroutines in C++, but I think stackless resumable functions will be more difficult. I assume I can harvest most of what I need from other parts of D. My initial thoughts on this is that I could have resumable functions return a special range which contained 3 things: -a pointer to the function -all the stack variables from the function -an integer index into a jump table at the beginning of the resumable function At compile time, each usage of yield in the resumable function would be replace with: -a command to update the jump table index, followed by -a label, who's offset would be contained in the jump table So initially calling a resumable function would return the range in question which would repeatedly call into the resumable function with a different index until the end of the resumable function was reached. Input on this would be appreciated.
Feb 21 2015
On Sat, 21 Feb 2015 21:19:32 +0000, bitwise wrote:Input on this would be appreciated.it seems to me that you can "abuse" delegates for this (i mean the=20 underlying "fat pointer"). resumable function can create closure (i think=20 all the code for this is already here), "resume address" pointer (this=20 can be added to closure), pointer to "real" delegate, hidden "yield=20 point" address, and return a delegate which does something like this on=20 call: * executes "real" delegate from "resume address". * "real" delegate yields by doing indirect call to "resume address" * assembler code at "resume address" stores new resume address (it's on=20 stack now) * and returns from "wrapping delegate" so from the point of programmer this will look as an ordinary delegate,=20 even with the same type, and it will be usable anywhere where ordinary=20 delegate is usable.=
Feb 21 2015
On Sunday, 22 February 2015 at 03:35:28 UTC, ketmar wrote:On Sat, 21 Feb 2015 21:19:32 +0000, bitwise wrote:I'm glad you mentioned "resume address". I guess I don't need a jump table since the function is not switching on a user variable ;) I don't like the idea of having a resumable function look like a regular delegate. There would be no clean way to check when the resumable function had finished. I've only skimmed the C++ proposal for resumable lambdas below, but it seems like their solution is to introduce a 'stop_iteration' exception which gets thrown when you try to call a resumable lambda that has run to completion. So basically, all uses of delegates would have to be wrapped in try/catch blocks.. http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4244.pdf The newest visual studio preview version has "generators". This is an example from the visual studio blog: generator<int> fib() { int a = 0; int b = 1; for (;;) { __yield_value a; auto next = a + b; a = b; b = next; } } So I'm assuming the above function would return something like this: template<class T> struct generator { T value; iterator begin() { /* executes function, stores value, and returns iterator to first yield */ } iterator end() { ... } void operator++() { /* execute function to next yield and store value */ } T& operator*() { return value; } }; I am considering something similar. Please excuse my incoherent pseudocode :) interface IResumableClosure { // address of resumable function // stack vars // methods for initializing a new MethodRange(T) } struct Generator(T) { IResumableClosure closure; Generator(IResumableClosure closure) { this.closure = closure; } int opApply(int delegate(ref T) dg) { foreach(value; MethodRange!T(closure)) if(dg(value)) return 1; return 0; } MethodRange!T getRange() { return MethodRange!T(closure); } } struct MethodRange(T) { IResumableClosure closure; // contains stack vars, resume address // last returned value, and 'finished' flag void *context; MethodRange(IResumableClosure closure) { this.closure = closure; this.context = closure.createContext(); if(!context->finished) this.value = invoke(context); } private T invoke(void* context) { // run function until yield, store return address in context } T front() { return value; } void popFront() { value = invoke(context); } bool empty() { return context.finished; } } Generator!int myResumableFunction() { for(int i = 0; i < 10; ++i) yield i; return; // exits the resumable function // return 1; // illegal inside resumable function, use yield } for(number; myResumableFunction()) writeln(number); // or auto gen = myResumableFunction(); auto metRang = gen.getRange(); // runs to first yield while(!metRang.empty()) { writeln(metRang.front); metRang.popFront(); } // or the caller could optionally return a MethodRange(T) directly if they were // ok with the function being invoked immediately. MethodRange!int myResumableFunction() { yield 1; } auto metRang = myResumableFunction(); // runs to first yield while(!metRang.empty()) { writeln(metRang.front); metRang.popFront(); } So like you said, I could wrap the resumable function in some kind of specialized closure, but I could use that to optionally initialize a MethodRange(T) or a Generator(T).Input on this would be appreciated.it seems to me that you can "abuse" delegates for this (i mean the underlying "fat pointer"). resumable function can create closure (i think all the code for this is already here), "resume address" pointer (this can be added to closure), pointer to "real" delegate, hidden "yield point" address, and return a delegate which does something like this on call: * executes "real" delegate from "resume address". * "real" delegate yields by doing indirect call to "resume address" * assembler code at "resume address" stores new resume address (it's on stack now) * and returns from "wrapping delegate" so from the point of programmer this will look as an ordinary delegate, even with the same type, and it will be usable anywhere where ordinary delegate is usable.
Feb 22 2015
On Mon, 23 Feb 2015 00:48:42 +0000, bitwise wrote:I don't like the idea of having a resumable function look like a regular delegate. There would be no clean way to check when the resumable function had finished.you don't need to. if you really need to do that, you're doing something=20 wrong trying to recreate ranges and exposing their internal design to the=20 user. this resumable function *is* delegate. nobody cares about it's=20 internals.I've only skimmed the C++ proposal for resumable lambdas below, but it seems like their solution is to introduce a 'stop_iteration' exception which gets thrown when you try to call a resumable lambda that has run to completion. So basically, all uses of delegates would have to be wrapped in try/catch blocks..resumable functions are not iterators. it's a slightly perversed flow=20 control method. iteration/generation is one of the use cases. and, by the way, yielding is a two-way communication channel. you seem to stuck with iteration/generation idea, but this is not the way=20 resumable functions should be seen. resumable functions are basics of=20 cooperative multitasking, and iteration/generation is just a special case=20 of coop mt. mimicking delegates allows to use resumable function in any code that=20 expects delegate. and defining interfaces (yeilding is two-way comm=20 channel!) will allow to build generator abstraction a-la range (or even=20 mimicking any necessary range).=
Feb 22 2015
you don't need to. if you really need to do that, you're doing somethingThis makes no sense to me. A usage example may be helpful.resumable functions are not iterators. it's a slightly perversed flow control method. iteration/generation is one of the use cases.c++?and, by the way, yielding is a two-way communication channel.http://www.boost.org/doc/libs/1_57_0/libs/coroutine/doc/html/index.html [quote] Coroutine Asymmetric coroutine Symmetric coroutine [/quote]you seem to stuck with iteration/generation idea, but this is not the way resumable functions should be seen.Not sure what to say to this..mimicking delegates allows to use resumable function in any code that expects delegate.If you can come up with even one example(with code) where it would make sense to accept both coroutines and delegates, I will be very surprised. In any case, I have revised my design. Generator(T) was redundant, so I removed it. Below is something that I think is well formed enough for me to start digging through the compiler for specifics. interface MethodRange(T) { property T front(); void popFront(); property bool empty(); int opApply(int delegate(T) dg); } class __ResumeableMethod(T, METHOD_TYPE, CONTEXT_TYPE) : MethodRange!T { // method locals and passed args CONTEXT_TYPE* context; // -initially contains method entry point // -once executed, contains the resume address // -when finished, contains null void *fptr; // object reference for instance methods void *obj; T value; this(CONTEXT_TYPE* context, void *fptr, void *obj) { this.context = context; this.fptr = fptr; this.obj = obj; invoke(context, &value); } private T invoke(CONTEXT_TYPE *context, T *yielded_value) { fptr(context); fptr = context->return_address; if(fptr) *yielded_value = context->yielded_value; } property override T front() { assert(!this.empty); return value; } override void popFront() { assert(!this.empty); invoke(context, &value); } property override bool empty() { return fptr == null; } int opApply(int delegate(T) dg) { while(!this.empty) { if(dg(this.front)) return 1; } return 0; } } MethodRange!int myResumableMethod() { for(int i = 0; i < 10; ++i) yield i; } // the compiler would automatically transform the above // method into something like the one below MethodRange!int myResumableMethod() { void __method(__ContextFor__method *ctx) { for(ctx->i = 0; i < 10; ++i) { ctx->yielded_value = i; ctx->return_address = &return_pos; return; return_pos: } ctx->return_address = null; } return new __ResumeableMethod!int(new __ContextFor__method, &__method, null); } // usage void main() { foreach(num; myResumableMethod()) writeln(num); // or MethodRange!int[] methods; auto mr = myResumableMethod(); if(!mr.empty) methods ~= mr; for(int i = 0; i < methods.length; ) { auto mr = methods[i]; int status = mr.front; // handle item status.. mr.popFront(); if(mr.empty) methods.remove(i); else ++i; } }
Feb 23 2015
On Mon, 23 Feb 2015 23:10:28 +0000, bitwise wrote:you still thinking in terms of generators. generator is a high-level=20 construct, resumable routine is a low-level construct. latter is used to=20 build the former.you don't need to. if you really need to do that, you're doing something=20 This makes no sense to me. A usage example may be helpful.as one of the possible high-level constructs that can be built with=20 resumable routines.resumable functions are not iterators. it's a slightly perversed flow control method. iteration/generation is one of the use cases.=20http://www.boost.org/doc/libs/1_57_0/libs/coroutine/doc/html/index.html =20 [quote] Coroutine Asymmetric coroutine Symmetric coroutine [/quote]i don't even want to know what boost does. it stinks anyway.anywhere. any code. any delegate usage. it's a simple idiom of "switching=20 control", where "function that calling delegate" can be seen as "delegate=20 that calling the function". heh. anytime you need to switch the=20 controlling side without rewriting the code. if you can't think out the=20 use case for this, you still looking at resumable routines from the wrong=20 POV.mimicking delegates allows to use resumable function in any code that expects delegate.=20 If you can come up with even one example(with code) where it would make sense to accept both coroutines and delegates, I will be very surprised.In any case, I have revised my design. Generator(T) was redundant, so I removed it. Below is something that I think is well formed enough for me to start digging through the compiler for specifics.it's like building the brick house without having the bricks. you trying=20 to build the house when you have to make bricks. sure, you can do that...=20 and than cursing while smashing it into bricks when you need to build the=20 fence. or building fences from houses. what you *really* trying to do is to build specific actor instead of=20 building the foundation for programming with actors. building the=20 foundation for actor model is way better and will allow you to build your=20 generators easily.=
Feb 23 2015
On Tuesday, 24 February 2015 at 00:48:34 UTC, ketmar wrote:On Mon, 23 Feb 2015 23:10:28 +0000, bitwise wrote:you still thinking in terms of generators. Generator is a high-level construct, resumable routine is a low-level construct. latter is used to build the former.I think you're getting confused between "stackless" and "stackful" resumable functions. If I wanted stackful resumable functions, I would just use D's Fiber. If I wanted something lower level, I would simply make a D wrapper for boost::fcontext. http://www.boost.org/doc/libs/1_57_0/boost/context/fcontext.hpp #define RF "resumable function" // :) But, I am not talking about stackful RF. The control flow you're describing is that of a stackful RF. With stackless RFs, you can't just randomly switch control flow between coroutines, nor can you yield from nested stack frames. A stackless RF runs on the same stack as everything else. Only the local variables and RF's arguments are allocated on the heap. That said, I can't think of a lower level abstraction than what I have provided that would actually be useful...i don't even want to know what boost does. it stinks anyway.Maybe this is why you don't get what I'm saying ;)anywhere. any code. any delegate usage. it's a simple idiom of "switching control", where "function that calling delegate" can be seen as "delegate that calling the function".Again, I'm pretty sure you're thinking of stackful RFs.it's like building the brick house without having the bricks.Don't be silly, we're clearly building a bike shed here.
Feb 23 2015
On Tue, 24 Feb 2015 03:22:10 +0000, bitwise wrote:I think you're getting confused between "stackless" and "stackful" resumable functions.ahem. seems that you are right, and i outsmarted myself yet again. seems=20 that my head is too small to keep three different task unmessed (forum=20 discussion, plus two of my projects). sorry.=
Feb 23 2015
ahem. seems that you are right, and i outsmarted myself yet again. seems that my head is too small to keep three different task unmessed (forum discussion, plus two of my projects). sorry.If it's any consolation, I did accidentally use a C++ constructor in my first example.. I better sleep with one eye opened tonight ;)
Feb 23 2015
ketmar You know you may be kinda right about reusability though... I am not as familiar with "await" as I am with coroutines, but I think the principal is similar. The Visual Studio team seems to have chosen to tackle stackless resumable routines and await at the same time, so there may be some reusability there. I couldn't say for sure though. In any case, I don't think it would be hard to refactor my suggested implementation under the covers to facilitate something like await without hurting the user-facing functionality.
Feb 24 2015
On Tue, 24 Feb 2015 15:53:53 +0000, bitwise wrote:In any case, I don't think it would be hard to refactor my suggested implementation under the covers to facilitate something like await without hurting the user-facing functionality.sure, if you will get something working, it will be easier to chop it to=20 pieces if necessary. or one can simply emulate one thing with another=20 thing as a quickhack.=
Feb 24 2015
On Sat, 21 Feb 2015 21:19:32 +0000, bitwise wrote: p.s. i think you will need to so some housekeeping in "wrapping=20 delegate", of course. it depends of compiler internals though, and from=20 codegen details.=
Feb 21 2015