View mode: basic / threaded / horizontal-split · Log in · Help
January 21, 2013
Re: Internal and external iteration, fibers
On 2013-01-21 20:00, Nick Sabalausky wrote:

> I don't know whether or not it can be done in D. But, if it can be
> done, it would definitely require awkward syntax. Probably more awkward
> than the preprocessor-based syntax of the C/C++ version. (Not that I
> want a preprocessor in D.)
>
> Maybe you could do it by sticking the whole coroutine into a string
> literal that gets ripped apart and reassembled by a CTFE D parser, but
> that would just be so clumsy and error-prone, and frankly far more
> complex than should really be necessary, that I'd call it more of a
> kludge than a solution. And really, if I have to write D code inside a
> string literal to use it, that alone indicates that we're looking down
> the wrong path.

I know people don't like it but I have to say, this seems it could be a 
job for AST macros.

-- 
/Jacob Carlborg
January 21, 2013
Re: Internal and external iteration, fibers
On Monday, 21 January 2013 at 08:44:10 UTC, Nick Sabalausky wrote:
>> I ask, because if except for the overhead, fibers are a good 
>> general solution, then it makes sense to determine if anything 
>> can be done to lessen the overhead before trying to implement 
>> yet another solution.
>> 
>
> Yea, they *would* be a good general solution, and I'm sure the 
> overhead
> can be decreased, but AIUI I don't think it's even theoretically
> possible for them to optimized enough to compete with any of 
> the other
> approaches as a general-purpose thing.
>
> The other stuff can be optimized down as far as being little 
> more than
> an increment per iteration. But AIUI, using a real fiber would 
> require
> two context-switches per iteration, so I'm not sure that can 
> ever
> compete.

I have not yet had time to actually use fibers for anything real, 
but I did play around with them and the usage seemed to be 
exactly what we're looking for to implement co-routines. Since 
you have experience using them for real, do you think they are 
useful in general assuming that the performance can be made par 
with the stackless select switch method?

By chance, do you know if the current implementation is a 
built-in language feature or if it's implemented entirely as a 
library?

--rt
January 21, 2013
Re: Internal and external iteration, fibers
On Monday, 21 January 2013 at 19:23:19 UTC, Jacob Carlborg wrote:
> I know people don't like it but I have to say, this seems it 
> could be a job for AST macros.

It would be just as ugly as C macros. Well maybe not as ugly, but 
D should have direct support for co-routines, it's an important 
feature with plenty of uses.

BTW, has anyone in here has experience working with Simula? 
Co-routines as a language feature has been around for decades in 
a proven way.

--rt
January 21, 2013
Re: Internal and external iteration, fibers
On Mon, 21 Jan 2013 21:15:48 +0100
"Rob T" <alanb@ucora.com> wrote:

> On Monday, 21 January 2013 at 08:44:10 UTC, Nick Sabalausky wrote:
> >> I ask, because if except for the overhead, fibers are a good 
> >> general solution, then it makes sense to determine if anything 
> >> can be done to lessen the overhead before trying to implement 
> >> yet another solution.
> >> 
> >
> > Yea, they *would* be a good general solution, and I'm sure the 
> > overhead
> > can be decreased, but AIUI I don't think it's even theoretically
> > possible for them to optimized enough to compete with any of 
> > the other
> > approaches as a general-purpose thing.
> >
> > The other stuff can be optimized down as far as being little 
> > more than
> > an increment per iteration. But AIUI, using a real fiber would 
> > require
> > two context-switches per iteration, so I'm not sure that can 
> > ever
> > compete.
> 
> I have not yet had time to actually use fibers for anything real, 
> but I did play around with them and the usage seemed to be 
> exactly what we're looking for to implement co-routines.

Their usage, yes, and that does make it a very enticing prospect. And
they are indeed fantastic for many things. But as soon as you start
using them to implement something like:

coroutine int myCoroutine()
{
   yield 10;
   yield 20;

   if(blah)
       yield 30;

   foreach(i; arr)
       yield i;

   //etc
}

In other words, exactly the sorts of use-cases that coroutines are
perfectly suited for. Then you have to consider that your coroutine
may get used for anything from:

foreach(i; myCoroutine)
{
   string result = curl("http://example.com/"~to!string(i));
   writeFile(to!string(i)~".txt", result);
}

to things like:

int sum = myCoroutine.reduce!"a+b"();

The first case, with the I/O, is perfectly fine even if the coroutine
operates using fibers. But the second example, as sleek and deceptively
appealing as it looks, would have very poor performance because it's
doing a ton of context switching even though all it *really* needs to
do is grab a bunch of ints and add them.

OTOH, *both* examples would be perfectly fine if the coroutine were
trivially rewritten behind-the-scenes into a stackless event-loop that
*didn't* use fibers:

