c++ - memcmp の実装

Question

以下は、memcmp の Microsoft CRT 実装です。

int memcmp(const void* buf1,
           const void* buf2,
           size_t count)
{
    if(!count)
        return(0);

    while(--count && *(char*)buf1 == *(char*)buf2 ) {
        buf1 = (char*)buf1 + 1;
        buf2 = (char*)buf2 + 1;
    }

    return(*((unsigned char*)buf1) - *((unsigned char*)buf2));
}

基本的に、バイトごとの比較を実行します。

私の質問は2つの部分に分かれています：

これを int by int 比較に変更しない理由はありますcount < sizeof(int)か?
1 を実行した場合、潜在的/明らかな問題はありますか?

注: 私は CRT をまったく使用していないので、とにかくこの関数を実装する必要があります。正しく実装する方法についてのアドバイスを探しています。

score 7 · Accepted Answer

必要に応じて、int ごとの比較またはさらに広いデータ型として実行できます。

(少なくとも) 注意しなければならない 2 つの点は、最初と最後でオーバーハングがあることと、2 つの領域間でアライメントが異なるかどうかです。

アラインメント規則に従わずに値にアクセスすると、一部のプロセッサの実行速度が低下します (実行しようとするとクラッシュするプロセッサもあります)。

したがって、コードはおそらくアラインメント領域まで比較し、次に比較し、次に再度比較することができますが、両方の領域のアラインメントcharがおそらく重要になります。intintchar

その余分なコードの複雑さが、得られる節約に値するかどうかは、制御できない多くの要因に依存します。考えられる方法は、両方の領域が同じように配置されている理想的なケースを検出して高速に実行することです。それ以外の場合は、文字ごとに実行します。

score 5 · Accepted Answer

あなたが提案する最適化は非常に一般的です。最大の懸念は、単一バイト以外のアライメントされていないアクセスを許可しない、またはそのモードで遅いプロセッサで実行しようとする場合です。x86 ファミリーにはその問題はありません。

また、より複雑であるため、バグが含まれる可能性が高くなります。

score 1 · Accepted Answer

大きなチャンク内で不一致を見つけた場合は、正しい戻り値を計算できるように、そのチャンクchar 内で最初に異なるものを特定する必要があることを忘れないでください（memcmp()最初の異なるバイトの差をunsigned char値として扱います）。

score 0 · Accepted Answer

intとして比較する場合は、アライメントをチェックし、countがsizeof（int）で割り切れるかどうかをチェックする必要があります（最後のバイトをcharとして比較するため）。

score 0 · Accepted Answer

それは本当に彼らの実装ですか？int-wise を実行しない以外に、他の問題があります。

一貫性を捨てる。
その return ステートメントは機能しますか? unsigned char - unsigned char = signed int?

一度に int が機能するのは、ポインターが整列している場合、またはそれぞれの先頭から数バイトを読み取ることができ、両方がまだ整列している場合にのみ機能するため、整列境界の前に両方が 1 の場合は、それぞれの 1 文字を読み取ることができます。 int-at-a-time ですが、一方が整列していて他方が整列していないなど、それらが異なって整列している場合、これを行う方法はありません。

memcmp は、実際に比較し (最後まで行かなければならない)、データが長い場合、最も非効率的です (つまり、最も時間がかかります)。

私は自分で書きませんが、データの大部分を比較する場合は、配置を確認したり、末尾を埋めたり、必要に応じて一度に単語を実行したりできます。

score 0 · Accepted Answer

もう 1 つのアイデアは、プロセッサのキャッシュとフェッチを最適化することです。プロセッサは、個々のバイトをランダムにフェッチするのではなく、大きなチャンクでフェッチすることを好みます。内部の仕組みはすでにこれを説明しているかもしれませんが、とにかく良い練習になるでしょう. 常にプロファイリングして、最も効率的なソリューションを決定します。

疑似コード:

while bytes remaining > (cache size) / 2 do // Half the cache for source, other for dest.
  fetch source bytes
  fetch destination bytes
  perform comparison using fetched bytes
end-while
perform byte by byte comparison for remainder.

詳細については、Web で「データ駆動設計」および「データ指向プログラミング」を検索してください。

ARM ファミリなどの一部のプロセッサでは、命令の条件付き実行 (32 ビット、非サム) モードが可能です。プロセッサは命令をフェッチしますが、条件が満たされた場合にのみ命令を実行します。この場合、ブール代入に関して比較を言い換えてみてください。これにより、実行される分岐の数も減り、パフォーマンスが向上します。

ループ展開も参照してください。アセンブリ言語
も参照してください。

アルゴリズムを特定のプロセッサに合わせて調整することで多くのパフォーマンスを得ることができますが、移植性の領域では緩んでいます。

score 0 · Accepted Answer

あなたが見つけたコードはの単なるデバッグ実装でありmemcmp、パフォーマンスではなく、単純さと読みやすさのために最適化されています。

組み込みコンパイラの実装はプラットフォーム固有であり、(ターゲットアーキテクチャに応じて) dwords または qwords を可能な限り一度に比較するプロセッサ命令を生成するのに十分スマートです。また、組み込みの実装は、両方のバッファが同じアドレスを持っている場合、すぐに戻ることがあります(buf1 == buf2)。このチェックは、デバッグの実装にもありません。

最後に、実行するプラットフォームが正確にわかっている場合でも、プログラムの残りの部分に固有のさまざまな要因に依存するため、完璧な実装はまだ一般的ではありません。

保証されている最小のバッファアラインメントは?
アクセス違反を引き起こさずに、バッファの末尾を越えたパディングバイトを読み取ることができますか?
バッファパラメータは同じでよいですか?
バッファサイズは 0 でよいですか?
バッファの内容が等しいかどうかだけを比較する必要がありますか? それとも、どちらが大きいか (戻り値 < 0 または > 0) を知る必要がありますか?
...

パフォーマンスが問題になる場合は、アセンブリで比較ルーチンを作成することをお勧めします。ほとんどのコンパイラには、ソース用に生成されたアセンブリライシングを表示するオプションがあります。そのコードを取得して、ニーズに合わせて調整できます。

score -1 · Accepted Answer

多くのプロセッサは、これを単一の命令として実装します。実行しているプロセッサを保証できる場合は、1 行のインラインアセンブラで実装できます。

c++ - memcmp の実装

8 に答える 8

Related

Reference