(どこで何か間違っているのかを見つけるために、これをできるだけ単純化しようとしました。)
コードのアイデアは、グローバル配列 *v を持っていることです (この配列を使用しても速度が低下しないことを願っています。スレッドはすべて異なる範囲で動作するため、スレッドが同じ値にアクセスすることはありません)。2 つのスレッドを作成しようとしています。それぞれが、それぞれのパラメーターを指定して関数 merge_sort() を呼び出して、前半と後半をそれぞれソートします。
スレッド化された実行では、プロセスが 80 ～ 100% の CPU 使用率 (デュアル コア CPU の場合) に達していることがわかりますが、非スレッド実行では 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;
}
出力 (100 万の値):
Sort time (s): 1.294
スレッドなしで、merge_sort を直接呼び出して出力します。
Sort time (s): 1.388
出力 (1000 万の値):
Sort time (s): 12.75
スレッドなしで、merge_sort を直接呼び出して出力します。
Sort time (s): 13.838
解決：
WhozCraig と Adam にも感謝したいと思います。彼らは最初からこれを示唆していました。
私は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);
編集、私の3GHzデュアルコアCPUで時々：
100 万の値: 1 スレッド: 7.236 秒 2 スレッド: 4.622 秒 4 スレッド: 4.692 秒
1000 万の値: 1 スレッド: 82.034 秒 2 スレッド: 46.189 秒 4 スレッド: 47.36 秒