www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.announce - Combine Coroutines and Input Ranges for Dead-Simple D Iteration

reply "Nick Sabalausky" <SeeWebsiteToContactMe semitwist.com> writes:
A little write-up I just did on something I thought was pretty cool:

Combine Coroutines and Input Ranges for Dead-Simple D Iteration
https://www.semitwist.com/articles/article/view/combine-coroutines-and-input-ranges-for-dea
-simple-d-iteration 
May 01 2012
next sibling parent Rory McGuire <rjmcguire gmail.com> writes:
--e89a8f50398ced59d804bef605b4
Content-Type: text/plain; charset=UTF-8

Fibers are basically just execution stacks like greenlets from python so I
would imagine you can clone/copy them.

Nice write up, I think it will help people get more fibre in their D diet.
:)

On Tue, May 1, 2012 at 10:27 AM, Nick Sabalausky <
SeeWebsiteToContactMe semitwist.com> wrote:

 A little write-up I just did on something I thought was pretty cool:

 Combine Coroutines and Input Ranges for Dead-Simple D Iteration

 https://www.semitwist.com/articles/article/view/combine-coroutines-and-input-ranges-for-dead-simple-d-iteration

--e89a8f50398ced59d804bef605b4 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Fibers are basically just execution stacks like greenlets from python so I = would imagine you can clone/copy them.<br> <br>Nice write up, I think it will help people get more fibre in their D di= et. :)<br><br><div class=3D"gmail_quote">On Tue, May 1, 2012 at 10:27 AM, N= ick Sabalausky <span dir=3D"ltr">&lt;<a href=3D"mailto:SeeWebsiteToContactM= e semitwist.com" target=3D"_blank">SeeWebsiteToContactMe semitwist.com</a>&= gt;</span> wrote:<br> <blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p= x #ccc solid;padding-left:1ex">A little write-up I just did on something I = thought was pretty cool:<br> <br> Combine Coroutines and Input Ranges for Dead-Simple D Iteration<br> <a href=3D"https://www.semitwist.com/articles/article/view/combine-coroutin= es-and-input-ranges-for-dead-simple-d-iteration" target=3D"_blank">https://= www.semitwist.com/articles/article/view/combine-coroutines-and-input-ranges= -for-dead-simple-d-iteration</a><br> <br> <br> </blockquote></div><br> --e89a8f50398ced59d804bef605b4--
May 01 2012
prev sibling next sibling parent Jacob Carlborg <doob me.com> writes:
On 2012-05-01 10:27, Nick Sabalausky wrote:
 A little write-up I just did on something I thought was pretty cool:

 Combine Coroutines and Input Ranges for Dead-Simple D Iteration
 https://www.semitwist.com/articles/article/view/combine-coroutines-and-input-ranges-for-dead-simple-d-iteration

Cool, that's how easy opApply should have been. -- /Jacob Carlborg
May 01 2012
prev sibling next sibling parent Robert Clipsham <robert octarineparrot.com> writes:
On 01/05/2012 09:27, Nick Sabalausky wrote:
 A little write-up I just did on something I thought was pretty cool:

 Combine Coroutines and Input Ranges for Dead-Simple D Iteration
 https://www.semitwist.com/articles/article/view/combine-coroutines-and-input-ranges-for-dead-simple-d-iteration

This got me thinking, so I tried to do something a little similar myself, the result is below. If you only have one type to iterate over, you can make the user code look even cleaner! I can't help but feel it can become even cleaner too. (Scroll to the "User code" comment to miss out the implementation). The code: ---- import core.thread; class VFiber(Elem) : Fiber { Elem elem; this(void delegate() dg) { super(dg); } } auto visitor(T, Elem = T.visitType)(T t) { static struct Visitor { T t; VFiber!Elem f; disable this(); disable this(this); this(T t) { this.t = t; f = new VFiber!Elem(&t.visit); f.call(); } Elem front() property { return f.elem; } void popFront() { f.call(); } bool empty() property { return f.state == Fiber.State.TERM; } } return Visitor(t); } void yield(Elem)(Elem el) { auto f = cast(VFiber!Elem)cast(void*)Fiber.getThis(); if (f is null) throw new FiberException("Cannot yield a value from outside the visit() method"); f.elem = el; Fiber.yield(); } // User code starts here struct Iterable { string[] strs = ["hello", "world"]; alias string visitType; void visit() { foreach(str; strs) yield(str); } } void main() { import std.stdio; Iterable i; foreach(el; i.visitor) { writefln("%s", el); } } ---- -- Robert http://octarineparrot.com/
May 01 2012
prev sibling next sibling parent "Adam D. Ruppe" <destructionator gmail.com> writes:
You might find this interesting too...

