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:
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
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
next sibling parent reply 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
 =
https://www.semitwist.com/articles/article/view/combine-coroutines-and-inp= ut-ranges-for-dead-simple-d-iteration
=20
 This is fun and all, but because of the horrible performance we =
really=20
 shouldn't be recommending people to use it.
=20 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
parent reply "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
parent reply "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
parent reply "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
parent reply Rory McGuire <rjmcguire gmail.com> writes:
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.
It may be slow relative to incrementing a integer: 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.
May 02 2012
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
prev 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 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