Реализация Mergesort pThread занимает столько же времени, сколько и однопоточный

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

Идея кода в том, что у меня есть глобальный массив * v (я надеюсь, что использование этого массива не замедляет работу, потоки никогда не должны получать одно и то же значение, потому что все они работают в разных диапазонах), и я пытаюсь создать 2 потока каждая сортирует первую половину, соответственно вторую половину, вызывая функцию merge_sort () с соответствующими параметрами.

На многопоточном прогоне я вижу, что процесс идет на 80-100% использования процессора (на двухъядерном процессоре), в то время как на процессах без потоков он остается только на 50%, но время выполнения очень близко.

---

Это (соответствующий) код:

// Это 2 функции сортировки, каждый поток вызовет merge_sort (..). Это проблема? оба потока вызывают одну и ту же (нормальную) функцию?

void merge (int *v, int start, int middle, int end) {
//dynamically creates 2 new arrays for the v[start..middle] and v[middle+1..end]
//copies the original values into the 2 halves
//then sorts them back into the v array
}

void merge_sort (int *v, int start, int end) {
//recursively calls merge_sort(start, (start+end)/2) and merge_sort((start+end)/2+1, end) to sort them
//calls merge(start, middle, end)
}

// здесь я ожидаю, что каждый поток будет создан и вызовет merge_sort в определенном диапазоне (это упрощенная версия исходного кода, чтобы облегчить поиск ошибки)

void* mergesort_t2(void * arg) {
t_data* th_info = (t_data*)arg;
merge_sort(v, th_info->a, th_info->b);
return (void*)0;
}

// в основном я просто создаю 2 потока, вызывающих вышеуказанную функцию

int main (int argc, char* argv[])
{
//some stuff

//getting the clock to calculate run time
clock_t t_inceput, t_sfarsit;
t_inceput = clock();

//ignore crt_depth for this example (in the full code i'm recursively creating new threads and i need this to know when to stop)
//the a and b are the range of values the created thread will have to sort
pthread_t thread[2];
t_data next_info[2];
next_info[0].crt_depth = 1;
next_info[0].a = 0;
next_info[0].b = n/2;
next_info[1].crt_depth = 1;
next_info[1].a = n/2+1;
next_info[1].b = n-1;

for (int i=0; i<2; i++) {
if (pthread_create (&thread[i], NULL, &mergesort_t2, &next_info[i]) != 0) {
cerr<<"error\n;";
return err;
}
}

for (int i=0; i<2; i++) {
if (pthread_join(thread[i], &status) != 0) {
cerr<<"error\n;";
return err;
}
}

//now i merge the 2 sorted halves
merge(v, 0, n/2, n-1);

//calculate end time
t_sfarsit = clock();

cout<<"Sort time (s): "<<double(t_sfarsit - t_inceput)/CLOCKS_PER_SEC<<endl;
delete [] v;
}

---

Вывод (на 1 млн. Значений):

Sort time (s): 1.294

Вывод с прямым вызовом merge_sort, без потоков:

Sort time (s): 1.388

---

Вывод (на 10 млн. Значений):

Sort time (s): 12.75

Вывод с прямым вызовом merge_sort, без потоков:

Sort time (s): 13.838

---

Решение:

Я хотел бы поблагодарить WhozCraig и Адама, так как они намекали на это с самого начала.

Я использовал inplace_merge(..) функции вместо моей и время выполнения программы, как они должны сейчас.

Вот моя начальная функция слияния (не совсем уверен, что если начальная, я, вероятно, несколько раз ее модифицировал, так как индексы массивов могут быть неправильными прямо сейчас, я перебирал между [a, b] и [a, b) это была только последняя закомментированная версия):

void merge (int *v, int a, int m, int c) { //sorts v[a,m] - v[m+1,c] in v[a,c]

//create the 2 new arrays
int *st = new int[m-a+1];
int *dr = new int[c-m+1];
//copy the values
for (int i1 = 0; i1 <= m-a; i1++)
st[i1] = v[a+i1];
for (int i2 = 0; i2 <= c-(m+1); i2++)
dr[i2] = v[m+1+i2];

//merge them back together in sorted order
int is=0, id=0;
for (int i=0; i<=c-a; i++)  {
if (id+m+1 > c || (a+is <= m && st[is] <= dr[id])) {
v[a+i] = st[is];
is++;
}
else {
v[a+i] = dr[id];
id++;
}
}
delete st, dr;
}

все это было заменено на:

inplace_merge(v+a, v+m, v+c);

---

Отредактируйте несколько раз на моем 3-ГГц двухъядерном процессоре:

1 миллион значений:
1 поток: 7,236 с
2 темы: 4.622 с
4 темы: 4.692 с

10 миллионов значений:
1 поток: 82,034 с
2 темы: 46,189 с
4 темы: 47,36 с