☰

コンパイラは、セットの要素に対する空の範囲指定ループを最適化しないのはなぜですか? 質問する

tag-icon • tag-icon c++ compiler-optimization
コンパイラは、セットの要素に対する空の範囲指定ループを最適化しないのはなぜですか? 質問する

コードをテストしているときに、空の範囲指定for loopが削除されているかどうかによって実行時間が大幅に増加することに気づきました。通常、コンパイラは for ループが役に立たないことに気づき、無視されると思います。コンパイラのフラグとして、私は-O3( gcc 5.4) を使用しています。また、セットの代わりにベクターを使用してテストしましたが、どちらの場合も機能し、実行時間は同じです。反復子の増分によって余分な時間がかかるようです。

範囲指定の for ループがまだ存在する最初のケース (遅い):

#include <iostream>
#include <set>
int main () {
    long result;
    std::set<double> results;
    for (int i = 2; i <= 10000; ++i) {
        results.insert(i);
        for (auto element : results) {
            // no operation
        }
    }
    std::cout << "Result: " << result << "\n";
}

範囲指定の for ループを削除した 2 番目のケース (高速):

#include <iostream>
#include <set>
int main () {
    long result;
    std::set<double> results;
    for (int i = 2; i <= 10000; ++i) {
        results.insert(i);
    }
    std::cout << "Result: " << result << "\n";
}

ベストアンサー1

内部的にstd::setイテレータは何らかのポインタ チェーンを使用します。これが問題のようです。

問題に類似した最小限の設定は次のとおりです。

struct S
{
    S* next;
};

void f (S* s) {
    while (s)
        s = s->next;
}

これは、複雑なコレクションの実装や反復子のオーバーヘッドの問題ではなく、単にオプティマイザーが最適化できないこのポインタ チェーン パターンの問題です。

ただし、このパターンでオプティマイザーが失敗する正確な理由はわかりません。

また、このバリアントは最適化によって削除されることに注意してください。

void f (S* s) {
    // Copy paste as many times as you wish the following two lines
    if(s)
        s = s->next;
}

編集

@hvd が示唆しているように、これはコンパイラがループが無限でないことを証明できないことに関係している可能性があります。そして、OP ループを次のように記述すると:

void f(std::set<double>& s)
{
    auto it = s.begin();
    for (size_t i = 0; i < s.size() && it != s.end(); ++i, ++it)
    {
        // Do nothing
    }
}

コンパイラはすべてを最適化します。

おすすめ記事