Perl - Synchronizing Data Access

Question

I'm starting to learn parallel programming, and I want to compare a single-threaded program with a multi-threaded one.

I need to make a very simple algorithm that calculates the largest number of possible prime numbers within one minute and shows me the last calculated prime number and its position in the prime numbers.

For example, prime number 23, would appear as the number 23 and its position 9, because it is the 9th prime number.

Without using threads, the number of primes found was 233,596 and the last prime 3,246,107. But with threads, 229,972 primes were found and the last prime was 3,192,463.

I think that is wrong, because multi-threading was supposed to obtain a superior result to the single thread. I believe it is a pretty basic error, but I cannot solve it as I still do not understand much of Perl's parallelism.

This is the code. It calculates prime numbers for one minute single-threaded, and then the same calculation with four threads using shared variables.

use threads;
use threads::shared;

my $seconds = 60;

 # WITHOUT THREAD #
print "\n\n Calc without Threads:\n";
my $endTime = time() + $seconds;
calcWithoutThread();


print "\n\n ----------------===========================---------------- \n";

 # WITH THREAD #
print "\n\n Calc with Threads:\n";
my $prime :shared = 5;          # Starts from the 5th prime
my $totalPrime :shared = 2; # Starts with prime 2 and prime 3
my $lastPrime :shared = 0;
my $endTime1 = time() + $seconds;
my $thread1 = threads->create(\&calcWithThread);
my $thread2 = threads->create(\&calcWithThread);
my $thread3 = threads->create(\&calcWithThread);
my $thread4 = threads->create(\&calcWithThread);
$thread1->join();
$thread2->join();
$thread3->join();
$thread4->join();
print " Was found $totalPrime prime numbers. Last prime: $lastPrime.";


# SUB's #

sub calcWithoutThread{
    $prime = 5;            # Starts from the 5th prime
    $totalPrime = 2;           # Starts with prime 2 and prime 3
    $lastPrime = 0;
    while (time() < $endTime){
        if(calcPrime($prime)){  
            $totalPrime ++;
            $lastPrime = $prime;
        }
        $prime ++;
    }
    print " Was found $totalPrime prime numbers. Last prime: $lastPrime.";
}

sub calcWithThread{
    while (time() < $endTime1) {
        lock($prime);           
        if(calcPrime($prime)){
            $totalPrime ++;
            $lastPrime = $prime;
        }
        $prime ++;
    }   
}

sub calcPrime{
    for($i=2 ; $i< sqrt ($prime) ; $i++){
        if( $prime % $i == 0){
            return 0;
        }
    }
    return 1;   
}

The logic is that the threads do this calculation synchronously, if it is prime number or not, and also do not overlap values while calculating.

Answer 1

The problem is that your threads are synchronised with one another by the locked variable $prime. That means they don't have a chance to run simultaneously, and will also suffer the overhead of switching threads and synchronising access to the variable

Primes aren't a great test for parallel processing, as the calculation of each prime depends on the previous result. However, you could do it by keeping a separate $prime variable, but starting at 5, 6, 7, and 8 for the four threads and adding 4 between tests. That way they don't duplicate each other's work but together cover every integer

There is immediately a problem with this in that none of the even numbers will ever be prime, so two of the four threads will never produce a result. It is still a valid test of parallelism, but clearly very inefficient. You could fix that by starting the threads with 5, 7, 9, and 11, and incrementing by 8 before each test. Then every thread will be profitable

Don't forget that you will have to code the same algorithm for the single-threaded code, otherwise the parallel section gets an unfair advantage

---

Update

Perhaps a better way would be to lock $prime only to fetch the next number to be tested and increment it. That way all the threads can do their calculations in parallel and only queue up to get another job

You would then have to lock $total_prime to prevent two threads from incrementing it simultaneously, and also update $last_prime while that lock is in effect. Because parallel threads may well generate prime numbers out of sequence you will also have to check whether the prime just found is greater than the latest one discovered by any thread

Your subroutine would look like this. I apologise for changing the identifiers, but Perl traditionally uses snake_case and I find camelCase unpleasant to read. Snake case is also much easier for many people whose first language isn't English, and who cannot pick out the capital letters so easily

sub calc_with_thread {

    while ( time() < $end_time_1 ) {

        my $test = do {
            lock $prime;
            $prime++;
        };

        if ( calc_prime($test) ) {
            lock $total_prime;
            ++$total_prime;
            $last_prime = $test if $test > $last_prime;
        }
    }   
}