При выполнении расчета — сколько потоков я должен открыть?

Я пишу программу, которая выполняет длинные вычисления, которые я могу разбить на столько задач, сколько захочу. Для обсуждения давайте предположим, что я пишу алгоритм для определения, является ли число p простым, пытаясь разделить его на все числа от 2 до p-1. Эта задача, очевидно, может быть разбита на множество потоков.

Я на самом деле написал пример приложения, которое делает именно это. В качестве параметра я даю число, которое я хочу проверить, и количество потоков, которые нужно использовать (каждому потоку дается диапазон одинакового размера чисел, на который нужно попытаться разделить p — вместе они охватывают весь диапазон).

У моей машины 8 ядер. Я начал запускать программу с большим числом, которое, как я знаю, является простым (2971215073), и с 1, 2, 3 потоками и т. Д. До достижения 8 потоков — каждый раз, когда программа работала быстрее, чем предыдущая, что я и ожидал. Тем не менее, когда я пробовал числа больше 8, время вычислений становилось все меньше (даже если немного)!

В моих потоках нет ни ввода-вывода, ни чего-либо подобного, только вычисления процессора. Я ожидал, что время выполнения ухудшится, когда я пропущу 8 потоков, поскольку будет больше переключения контекста, а число параллельно работающих потоков останется равным 8. Трудно сказать, где находится пик, поскольку различия очень малы и меняются от одного запуска к другому, однако ясно, что, например, 50 потоков как-то работают быстрее, чем 8 (на ~ 300 мс) …

Я предполагаю, что, поскольку у меня так много потоков, я получаю больше времени выполнения, так как у меня большая часть в системном пуле потоков, поэтому мои потоки выбираются больше. Тем не менее, кажется, что не имеет смысла, что чем больше потоков я создаю, тем быстрее работает программа (иначе почему бы не каждому создать 1000 потоков ??).

Может ли кто-нибудь предложить объяснение и, возможно, лучшую практику относительно того, сколько потоков создать относительно количества ядер на машине?

Благодарю.

Мой код для тех, кто заинтересован (скомпилировано на Windows, VS2012):

#include <Windows.h>
#include <conio.h>
#include <iostream>
#include <thread>
#include <vector>

using namespace std;

typedef struct
{
unsigned int primeCandidate;
unsigned int rangeStart;
unsigned int rangeEnd;
} param_t;DWORD WINAPI isDivisible(LPVOID p)
{
param_t* param = reinterpret_cast<param_t*>(p);

for (unsigned int d = param->rangeStart; d < param->rangeEnd; ++d)
{
if (param->primeCandidate % d == 0)
{
cout << param->primeCandidate << " is divisible by " << d << endl;
return 1;
}
}

return 0;
}

bool isPrime(unsigned int primeCandidate, unsigned int numOfCores)
{
vector<HANDLE> handles(numOfCores);
vector<param_t> params(numOfCores);
for (unsigned int i = 0; i < numOfCores; ++i)
{
params[i].primeCandidate = primeCandidate;
params[i].rangeStart = (primeCandidate - 2) * (static_cast<double>(i) / numOfCores) + 2;
params[i].rangeEnd = (primeCandidate - 2) * (static_cast<double>(i+1) / numOfCores) + 2;
HANDLE h = CreateThread(nullptr, 0, reinterpret_cast<LPTHREAD_START_ROUTINE>(isDivisible), &params[i], 0, 0);
if (NULL == h)
{
cout << "ERROR creating thread: " << GetLastError() << endl;
throw exception();
}
handles[i] = h;
}

DWORD ret = WaitForMultipleObjects(numOfCores, &handles[0], TRUE, INFINITE);
if (ret >= WAIT_OBJECT_0 && ret <= WAIT_OBJECT_0 + numOfCores - 1)
{
for (unsigned int i = 0; i < numOfCores; ++i)
{
DWORD exitCode = -1;
if (0 == GetExitCodeThread(handles[i], &exitCode))
{
cout << "Failed to get thread's exit code: " << GetLastError() << endl;
throw exception();
}

if (1 == exitCode)
{
return false;
}
}

return true;
}
else
{
cout << "ERROR waiting on threads: " << ret << endl;
throw exception();
}
}

int main()
{
unsigned int primeCandidate = 1;
unsigned int numOfCores = 1;

cout << "Enter prime candidate: ";
cin >> primeCandidate;
cout << "Enter # of cores (0 means all): ";
cin >> numOfCores;
while (primeCandidate > 0)
{
if (0 == numOfCores) numOfCores = thread::hardware_concurrency();

DWORD start = GetTickCount();
bool res = isPrime(primeCandidate, numOfCores);
DWORD end = GetTickCount();
cout << "Time: " << end-start << endl;
cout << primeCandidate << " is " << (res ? "" : "not ") << "prime!" << endl;

cout << "Enter prime candidate: ";
cin >> primeCandidate;
cout << "Enter # of cores (0 means all): ";
cin >> numOfCores;
}

return 0;
}