Q&A
システムやCPUが不明ですが、今時のCPUなら隣接データはキャッシュに乗るので処理が早い可能性が有ります。
前提
C言語でバブルソートの評価を行いました。
ランダムなデータと降順のデータ(データ数2500,10000,40000)を昇順にソートして、実行時間・交換回数を計測しました。
結果は以下の通り。
| 実行時間(ms) | 2500 | 10000 | 40000 |
|---|---|---|---|
| ランダム | 8.09 | 203.91 | 3928.74 |
| 降順 | 8.29 | 113.65 | 1832.24 |
| 交換回数(回) | 2500 | 10000 | 40000 |
|---|---|---|---|
| ランダム | 1545023 | 24960941 | 398801402 |
| 降順 | 3123750 | 49995000 | 799980000 |
[追記]
データはint型の整数で、テキストデータからint型配列へ読み出しています。
また実行時間はソートの開始から終了までを図っています。
問題
降順の方が実行時間が短くすんでいる理由が分かりません。
交換回数を見る限り、降順の方が時間がかかりそうなものですが…。
ご教授願えればと思います。
c
1#include <stdio.h> 2#include <stdlib.h> 3#include <string.h> 4#include <sys/time.h> 5#include "data.h" 6 7int swap_counter=0; 8int comparison_counter=0; 9 10/* 要素の交換 */ 11void swap(int *a, int i, int j) { 12 int t = a[i]; 13 a[i] = a[j]; 14 a[j] = t; 15#if defined(VERBOSE_MODE) || defined(COUNT_SWAP) 16 swap_counter++; 17#endif 18} 19 20/* バブルソート */ 21void bubblesort(int *a, int size) { 22 int i, j; 23 for(i=size-1; i>0; i--) { 24 for(j=0; j<i; j++) { 25#if defined(VERBOSE_MODE) || defined(COUNT_COMPARISON) 26 comparison_counter++; 27#endif 28 if (a[j]>a[j+1]) { 29 swap(a, j, j+1); 30 } 31 } 32 } 33} 34 35/* 時間計測 */ 36double get_time() { 37 struct timeval tv; 38 gettimeofday(&tv, NULL); 39 return tv.tv_sec + (double)tv.tv_usec*1e-6; 40} 41 42/* 使用法の表示 */ 43void print_usage() { 44 fprintf(stderr, "usage: bubblesort data\n"); 45} 46 47 48int main(int argc, char* argv[]) { 49 if (argc != 2) { 50 print_usage(); 51 exit(1); 52 } 53 54 FILE *fp = fopen(argv[1], "r"); 55 if (fp == NULL) { 56 fprintf(stderr, "File not found %s\n", argv[1]); 57 exit(1); 58 } 59 int size = read_size(fp); 60 int* data = read_data(fp, size); 61 fclose(fp); 62 63#ifdef VERBOSE_MODE 64 printf("ソート前\n"); 65 print_data(data, size); 66#endif 67 68 double starting_time = get_time(); 69 bubblesort(data, size); // ソート 70 double end_time = get_time(); 71 double consumed_time_in_msec = (end_time-starting_time) * 1000; 72 73#ifdef VERBOSE_MODE 74 printf("\nソート後\n"); 75 print_data(data, size); 76#endif 77 78#ifdef VERBOSE_MODE 79 printf("size: %d\n", size); 80 printf("swap: %d\n", swap_counter); 81 printf("comparison: %d\n", comparison_counter); 82 printf("time (msec): %f\n", consumed_time_in_msec); 83#else 84 85#ifdef COUNT_SWAP 86 printf("%d", swap_counter); 87#endif 88#ifdef COUNT_COMPARISON 89 printf("%d", comparison_counter); 90#endif 91#if !defined(COUNT_SWAP) && !defined(COUNT_COMPARISON) 92 printf("%f", consumed_time_in_msec); 93#endif 94 95#endif 96 97 free_data(data); 98} 99
ソースを提示してください。
隣接データがキャッシュに乗る
->比較の際に片方を取りに行くだけでもう一方もついてくる
->常に隣同士を比較する降順の方が速い
ということでしょうか。
ソースを提示してください。
もしかして焼きそばソースか何かのことだと思っていますか？
すみません、いまお湯ないんです…。
最近のCPUのキャッシュ構造は分からない（CPUのマニュアルがないｗ）のですが、キャッシュ・ラインというのは通常８〜１６ワード（ワードはレジスタのビット長）あって、それを一気に読み込みます。従って、１ワード読むと後続（実際は８バイトとか切りの良いアドレスからフィッチします）データもキャッシュに読み込まれます。従って、隣接データをアクセスする時は、ウエイトのかかるメモリをアクセスしないので（データの読み込みの）処理速度が上がります。
なんだ荒らしか。
cateyeさん、腑に落ちました。ありがとうございました。
ソース、明日載せますねー。
まぁ、キャシュだけではない気もしますが・・・（別の問題だったりしますから）Zuishinの仰るようにソースを提示されれば、解決の糸口に成るかもです・・・
#バブルソートは少ないデータでしか使ったことがない・・・構造体で２０〜３０ぐらいか＾＾；
「比較回数」ってどうやって見ているんですか？
単純に要素同士を大小比較した回数のことを言うのであれば、バブルソートのアルゴリズムでは、元のデータの並びによって比較回数が変化することはありえないと思うのですが…
交換回数の間違いでした。
直しておきました。
表のほうが直っていません
ごもっともでした。
cateyeさんの
「最近のCPUのキャッシュ構造は分からない（CPUのマニュアルがないｗ）のですが、キャッシュ・ラインというのは通常８〜１６ワード（ワードはレジスタのビット長）あって、それを一気に読み込みます。従って、１ワード読むと後続（実際は８バイトとか切りの良いアドレスからフィッチします）データもキャッシュに読み込まれます。従って、隣接データをアクセスする時は、ウエイトのかかるメモリをアクセスしないので（データの読み込みの）処理速度が上がります。」
という理由で納得できたので締めます。
解答くださった方々ありがとうございました。
回答2件
0
ベストアンサー
現代のCPUにとって失速の原因はパイプラインストールと呼ばれる分岐予測のミスマッチです。
c
1void bubblesort(int *a, int size) { 2 int i, j; 3 for(i=size-1; i>0; i--) { 4 for(j=0; j<i; j++) { 5#if defined(VERBOSE_MODE) || defined(COUNT_COMPARISON) 6 comparison_counter++; 7#endif 8 if (a[j]>a[j+1]) { 9 swap(a, j, j+1); 10 } 11 } 12 } 13}
この中で分岐はif(){swap(a,j,j+1);}の部分です。
降順の場合、ここは常に分岐するのでパイプラインストールが発生しません。
c
1swap(a, j, a[j]>a[j+1] ? j+1 : j);
と、分岐させない事で同等ないしはランダムのほうが高速化される可能性があるかと思います。
投稿2019/10/21 05:40
総合スコア15149
forも分岐じゃない？とか結局分岐してるのでは？とか面倒くさいけど
- 前回の分岐履歴をもとに予測している
- 条件jmp + call は分岐予測をミスったときのコストがでかい
ようなCPUを使うと起きる現象な気がします
解答ありがとうございます。
swapを3項のに換えた結果、
データ40000について：
ランダムデータの実行時間が3129.6(ms)に縮みました。
一方降順データの実行時間は3211.5(ms)に伸びました。
交換回数は共に799980000回です。
どうも降順データが早かった理由ではないようです…。
> 同等ないしはランダムのほうが高速化
という予想から外れてませんし想像の範疇です。
swapを呼ぶ・呼ばないの予測を行わない事で、有意に縮みました。
降順データが遅くなる件は詳しいところは分かりませんが2,3ほど予想はできます。
1. ループ内の命令列が複雑化することで長くなってCPUのループ最適化が死んだ
2. 今回使った方法では条件分岐を排除しきれていない
3. 引数が変更される可能性を入れたことで、関数のインライン展開に悪影響を及ぼした。
4. コンパイラが生成する機械語がCPUに対して最適ではない
なるほど…ありがとうございます。
それぞれについて調べてみます。
0
「キャッシュ・ラインというのは通常８〜１６ワード（ワードはレジスタのビット長）あって、それを一気に読み込みます。従って、１ワード読むと後続（実際は８バイトとか切りの良いアドレスからフィッチします）データもキャッシュに読み込まれます。従って、隣接データをアクセスする時は、ウエイトのかかるメモリをアクセスしないので（データの読み込みの）処理速度が上がります」ため。
投稿2019/10/21 02:45
総合スコア11
バブルソートなので配列ならランダムでも降順でも隣接データになると思います。可能性の話だけで、何の検証もされていません。
おh…ホントですね…。
ソース載せますorz
あなたの回答
tips
プレビュー
