1

ファイル内の一連の long の中から最小値と最大値を見つけるアルゴリズムを実装しようとしています。テスト ファイルには 10 億の long が含まれています。

アルゴリズムは期待どおりに機能しますが、単純なバージョンよりも高速には実行されません。単純なバージョンでは約 2n 回の比較が実行されるのに対し、このバージョンでは 3n/2 回の比較が実行されるため、大幅に高速になるはずです。

$ time ./findminmax_naive somelongs 
count: 1000000000
min: 0
max: 2147483647

real    0m24.156s
user    0m4.956s
sys     0m3.896s

$ time ./findminmax_faster somelongs 
count: 1000000000
min: 0
max: 2147483647

real    0m25.048s
user    0m6.948s
sys     0m3.980s

「素朴な」バージョンは次のとおりです。

#include <alloca.h>
#include <stdio.h>
#include <stdlib.h>

int
main(int ac, char *av[])
{
        FILE *f;
        long count, readcount, i, min, max;
        size_t rlen;
        long *n;

        if (ac != 2 && ac != 3) {
                fprintf(stderr, "Usage: %s <file> [readcount]\n", av[0]);
                exit(1);
        }

        f = fopen(av[1], "r");
        if (f == NULL)
            perror("fopen");
        readcount = 1024;
        if (ac == 3)
            readcount = atol(av[2]);
        n = alloca(sizeof (long) * readcount);
        rlen = fread(n, sizeof (*n), 1, f);
        min = max = n[0];
        count = 1;
        while (1) {
                rlen = fread(n, sizeof (*n), readcount, f);
                for (i = 0; i < (long)rlen; i++) {
                        count++;
                        if (n[i] < min)
                            min = n[i];
                        if (n[i] > max)
                            max = n[i];
                }
                if (feof(f))
                        break;
        }
        printf("count: %ld\n", count);
        printf("min: %ld\n", min);
        printf("max: %ld\n", max);
        exit(0);
}

（はずの）「高速」バージョンのコードは次のとおりです。

#include <alloca.h>
#include <stdio.h>
#include <stdlib.h>

int
main(int ac, char *av[])
{
        FILE *f;
        long count, readcount, i, min, max;
        size_t rlen;
        long *n;

        if (ac != 2 && ac != 3) {
                fprintf(stderr, "Usage: %s <file> [readcount]\n", av[0]);
                exit(1);
        }

        f = fopen(av[1], "r");
        if (f == NULL)
                perror("fopen");
        readcount = 1024;
        if (ac == 3)
                readcount = atol(av[2]);
        readcount = (readcount + 1) & (-1 << 1);
        n = alloca(sizeof (long) * readcount);
        rlen = fread(n, sizeof (*n), 1, f);
        min = max = n[0];
        count = 1;
        while (1) {
                rlen = fread(n, sizeof (*n), readcount, f);
                for (i = 0; i < (long)rlen; i += 2) {
                        count += 2;
                        if (n[i] < n[i + 1]) {
                                if (n[i] < min)
                                        min = n[i];
                                if (n[i + 1] > max)
                                        max = n[i + 1];
                        } else {
                                if (n[i + 1] < min)
                                        min = n[i + 1];
                                if (n[i] > max)
                                        max = n[i];
                        }
                }
                if (feof(f))
                        break;
        }
        if (rlen % 2) {
                if (n[rlen - 1] < min)
                        min = n[rlen - 1];
                if (n[rlen - 1] > max)
                        max = n[rlen - 1];
                count++;
        }
        printf("count: %ld\n", count);
        printf("min: %ld\n", min);
        printf("max: %ld\n", max);
        exit(0);
}

私が何を見逃したか分かりますか？

ご協力いただきありがとうございます。

-- ジェレミー

4

4 に答える 4

0

最初に、すべての質問に 1 つの回答でお答えすることをお許しください。私はこれをstackoverflow.comで行うべきではないことを知っていますが、さまざまな主題が多かれ少なかれ絡み合っていることを考えると、その方が簡単です.

序章

したがって、アルゴリズムをテストするために現在使用しているコードは次のとおりです。以前のバージョンとの違い:

  • コマンドライン引数で選択した両方のバージョンが含まれます。
  • @chr、@Dukeling: システムコールまたはライブラリ呼び出しを防ぐために、ファイルを mmap(2) します。
  • @chr、@Dukeling: 選択したアルゴリズムを実行する前に、すべてのページをメモリにフォールトさせるオプションの「ウォームアップ」オプションがあります。
  • @Dukeling: プログラムは、gettimeofday(2) を使用して、アルゴリズム自体にかかった時間を記録します。