struct myCoroutine_localVars
{
   int state=0; // Simulate the instruction pointer
   int i; // The foreach loop variable
}
enum IsDone {Yes, No}
IsDone myCoroutine(ref myCoroutine_localVars context, ref int
yieldValue)
{
   switch(context.state)
   {
   case 0:
       context.state = 1;
       yieldValue = 10;
       return IsDone.No; // yield 10

   case 1:
       context.state = 2;
       yieldValue = 20;
       return IsDone.No; // yield 20

   case 2:
       if(blah)
       {
           context.state = 3;
           yieldValue = 30;
           return IsDone.No; // yield 30;
       }
       context.state = 3;
       goto case 3:

   case 3:
       context.i = 0; // Start for loop
       context.state = 4;
       goto case 4:

   case 4:
       if(context.i < arr.length)
       {
           context.i++;
           yieldValue = arr[context.i - 1];
           return IsDone.No; // yield i
       }
       context.state = 5;
       goto case 5:

   case 5:
       return IsDone.Yes;
   }
}

// foreach(val; myCoroutine) {...stuff...}
//   becomes -->
myCoroutine_localVars context;
int yieldValue;
while(myCoroutine(context, yieldValue) == IsDone.No)
{
   int val = yieldValue;
   ...stuff...
}

Note that looks similar to an equivalent hand-written input
range. So you'd have the performance of an input range in *all*
situations, while still having the convenience of coroutine syntax. (My
understanding is that this is how C#'s coroutines work. And I *know*
that's how C/C++'s protothreads work.) Note that transformation can
be easily automated since C/C++'s protothreads does exactly that
using nothing more than some very simple preprocessor macros.

Real fibers are enticing as an easy way to implement coroutines, but
once implemented, the only thing fibers would really accomplish here is
to slow things down for certain use-cases.

