ソートアルゴリズムをマルチスレッドで

コメントを残す

唐突ですが、何となく気になったのでやってみました。

ただの話題作りとも言います。

アルゴリズムのレベルでマルチスレッド化できるソートアルゴリズムを考える

よく使用される(あるいははサンプルなどで登場する)ソートアルゴリズムとしては以下の物があります。

  • バブルソート
  • 選択ソート
  • 挿入ソート
  • シェルソート
  • クイックソート
  • ヒープソート
  • マージソート

この中でマルチスレッド化が出来る物と出来ない物を考えてみたいと思います。

マルチスレッド化するため必要な条件としては

  • ソート時にメモリ空間が競合しないこと

になります。特に常に全域を調べていくソート法ではマルチスレッド化が出来ないですね。

ちなみに、普通にどのソート法であったとしても

  1. ソート対象領域をいくつかに分ける
  2. それぞれに対してソートを適応(これはマルチスレッド化可能)
  3. 完了した領域を併合する(マージソートの併合と同じ)

と言う方法でマルチスレッド化をはかることは出来ますが・・・。

と言うわけで分類をしてみると

マルチスレッド化が出来る

  • シェルソート
  • クイックソート
  • マージソート

マルチスレッド化が出来ない

  • バブルソート
  • 選択ソート
  • 挿入ソート
  • ヒープソート

となります。・・・あっていますよね？

どうやってマルチスレッド化する？

マルチスレッド化可能な各アルゴリズムで、どの部分がマルチスレッド化可能かは、アルゴリズムの流れを見て見れば分かります。

シェルソート

  1. ある数列を作成(データ数より大きくならない場所でストップ)
  2. 作成した数列よりデータの間隔を決定
  3. 間隔をあけた挿入ソートをデータ全体に行う(これはマルチスレッド化可能)
  4. 数列に従い間隔を狭くし、間隔が1になるまで3.を繰り返す
  5. 間隔を1にして挿入ソートを全体に行う

クイックソート

  1. 対象のデータ列から適当な値をピボット値として選択
  2. ピボット値より小さい物と大きい物を領域に分割
  3. 分割した領域それぞれに1.および2.を再度行う(これはマルチスレッド化可能)
  4. なお、対象の領域が狭すぎる場合は領域分割ではなく別のソート法を適応する場合が一般的(この場合、ソート法は挿入ソートが主に使われる)

マージソート

  1. 対象のデータ列の領域を分割する
  2. 分割された領域がある程度より小さくなった段階で適当なソートを行う(データ数が1(ソートしない)でも可。2以上のソート法は挿入ソートが主に使われる)
  3. 隣り合ったソート済み領域同士のデータを併合していく(各領域が競合しない範囲でマルチスレッド化可能)

と言うわけで、実証実験

非マルチスレッドのアルゴリズムとマルチスレッド化したアルゴリズムで時間をとった結果を示してみます。

データは32bit符号あり乱数を2^26(67108864)個でテストしています。各ソートに与えるデータは同一のデータを与えてあります。

マルチスレッド数は私のPCのCPUコア数でもある4を指定してあります。

また、STLの結果を参考として書いてあります。STLはマルチスレッド化できませんのでそのままです。

[NonMultiThread]

STL Sort: 25201886 ( 9.68 sec)

QuickSort: 18835701 ( 7.23 sec)

ShellSort: 118644022 (45.56 sec)

MergeSort: 33707226 (12.94 sec)

[MultiThread]

STL Sort: 25908523 ( 9.95 sec)

QuickSort: 5569027 ( 2.14 sec)

ShellSort: 70368854 (27.02 sec)

MergeSort: 21896956 ( 8.41 sec)

マルチスレッド化でそれなりに高速になっているのが分かると思います。

特にQuickSortの伸び率が3倍前後とかなりいい結果ですね。

が、この結果には微妙なトリックが

マルチスレッド化するときに問題になるのが「タスクの大きさをどれくらいにするか」という物です。

タスクが小さくなりすぎるとマルチスレッド化したときにタスクの発行やスレッドの管理に時間を使ってしまい、速度が落ちてしまう、と言う現象がおこります。

