未ソートデータとソート済データをソートプログラムに入れた場合の、実行にかかる時間の比較

Question

解決したい疑問点

環境は、Windows7, eclipse を使っています。

一方向連結リストをソートするプログラムに、未ソートデータとソート済データを入力した場合について、プログラムの実行時間を比較したところ、未ソートデータのほうが時間がかかったのですが、なぜそうなるのかがわかりません。

下記ソースコードの概要は、
・gpa,credit,name の3要素から構成される生徒の成績データが、input.txtファイルに
....................
3.5 40 Taro
2.1 60 Hanako
.
.
....................
のような形で数万人分記録されていて、それを input 関数で構造体の連結リストに入力する。
・input.txtファイルとoutput.txtファイルの場所はコマンドライン引数で入力。
・gpa,credit,name のいずれでソートするかもコマンドライン引数で入力。今回は name でソート。
・ソートは昇順。最大値抽出法を使用。
・ソート部分の実行時間を知るため、sort 関数を clock 関数で囲んでいる。
・入力データには、バラバラの未ソートデータおよび、すでにソート済のデータの2つを使用し、比較する。

該当のソースコード

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

typedef struct school_record SRec;
struct school_record{
	float gpa;
	int credit;
	char name[200];
	SRec *next;
};

SRec* input(SRec* p, char* fname1);
void output(SRec* p, char* fname2);
int gpa_comp(const void* val1, const void* val2);
int credit_comp(const void* val1, const void* val2);
int name_comp(const void* val1, const void* val2);
SRec* listsort(SRec* header, int (*comp)(const void*, const void*));
SRec* sort(SRec* header, char* key);



int main(int argc, char *argv[])
{
	SRec* header = NULL, *Sheader;
	clock_t clk_start, clk_end;

	// コマンドライン引数チェック
	if(argc != 4){
		fputs("コマンドライン引数の数が間違っています.\n", stderr);
		exit(0);
	}
	if(strcmp(argv[1],"gpa") && strcmp(argv[1],"credit") && strcmp(argv[1],"name")){
		fputs("1つめのコマンドライン引数は, gpa, credit, name のいずれかにしてください.\n", stderr);
		exit(0);
	}

	header = input(header, argv[2]);

	clk_start = clock(); // sort関数の処理時間を計測
	Sheader = sort(header, argv[1]);
	clk_end = clock();

	output(Sheader, argv[3]);

	printf("%f", (double)(clk_end - clk_start) / CLOCKS_PER_SEC);

	return 0;
}




SRec* input(SRec* header, char* fname1)
{
	float gpa;
	int credit;
	char name[200];
	SRec *p;
	SRec **tail = &header;

	// ファイルのオープン
	FILE *fp;
	if ((fp = fopen(fname1, "r")) == NULL){
		fprintf(stderr, "%sのオープンに失敗しました.\n", fname1);
		exit(1);
	}

	// データをリストへコピー
	while( fscanf(fp, "%f%d%s", &gpa, &credit, name) != EOF){

		// 領域確保
		if( (p = (SRec*)malloc(sizeof(SRec)) ) == NULL){
			fprintf(stderr, "データ領域の確保に失敗しました.\n");
			exit(1);
		}
		// 一時変数からリストへ書き込み
		p->gpa = gpa;
		p->credit = credit;
		strcpy(p->name, name);
		p->next = NULL;

		// リストの末尾に要素を追加 (tail は header か next を指すポインタ)
		*tail = p;
		tail = &(p->next);
	}
	fclose(fp);
	return header;
}



void output(SRec* p, char* fname2)
{
	SRec* tmp;

	// ファイルのオープン
	FILE *fp;
	if ((fp = fopen(fname2, "w")) == NULL){
		fprintf(stderr, "%sのオープンに失敗しました.\n", fname2);
		exit(1);
	}
	// データの書き込み
	while( p != NULL ){
		fprintf(fp, "%.1f %3d %s\n", p->gpa, p->credit, p->name);
		tmp = p;
		p = p->next;
		free(tmp);
	}
	fclose(fp);
}






// gpa比較関数
int gpa_comp(const void* val1, const void* val2)
{
	return ( (*(SRec*)val1).gpa < (*(SRec*)val2).gpa ) ? -1 : ( (*(SRec*)val1).gpa == (*(SRec*)val2).gpa ) ? 0 : 1 ;
}

// credit比較関数
int credit_comp(const void* val1, const void* val2)
{
	return ( (*(SRec*)val1).credit < (*(SRec*)val2).credit ) ? -1 : ( (*(SRec*)val1).credit == (*(SRec*)val2).credit ) ? 0 : 1 ;
}

// name比較関数
int name_comp(const void* val1, const void* val2)
{
	return strcmp( (*(SRec*)val1).name, (*(SRec*)val2).name);
}



// ソートを行う関数
SRec* listsort(SRec* header, int (*comp)(const void*, const void*))
{
	SRec* Sheader = NULL, *q;
	SRec** p, **max;  //header か next を指すポインタ

	// 元リストが空になるまで以下を繰り返し
	while( header != NULL ){
		p = &header, max = &header;

		// 元リストの最大値を探す
		while( *p != NULL ){
			if( comp(*max, *p) < 0 ){
				max = p;
			}
			p = &( (*p)->next );
		}
		// 元リストの最大値を削除して、新リストの先頭に挿入
		q = Sheader;
		Sheader = *max;
		*max = (*max)->next;  // 削除完了
		Sheader->next = q;    // 挿入完了
	}
	return Sheader;
}