Well, also, real fibers would allow yielding from a function called
by myCoroutine. But even without fibers there are ways to get around
that limitation (as demonstrated by C/C++'s protothreads library).

> Since 
> you have experience using them for real, do you think they are 
> useful in general assuming that the performance can be made par 
> with the stackless select switch method?
> 

If they could, then yes, but I don't believe that's a realistic
possibility. (Others can correct me if I'm wrong, but I'm fairly
sure.)

> By chance, do you know if the current implementation is a 
> built-in language feature or if it's implemented entirely as a 
> library?
> 

In short, I don't know. Others could answer better.

In long:

I *think* they're implemented in druntime, or at least their core
functionality anyway. I don't know whether or not the druntime
implementation relies on any special compiler support. Others can
probably answer that.

I do know that D's fibers don't use the OS-provided fibers (at
least on Windows) since, at least on Windows, the OS fibers are
generally considered to not be very fast or good.
January 22, 2013
Re: Internal and external iteration, fibers
On Monday, 21 January 2013 at 19:23:19 UTC, Jacob Carlborg wrote:
> On 2013-01-21 20:00, Nick Sabalausky wrote:
>
>> I don't know whether or not it can be done in D. But, if it 
>> can be
>> done, it would definitely require awkward syntax. Probably 
>> more awkward
>> than the preprocessor-based syntax of the C/C++ version. (Not 
>> that I
>> want a preprocessor in D.)
>>
>> Maybe you could do it by sticking the whole coroutine into a 
>> string
>> literal that gets ripped apart and reassembled by a CTFE D 
>> parser, but
>> that would just be so clumsy and error-prone, and frankly far 
>> more
>> complex than should really be necessary, that I'd call it more 
>> of a
>> kludge than a solution. And really, if I have to write D code 
>> inside a
>> string literal to use it, that alone indicates that we're 
>> looking down
>> the wrong path.
>
> I know people don't like it but I have to say, this seems it 
> could be a job for AST macros.

I was thinking the same thing, but don't wanted to bug people. 
Indeed, it is the perfect job for AST macro. I can concur now 
that you mentioned it xD
January 22, 2013
Re: Internal and external iteration, fibers
On Monday, 21 January 2013 at 20:15:49 UTC, Rob T wrote:
> On Monday, 21 January 2013 at 08:44:10 UTC, Nick Sabalausky 
> wrote:
>>> I ask, because if except for the overhead, fibers are a good 
>>> general solution, then it makes sense to determine if 
>>> anything can be done to lessen the overhead before trying to 
>>> implement yet another solution.
>>> 
>>
>> Yea, they *would* be a good general solution, and I'm sure the 
>> overhead
>> can be decreased, but AIUI I don't think it's even 
>> theoretically
>> possible for them to optimized enough to compete with any of 
>> the other
>> approaches as a general-purpose thing.
>>
>> The other stuff can be optimized down as far as being little 
>> more than
>> an increment per iteration. But AIUI, using a real fiber would 
>> require
>> two context-switches per iteration, so I'm not sure that can 
>> ever
>> compete.
>
> I have not yet had time to actually use fibers for anything 
> real, but I did play around with them and the usage seemed to 
> be exactly what we're looking for to implement co-routines. 
> Since you have experience using them for real, do you think 
> they are useful in general assuming that the performance can be 
> made par with the stackless select switch method?
>

It has no chance to be as fast. However, I use them quite a lot 
and they are very useful. Especially to hide IO latency or for 
dependancy management. I use them for the latter, some other 
software (like vide.d) use them for the former.

This cannot be achieved with stackless coroutine method as you 
need to yield from anywhere, not only the root function.

> By chance, do you know if the current implementation is a 
> built-in language feature or if it's implemented entirely as a 
> library?
>

This is done as library right now, which is awesome !
January 22, 2013
Re: Internal and external iteration, fibers
"deadalnix" <deadalnix@gmail.com> wrote in message 
news:zrmlbyboedaswcllzwgb@forum.dlang.org...
> On Monday, 21 January 2013 at 19:23:19 UTC, Jacob Carlborg wrote:
>> On 2013-01-21 20:00, Nick Sabalausky wrote:
>>
>> I know people don't like it but I have to say, this seems it could be a 
>> job for AST macros.
>
> I was thinking the same thing, but don't wanted to bug people. Indeed, it 
> is the perfect job for AST macro. I can concur now that you mentioned it 
> xD
January 22, 2013
Re: Internal and external iteration, fibers
"deadalnix" <deadalnix@gmail.com> wrote in message 
news:zrmlbyboedaswcllzwgb@forum.dlang.org...
> On Monday, 21 January 2013 at 19:23:19 UTC, Jacob Carlborg wrote:
>> On 2013-01-21 20:00, Nick Sabalausky wrote:
>>
>>
>> I know people don't like it but I have to say, this seems it could be a 
>> job for AST macros.
>
> I was thinking the same thing, but don't wanted to bug people. Indeed, it 
> is the perfect job for AST macro. I can concur now that you mentioned it 
> xD

AST macros are just compiler support pushed into user code/libraries. 
Exposing the AST to the user is a huge task and forces any supporting 
compiler to use a fixed AST representation.
January 22, 2013
Re: Internal and external iteration, fibers
On Tue, Jan 22, 2013 at 2:55 AM, deadalnix <deadalnix@gmail.com> wrote:
> On Monday, 21 January 2013 at 19:23:19 UTC, Jacob Carlborg wrote:

>> I know people don't like it but I have to say, this seems it could be a
>> job for AST macros.
>
> I was thinking the same thing, but don't wanted to bug people. Indeed, it is
> the perfect job for AST macro. I can concur now that you mentioned it xD

Would any of you be so kind as to propose another definition for AST
macros here ?

http://wiki.dlang.org/Commonly-Used_Acronyms
January 22, 2013
Re: Internal and external iteration, fibers
On Tue, Jan 22, 2013 at 06:51:07AM +0100, Philippe Sigaud wrote:
> On Tue, Jan 22, 2013 at 2:55 AM, deadalnix <deadalnix@gmail.com> wrote:
> > On Monday, 21 January 2013 at 19:23:19 UTC, Jacob Carlborg wrote:
> 
> >> I know people don't like it but I have to say, this seems it could
> >> be a job for AST macros.
> >
> > I was thinking the same thing, but don't wanted to bug people.
> > Indeed, it is the perfect job for AST macro. I can concur now that
> > you mentioned it xD
> 
> Would any of you be so kind as to propose another definition for AST
> macros here ?
> 
> http://wiki.dlang.org/Commonly-Used_Acronyms

I don't think anyone has defined what "AST macros" are supposed to be
yet. There have been some vague ideas thrown about, but nothing is
concrete AFAIK.

For one thing, it's not even clear how said "AST macros" are supposed to
work, or what they're supposed to do.

Do they perform *arbitrary* transformations from some given AST subtree
into another? (Arbitrary, as in, you can implement an "in-library"
optimizer that substitutes inefficient subtrees with optimized versions,
or even a codegen that transforms AST trees into a linear form that maps
directly to IR or machine code.)

Or is it something simpler and more within our reach, something like the
C preprocessor but operating on AST subtrees instead of tokens (as in, a
macro is called with some AST tree fragments as parameters, which get
grafted into the macro body's AST at certain points)?

Or is it something else altogether, like some kind of compile-time
introspection that allows you to access and modify node attributes in
the parsed AST of the code in some way, so that you change the way it's
compiled?

Until this is pinned down, "AST macros" can virtually be *anything*. It
has been said that they can solve all kinds of problems in D, including
the halting problem, world peace, and world hunger, and can be used to
construct all manner of amazing features like writing your code for you,
implementing an oracle machine, etc..  But nobody even knows what they
are or how they're supposed to work.


T

-- 
Freedom: (n.) Man's self-given right to be enslaved by his own depravity.
1 2 3 4 5 6
Top | Discussion index | About this forum | D home