Beefy Boxes and Bandwidth Generously Provided by pair Networks
Come for the quick hacks, stay for the epiphanies.
 
PerlMonks  

Re^4: [OT]: threading recursive subroutines.

by BrowserUk (Patriarch)
on Feb 04, 2011 at 00:07 UTC ( [id://886102]=note: print w/replies, xml ) Need Help??


in reply to Re^3: [OT]: threading recursive subroutines.
in thread [OT]: threading recursive subroutines.

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.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://886102]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others surveying the Monastery: (3)
As of 2024-03-19 10:19 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found