Beefy Boxes and Bandwidth Generously Provided by pair Networks
laziness, impatience, and hubris
 
PerlMonks  

comment on

( [id://3333]=superdoc: print w/replies, xml ) Need Help??

I just noticed this, I don't think it was a part of the post when I originally saw it. We must have overlapped.

No, that does not limit the number of workers.

Actually, the futures code does limit the number of workers. In the case of the posted sample, to 6 threads (plus the original):

#! perl -slw use strict; use futures; sub fibonacci { my $n = shift; return $n if $n < 2; my $r1 = futures->new( \&fib_t1, $n -2 ); #1 my $r2 = futures->new( \&fib_t1, $n -1 ); #2 return $r1 + $r2; } sub fib_t1 { my $n = shift; return $n if $n < 2; my $r1 = futures->new( \&fib_t2, $n -2 ); #3 & #5 my $r2 = futures->new( \&fib_t2, $n -1 ); #4 & #6 return $r1 + $r2; } sub fib_t2 { my $n = shift; return $n if $n < 2; return fib_t2( $n -2 ) + fib_t2( $n -1 ); }

It does it through the expedient of using 3 levels of sub call. The first two spawn threads, but the third, fib_t2(), uses straight recursion. This was done manually, and 3 levels were chosen so as to have 4 threads running for the majority of the time, to match my 4-cores.

But it is not hard to see how this could be done automatically at either compile-time or run-time.

There is the possibility of avoiding the two essentially redundant spawns at the first level, by having the second level return a future that closes over the addition of the two futures it creates.

Something like:

#! perl -slw use strict; use futures; sub fibonacci { my $n = shift; return $n if $n < 2; return fib_t1( $n -2 ) + fib_t1( $n -1 ); } sub fib_t1 { my $n = shift; return $n if $n < 2; return futures->new( sub{ futures->new( \&fib_t2, $n-2 ) + futures->new( \&fib_t2, +$n-1 ) } ); } sub fib_t2 { my $n = shift; return $n if $n < 2; return fib_t2( $n -2 ) + fib_t2( $n -1 ); }

In this way, only 4 threads would be created and the original thread would wait for their completion.

And by eliminating the temporary variables, it possible to see how the forms of the three levels of subroutine actually closely mirror each other.

The next step is to move the decision as to which of the forms to use for any given level under the covers of the futures module. At that point, the user constructs a single recursive routine in the familiar way, but using futures for each recursive call, and the module keeps track of how many threads it is spawning.

Ultimately, rather than having to use the futures constructor, the goal would be to simply mark the subroutine with an attribute and have it all taken care of transparently. Something like:

sub fibonacci :future { my $n = shift; return $n if $n < 2; return fibonacci( $n -2 ) + fibonacci( $n -1 ); }

Now, everything that was done manually in the second code block above should be feasible without further application programmer intervention.

As already discussed, it wouldn't benefit such a trivial function, but it could for others.


Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.

In reply to Re^4: [OT]: threading recursive subroutines. by BrowserUk
in thread [OT]: threading recursive subroutines. by BrowserUk

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Are you posting in the right place? Check out Where do I post X? to know for sure.
  • Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
    <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
  • Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
  • Want more info? How to link or How to display code and escape characters are good places to start.
Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others making s'mores by the fire in the courtyard of the Monastery: (4)
As of 2024-03-28 18:01 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found