34

このクラスのベンチマーク:

struct Sieve {
  std::vector<bool> isPrime;

  Sieve (int n = 1) {
    isPrime.assign (n+1, true);
    isPrime[0] = isPrime[1] = false;

    for (int i = 2; i <= (int)sqrt((double)n); ++i)
      if (isPrime[i]) 
        for (int j = i*i; j <= n; j += i)
          isPrime[j] = false;
  }
};

多数のコンストラクターを呼び出すと、64 ビット バイナリーと 32 ビット バージョン (リリース ビルド) でパフォーマンス (CPU 時間) が 3 倍以上悪くなります。

Sieve s(100000000);

テストsizeof(bool)しましたが1、両方のバージョンに対応しています。64ビット版と32ビット版で代用vector<bool>すると性能は同じになります。vector<char>何故ですか？

S(100000000)(リリース モード、最初は 32 ビット、2 番目は 64 ビット))の実行時間は次のとおりです。

vector<bool>0.97秒 vector<char>3.12秒 0.99秒 0.99秒 1.57秒 vector<int> 1.59秒

また、VS2010 (Wouter Huysentruit の応答によって促された) でサニティ テストを行ったところ、0.98 秒 0.88 秒が生成されました。したがって、VS2012 の実装には問題があります。

Microsoft Connectにバグ レポートを送信しました

編集

int以下の多くの回答は、インデックス作成に使用することの欠陥についてコメントしています。これは事実かもしれませんが、偉大な魔法使い自身でさえfor (int i = 0; i < v.size(); ++i)彼の著書で標準を使用しているため、そのようなパターンによってパフォーマンスが大幅に低下することはありません。さらに、この問題は、Going Native 2013 カンファレンスで提起され、C++ 専門家の主宰グループはsize_t、インデックス作成および戻り値の型として使用するという初期の推奨事項についてsize()、誤りとしてコメントしました。彼らは言った：「ごめんなさい、私たちは若かった...」

この質問のタイトルは次のように言い換えることができます: VS2010 から VS2012 にアップグレードすると、このコードのパフォーマンスが 3 倍以上低下します。

編集

インデックスのメモリ アライメントを見つけようと大雑把な試みを行ったiところj、このインストルメント化されたバージョンであることがわかりました。

struct Sieve {
  vector<bool> isPrime;

  Sieve (int n = 1) {
    isPrime.assign (n+1, true);
    isPrime[0] = isPrime[1] = false;

    for (int i = 2; i <= sqrt((double)n); ++i) {
      if (i == 17) cout << ((int)&i)%16 << endl;
      if (isPrime[i]) 
        for (int j = i*i; j <= n; j += i) {
          if (j == 4) cout << ((int)&j)%16 << endl;
          isPrime[j] = false;
        }
    }
  }
};

自動的に魔法のように高速に実行されるようになりました (32 ビット バージョンよりわずか 10% 遅くなります)。intこのことと VS2010 のパフォーマンスにより、オプティマイザーが .NETではなくインデックスを処理する固有の問題を抱えているという理論を受け入れるのが難しくなりますsize_t。

4

3 に答える 3

37

std::vector<bool>ここで直接のせいではありません。パフォーマンスの違いは、最終的には、ループでの符号付き 32 ビットint型の使用と、コンパイラによるかなり貧弱なレジスタ割り当てによって引き起こされます。たとえば、最も内側のループを考えてみましょう。

for (int j = i*i; j <= n; j += i)
    isPrime[j] = false;

ここで、jは 32 ビットの符号付き整数です。ただし、 で使用する場合はisPrime[j]、添え字の計算を実行するために、64 ビット整数に昇格 (および符号拡張) する必要があります。jコンパイラは64 ビット値として扱うことはできません。これは、ループの動作が変わるためです (たとえば、ifnが負の場合)。コンパイラは、32 ビットの amount を使用してインデックス計算を実行することもできません。jこれは、その式の動作が変わるためです (たとえば、ifjが負の場合)。

そのため、コンパイラは 32 ビットを使用してループのコードを生成する必要があり、次に添字計算用にそれを 64 ビット整数にj変換するコードを生成する必要があります。jを使用して外側のループに対して同じことを行う必要がありますi。残念ながら、この場合、コンパイラはレジスタを適切に割り当てないように見えます(*)。スタックにテンポラリをスピルし始め、目に見えるパフォーマンス ヒットを引き起こします。

どこでも使用するようにプログラムを変更するとsize_t(x86 では 32 ビット、x64 では 64 ビット)、生成されたコードは 1 つのサイズの値でのみ動作する必要があるため、パフォーマンスは x86 と同等であることがわかります。

Sieve (size_t n = 1)
{
    isPrime.assign (n+1, true);
    isPrime[0] = isPrime[1] = false;

    for (size_t i = 2; i <= static_cast<size_t>(sqrt((double)n)); ++i)
        if (isPrime[i]) 
            for (size_t j = i*i; j <= n; j += i)
                isPrime[j] = false;
}

特にこれらの型の幅が異なる場合、符号付きと符号なしの型を混在させると危険であり、予期しないエラーが発生する可能性があるため、とにかくこれを行う必要があります。

を使用してstd::vector<char>も問題は「解決」しますが、理由は異なります。 a の要素にアクセスするために必要な添え字の計算は、 の要素にstd::vector<char>アクセスする場合よりも大幅に簡単ですstd::vector<bool>。オプティマイザーは、より単純な計算に対してより優れたコードを生成できます。

(*) 私はコード生成には取り組んでおらず、アセンブリや低レベルのパフォーマンス最適化の専門家ではありませんが、生成されたコードを見て、ここで報告されているように、Visual C++ 2010 の生成がより優れていることを考えると、コンパイラには改善の余地があると思います。あなたが開いた Connect バグがコンパイラ チームに転送され、彼らが調査できるようにします。

于 2013-04-18T06:31:29.670 に答える