— boreal-kiss.com

Archive
Tag "GCD"

イントロダクション

Grand Central Dispatch (GCD)にはforループをマシンのコア数に応じて並列処理してくれる便利な関数 dispatch_apply(size_t, dispatch_queue_t, void) が存在する。

void dispatch_apply(
	size_t iterations,
	dispatch_queue_t queue,
	void (^block)(size_t));

引数は前から順番に、forループのイテレーション回数、タスク送信先のキュー、各イテレーションで行われるタスク、である。この関数はforループの各イテレーションごとにキューにタスクを送っている。したがって、もしタスクの処理時間がキューにタスクを送信するためにかかる時間(オーバーヘッド)より小さくなるような場合には注意が必要となる。普通にforループをまわす時よりも処理が遅くなる可能性があるからだ。具体例を見てみよう。

実行環境

Mac OS X 2.4 GHz Intel Core 2 Duo (CPU2個)

forループ vs. GCD その1

以下のような「何もしない」blockをforループでまわして処理にかかった時間を計測してみる。

void (^block)(int i) = ^(int i){
 
};

比較するのは普通のforループ処理を行う関数 loop_normal(int, void)

static void loop_normal(int count, void (^block)(int)){
	for (int i=0; i<count; i++){
		block(i);
	}
}

とGCDを用いた場合の関数 loop_normal_gcd(int, void) である。

static void loop_normal_gcd(int count, void (^block)(int)){
	void (^block_gcd)(size_t i) = ^(size_t i){
		block(i);
	};
 
	dispatch_queue_t queue 
		= dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0);
	dispatch_apply(count, queue, block_gcd);
}

比較した結果が下図になる(横軸はイテレーション回数、縦軸が関数の処理にかかった時間)。これを見るとGCDを用いた場合の方が(格段に)遅くなっていることがわかるだろう。この原因は「何もしない」タスクを完了するための時間に比べてキュー送信のオーバーヘッドが大きいことによる。

for loop vs GCD

それではこのオーバーヘッドが無視できるような構造にするにはどうすればよいだろうか。ひとつの方法はループにストライドを導入することである。

ストライドの導入

この方式はストライドで定義される整数値分の回数のイテレーションを一回のイテレーションに押し込んでしまう方法だ。これによりforループのイテレーション回数が減り、かわりに一回のイテレーションにおけるタスク量を増やすことができる。具体的に見てみよう。まず普通のforループを行う関数 loop_normal(int, void) がある。これはcount回のイテレーションを行う。

static void loop_normal(int count, void (^block)(int)){
	for (int i=0; i<count; i++){
		block(i);
	}
}

次に上記関数と全く同じ処理を行う関数が以下の loop_stride(int, int, void) である。ただし整数 stride (stride < count) を導入することで関数内部のループ回数が (count / stride) になっていることに注目してもらいたい。イテレーション回数が減った分イテレーション一回のタスク量が増えていることもわかるだろう。

static void loop_stride(int count, int stride, void (^block)(int)){
	int iMax = count / stride;
	int remainder = count % stride;
 
	void (^block_stride)(int i) = ^(int i){
		int j = i * stride;
		int jMax = j + stride;
 
		if (i == iMax - 1){
			jMax += remainder;
		}
 
		while (j < jMax) {
			block(j);
			j++;
		}
	};
 
	for (int i=0; i<iMax; i++){
		block_stride(i);
	}
}

ストライドを導入すればイテレーションの一回のタスク量を増やせることがわかった。それでは実際にGCDに放り込んで結果を見てみよう。

forループ vs. GCD その2

比較したのは普通のforループを行う関数 loop_normal(int, void)

static void loop_normal(int count, void (^block)(int)){
	for (int i=0; i<count; i++){
		block(i);
	}
}

とストライドを導入して一回のタスク量を増やした関数 loop_stride_gcd(int, int, void) である。

static void loop_stride_gcd(int count, int stride, void (^block)(int)){
	int iMax = count / stride;
	int remainder = count % stride;
 
	void (^block_gcd)(size_t i) = ^(size_t i){
		int j = i * stride;
		int jMax = j + stride;
 
		if (i == iMax - 1){
			jMax += remainder;
		}
 
		while (j < jMax) {
			block(j);
			j++;
		}
	};
 
	dispatch_queue_t queue 
		= dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0);
	dispatch_apply(iMax, queue, block_gcd);
}

そして両者の引数に「何もしない」blockを渡し実行時間を比較した。

void (^block)(int i) = ^(int i){
 
};

ここではイテレーションの回数は100,000回に固定し、ストライドの値を変化させて両者を比較した。結果は以下の図になる(横軸はストライドの値、縦軸は関数の処理にかかった時間)。ストライドの値が大きい場合はGCDを用いた場合の方が処理が早くなっていることがわかる。これらはつまりキューにタスクを送る際のオーバーヘッドが全体として無視できる程度になっていることを意味する。

for loop vs GCD (stride)

まとめ

GCDの恩恵を受けるためにはタスクは適度に重い(処理に時間がかかる)ものである必要があることがわかった。タスクが軽すぎる場合、GCDを利用することでかえって普通のforループよりも処理が遅くなる場合がある。これはGCDのオーバーヘッドによる。このような場合にはforループにストライドを導入することでイテレーション回数を減らし一回のタスクを重くすることで解決できる。

Read More

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秒以上になっているものがあるのはループを行う際のオーバーヘッドの累積によるもの。 []
Read More