今回のように整数のソートだと比較と代入がかなり早く行われるのであまりに少ないデータ数までタスクとして発行してしまうととんでもないことになります。

その結果を示すためにちょっとグラフを作ってみました。QuickSortとMergeSortをマルチスレッドタスクとして発行する数を変えてテストした物です。

縦軸はソートが完了するまでにかかった時間(秒)、横軸はタスクを発行する分割限界数です。

20130210171014

グラフより

  1. クイックソートの場合、2^12個～2^22個くらいのデータまででソートタスクを発行すると速度がよい
  2. マージソートの場合、2048個くらいのデータまででマージタスクを発行すると速度がよい
  3. どちらも512個より少ない数でもタスクを発行してしまうと極端に実行効率が悪くなる

この辺はデータ数、CPUの各コア演算速度、CPUの有効演算コア数によって変わるので参考データですが、やはりあまりに細かく分割すると良くないことは確認できました。

といっても、簡単なソートくらいでマルチスレッド処理は普通使わないよね・・・

まあ、こんなものでマルチスレッド化する意味があるとすればせいぜいデータベースのソートくらいですか・・・。

ゲームなどで少量のデータをソートするくらいなら普通にやるのが正しいですしね・・・。

最後にコードを

無用だと思いますが何となく示してみます。

乱数処理やスレッドプールは自分で作ってくださいね。

また、MergeSortは面倒だったので2の累乗専用となっています。