コードは次のとおりです。

#include <sys/mman.h>
#include <sys/time.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

#define ROUNDUP(x, y)   ((((x) + ((y) - 1)) / (y)) * (y))
#define USCARRY(x)      ((x) < 0 ? (x) + 1000000 : (x))

int
main(int ac, char *av[])
{
        struct stat st;
        struct timeval start, end;
        long count, min, max, pgsiz;
        long *n, *p, *endp;
        int fd, warmup;

        if (ac != 3 && ac != 4) {


              fprintf(stderr, "Usage: %s <\"trivial\"|\"faster\"> "
                    "<file> [warmup]\n", av[0]);
                exit(1);
        }

        fd = open(av[2], O_RDONLY);
        if (fd == -1)
                perror("open");
        fstat(fd, &st);
        pgsiz = sysconf(_SC_PAGESIZE);
        n = mmap(NULL, ROUNDUP(st.st_size, pgsiz), PROT_READ,
            MAP_SHARED, fd, 0);
        if (n == MAP_FAILED)
                perror("mmap");
        warmup = 0;
        if (ac == 4)
                warmup = atoi(av[3]);
        // warm up the filesystem cache
        count = st.st_size / sizeof (*n);
        endp = &n[count - 1];
        //printf("%zu\n", sizeof (*p));
        //printf("%zu\n", sizeof (count));
        //exit(0);
        if (warmup) {
                for (p = n; p <= endp; p++) {
                        fwrite(p, sizeof (*p), 1, stdout);
                        min = *p;
                }
        }
        // start algorithm
        gettimeofday(&start, NULL);
        if (!strcmp(av[1], "trivial")) {
                min = max = n[0];
                p = &n[1];
                while (p <= endp) {                     // c1 * n
                        if (p[0] < min)                 // c2 * n
                                min = p[0];             // c3 * x
                        if (p[0] > max)                 // c2 * n
                                max = p[0];             // c3 * y
                        p++;                            // c4 * n
                }                       
        } else if (!strcmp(av[1], "faster")) {
                min = max = n[0];
                p = &n[1];
                while (p < endp) {                      // c1 * n/2
                        if (p[0] < p[1]) {              // c2 * n/2
                                if (p[0] < min)         // c2 * n/4
                                        min = p[0];     // c3 * x/2
                                if (p[1] > max)         // c2 * n/4
                                        max = p[1];     // c3 * y/2
                        } else {
                                if (p[1] < min)         // c2 * n/4
                                        min = p[1];     // c3 * x/2
                                if (p[0] > max)         // c2 * n/4
                                        max = p[0];     // c3 * y/2
                        }
                        p += 2;                         // c5 * n
                }                                       
                if (p == endp) {
                        if (*endp < min)
                                min = *endp;
                        else if (*endp > max)
                                max = *endp;
                }
        } else {
                printf("sorry\n");
                exit(1);
        }
        gettimeofday(&end, NULL);
        printf("time: %ld.%ld\n", end.tv_sec - start.tv_sec,
            USCARRY(end.tv_usec - start.tv_usec));
        printf("count: %ld\n", count);
        printf("min: %ld\n", min);
        printf("max: %ld\n", max);
        exit(0);
}

テストケース

テストケースに使用するファイルは次のとおりです。

$ ls -l _*
-rw-r--r-- 1 jlh jlh 2400000000 May 27 23:37 _bestcase
-rw-r--r-- 1 jlh jlh 2400000000 May 27 08:40 _random
-rw-r--r-- 1 jlh jlh 2400000000 May 27 23:38 _worstcase

$ od -N 64 -t dL _bestcase 
0000000                    0            300000000
0000020                    1            299999999
0000040                    2            299999998
0000060                    3            299999997
0000100

$ od -N 64 -t dL _random
0000000  8600270969454287374  8436406000964321037
0000020  7348498334162074664  2050332610730417325
0000040  8183771519386464726  4134520779774161130
0000060  2045475555785071180  2859007060406233926
0000100

