5

C の最適化を学習するための演習として、Linux で可能な限り高速な crc32 実装を作成しようとしています。最善を尽くしましたが、オンラインで多くの優れたリソースを見つけることができませんでした。私のバッファサイズが適切かどうかさえわかりません。実験を繰り返して選ばれました。

#include <stdio.h>
#define BUFFSIZE 1048567

const unsigned long int lookupbase = 0xEDB88320;
unsigned long int crctable[256] = {
0x00000000, 0x77073096, 0xEE0E612C, 0x990951BA,
/* LONG LIST OF PRECALCULTED VALUES */
0xB40BBE37, 0xC30C8EA1, 0x5A05DF1B, 0x2D02EF8D};

int main(int argc, char *argv[]){
    register unsigned long int x;
    int i;
    register unsigned char *c, *endbuff;
    unsigned char buff[BUFFSIZE];
    register FILE *thisfile=NULL;
    for (i = 1; i < argc; i++){
        thisfile = fopen(argv[i], "r");
        if (thisfile == NULL) {
            printf("Unable to open ");
        } else {
            x = 0xFFFFFFFF;
            c = &(buff[0]);
            endbuff = &(buff[fread(buff, (sizeof (unsigned char)), BUFFSIZE, thisfile)]);
            while (c != endbuff){
                while (c != endbuff){
                    x=(x>>8) ^ crctable[(x&0xFF)^*c];
                    c++;
                }
                c = &(buff[0]);
                endbuff = &(buff[fread(buff, (sizeof (unsigned char)), BUFFSIZE, thisfile)]);
            }
            fclose(thisfile);
            x = x ^ 0xFFFFFFFF;
            printf("%0.8X ", x);
        }
        printf("%s\n", argv[i]);
    }
    return 0;
}

私が読むことができる提案やリソースを事前に感謝します.

4

3 に答える 3

4

Linuxでは？キーワードを忘れてください。これはコンパイラへregisterの単なる提案gccであり、私の経験からすると、スペースの無駄です。それを自分で理解する能力以上gccのものです。

非常識な最適化レベルでコンパイルしていることを確認し-O3、それを確認します。私はgccそのレベルでコードを生成するのを見たことがあり、それを理解するのに何時間もかかりました。

また、バッファサイズについては、できるだけ大きくしてください。バッファリングを使用しても、呼び出しのコストfreadは依然としてコストであるため、実行する回数が少ないほど良いです。バッファサイズを1Kから1Mに増やすと大幅な改善が見られますが、1Mから2Mに増やすとそれほどではありませんが、パフォーマンスが少しでも向上します。また、2Mは使用できる上限ではありません。可能であれば、1ギガバイト以上に設定します。

次に、（内部ではなくmain）ファイルレベルで配置することをお勧めします。ある時点で、スタックはそれを保持できなくなります。

ほとんどの最適化と同様に、通常、スペースを時間と交換することができます。小さいファイル（1M未満）の場合、バッファーをいくら大きくしても読み取りは1つしかないため、改善は見られないことに注意してください。プロセスのロードにメモリの設定にさらに時間がかかる場合は、わずかに速度が低下することもあります。

ただし、これは小さなファイル（とにかくパフォーマンスが問題にならない場合）にのみ適用されるため、実際には問題にはなりません。パフォーマンスが問題となる大きなファイルは、うまくいけば改善が見られるはずです。

そして、私はあなたにこれを言う必要はないことを知っています（あなたがそれをしていることを示しているので）、しかし私は知らない人のためにとにかくそれについて言及します：測定、推測しないでください！地面には当て推量で最適化した人々の死体が散らばっています:-)

于 2011-03-22T01:19:39.353 に答える
3

CRC計算の実際の計算を高速化することはできないため、確認できる領域は、（a）ファイルの読み取りと（b）ループのオーバーヘッドです。

