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.
|