string yield(string what) { return `if(auto result = 
dg(`~what~`)) return result;`; }

     int opApply(int delegate(ref uint) dg) {
         for (int i = 0; i < array.length; i++)
                 mixin(yield("array[i]"));

         return 0;
     }


The little mixin does the boilerplate making opApply
a bit more succinct, without anything really fancy.
May 01 2012
prev sibling next sibling parent reply "jerro" <a a.com> writes:
On Tuesday, 1 May 2012 at 08:26:45 UTC, Nick Sabalausky wrote:
 A little write-up I just did on something I thought was pretty 
 cool:

 Combine Coroutines and Input Ranges for Dead-Simple D Iteration
 https://www.semitwist.com/articles/article/view/combine-coroutines-and-input-ranges-for-dead-simple-d-iteration

This is fun and all, but because of the horrible performance we really shouldn't be recommending people to use it.
May 01 2012
parent reply "Nick Sabalausky" <SeeWebsiteToContactMe semitwist.com> writes:
"jerro" <a a.com> wrote in message 
news:sxfngaqnhwxqookrvkif forum.dlang.org...
 On Tuesday, 1 May 2012 at 08:26:45 UTC, Nick Sabalausky wrote:
 A little write-up I just did on something I thought was pretty cool:

 Combine Coroutines and Input Ranges for Dead-Simple D Iteration
 https://www.semitwist.com/articles/article/view/combine-coroutines-and-input-ranges-for-dead-simple-d-iteration

This is fun and all, but because of the horrible performance we really shouldn't be recommending people to use it.

So it is bad performance?
May 01 2012
parent "Nick Sabalausky" <SeeWebsiteToContactMe semitwist.com> writes:
"jerro" <a a.com> wrote in message 
news:qpipqzzdbpkoxtzvhefw forum.dlang.org...
 Compared to normal iteration schemes, yes.  It may be comparable to 
 opApply in terms of performance though.  If you're curious, look at the 
 Fiber context switching code (starting at switchIn and switchOut).

It's much slower than opApply. This loop takes 70s on my machine: foreach(el; visitor(Iterable(1000_000_000))) sum += 1; And this one takes 2.7s: auto iter(int n) { struct I { int n; int opApply(int delegate(ref int) dg) { for(int i = 0; i < n; i++) if(int r = dg(i)) return r; return 0; } } return I(n); } foreach(el; iter(1000_000_000)) sum += 1;

What compiler options is that with?
May 01 2012
prev sibling next sibling parent Sean Kelly <sean invisibleduck.org> writes:
On May 1, 2012, at 1:50 PM, Nick Sabalausky wrote:

 "jerro" <a a.com> wrote in message=20
 news:sxfngaqnhwxqookrvkif forum.dlang.org...
 On Tuesday, 1 May 2012 at 08:26:45 UTC, Nick Sabalausky wrote:
 A little write-up I just did on something I thought was pretty cool:
=20
 Combine Coroutines and Input Ranges for Dead-Simple D Iteration
 =



ut-ranges-for-dead-simple-d-iteration
=20
 This is fun and all, but because of the horrible performance we =


 shouldn't be recommending people to use it.

So it is bad performance?

