• bearophile (78/84) Nov 01 2014 Now in Phobos there is std.concurrency.Generator. In Python they
• Sean Kelly (4/4) Nov 01 2014 I see generators as being somewhat like opApply in terms of how
• bearophile (8/8) Nov 05 2014 Another problems of std.concurrency.Generator is that currently

"bearophile" <bearophileHUGS lycos.com> writes:

Now in Phobos there is std.concurrency.Generator. In Python they 
added "yield from" for various reasons:
http://legacy.python.org/dev/peps/pep-0380/

One of the reasons is performance:

Using a specialised syntax opens up possibilities for 
optimisation when there is a long chain of generators. Such 
chains can arise, for instance, when recursively traversing a 
tree structure. The overhead of passing __next__() calls and 
yielded values down and up the chain can cause what ought to be 
an O(n) operation to become, in the worst case, O(n**2).<


An example:

-------------------
import std.stdio, std.concurrency, std.range, std.datetime;

struct Node {
     uint data;
     Node* left, right;
}

Node* generateCompleteBinaryTree(in uint depth, ref uint count) {
     if (depth == 0)
         return null;

     auto t = new Node(count++);
     t.left = generateCompleteBinaryTree(depth - 1, count);
     t.right = generateCompleteBinaryTree(depth - 1, count);
     return t;
}

Generator!(const typeof(Node.data)) visitBinaryTree(in Node* t) {
     return new typeof(return)({
         if (t != null) {
             yield(t.data);
             foreach (t2; [t.left, t.right])
                 foreach (d; t2.visitBinaryTree)
                     yield(d);
         }
     });
}

void main() {
     StopWatch sw;
     foreach (immutable uint n; 1 .. 16) {
         sw.reset;
         sw.start;
         uint count = 0;
         auto t = generateCompleteBinaryTree(n, count);
         sw.stop;
         immutable t1 = sw.peek.nsecs;
         sw.reset;
         sw.start;
         immutable len = t.visitBinaryTree.walkLength;
         sw.stop;
         immutable t2 = sw.peek.nsecs;
         writeln(n, " ", len, " ", t1, " ", t2);
     }
}
-------------------

Outputs:

1 1 5517 43650
2 3 4539 51333
3 7 4609 108323
4 15 5866 215530
5 31 8380 446844
6 63 13339 926025
7 127 23606 1914209
8 255 47282 3899238
9 511 93168 8586915
10 1023 211549 34013820
11 2047 362057 35226963
12 4095 19813342 83622988
13 8191 1370285 200720273
14 16383 2895968 357415886
15 32767 12413030 813869919


So is it possible to implement something like a 
std.concurrency.yieldAll that helps keep that complexity low?


Generator!(const typeof(Node.data)) visitBinaryTree(in Node* t) {
     return new typeof(return)({
         if (t != null) {
             yield(t.data);
             foreach (t2; [t.left, t.right])
                 yieldAll(t2.visitBinaryTree);
         }
     });
}


But perhaps the time to create the generators dwarfs the O(n^2) 
behavour in most practical cases...

Bye,
bearophile

"Sean Kelly" <sean invisibleduck.org> writes:

I see generators as being somewhat like opApply in terms of how 
they're written. So a single generator would recurve across the 
entire tree. Allocating a new generator per node isn't going to 
be very efficient, even if we optimize for that case.

"bearophile" <bearophileHUGS lycos.com> writes:

Another problems of std.concurrency.Generator is that currently 
it's not pure, not nothrow, not  safe and not  nogc. So its usage 
turns clean code into something that much less guarantees. This 
is unfortunate because you want to use it mostly in the 
functional-style code where you want those well-behaving 
guarantees.

Bye,
bearophile