perl threads in a recursive function

[Anonymous Monk]

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

[moritz]

Read perlthrtut. Threads are spawned with threads->create(\&codref, @args); and it doesn't matter if the function that does it is recursive or not.

That said, the requirement does sound odd, and you'd do well to question it critically. Maybe you have an XY Problem?

[Corion]

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.

[Anonymous Monk]

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

[Corion]

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.

[BrowserUk]

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.