Compared to normal iteration schemes, yes. It may be comparable to = opApply in terms of performance though. If you're curious, look at the = Fiber context switching code (starting at switchIn and switchOut).=
May 01 2012
prev sibling next sibling parent "jerro" <a a.com> writes:
On Tuesday, 1 May 2012 at 20:49:48 UTC, Nick Sabalausky wrote:
 "jerro" <a a.com> wrote in message
 news:sxfngaqnhwxqookrvkif forum.dlang.org...
 On Tuesday, 1 May 2012 at 08:26:45 UTC, Nick Sabalausky wrote:
 A little write-up I just did on something I thought was 
 pretty cool:

 Combine Coroutines and Input Ranges for Dead-Simple D 
 Iteration
 https://www.semitwist.com/articles/article/view/combine-coroutines-and-input-ranges-for-dead-simple-d-iteration

This is fun and all, but because of the horrible performance we really shouldn't be recommending people to use it.

So it is bad performance?

It has bad performance compared to something like iota - I get about 15 million iterations per second for this loop: struct Iterable { alias string visitType; void visit() { foreach(i; 0 .. 10_000_000) yield(i); } } ... foreach(el; visitor(i)) sum ++; using Robert Clipsham's code, compared to billions iterations per second with a regular loop. The problem is that people new to D could see this, assume it performs similar to ranges like iot and then wonder why their code is slow.
May 01 2012
prev sibling next sibling parent "jerro" <a a.com> writes:
 Compared to normal iteration schemes, yes.  It may be 
 comparable to opApply in terms of performance though.  If 
 you're curious, look at the Fiber context switching code 
 (starting at switchIn and switchOut).

It's much slower than opApply. This loop takes 70s on my machine: foreach(el; visitor(Iterable(1000_000_000))) sum += 1; And this one takes 2.7s: auto iter(int n) { struct I { int n; int opApply(int delegate(ref int) dg) { for(int i = 0; i < n; i++) if(int r = dg(i)) return r; return 0; } } return I(n); } foreach(el; iter(1000_000_000)) sum += 1;
May 01 2012
prev sibling next sibling parent "jerro" <a a.com> writes:
 What compiler options is that with?

I used DMD and compiler flags -O -inline -release on x86_64 linux.
May 02 2012
prev sibling next sibling parent Rory McGuire <rjmcguire gmail.com> writes:
--e89a8fb205043e819604bf098b10
Content-Type: text/plain; charset=UTF-8

On Wed, May 2, 2012 at 9:38 AM, jerro <a a.com> wrote:

 What compiler options is that with?

I used DMD and compiler flags -O -inline -release on x86_64 linux.

65 seconds without any command line options. 54 seconds with -O -inline -release. vs: 3.2 seconds dmd without any command line options. 2.2 seconds with dmd -O -inline -release. And that is for 1000_000_000 Fiber context switches. intel 2600K 4.5GHz, gnu/linux, ubuntu 12.04. --e89a8fb205043e819604bf098b10 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable <div><div class=3D"gmail_quote">On Wed, May 2, 2012 at 9:38 AM, jerro <span= dir=3D"ltr">&lt;<a href=3D"mailto:a a.com" target=3D"_blank">a a.com</a>&g= t;</span> wrote:<br><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0= .8ex;border-left:1px #ccc solid;padding-left:1ex"> <div class=3D"im"><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .= 8ex;border-left:1px #ccc solid;padding-left:1ex"> What compiler options is that with?<br> </blockquote> <br></div> I used DMD and compiler flags -O -inline -release on x86_64 linux.<br> <br> </blockquote></div><br></div><div>It may be slow relative to incrementing a= integer:<div><br></div><div>65 seconds without any command line options.</= div><div>54 seconds with =C2=A0-O -inline -release.</div><div><br></div><di= v> vs:</div><div><br></div><div>3.2 seconds dmd without any command line optio= ns.</div><div>2.2 seconds with dmd=C2=A0-O -inline -release.<br><br>And tha= t is for=C2=A0<span style>1000_000_000 Fiber context switches.</span><br></= div></div> <div><span style>intel 2600K =C2=A0</span><span style>4.5GHz, gnu/linux, u= buntu 12.04</span><span style>.</span></div> --e89a8fb205043e819604bf098b10--
May 02 2012
prev sibling next sibling parent reply "SomeDude" <lovelydear mailmetrash.com> writes:
On Tuesday, 1 May 2012 at 08:26:45 UTC, Nick Sabalausky wrote:
 A little write-up I just did on something I thought was pretty 
 cool:

 Combine Coroutines and Input Ranges for Dead-Simple D Iteration
 https://www.semitwist.com/articles/article/view/combine-coroutines-and-input-ranges-for-dead-simple-d-iteration

