5

私は奇妙な問題に遭遇しました:私は次のコードを持っています:

int matches = 0;
for (int str_id = 0; str_id < STR_COUNT; str_id++) {
    if (test(strings1[str_id], strings2[str_id]) == 0)
        matches++;
}

関数を使用して、null で終わる文字列のペアを比較しtest()ます。strings1とは、同じ長さの null で終わる文字列strings2を含むベクトルです。STR_COUNT

がその引数を逆参照するかどうかに応じて、このスニペットは、およびtest()の文字列の長さに関して一定時間または線形時間で実行されます。つまり、私が使用する場合：strings1strings2

int test(char* a, char* b) {
    return (a != b)
}

実行時間は、strings1 と strings2 に格納されている文字列の長さに依存しません。一方、私が使用する場合

int test(char* a, char* b) {
    return (*a != *b)
}

strings1実行時間は、およびに格納されている文字列の長さに比例して増加しstrings2ます。

なぜこれが起こるのでしょうか？

編集: 問題の完全な例: http://pastebin.com/QTPAkP1g

4

2 に答える 2

3

データの局所性の影響が見られます。

ポインタを比較するだけの場合、操作は 2 つのベクトルのメモリのみにアクセスします。ベクトルはそれらの要素を連続して格納するため、各メモリ アクセスは、前の反復中にアクセスされた場所に非常に近い場所になります。これは非常に良い地域であり、キャッシュはあなたに微笑みかけます.

ポインターを逆参照する場合、追加のメモリ アクセスがミックスに追加されるため、キャッシュはより多くの作業を行う必要があり、その効果は実装に大きく依存します。

データから推定すると、文字列はメモリ内にまとめられているように見えるため、1 つの文字列の開始点から次の文字列の開始点までの距離は、文字列の長さに依存します。短い文字列は、長い文字列よりも密集しています。

特に、いくつかの非常に短い文字列を 1 つのキャッシュ ラインにパックできる場合があります。その場合、1 つのキャッシュ ラインで複数回の反復のメモリ アクセスを処理できます。文字列が長くなると、1 つのキャッシュ ラインに収まる文字列が少なくなるため、キャッシュの効率が低下します。最終的に、文字列は十分に長くなり、各文字列が個別のキャッシュ ラインを占有するようになり、キャッシュは何のメリットもありません。

于 2012-10-01T17:02:35.743 に答える
2

最初のケースでは、の限りstrings1 != strings2、条件が真になることは決してないことが証明できるからです。最適化コンパイラは、ループ全体に観察可能な副作用がないことを推測できるため、ループを最適化して忘却することができます。

それは;strings[str_id]に等しいと考えてください。簡単にするために、が1に等しいとstrings + str_id * sizeof(*strings)仮定しましょう（一般性を失うことなくこれを行うことができます）。sizeofその後、あなたの状態は次のようになります。

if (test(strings1 + str_id, strings2 + str_id) == 0)

コンパイラがインライン化できる場合、コードtestの最初のバージョンは次のようになります。test

if ((strings1 + str_id != strings2 + str_id) == 0)

または（連続した簡略化されたが同等の形式）

if (strings1 + str_id == strings2 + str_id)

if (strings1 == strings2)

したがって、 （これはほぼ確実に当てはまります）、コンパイラは外部の原因によって変更されることはないとstrings1 != strings2想定できるため、ループ全体をスキップして、代わりに何もしないことができます。何もしないことは一定時間です。strings1strings2

の2番目のバージョンでtestは、実際にループを実行し、各反復でポインターを逆参照する以外に条件が真であるかどうかを知る方法がないため、実行時間は線形になります。

于 2012-09-29T18:17:14.170 に答える