// keyに対応する比較関数をlistsort関数へ振り分ける
SRec* sort(SRec* header, char* key)
{
	SRec* Sheader = NULL;

	if(strcmp(key, "gpa") == 0){
		Sheader = listsort(header, gpa_comp);
	}
	if(strcmp(key, "credit") == 0){
		Sheader = listsort(header, credit_comp);
	}
	if(strcmp(key, "name") == 0){
		Sheader = listsort(header, name_comp);
	}

	return Sheader;
}

結果

　　　　 入力データ
データ数　　 未ソート ソート済
.............................................
10000個　　　0.70秒　　 0.76秒
20000個　　　3.02秒　　 2.91秒
40000個　　　13.58秒　　12.96秒
50000個　　　24.72秒　 21.22秒
60000個　　　41.66秒　 34.53秒
80000個　　　86.76秒 68.59秒
100000個　　 147.48秒　 111.96秒
..............................................

となりました。ソートは問題なく行われます。
データ数が多くなると、ソート済データのほうが実行時間がかなり早いです。

なぜなのか

listsort 関数内に関して、ループを回す回数は未ソートとソート済で変わらないはずです。未ソートとソート済で違うところがあるとすれば、それは

// 元リストの最大値を探す
        while( *p != NULL ){
            if( comp(*max, *p) < 0 ){
                max = p;
            }
            p = &( (*p)->next );
        }

のif文が、未ソートの場合は実行される時とされない時があり、ソート済の場合は毎回実行される、ということだと思います。
ですから、むしろソート済のほうが実行時間が長くなるはずだと思うのですが・・・

なぜ未ソートのほうが時間がかかるのか、教えてください。

Answer 1

結論から言うと、データの局所性の影響によるものだと考えられます。

まず、アセンブルリストを出力してどのようにコンパイルされたのかを確認したところ、比較部分でcmovsを使っていたので、ソート済みとソートなしとではまったく同じパスが実行される、つまり、その部分では速度に差が出ないということが判りました。

となると、考えられるのはデータの局所性の影響です。1要素のサイズが216バイト(64bit環境の場合)で、1万件だと2,160,000バイト、つまり、2MBちょっとということで、そこそこ大きいです。実際にはヒープの管理領域も含まれるのでそれよりも若干大きくなるでしょう。とはいえ、デスクトップ向けのCPUなら十分キャッシュに収まります。2万件だと4MB超。CPUのモデルによってはそろそろ収まりきれないかもしれません。4万件だと8MB超。ハイエンド向けのCPUでもキャッシュから溢れます。
キャッシュから溢れた場合は、次にそのデータを読むときはシステムメモリ(DRAM)から読み出すことになりますが、その際、プリフェッチという仕組みが働き、ある程度まとまったサイズの連続した領域を「先読み」します。先読みした領域はキャッシュに保存されるので、DRAMよりも遥かに高速に読み書きできます。

ここで「局所性」が効いてくるわけです。順番がバラバラだと、先読みした領域に次に使いたいデータが存在する確率は低いですが、順番が整っている(ソート済みの)データだと、次に使いたいデータが先読みした領域に存在する可能性は極めて高くなります。
キャッシュが有効に働くというわけです。

ソート済みのデータの方が実行時間が短いのは、そして、件数が多いほどより顕著に表れるのはそのためではないかと思われます。

Comments

[zazenbo]

初学者ゆえ知らないことだらけでしたが、わかりやすい説明のおかげで理解することができました。
他の方もわかりやすかったのですが、最も詳しい説明だったのでベストアンサーにさせて頂きます。

回答ありがとうございました！

Answer 2

コンパイラ・CPUの仕様によりますが
アセンブリ言語レベルですと
CPUの高速化(パイプライン)の都合で条件分岐の予測をCPUが間違えると遅くなります。

ループ内の条件分岐ですので、CPUが前回の分岐と同方向を予測するアルゴリズム
もしくは、常に分岐すると予測するアルゴリズムであった場合
ソート済みか否かで速度が変わる要因になります。

---

なんとなくですが、三項演算子を用いる事でcmov命令に最適化されそうな気がします。

max = comp(*max, *p) < 0 ? p : max;

Comments

[zazenbo]

CPUが効率的に処理してくれるから本来の時間計算量以上の性能が出たわけですね。

三項演算子は試してみましたが、結果は同じでした…。

回答ありがとうございました！

Answer 3

未検証なので自信はないのですが、「参照の局所性」とか呼ばれたりする現象ではないかと思います。
ソート済みの方がメモリアクセスする範囲が集中しますので、メモリのキャッシュが有効に働いて効率的になるからではないかと思います。

Comments

[zazenbo]

「参照の局所性」、知らなかったですが、たしかに影響していそうですね。

回答ありがとうございました！

Answer 4

ソート時と未ソート時ではcomp関数の実行時間が違うからでは

Comments

[zazenbo]

comp関数の実行時間、実質的には strcmp 関数の実行時間ということですかね？
未ソートとソート済で実行時間が変わる理由が思いつかないです…

[y_waiwai]

まあ、ソート済みであれば常に最小の文字比較で終わるけど、ソートされてなければ、（それに比べ）長い文字の比較となるってとこですな。
strcmp関数を自分で実装するとなるとどういうふうに組むか、を考えるとわかると思います

[zazenbo]

たとえば未ソートなら
taro と hanako
のような比較が多く、ソート済なら
tarao と taro
のような比較が多くなると思います。
strcmp関数では文字列の1文字目から順に大きさを比較し、大きさが違う文字があった時点でreturnするので、未ソートの taro と hanako では1文字目でreturn、ソート済の tarao と taro では4文字目でreturnとなると思います。ですからその意味でもやはり、未ソートのほうが早く終わるように思えてしまうのですが・・・