CRC32計算をスピードアップするにはどうすればよいですか？

StackOverflow https://stackoverflow.com/questions/5385575

  •  28-10-2019
  •  | 
  •  

質問

CRC32の実装をLinuxでできるだけ速いCRC32実装を作成しようとしています。C。バッファサイズが賢明かどうかさえわかりません。繰り返し実験によって選ばれました。

#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;
}

私が読むことができる提案やリソースを前もってありがとう。

役に立ちましたか？

解決

レジスタに3つの値を保存するように要求しましたが、標準x86には4つの汎用レジスタしかありません。これは、最後の残りのレジスタには非常に多くの負担です。これが私が期待する理由の1つです。 register 本当にあなたが使用することを妨げるだけです &foo 変数のアドレスを見つける。最近では、最新のコンパイラがヒントとしても使用しているとは思わない。 3つの用途をすべて削除し、アプリケーションを再度時間をかけてください。

あなたは自分でファイルの巨大なチャンクで読んでいるので、あなたも使用するかもしれません open(2) と read(2) 直接、舞台裏ですべての標準的なIO処理を削除します。別の一般的なアプローチは次のとおりです open(2) と mmap(2) メモリへのファイル：ページが必要なときにOSページを入れます。これにより、将来のページが可能になる場合があります 楽観的に 計算を行っている間にディスクから読む：これは一般的なアクセスパターンであり、OSデザイナーが最適化しようとした1つです。 （ 単純 ファイル全体を一度にマッピングするメカニズムは、おそらく32ビットプラットフォームで約2.5ギガバイト、64ビットプラットフォームで非常に大きく、処理できるファイルのサイズに上限を設けます。チャンクでファイルをマッピングすることで、32ビットプラットフォームでも任意のサイズのファイルを処理できますが、読み取り用のループのコストで、マッピング用です。）

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

最後の速度から本当に声を出していて、コンピューター前のテーブルのサイズを大幅に増やすことを気にしないなら、8ビットのチャンクではなく、16ビットのチャンクでファイルを見ることができます。多くの場合、16ビットアライメントに沿ってメモリにアクセスすることは8ビットアライメントに沿ったよりも高速であり、ループを介して半分の反復を削減するため、通常は大きな速度が向上します。もちろん、マイナス面はメモリ圧力の増加です（それぞれ4バイトの256エントリではなく、それぞれ8バイトのエントリ、8バイトのエントリ）、はるかに大きなテーブルがCPUキャッシュに完全に収まる可能性がはるかに低くなります。

そして、私の心を横切る最後の最適化のアイデアは fork(2) 2、3、または4つのプロセス（またはスレッドを使用）になり、それぞれがCRC32を計算できます 部分 ファイルの後、すべてのプロセスが完了した後、最終結果を結合します。 CRC32は、SMPまたはマルチコアコンピューターから複数のコアを使用しようとすることで実際に恩恵を受けるほど計算的に集中していない可能性があります。 - しかし、それは努力を返済するかもしれません、そして、マルチプロセスまたはマルチスレッドソフトウェアの書き方を学ぶことは、関係なく努力する価値があります。

他のヒント

Linuxで？を忘れてください register キーワード、それはただです 提案 コンパイラに、そして私の経験から gcc, 、それは空間の無駄です。 gcc は もっと それ自体を理解できるよりも。

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

そして、バッファサイズでは、できるだけ大きくします。バッファリングであっても、呼び出しのコスト fread まだコストなので、やるほどそれが少ないほど良いです。バッファーのサイズを1kから1mに増やした場合、1mから2mに上昇させた場合はそれほど大きくなりますが、パフォーマンスの増加でさえも増加します。そして、2mはあなたが使用できるものの上限ではありません、私はそれを1つ以上に設定します ギガバイト もし可能なら。

その後、あなたはそれをファイルレベルに置きたいかもしれません（内側ではなく main）。ある時点で、スタックはそれを保持することができません。

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

しかし、これは小さなファイルのみであるため（とにかくパフォーマンスが問題ではない場合）、それは本当に重要ではありません。パフォーマンスがある大きなファイル は 問題は、うまくいけば改善が見つかるはずです。

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

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

あなたはかなり大きなバッファサイズを使用していますが、それは良いことです（しかし、なぜそれは奇数なのか？）。 FREAD（3）標準ライブラリ関数の代わりに読み取り（2）システムコール（UNIXのようなシステムを使用していると仮定）を使用すると、 copy 操作（Freadの内部バッファーからバフファーへのデータをコピーする）。

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

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

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

  • c = &(buff[0]) 正確に同等です c = buff

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

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top