Problem updating array and array pointer in "parallel_for" function

[tigerlcf]

I'm trying to learn parallel programming, so I started by calculating prime numbers in parallel and loading them into a vector array. The problem I have is that the array doesn't get loaded correctly. I use a variable primeCount as the index to the primeArray to load the prime numbers into the array. I created a lock and unlock around all the code in the function calculatePrime that is called by the parallel_for loop, to make sure the variable I used as the index (primeCount) to the array would NOT change while I was trying to use it and increment it.
I have done a lot of testing and sometimes nothing gets loaded into the array when a prime number is found and sometimes the variable primeCount is not incremented before the next prime number is found.
I'm using Visual Studio 2015 Community (I know 2017 will be release next week so I tried it on the latest release of 2017RC)
There seems to be more errors in Debug mode than Release.
The program doesn't list all the valid prime numbers, they can be found on the web.
I do list what seems to be the errors. Note on my computer if you just test the 1st 100 numbers there MANY errors and not the same errors each time the program is ran.
One run of the program 10 of array element between 0 and 24 had a value of "0" left or loaded into it, which means 10 of the 25 prime numbers between 2 and 100 were not loaded.

CPU: Intel i7-3770
16Gb RAM
Windows 10 Home 1607 OS Build 14393.693
Microsoft Visual Studio 2015 Community

What am I doing wrong???
HELP!!

C++ Code:

// Parallel Prime Number Test

#include <ppl.h>
#include <iostream>
#include <vector>
#include <sstream>

using namespace std;
using namespace Concurrency;

unsigned int sqrtN;
unsigned int primeCount;
unsigned int highestPossiableNumberToTest = LONG_MAX; // I tried to use ULONG_MAX but there's not enough
// Ram in my computer for this many prime numbers

// Set up the array to load the prime numbers into
unsigned int arraySize = 20000; // Start with array size = 20,000 It may get larger
vector<unsigned int> primeArray(arraySize);


void calculatePrime(unsigned int n)
{
critical_section lock_prime_count;
sqrtN = sqrt(n); // get the square root on the number testing for prime
for (unsigned int i = 3; i <= sqrtN; i += 2)
{
if ((n % i) == 0)
{
return; // Well n is not prime so exit the test of this number
}
}

// n is prime, lock array "primeArray and "primeCount" and load the pimeNumber
// into primeArray and incriment the promeCount
// lock lock_prime_count so only one this parallel function can make changes at the time
lock_prime_count.lock();
primeArray[primeCount] = n;
string s;
if (primeArray[primeCount] != n)
{
s.append("Error primeArray[");
s.append(to_string(primeCount));
s.append("] did NOT load correctly, the prime number \"");
s.append(to_string(n));
s.append("\" should have been loaded,\n but \"");
s.append(to_string(primeArray[primeCount]));
s.append("\" was found in primeArray[");
s.append(to_string(primeCount));
s.append("] during the \"lock_prime_count.lock\"\n");
}
else
{
s.append("primeArray[");
s.append(to_string(primeCount));
s.append("] seemed to loaded correctly with prime number \"");
s.append(to_string(n));
s.append("\"\n");
// cout << "primeArray loaded correctly array index =: " << primeCount << " prime number =: " << n << endl;
}
cout << s;

primeCount++;
lock_prime_count.unlock();
}

