I need to solve a large problem, on a large graph instances, and in order to do so I divide the input space between threads to solve indipendenlty the same function on each set of inputs. When i time to understand the scalability of my software, I notice that when I increase the number of threads used, after 4 threads the time increases. I coded a really small example to see why this happens, here it follows:
#include <algorithm>
#include <random>
#include <thread>
#include <iostream>
#include <chrono>
template<typename T>
inline double getMs(T start, T end) {
return double(
std::chrono::duration_cast<std::chrono::milliseconds>(end - start)
.count()) /
1000;
}
int main(int) {
std::random_device rd;
std::mt19937 g(rd());
unsigned int n = std::thread::hardware_concurrency();
std::cout << n << " concurrent threads are supported.\n";
for (size_t np = 2; np < 17; np++) {
auto start = std::chrono::high_resolution_clock::now();
std::cout << np << " threads: ";
std::vector<std::thread> threads(np);
int number_stops = 50; // memory 39420
int number_transfers = 1; // memory
int number_structures = 1; // memory
int number_iterations = 1000000; // time
auto dimension = number_stops * (number_transfers + 1) * number_structures;
auto paraTask = [&]() {
for (int b = 0; b < number_iterations; b++) {
//std::srand(unsigned(std::time(nullptr)));
std::vector<int> v(dimension, 1586)
//std::generate(v.begin(), v.end(), std::rand);
v.clear();
}
};
for (size_t i = 0; i < np; i++) {
threads[i] =
std::thread(paraTask);
}
// Join the threads
for (auto&& thread : threads) thread.join();
double elapsed = getMs(start, std::chrono::high_resolution_clock::now());
printf("parallel completed: %.3f sec.\n",
elapsed);
}
return 0;
}
Just a brief description. In order to emulate the actual software I'm working on, I use here the variables:
int number_stops = 50; // memory 39420
int number_transfers = 1; // memory
int number_structures = 1; // memory
int number_iterations = 1000000; // time
Without much details, the first three are there to simulate the memory consumption (how many vector entries I fill in each call), while the fourth one is there to simulate the number of iterations. This is here to see what causes the increasing in time, if is the memory consumption when we add threads, or if we have more problems with more computational time in each thread. (or both)
I copy down here the result with the setting above:
16 concurrent threads are supported.
2 threads: parallel completed: 0.995 sec.
3 threads: parallel completed: 1.017 sec.
4 threads: parallel completed: 1.028 sec.
5 threads: parallel completed: 1.081 sec.
6 threads: parallel completed: 1.131 sec.
7 threads: parallel completed: 1.122 sec.
8 threads: parallel completed: 1.216 sec.
9 threads: parallel completed: 1.445 sec.
10 threads: parallel completed: 1.603 sec.
11 threads: parallel completed: 1.596 sec.
12 threads: parallel completed: 1.626 sec.
13 threads: parallel completed: 1.634 sec.
14 threads: parallel completed: 1.611 sec.
15 threads: parallel completed: 1.648 sec.
16 threads: parallel completed: 1.688 sec.
So, as you can see, the time increases. Why is that. I also tried the other way around (less iteration but more memory):
int number_stops = 50; // memory 39420
int number_transfers = 100; // memory
int number_structures = 100; // memory
int number_iterations = 50; // time
and the same happens, the time increases:
16 concurrent threads are supported.
2 threads: parallel completed: 0.275 sec.
3 threads: parallel completed: 0.267 sec.
4 threads: parallel completed: 0.278 sec.
5 threads: parallel completed: 0.282 sec.
6 threads: parallel completed: 0.303 sec.
7 threads: parallel completed: 0.314 sec.
8 threads: parallel completed: 0.345 sec.
9 threads: parallel completed: 0.370 sec.
10 threads: parallel completed: 0.368 sec.
11 threads: parallel completed: 0.395 sec.
12 threads: parallel completed: 0.407 sec.
13 threads: parallel completed: 0.431 sec.
14 threads: parallel completed: 0.444 sec.
15 threads: parallel completed: 0.448 sec.
16 threads: parallel completed: 0.455 sec.
To give more context, here the specification of my computer:
- CPU - 11th Gen Intel(R) Core(TM) i7-11700KF @ 3.60GHz
- RAM - 16 GB DDR4
- Windows 11 Compiler - MS_VS 2022
Furthermore, here an hardware report from CPU-Z
My CPU has 8 physical cores, and 16 logical ones.
