— boreal-kiss.com

Grand Central Dispatch: forループ処理を並列化する

Grand Central Dispatch

OSX 10.6から導入されたGrand Central Dispatch (GCD)は複数タスクを処理するための便利な仕組みのことで、これを使うとマルチコアの恩恵を簡単に受けることができる。複数同時処理といった仕組みとしてスレッドがあるが、GCDの場合(スレッドを作成する時・制御する時のような)面倒くさい手順を一切踏まなくてよくなる。さらにシステム側でCPUを適切に利用する工夫がされているので(CPU1個なら1個、2個なら2個、8個なら8個勝手に使ってくれる)実行環境を気にしなくてよい、という利点が挙げられる。詳細は以下のドキュメントが非常に参考になる。

さて今回、CPUが複数あるマシンでGCDの恩恵を受けているかどうかを簡単な計算で確認したので以下に結果を載せておく。GCDにはforループを簡単に並列化する仕組みがあるのでそれを利用した。なお計算を行ったマシンは2.4 GHz Intel Core 2 Duo。

forループの並列化

以下のようなforループがあるとする。

for (int i=0; i<count; i++){
	//Do some work.
}

ループ内のi回目の処理が他と独立したタスクである場合GCDのdispatch queueを用いて並列処理が可能になる。以下は上記forループと同じ仕事を行う。

//GCD way.
void (^block)(size_t i) = ^(size_t i){
	//Do some work.
};
 
dispatch_queue_t queue 
	= dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0);
dispatch_apply(count, queue, block);

ここで

void (^block)(size_t i)

はblockと呼ばれるApple独自のC言語の拡張である。これは簡単に言うと一連の作業をまとめてオブジェクト化したものであり1、GCDとは親密な関係にある。block自体も簡単で便利な仕組みなので、興味があるひとは以下のドキュメントを参考にしてほしい。

さて上記の場合、blockに記述された内容がforループ内の処理に相当し、これをGCDのdispatch_apply()の引数として渡してシステム側で処理してもらっている。記述が簡単な点にも注目してもらいたい。

計算結果

普通のforループとdispatch queueを用いた場合を比較したものを載せておく。forループ内の1回の処理時間(t_task)を横軸、ループ終了までにかかった時間を縦軸にとってある。ここでループの回数(count)はt_taskの値ごとに異なっており

t_task x count = 10 sec.

となるように設定してある。例えば図の一番左のバーの場合、ループ内の一回の処理時間を0.00001秒、ループの総数を1000000回としてある(全処理時間は0.00001 x 1000000 = 10秒)2。試行範囲に限って言えばdispatch queueを用いた方が2倍ほど早いことがわかる。2倍という数字はCPU2個使った並列化、ということだろう。設定によっては普通のforループの方が早くなるようなことがあるかと思われたがそのようなこともなかったので、並列化が可能であればGCDはどんどん使った方が良さそうだ。

確認用プログラム

上記計算に使用したプログラム。ループ内の処理時間の変更は指定時間スリープさせることで実現させてある。gettimeofday_sec()はマイクロ秒測定用の関数でC言語: 実行時間測定の方法より拝借した。

#import <Foundation/Foundation.h>
#include <sys/time.h>
 
double gettimeofday_sec();
static void test_normal_loop(int count, NSTimeInterval sleep);
static void test_dispatch_que(int count, NSTimeInterval sleep);
 
int main (int argc, const char * argv[]) {
    NSAutoreleasePool * pool = [[NSAutoreleasePool alloc] init];
 
	const NSTimeInterval TEN_SEC = 10.0;
 
	for (int count = 10; count < 1e7; count*=10){
		NSTimeInterval sleep = TEN_SEC / count;
		test_normal_loop(count, sleep);
		test_dispatch_que(count, sleep);
	}
 
    [pool drain];
    return 0;
}
 
double gettimeofday_sec(){
    struct timeval tv;
    gettimeofday(&tv, NULL);
    return tv.tv_sec + (double)tv.tv_usec*1e-6;
}
 
static void test_normal_loop(int count, NSTimeInterval sleep){
	double t1 = gettimeofday_sec();
 
	for (int i=0; i<count; i++){
		[NSThread sleepForTimeInterval:sleep];
	}
 
	double t2 = gettimeofday_sec();
 
	printf("%f\n", t2 - t1);
}
 
static void test_dispatch_que(int count, NSTimeInterval sleep){
	double t1 = gettimeofday_sec();
 
	void (^block)(size_t i) = ^(size_t i){
		[NSThread sleepForTimeInterval:sleep];
	};
 
	dispatch_queue_t queue 
		= dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0);
	dispatch_apply(count, queue, block);
 
	double t2 = gettimeofday_sec();
 
	printf("%f\n", t2 - t1);
}

Footnotes

  1. 仕組みとしてはNSInvocationに似ているがblockは特定のメソッドだけに固執しておらず、記述された内容をprocedualに実行できる []
  2. 縦軸のループ処理時間が10秒以上になっているものがあるのはループを行う際のオーバーヘッドの累積によるもの。 []
0 comments
Submit comment