5

次の関数を使用して、VS2008、.NET 3.5 プロジェクトのファイルの CRC32 を計算しています。

public UInt32 ComputeHash(System.IO.Stream stream)
{
    unchecked
    {
        const int BUFFER_SIZE = 1024;

        UInt32 crc32Result = 0xFFFFFFFF;
        byte[] buffer = new byte[BUFFER_SIZE];
        int count = stream.Read(buffer, 0, BUFFER_SIZE);

        while (count > 0)
        {
            for (int i = 0; i < count; i++)
            {
                crc32Result = ((crc32Result) >> 8) ^ _crc32Table[(buffer[i]) ^ (crc32Result) & _LOOKUP_TABLE_MAX_INDEX];
            }
            count = stream.Read(buffer, 0, BUFFER_SIZE);
        }

        return ~crc32Result;
    }
}

簡潔にするために、ルックアップ テーブル (_crc32Table) を作成する関数は省略しています。テーブルは UInt32 の配列であり、クラスがインスタンス化されるときに構築され、256 個の値を含みます (256 は _LOOKUP_TABLE_MAX_INDEX + 1 の値でもあります)。

これを MD5CryptoServiceProvider および SHA1CryptoServiceProvider ComputeHash 関数と比較していくつかのベンチマークを実行しましたが、はるかに高速です。MD5 関数は 2 倍以上高速で、SHA1 ハッシュは約 35% 高速です。CRC32 は速いと言われましたが、それは私が見ているものではありません。

私の仮定は間違っていますか？これは予想されることですか、それともこのアルゴリズムに欠陥がありますか?

4

4 に答える 4

6

コードを組み込み関数と比較し、なぜ高速なのかを尋ねています。あなたがする必要があるのは、組み込み関数のソースを見つけることです。それらはどのように機能しますか？違いを見てください。

ビルトイン関数がネイティブ ライブラリを呼び出し、マネージ メモリ フレームワーク内で実行する必要がないことをごまかします。

于 2009-06-03T16:51:32.140 に答える
3

プロファイリングは、IO 呼び出し (読み取り) と CRC 計算にかかる時間を判断するのに役立ちます。コードは多くの場合、IO バウンドです。ただし、C# で非常に高速な CRC 関数を実装した人として、MD5 よりも遅い理由についていくつかの指針を示すことができます。

  • 一度に 1 バイトずつメモリを読み取っています。一度に 4 バイトを読み取れるように 4 分割を実装するか、一度に 8 バイトを読み取れるように 8 分割を実装します (ただし、コードが実際に 64 ビット モードで実行される場合のみ- フォールバックする必要があります)。 if(sizeof(IntPtr) < 8) などを使用してテストする必要があります。
  • ループの反復ごとに 1 バイトを処理しているため、バイトごとにループのオーバーヘッドが発生します。slicing-by-N を実装するか、ループ展開を検討してください。(両方を行う必要はないかもしれません。)
  • バイトごとに 2 つの配列境界チェックが発生しています。「安全でない」コードを使用して、境界チェックを回避できます。安全でないコードでは、.NET 配列にのみアクセスしているため、既にマシン ワードのサイズに揃えられていると想定できますが、読み取りポインターを揃えることも確認する必要があります。アンセーフ コードは安全ではないことに注意してください。
  • MD5 は非常に高速なアルゴリズムになるように設計されており、上記の問題はありません。一度に複数のバイトを読み取り、それらを並行して処理し、アンマネージ コードで実装されます。
  • これはマイナーですが、ループ構成が最適ではありません。count != 0 を知っているので、count を事前にデクリメント (つまり --count) し、ゼロと比較する do/while ループは、2 つの変数を比較する for ループよりも優れています。あなたのコードでは、これによりいくつかの命令が節約され、おそらくバイトあたりのメモリ読み取りが節約されます。

slicing-by-N を実装する場合は、すべてのルックアップ テーブルを 1 つの大きなテーブルにパックして、同じポインターを介してすべてにアクセスできるようにします。また、slicing-by-4 と slicing-by-8 に同じテーブルを使用することもできます。また、典型的な N によるスライスの実装では、特定のマシン エンディアンが想定されるため、ビッグ エンディアン マシン用に別のバージョンが必要になる場合があります。これは、BitConverter.IsLittleEndian を使用して確認できます。

于 2016-05-08T17:12:08.673 に答える
0

このコードの実行時に自動的に実行される最適化についてはあまり詳しくありませんが、プロファイリングが機能しない場合はいくつかのオプションがあります。

まだ最適化されていない場合は、アンセーフ コードを試して、buffer[i] と _crc32Table ルックアップにポインター演算を使用することをお勧めします。

パフォーマンスの問題が発生している他の唯一の場所は、Stream.Read 呼び出しです。さまざまな BUFFER_SIZE 値を試しましたか?

自動的に最適化されていない場合は、より大きなバイトバッファーを使用し、手動でループ展開を行うことも役立ちます。

于 2009-06-03T17:11:06.110 に答える