#include <windows.h>
#include <stdio.h>
#include "randmt.h"
#include "threadpool.h"
typedef int inttype_t;
#define QUICKSORT_USEINSERT 32
#define MERGESORT_USEINSERT 64
typedef void (*LPFNSORT)(inttype_t *,uintptr_t,size_t);
CThreadPool *g_lpPool = NULL;
void addtask(LPFNSORT fn,inttype_t *p,uintptr_t value,size_t width)
{
	if(width >= 4096){ g_lpPool->AddTask(fn,p,value,width); }
	else{ fn(p,value,width); }
}
void insertsort(inttype_t *p,uintptr_t value,size_t width)
{
	size_t i,j; inttype_t n;
	for(i = 1;i < width;i++){
		n = p[i];
		if(p[i - 1] > n){
			for(j = i;j > 0 && p[j - 1] > n;j--){
				p[j] = p[j - 1];
			}
			p[j] = n;
		}
	}
}
void quicksort(inttype_t *p,uintptr_t value,size_t width)
{
	if(width < QUICKSORT_USEINSERT){ insertsort(p,0,width); return; }
	inttype_t n,n1,n2,n3; ptrdiff_t i,j,ll,rl;
	i = width / 2; j = width - 1;
	n1 = p[0]; n2 = p[i]; n3 = p[j];
	if(n1 > n2){ n = n1; n1 = n2; n2 = n; }
	if(n1 > n3){ n = n1; n1 = n3; n3 = n; }
	if(n2 > n3){ n = n2; n2 = n3; n3 = n; }
	p[0] = n1; p[i] = n2; p[j] = n3;
	i = 1; j = width - 2;
	while(1){
		while(p[i] < n2) i++;
		while(p[j] > n2) j--;
		if(i >= j) break;
		n = p[i]; p[i] = p[j]; p[j] = n;
		i++; j--;
	}
	ll = i; rl = (ptrdiff_t)width - (j + 1);
	if(ll > 0){ addtask(quicksort,p,value,ll); }
	if(rl > 0){ addtask(quicksort,p + (j + 1),value,rl); }
}
void shellsort(inttype_t *p,uintptr_t value,size_t width)
{
	size_t i,j; inttype_t n;
	for(i = value;i < width;i += value){
		n = p[i];
		if(p[i - value] > n){
			for(j = i;j > 0 && p[j - value] > n;j -= value){
				p[j] = p[j - value];
			}
			p[j] = n;
		}
	}
}
void mergesort(inttype_t *p,uintptr_t value,size_t width)
{
	size_t i,j,k,wi,wj; inttype_t *t = (inttype_t *)value;
	for(i = 0;i < width;i++){ t[i] = p[i]; }
	wi = width / 2; wj = width;
	for(i = k = 0,j = wi;i < wi && j < wj;k++){
		p[k] = t[i] < t[j] ? t[i++] : t[j++];
	}
	for(;i < wi;i++,k++){ p[k] = t[i]; }
	for(;j < wj;j++,k++){ p[k] = t[j]; }
}
int main(void)
{
	CThreadPool pool(4);
	LARGE_INTEGER liBegin,liEnd,liFreq; inttype_t *a,*b,*c;
	size_t intervals[256]; size_t i,j,interval; size_t len = 8192 * 8192;
	srandMT(0);
	a = new inttype_t[len]; b = new inttype_t[len]; c = new inttype_t[len];
	for(i = 0;i < len;i++){ a[i] = randMT(); }
	QueryPerformanceFrequency(&liFreq); g_lpPool =
	memcpy(b,a,sizeof(inttype_t) * len);
	QueryPerformanceCounter(&liBegin);
	std::sort(b,b + len);
	QueryPerformanceCounter(&liEnd);
	printf("STL Sort: %lld (%5.2f sec)\n",liEnd.QuadPart - liBegin.QuadPart,(double)(liEnd.QuadPart - liBegin.QuadPart) / (double)liFreq.QuadPart);
	memcpy(b,a,sizeof(inttype_t) * len);
	QueryPerformanceCounter(&liBegin);
	quicksort(b,0,len);
	g_lpPool->Wait(INFINITE);
	QueryPerformanceCounter(&liEnd);
	printf("QuickSort(%d): %lld (%5.2f sec)\n",g_nWidth,liEnd.QuadPart - liBegin.QuadPart,(double)(liEnd.QuadPart - liBegin.QuadPart) / (double)liFreq.QuadPart);
	memcpy(b,a,sizeof(inttype_t) * len);
	QueryPerformanceCounter(&liBegin);
	for(intervals[0] = 1,i = 0;intervals[i] < len;i++){ intervals[i + 1] = 3 * intervals[i] + 1; }
	for(i--;i > 0;i--){
		interval = intervals[i];
		if(len / interval < 8192){
			for(j = 0;j < interval;j++){
				shellsort(b + j,interval,len - j);
			}
		}
		else{
			for(j = 0;j < interval;j++){
				pool.AddTask(shellsort,b + j,interval,len - j);
			}
			pool.Wait(INFINITE);
		}
	}
	insertsort(b,0,len);
	QueryPerformanceCounter(&liEnd);
	printf("ShellSort: %lld (%5.2f sec)\n",liEnd.QuadPart - liBegin.QuadPart,(double)(liEnd.QuadPart - liBegin.QuadPart) / (double)liFreq.QuadPart);
	memcpy(b,a,sizeof(inttype_t) * len);
	QueryPerformanceCounter(&liBegin);
	for(i = 0;i < len;i += MERGESORT_USEINSERT){ insertsort(b + i,0,MERGESORT_USEINSERT); }
	for(j = MERGESORT_USEINSERT * 2;j <= len;j *= 2){
		if(j < 4096){
			for(i = 0;i < len;i += j){
				mergesort(b + i,(uintptr_t)(c + i),j);
			}
		}
		else{
			for(i = 0;i < len;i += j){
				pool.AddTask(mergesort,b + i,(uintptr_t)(c + i),j);
			}
			pool.Wait(INFINITE);
		}
		QueryPerformanceCounter(&liEnd);
		printf("MergeSort(%d): %lld (%5.2f sec)\n",g_nWidth,liEnd.QuadPart - liBegin.QuadPart,(double)(liEnd.QuadPart - liBegin.QuadPart) / (double)liFreq.QuadPart);
	}
	delete[] a; delete[] b; delete[] c;
	return 0;
}

関連する記事

  1. 実行時間を調べる処理 (2) C++で拡張を
  2. 実行時間を調べる処理 (1) 方法を見てみる
  3. ハッシュ取得処理の速度を調べてみた
  4. CUDAで遊んでみる
  5. QueryPerformanceCounterをもうちょっと検証してみよう

コメントを残す

メールアドレスが公開されることはありません。 ※ が付いている欄は必須項目です

この記事のトラックバック用URL