I'm trying to learn some multithreading and this seems like a good example, want to apply this to frustum culling later.
The goal is to find prime numbers in randomly generated vector of numbers.
Single threaded solution is simple, multithreaded way is to divide vector of random numbers in two parts, solve each one in the same time and merge results.
Here is the time it took to solve:
mt:
solved in: 17185.4 ms
solved in: 15832.2 ms
solved in: 16012.5 ms
solved in: 16354.9 ms
st:
solved in: 26942 ms
solved in: 30577.9 ms
solved in: 26403.4 ms
solved in: 29625.7 ms
It obviously works, but is the code correct?
This is from main.cpp:
PrimeNumbers numbers(100000, 0, 5000000);
PrimeNumberSolver* solver = new PrimeNumberSingleThread;
numbers.Solve(solver);
delete solver;
This is the rest of the code:
class PrimeNumberSolver abstract {
public:
bool isPrime(int n) {
for (int i = 2; i < n/2; ++i) {
if (n % i == 0)
return false;
}
return true;
}
virtual void solve(const std::vector<int>& source, std::vector<int>& result) = 0;
};
class PrimeNumberSingleThread final : public PrimeNumberSolver {
friend class PrimeNumbers;
private:
virtual void solve(const std::vector<int>& source, std::vector<int>& result) override{
for (unsigned i = 0; i < source.size(); ++i) {
if (isPrime(source[i]))
result.push_back(source[i]);
}
}
};
class PrimeNumberMultiThread final : public PrimeNumberSolver {
friend class PrimeNumbers;
private:
virtual void solve(const std::vector<int>& source, std::vector<int>& result) override {
std::vector<int> r1;
std::vector<int> r2;
//split source
int half = source.size() / 2;
int end = source.size();
std::mutex m;
//run two threads
std::thread t1([&]() {
for (int i = 0; i < half; ++i) {
//std::lock_guard<std::mutex> lock(m); //do i need to lock mutex before accessing source
if (isPrime(source[i]))
r1.push_back(source[i]);
}
});
std::thread t2([&]() {
for (int i = half; i < end; ++i) {
//std::lock_guard<std::mutex> lock(m); //do i need to lock mutex before accessing source
if (isPrime(source[i]))
r2.push_back(source[i]);
}
});
//join threads
if(t1.joinable()) t1.join();
if(t2.joinable()) t2.join();
//merge results
result.insert(result.end(), r1.begin(), r1.end());
result.insert(result.end(), r2.begin(), r2.end());
}
};
class PrimeNumbers {
public:
PrimeNumbers(int size, unsigned min, unsigned max) {
std::mt19937 rng;
for (int i = 0; i < size; ++i) {
rng.seed(std::random_device()());
std::uniform_int_distribution<std::mt19937::result_type> dist6(min, max);
randoms.push_back(dist6(rng));
}
std::cout << "Numbers are generated" << std::endl;
}
void Solve(PrimeNumberSolver* solver) {
double time = glfwGetTime();
solver->solve(randoms, primes);
std::cout << "solved in: " << (glfwGetTime() - time) * 1000.0 << " ms" << std::endl;
}
void printPrimes() {
for (unsigned i = 0; i < primes.size(); ++i)
std::cout << primes[i] << std::endl;
}
std::vector<int> randoms;
std::vector<int> primes;
};