$ od -N 64 -t dL _worstcase 
0000000            150000000            150000000
0000020            149999999            150000001
0000040            149999998            150000002
0000060            149999997            150000003
0000100

I/O ペナルティ

わかりました、最初にキャッシュをウォームアップして、結果を台無しにする可能性のある欠落ページがないことを確認しましょう:

$ ./findminmax trivial _random 
time: 3.543573
count: 300000000
min: 31499144704
max: 9223372004409096866

$ ./findminmax trivial _random 
time: 1.466323
count: 300000000
min: 31499144704
max: 9223372004409096866

$ perf stat -e  minor-faults,major-faults ./findminmax trivial _random 
time: 1.284729
count: 300000000
min: 31499144704
max: 9223372004409096866

 Performance counter stats for './findminmax trivial _random':

           586,066 minor-faults                                                
                 0 major-faults                                                

       1.350118552 seconds time elapsed

ご覧のとおり、主要なページ フォールトはありませんでした。今後は、I/O への影響がないことを当然のことと見なすことができます。2.命令数

命令数と分岐ミス

@H2CO3、@vvy、他の命令も同様にカウントされるという事実については、あなたは絶対に正しいです（ここでは、各操作が同じ数のCPUサイクルを必要とし、CPUキャッシュミスが発生すると考えます）。これまでに読んだアルゴリズムに関する文献が比較の数だけに焦点を当てている理由がわかりません (まあ、あまり読んだことがないことは認めますが ;))。

ループの各ステップについて、私なりの平均的なケース (ここでは最悪のケースは面白くないと思います) を考慮してコメントしましたが、これはあなたのものとは少し異なります。

私が間違っていなければ: - 簡単なバージョンの場合: n * (c1 + 2*c2 + c4) + (x + y) * c3 - 高速バージョンの場合: n/2 * (c1 + 3*c2 + c5 ) + (x + y) * c3

私の理解では、CPU ごとに異なるため、各 cN にかかる CPU サイクルの量を推測することは困難です。

ウォーム キャッシュを使用して、各アルゴリズムが各テスト ケースで実行されている間に、ほとんどアイドル状態のコンピューターで発生した命令、分岐、および分岐ミスの数を確認してみましょう (重大な偏差がないことを確認するために各ケースを 3 回テストしたことに注意してください) :

ランダムケース

$ perf stat -e branches,branch-miss,instructions ./findminmax_stackoverflow trivial _random
time: 1.547087
count: 300000000
min: 31499144704
max: 9223372004409096866

 Performance counter stats for './findminmax_stackoverflow trivial _random':

     1,083,101,126 branches                                                    
            52,388 branch-miss

     4,335,175,257 instructions              #    0.00  insns per cycle        

       1.623851849 seconds time elapsed


$ perf stat -e branches,branch-miss,instructions ./findminmax_stackoverflow faster _random
time: 2.748967
count: 300000000
min: 31499144704
max: 9223372004409096866

 Performance counter stats for './findminmax_stackoverflow faster _random':

       783,120,927 branches                                                    
        75,063,008 branch-miss

     3,735,286,264 instructions              #    0.00  insns per cycle        

       1.824884443 seconds time elapsed

より高速なバージョンでは命令が少ないことに注意してください。ただし、実行に時間がかかることに注意してください。おそらく、分岐ミスが桁違いに多いため、終了してください!

最良の場合

$ perf stat -e branches,branch-miss,instructions ./findminmax_stackoverflow trivial _bestcase 
time: 1.267697
count: 300000000
min: 0
max: 300000000

 Performance counter stats for './findminmax_stackoverflow trivial _bestcase':

     1,082,801,759 branches                                                    
            49,802 branch-miss

     4,334,200,448 instructions              #    0.00  insns per cycle        

       1.343425753 seconds time elapsed


$ perf stat -e branches,branch-miss,instructions ./findminmax_stackoverflow faster _bestcase 
time: 0.957440
count: 300000000
min: 0
max: 300000000

 Performance counter stats for './findminmax_stackoverflow faster _bestcase':

       782,844,232 branches                                                    
            49,768 branch-miss

     3,734,103,167 instructions              #    0.00  insns per cycle        

       1.035189822 seconds time elapsed

最悪の場合