かなり大きなバッファサイズを使用していますが、これは適切です（ただし、なぜ奇数なのですか？）。fread（3）標準ライブラリ関数の代わりにread（2）システムコール（UNIXライクなシステムを使用していると仮定）を使用すると、1つのcopy操作（freadの内部バッファーからバッファにデータをコピーする）を節約できます。

ループのオーバーヘッドについては、ループの展開を調べてください。

コードには、排除したい冗長性もいくつかあります。

  • sizeof (unsigned char)1です（Cでの定義による）。明示的に計算する必要はありません

  • c = &(buff[0])とまったく同じですc = buff

これらの変更はどちらも（適切なコンパイラーを想定して）コードのパフォーマンスを向上させることはありませんが、通常のCスタイルに従ってより明確でより明確になります。

于 2011-03-22T01:08:21.380 に答える
3

3 つの値をレジスタに格納するように要求しましたが、標準の x86 には 4 つの汎用レジスタregisterしかありません。これは、最後に残ったレジスタに配置するのは非常に大きな負担です。&foo変数のアドレスを見つけるために使用します。最近では、これをヒントとして使用する最新のコンパイラはないと思います。自由に 3 つの使用をすべて削除し、アプリケーションの時間を変更してください。

自分でファイルの巨大なチャンクを読み込んでいるので、 open(2)and をread(2)直接使用して、舞台裏のすべての標準 IO 処理を削除することもできます。別の一般的なアプローチはopen(2)、mmap(2)ファイルをメモリに保存することです。ページが必要なときに OS にページインさせます。これにより、計算中に将来のページを楽観的にディスクから読み取ることができます。これは一般的なアクセス パターンであり、OS 設計者が最適化を試みたものです。(単純なファイル全体を一度にマッピングするメカニズムでは、処理できるファイルのサイズに上限があり、おそらく 32 ビット プラットフォームでは約 2.5 ギガバイト、64 ビット プラットフォームでは絶対に巨大です。ファイルをチャンクにマッピングすると、32 ビット プラットフォームでも任意のサイズのファイルを処理できますが、現在のように読み取り用にループが発生する代わりに、マッピング用にループが発生します。)

David Gelhar が指摘しているように、奇数長のバッファを使用しています。これにより、ファイルをメモリに読み込むコード パスが複雑になる可能性があります。ファイルからバッファーへの読み取りに固執したい8192場合は、最後のループまで特別なケースがないため、(2 ページのメモリ) の倍数を使用することをお勧めします。

速度の最後のビットを追い求めることに本当に興味があり、事前計算テーブルのサイズを大幅に大きくすることを気にしない場合は、ファイルを 8 ビット チャンクではなく 16 ビット チャンクで見ることができます。多くの場合、16 ビット アラインメントに沿ってメモリにアクセスする方が 8 ビット アラインメントに沿ってアクセスする方が高速であり、ループの反復回数を半分に削減でき、通常は大幅な速度向上が得られます。もちろん、マイナス面はメモリ負荷が増加すること (4 バイトごとに 256 エントリではなく、8 バイトごとに 65k エントリ) であり、はるかに大きなテーブルは CPU キャッシュに完全に収まる可能性がはるかに低くなります。

そして、私の頭をよぎる最後の最適化のアイデアはfork(2)、2、3、または 4 つのプロセス (またはスレッド化を使用) にすることです。それぞれのプロセスは、ファイルの一部の crc32 を計算し、すべてのプロセスが完了した後に最終結果を組み合わせることができます。 . crc32 は、SMP またはマルチコア コンピューターから複数のコアを使用しようとすることから実際に利益を得るほど計算集約的ではない可能性があり、crc32 の部分的な計算を組み合わせる方法を理解することは実行できない可能性があります-私はそれを自分で調べていません:) - -しかし、それは努力に報いるかもしれません.マルチプロセスまたはマルチスレッドソフトウェアの書き方を学ぶことは、努力する価値があります.

于 2011-03-22T01:25:26.030 に答える