Call me stupid, but I've absolutely no idea what you're doing. What problem does the InputVisitor solve ? What are the current solutions ? What is the intent of your code ? What are the supposed advantages ? Your article says nothing about it.
May 02 2012
parent reply "Nick Sabalausky" <SeeWebsiteToContactMe semitwist.com> writes:
"SomeDude" <lovelydear mailmetrash.com> wrote in message 
news:ypakkndfsibcbgeljvgu forum.dlang.org...
 On Tuesday, 1 May 2012 at 08:26:45 UTC, Nick Sabalausky wrote:
 A little write-up I just did on something I thought was pretty cool:

 Combine Coroutines and Input Ranges for Dead-Simple D Iteration
 https://www.semitwist.com/articles/article/view/combine-coroutines-and-input-ranges-for-dead-simple-d-iteration

Call me stupid, but I've absolutely no idea what you're doing. What problem does the InputVisitor solve ? What are the current solutions ? What is the intent of your code ? What are the supposed advantages ? Your article says nothing about it.

Just an easier-to-read/write alternative to an opApply or an input range. More natural and straightforward than a hand-written input range, and cleaner syntax than opApply (and without opApply's downside of not being usable as a range).
May 02 2012
parent "Nick Sabalausky" <SeeWebsiteToContactMe semitwist.com> writes:
"Nick Sabalausky" <SeeWebsiteToContactMe semitwist.com> wrote in message 
news:jnr241$nh1$1 digitalmars.com...
 "SomeDude" <lovelydear mailmetrash.com> wrote in message 
 news:ypakkndfsibcbgeljvgu forum.dlang.org...
 On Tuesday, 1 May 2012 at 08:26:45 UTC, Nick Sabalausky wrote:
 A little write-up I just did on something I thought was pretty cool:

 Combine Coroutines and Input Ranges for Dead-Simple D Iteration
 https://www.semitwist.com/articles/article/view/combine-coroutines-and-input-ranges-for-dead-simple-d-iteration

Call me stupid, but I've absolutely no idea what you're doing. What problem does the InputVisitor solve ? What are the current solutions ? What is the intent of your code ? What are the supposed advantages ? Your article says nothing about it.

Just an easier-to-read/write alternative to an opApply or an input range. More natural and straightforward than a hand-written input range, and cleaner syntax than opApply (and without opApply's downside of not being usable as a range).

Of course, based on the timing results Jerro and Rory reported, Adam's mixin helper for opApply probably hits a better balance of performance vs usability.
May 02 2012
prev sibling parent "jerro" <a a.com> writes:
 It may be slow relative to incrementing a integer:

The opApply isn't just incrementing an integer - it's calling a function through a pointer. A loop that just increments an integer is an order of magnitude faster. This code (I used assembly because a compiler would optimize away such a simple loop) runs in 0.27s on my machine: auto sum = 0; auto n = 1000_000_000; asm { mov EAX, n; mov EBX, sum; loop: dec EAX; inc EBX; test EAX, EAX; jne loop; mov sum, EBX; } Ranges like iota are often as fast as using a for loop. For example this code: auto sum = 0; foreach(i; iota(to!int(args[1]))) sum += i; runs in 0.52 seconds when compiled with gdc with flags -O2 -finline-functions -frelease. When compiled with -O3, gcc uses paddd instruction and it runs in 0.1s.
 And that is for 1000_000_000 Fiber context switches.

I'm not saying that D fibers are slow - fiber context switches are way faster than thread context switches. When using them for IO, such as in vibe.d, overhead of fibers is negligible. But when used for iteration, they are way slower than the alternatives, because in that case there shouldn't be any context switches at all.
May 02 2012