int main()
{
std::string inputstring;

unsigned int startingNumber = 3;
unsigned int steppingNumber = 2;
unsigned int endingNumber;


critical_section lock_prime_count;


while (true) {
std::cout << "Enter the highest number to test, MUST be less than 2^31 - 1 or " <<
" 2,147,483,646 (Remember on commas): ";
std::getline(std::cin, inputstring);

// This code converts from string to number safely.
endingNumber = stoull(inputstring);
if (endingNumber > highestPossiableNumberToTest)
{
std::cout << "Number entered is Grater than " << highestPossiableNumberToTest <<
", please try again " << std::endl << std::endl;
}
else
break;
}

// Since I'm not sure of percentabe of the numbers which are prime, I'll set the array size
// to at least 20,000 or 9% of the endingNumber which ever is greater.
unsigned int testArraySize = endingNumber * .09;
if (testArraySize > arraySize)
{
arraySize = testArraySize;
primeArray.resize(arraySize);
}

// Load the number 2 into the array since it is the only even prime number
critical_section cs;
primeArray[0] = 2;
cout << "\nprimeArray[0] loaded with the 1st prime number of 2 " << endl;
primeCount = 1;


// Calculate all prime number between startingNumber (3) and endingNumber step by 2 to skip all even #'s
parallel_for(startingNumber, endingNumber, steppingNumber, (calculatePrime));

// Check primeArray and see if any array element < primeCount = 0
int errorCount = 0;
for (int i = 0; i < primeCount; i++)
if (primeArray[i] == 0)
errorCount++;

cout << "\nThere was " << errorCount << " array elements that didn't load (or a 0 was loaded)" << endl;

// List all array elements that didn't load (or were loaded with 0)
if (errorCount > 0)
{
cout << "\nHere is the list of array elements (NOT prime Numbers) that have 0 in them" << endl;
for (int i = 0; i < primeCount; i++)
{
if (primeArray[i] == 0)
cout << i << " ";
}
cout << endl;
cout << "\nThere was " << errorCount << " array elements that didn't load (the value was left at 0)" << endl;
}

// Sort array and list all numbers != 0 and less than primeCount;
cout << endl << endl << "Here is a list of the primeNumbers that loaded correctly (primeArray sorted for printout)" << endl;
cout << " Remeber the prime number \"2\" was loaded into the primeArray BEFORE the \"parallel_for\" loop" << endl;
partial_sort(primeArray.begin(), primeArray.begin() + primeCount, primeArray.begin() + primeCount);

for (int i = 0; i < primeCount; i++)
{
if (primeArray[i] != 0)
cout << primeArray[i] << " ";
}

cout << endl << endl << "This program found " << primeCount << " prime numbers (Remember the prime number \"2\"" <<
" was loaded before the \"parallel_for\" loop)" << endl;

cout << endl << "Press the Enter key to close this program!!!";
cin.get();

}

[TheIdeasMan]

Hi,

If you are going to do concurrency, then don't bother with the most inefficient prime number algorithm around - trial division. Google and wiki are your best friends. There are lots of examples on this site as well, so use the search function at the top of this page. JLBorges is one of out experts, so include that as a search term.

Please use code tags: http://www.cplusplus.com/articles/z13hAqkS/

Your program doesn't do anything in parallel, you need threads to do that.

Try to avoid infinite loops, they are only needed if there are multiple dependent exit points.

There is no need to put return; at the end of a void function. That is only required if one wants an early exit from a void function.

[JLBorges]

> Your program doesn't do anything in paralle

Concurrency::parallel_for
https://msdn.microsoft.com/library/520a6dff-9324-4df2-990d-302e3050af6a.aspx#parallel_for_function


With the same trial division primality test algorithm as in the original post:

#include <ppl.h>
#include <iostream>
#include <array>
#include <cmath>
#include <atomic>
#include <algorithm>

constexpr unsigned int SZ = 1'000'000 ;
std::array< unsigned int, SZ > primes { 2 } ;
std::atomic<unsigned int> cnt {0} ; // atomic

bool is_prime( unsigned int number ) // invariant: n > 2
{
    const unsigned int sqrt = std::sqrt(number) + 1 ;
    for( unsigned int i = 3 ; i <= sqrt ; ++i ) if( number%i == 0 ) return false ;
    return true ;
}

void append_if_prime( unsigned int number )
{
    if( is_prime(number) )
    {
        const auto i = ++cnt ;
        if( i < primes.size() ) primes[i] = number ;
    }
}

int main()
{
    // conservative. use the prime number theorem instead to get the lower bound
    // https://en.wikipedia.org/wiki/Prime_number_theorem
    const unsigned int BOUND = SZ * 10 ;

    Concurrency::parallel_for( 3U, BOUND, 2U, append_if_prime ) ;
    std::cout << cnt << " prime numbers in all " << " up to " << BOUND << "\n\n" ;

    std::sort( primes.begin(), primes.begin() + cnt ) ;
    
    if( cnt >= 100'000 )
        std::cout << "the " << 100'000 << "th prime number is: " << primes[99'999] << "\n\n" ;

    // list the first 50 prime numbers
    // for( std::size_t i = 0 ; i < 50 ; ++i ) std::cout << primes[i] << '\n' ;
} 

http://rextester.com/VIUJ11182

[JLBorges]

Can parallelise the sort too:

//std::sort( primes.begin(), primes.begin() + cnt ) ;
Concurrency::parallel_radixsort( primes.begin(), primes.begin() + cnt ) ;

// or for a std::sort like comparison-based in-place sort: 
// Concurrency::parallel_sort( primes.begin(), primes.begin() + cnt ) ; 

http://rextester.com/ESV25182

[tigerlcf]

JLBorges
Thank you VERY much!!!
This solved the problem!!!