$ perf stat -e branches,branch-miss,instructions ./findminmax_stackoverflow trivial _worstcase 
time: 7.860047
count: 300000000
min: 1
max: 299999999

 Performance counter stats for './findminmax_stackoverflow trivial _worstcase':

     1,490,947,270 branches                                                    
         2,127,876 branch-miss

     7,159,600,607 instructions              #    0.00  insns per cycle        

       6.916856158 seconds time elapsed


$ perf stat -e branches,branch-miss,instructions ./findminmax_stackoverflow faster _worstcase 
time: 7.616476
count: 300000000
min: 1
max: 299999999

 Performance counter stats for './findminmax_stackoverflow faster _worstcase':

     1,196,744,455 branches                                                    
         2,024,250 branch-miss

     6,594,182,002 instructions              #    0.00  insns per cycle        

       6.675068846 seconds time elapsed

したがって、非常に興味深いことに、「ランダムな」ケースは実際には最悪のケースよりも高速であり、大きな違いはありません。私が見る唯一の違いは、私の最悪のケースには「小さな」数字 (32 ビットでエンコードできる) が含まれているのに対し、ランダムなケースには真の 64 ビットの数字が含まれていることです。

「小さい」整数のランダムなケース

それでは、「小さな」乱数のセットを試してみましょう (まだエンコードされて 64 ビットに格納されています)。

$ od -N 64 -t dL _randomsmall 
0000000           1418331637           2076047555
0000020             22077878           1677970822
0000040           1845481621            609558726
0000060           1668260452            335112094
0000100

$ perf stat -e branches,branch-miss,instructions ./findminmax_stackoverflow trivial _randomsmall 
time: 7.682443
count: 300000000
min: 9
max: 2147483647

 Performance counter stats for './findminmax_stackoverflow trivial _randomsmall':

     1,481,062,942 branches                                                    
         2,564,853 branch-miss

     6,223,311,378 instructions              #    0.00  insns per cycle        

       6.739897078 seconds time elapsed


$ perf stat -e branches,branch-miss,instructions ./findminmax_stackoverflow faster _randomsmall 
time: 7.772994
count: 300000000
min: 9
max: 2147483647

 Performance counter stats for './findminmax_stackoverflow faster _randomsmall':

     1,177,042,675 branches                                                    
        77,686,346 branch-miss

     5,607,194,799 instructions              #    0.00  insns per cycle        

       6.834074812 seconds time elapsed

したがって、私が推測したように、小さな数は実際には大きな数よりも処理が遅くなります。たとえそれらがすべて 64 ビット ワードで構成されていたとしてもです。おそらくCPU設計者だけが知ることができる理由から、「小さな」数の分岐ミスがはるかに多くあります:-)。

もう 1 つの注目すべき点は、多くの場合、perf(1) によって測定される経過時間が、プログラム自体によって測定される経過時間よりも小さいことです。これは、プログラム自体がリアルタイムを使用するのに対し、perf(1) はプロセス時間 (プロセスが実際に実行される時間) を使用するという事実によって説明されると思います。getrusage(2) を使用しようとしましたが、ここに到達する時間が一致しません (たとえば、ユーザー時間として 1.6 秒、システム時間として 1.4 秒を取得しますが、perf(1) は 6.8 秒を測定します)。

結論

  • 実行時間に関しては、2 つのアルゴリズムに実質的な大きな違いはありませんが、些細な方のキャッシュ ミスは「高速な」アルゴリズムよりも (桁違いに) はるかに少ないですが、これは命令の量の増加によってバランスが取れているようです ( 10-20%);
  • より具体的には、このキャッシュ ミスの違いは、ランダムなケースでのみ見られます。最良のケースと最悪のケースは、両方のアルゴリズムで同じ量のキャッシュ ミスにつながるため、この点に関して縮退しているように見えます。したがって、これらの場合、「より高速な」アルゴリズムは、単純なアルゴリズムよりもわずかに高速です。「一般的な」ランダムなケースでは、自明なアルゴリズムの方が少し高速です。
  • 整数が小さいと、CPU ではるかに多くのキャッシュ ミスが発生します。
  • 最悪のケースと、int が小さいランダムなテスト ケースとの間に実際の違いはありません。

それで、あなたがそこまで来たら、ありがとう:)。申し訳ありませんが、このすべての実験はあいまいな結論にしかつながりませんでした。うまくいけば、賢明な読者がこれに光を当てるでしょう:)。

-- ジェレミー

于 2013-05-29T22:12:35.173 に答える