Beefy Boxes and Bandwidth Generously Provided by pair Networks
P is for Practical
 
PerlMonks  

perl threads in a recursive function

by Anonymous Monk
on Aug 21, 2013 at 11:13 UTC ( #1050324=perlquestion: print w/ replies, xml ) Need Help??
Anonymous Monk has asked for the wisdom of the Perl Monks concerning the following question:

Hi I want to create perl threads in a recursive function A new thread has to be created each time you call the function Please suggest a way how to achieve it

Comment on perl threads in a recursive function
Re: perl threads in a recursive function
by moritz (Cardinal) on Aug 21, 2013 at 11:17 UTC
Re: perl threads in a recursive function
by Corion (Pope) on Aug 21, 2013 at 11:17 UTC

    Have you considered reading threads.pm?

    If you want more specific help, consider telling us where exactly you encounter problems. The best approach is to show a short, self-contained example that we can use to reproduce your problem and suggest solutions.

      package hi; sub fn { my $thread_signal = threads->create(\&Signal_ThreadCb,@_); push @main::threads_pool,$thread_signal; } package main; hi::fn(); hi::fn(); hi::fn();
      At the thread creation point error is occuring ;Segmentation fault core dumped

        Maybe read the answers to getting segmentation fault core dumped when I am running, which describe symptoms quite similar to yours and the approach to solve them.

        You don't show the (relevant) parts of Signal_ThreadCb. If you are mixing signals and threads, be advised that this is usually not well-supported by Perl and the underlying operating systems.

Re: perl threads in a recursive function
by BrowserUk (Pope) on Aug 21, 2013 at 14:56 UTC
    A new thread has to be created each time you call the function

    It depends very much upon the function involved. But in any case, it makes no sense to start more threads than you have cores/processors.

    And for tail-recursive functions; it makes no sense at all. Better to re-write the function to use iteration.

    The only really effective way to use threads in a recursive function is to split the iterative component of the function -- if it has one -- at the highest (earliest) level of recursion and then use normal recursion below that level.

    NB: Pointing out that the threaded versions below are slower than the non-threaded is redundant :)

    By way of example, the quicksort algorithm can be coded in perl as:

    sub quicksort { return @_ unless @_ > 1; my $pivot = shift; return ( quicksort( grep $_ < $pivot, @_ ), $pivot, quicksort( grep $_ >= $pivot, @_ ), ); }

    Starting a new thread for every level of recursion would be stupid. At the lowest levels, you would be starting a whole thread only to immediately return the single argument to the caller. And as recursion doesn't 'bottom out' until the function is called with a single value, it means that to sort a million items, you would be starting a million threads at the lowest level alone; and many, many others before you reach that level.

    So, to stand a chance of benefiting from threading in a recursive algorithm, you need to strictly control and limit the number of threads that are used. The simplest way to do that is to use two (or more) levels of function whereby the top level(s) deploy threads on a number (often 2) partitions of the data; and then those threads run a standard recursive algorithm upon those partitions.

    For the quicksort algorithm above that might look like this:

    sub quicksort_t { return @_ unless @_ > 1; my $pivot = shift; ## partition the data into 2 parts and run the standard recursive +algorithm ## on those two partitions in separate threads; return combined (j +oined) results my $t1 = asyncl sub{ quicksort( grep $_ < $pivot, @_ ) }, @_; my $t2 = asyncl sub{ quicksort( grep $_ >= $pivot, @_ ) }, @_; return ( $t1->join, $pivot, $t2->join ); }

    NB: asyncl() is not the standard async() function from threads, but rather a modified version that handles list context returns correctly.

    Theoretically, the runtime is halved. In practice, the overhead of starting threads and passing long lists through slow shared memory makes this much less efficient. But the theory is good :)

    If that was efficient, and you have more than 2 cores, you could take it a step further and inject a second level of threaded partitioning, thus using 4 threads:

    sub _quicksort_t { return @_ unless @_ > 1; my $pivot = shift; ## partition the data into 2 parts and run the standard recursive +algorithm ## on those two partitions in separate threads; return combined (j +oined) results my $t1 = asyncl sub{ quicksort( grep $_ < $pivot, @_ ) }, @_; my $t2 = asyncl sub{ quicksort( grep $_ >= $pivot, @_ ) }, @_; return ( $t1->join, $pivot, $t2->join ); } sub quicksort_t { return @_ unless @_ > 1; my $pivot = shift; ## Partition and thread to a thread helper function my $t1 = asyncl sub{ _quicksort_t( grep $_ < $pivot, @_ ) }, @_; my $t2 = asyncl sub{ _quicksort_t( grep $_ >= $pivot, @_ ) }, @_; return ( $t1->join, $pivot, $t2->join ); }

    Luckily, cores tend to come in powers of two, so this can be extended to handle 8, 16 32 etc.

    So, whilst threading the quicksort function in Perl doesn't result in any benefit (a contrariis: quite the opposite), it does lend itself to describing the possibilities for threading recursive algorithms; which for different algorithms and/or different languages can yield significant benefits.


    With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
    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
Node Status?
node history
Node Type: perlquestion [id://1050324]
Approved by Corion
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others surveying the Monastery: (3)
As of 2014-10-20 23:39 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    For retirement, I am banking on:










    Results (93 votes), past polls