[解決済み] なぜGCCは、速度の代わりにサイズに最適化すると、15-20%速いコードを生成するのですか?

質問

2009年に初めて気づいたのですが、GCCは（少なくとも私のプロジェクトと私のマシンでは）、以下のように最適化すると、著しく速いコードを生成する傾向があるそうです。 サイズ ( -Os )ではなく、速度( -O2 または -O3 と、それ以来ずっと不思議に思っています。

この驚くべき動作を示す（かなり愚かな）コードを、ここに掲載するのに十分な大きさで作成することができました。

const int LOOP_BOUND = 200000000;

__attribute__((noinline))
static int add(const int& x, const int& y) {
    return x + y;
}

__attribute__((noinline))
static int work(int xval, int yval) {
    int sum(0);
    for (int i=0; i<LOOP_BOUND; ++i) {
        int x(xval+sum);
        int y(yval+sum);
        int z = add(x, y);
        sum += z;
    }
    return sum;
}

int main(int , char* argv[]) {
    int result = work(*argv[1], *argv[2]);
    return result;
}

でコンパイルすると -Os でコンパイルした場合、0.38秒、0.44秒かかることがわかります。 -O2 または -O3 . これらの時間は安定して得られ、実質的にノイズはありません (gcc 4.7.2, x86_64 GNU/Linux, Intel Core i5-3320M)．

(更新：全てのアセンブリコードを ギットハブ : それらは投稿を肥大化させ、どうやら質問にはほとんど価値を与えないようである。 fno-align-* フラグも同じような効果があります)。

以下は、生成されたアセンブリに -Os と -O2 .

残念ながら、私のアセンブリに関する理解は非常に浅いため、次に行ったことが正しいかどうかは全くわかりません。 -O2 のアセンブリに統合し、そのすべての差分を -Os ただし その .p2align 行、結果 こちら . このコードはまだ0.38sで実行され が違うだけです。 .p2align のものです。

推測するに、これらはスタックアライメントのためのパディングです。というのは なぜGCCはNOPを含む関数をパッドするのですか？ これは、コードの実行速度を上げるために行われるものですが、どうやら私の場合はこの最適化が裏目に出たようです。

この場合、パディングが犯人なのでしょうか？なぜ、どのように？

このノイズのせいで、タイミングの微調整がかなり不可能になっています。

CやC++のソースコードでマイクロ最適化（スタックアライメントとは無関係）を行う際に、このような偶然のラッキー/アンラッキーアライメントが干渉しないようにするにはどうしたらよいでしょうか？

---

UPDATEです。

以下 パスカル・キュオックさんの回答 アライメントを少しいじってみました。を渡すことで -O2 -fno-align-functions -fno-align-loops をgccに渡すと、すべての .p2align はアセンブリから消え、生成された実行ファイルは 0.38s で実行されます。によると gccドキュメント :

-Os はすべての -O2 最適化フラグを有効にしますが、] -Os は以下の最適化フラグを無効にします。

  -falign-functions  -falign-jumps  -falign-loops
  -falign-labels  -freorder-blocks  -freorder-blocks-and-partition
  -fprefetch-loop-arrays

ということは、かなり（誤）配列の問題のようですね。

については、まだ懐疑的です。 -march=native で提案されているように Marat Dukhanの回答 . この（誤）整列の問題に干渉しているだけではないのか、私のマシンには全く影響がないのか、納得がいきません。(それでも、私は彼の答えにupvotedしました)。

---

UPDATE 2:

を取ることができます。 -Os を写真から取り出す。 でコンパイルすると、次のようなタイムが得られます。

• -O2 -fno-omit-frame-pointer 0.37s

• -O2 -fno-align-functions -fno-align-loops 0.37s

• -S -O2 のアセンブリを手動で移動させます。 add() 後 work() 0.37s

• -O2 0.44s

の距離のように見えます。 add() は、コールサイトからの距離が非常に重要です。試してみたところ perf の出力は perf stat と perf report は、私にはほとんど意味がありません。しかし、私はそこから一貫した結果を1つだけ得ることができました。

-O2 :

 602,312,864 stalled-cycles-frontend   #    0.00% frontend cycles idle
       3,318 cache-misses
 0.432703993 seconds time elapsed
 [...]
 81.23%  a.out  a.out              [.] work(int, int)
 18.50%  a.out  a.out              [.] add(int const&, int const&) [clone .isra.0]
 [...]
       ¦   __attribute__((noinline))
       ¦   static int add(const int& x, const int& y) {
       ¦       return x + y;
100.00 ¦     lea    (%rdi,%rsi,1),%eax
       ¦   }
       ¦   ? retq
[...]
       ¦            int z = add(x, y);
  1.93 ¦    ? callq  add(int const&, int const&) [clone .isra.0]
       ¦            sum += z;
 79.79 ¦      add    %eax,%ebx

について fno-align-* :

 604,072,552 stalled-cycles-frontend   #    0.00% frontend cycles idle
       9,508 cache-misses
 0.375681928 seconds time elapsed
 [...]
 82.58%  a.out  a.out              [.] work(int, int)
 16.83%  a.out  a.out              [.] add(int const&, int const&) [clone .isra.0]
 [...]
       ¦   __attribute__((noinline))
       ¦   static int add(const int& x, const int& y) {
       ¦       return x + y;
 51.59 ¦     lea    (%rdi,%rsi,1),%eax
       ¦   }
[...]
       ¦    __attribute__((noinline))
       ¦    static int work(int xval, int yval) {
       ¦        int sum(0);
       ¦        for (int i=0; i<LOOP_BOUND; ++i) {
       ¦            int x(xval+sum);
  8.20 ¦      lea    0x0(%r13,%rbx,1),%edi
       ¦            int y(yval+sum);
       ¦            int z = add(x, y);
 35.34 ¦    ? callq  add(int const&, int const&) [clone .isra.0]
       ¦            sum += z;
 39.48 ¦      add    %eax,%ebx
       ¦    }

について -fno-omit-frame-pointer :

 404,625,639 stalled-cycles-frontend   #    0.00% frontend cycles idle
      10,514 cache-misses
 0.375445137 seconds time elapsed
 [...]
 75.35%  a.out  a.out              [.] add(int const&, int const&) [clone .isra.0]                                                                                     ¦
 24.46%  a.out  a.out              [.] work(int, int)
 [...]
       ¦   __attribute__((noinline))
       ¦   static int add(const int& x, const int& y) {
 18.67 ¦     push   %rbp
       ¦       return x + y;
 18.49 ¦     lea    (%rdi,%rsi,1),%eax
       ¦   const int LOOP_BOUND = 200000000;
       ¦
       ¦   __attribute__((noinline))
       ¦   static int add(const int& x, const int& y) {
       ¦     mov    %rsp,%rbp
       ¦       return x + y;
       ¦   }
 12.71 ¦     pop    %rbp
       ¦   ? retq
 [...]
       ¦            int z = add(x, y);
       ¦    ? callq  add(int const&, int const&) [clone .isra.0]
       ¦            sum += z;
 29.83 ¦      add    %eax,%ebx

の呼び出しで失速しているように見えます。 add() をスローにした場合。

を調べました。 すべて その perf -e は、私のマシンで吐き出すことができます。上記の統計値だけではありません。

同じ実行ファイルに対して stalled-cycles-frontend は実行時間と直線的な相関を示し、これほど明確な相関を示すものは他に見当たりませんでした。(比較対象 stalled-cycles-frontend を異なる実行ファイルに対して行うことは、私には意味がありません)。

キャッシュミスの件は、最初のコメントとして出てきましたので、記載させていただきました。で私のマシンで計測できるキャッシュミスを全て調べました。 perf 上にあげたものだけではありません。キャッシュミスは非常にノイジーで、実行時間との相関はほとんどありません。

解決方法は？

私の同僚が、私の質問に対するもっともな答えを見つけるのを手伝ってくれました。彼は256バイトの境界が重要であることに気づきました。彼はここに登録していないので、自分で答えを投稿するよう私に勧めてくれました（そして全ての名声を手に入れました）。

---

短い回答です。

この場合、パディングが犯人なのでしょうか？なぜ、どのように？

すべてはアライメントに集約される。 アラインメントがパフォーマンスに大きな影響を与えることがあるので、そのために -falign-* というフラグがあります。

を提出しました。 gcc開発者への(インチキ？)バグレポート . その結果、デフォルトの動作は ループはデフォルトで8バイトに揃えますが、10バイト以上埋める必要がなければ16バイトに揃えるようにしています。 どうやらこのデフォルトは、この特別なケースと私のマシンでは最良の選択ではないようです。Clang 3.4 (trunk) で -O3 は適切なアライメントを行い、生成されたコードはこの奇妙な挙動を示しません。

もちろんです。 不適切なアライメントが行われた場合、事態を悪化させます。 不要な/悪いアライメントは、ただ意味もなくバイトを消費し、キャッシュミスなどを増加させる可能性があります。

このノイズのために、タイミングを最適化することができません。 は不可能です。

このような偶然の幸運/不運のアライメントを確認するには、どうすればよいのでしょうか。 スタックとは関係ない）微細な最適化を行う際に、干渉を受けないようにするためです。 CやC++のソースコードで、アライメントをとることはできますか？

gccに正しいアライメントを行うように指示するだけでよい。

g++ -O2 -falign-functions=16 -falign-loops=16

---

長い回答です。

場合、コードの実行速度が遅くなります。

• アン XX バイトバウンダリーカット add() を真ん中にして( XX は機種に依存します。）

• を呼び出すと add() を飛び越えなければならない。 XX バイトの境界があり、ターゲットがアライメントされていない。

• もし add() がアライメントされていない。

• ループがアライメントされていない場合。

最初の2つは、コード上で美しく表示され、その結果 Marat Dukhan さんのご厚意により . この場合 gcc-4.8.1 -Os (0.994秒で実行されます)。

00000000004004fd <_ZL3addRKiS0_.isra.0>:
  4004fd:       8d 04 37                lea    eax,[rdi+rsi*1]
  400500:       c3   

256バイトのバウンダリーカット add() は真ん中にあり、どちらも add() もループも整列していません。驚くなかれ、これが一番遅いケースなのだ!

この場合 gcc-4.7.3 -Os (0.822秒で実行）では、256バイトの境界はコールドセクションにしか切り込まない（ただし、ループも add() がカットされる)。

00000000004004fa <_ZL3addRKiS0_.isra.0>:
  4004fa:       8d 04 37                lea    eax,[rdi+rsi*1]
  4004fd:       c3                      ret

[...]

  40051a:       e8 db ff ff ff          call   4004fa <_ZL3addRKiS0_.isra.0>

何も整列せず、呼び出しの add() は256バイトの境界を飛び越えなければなりません。このコードは2番目に遅いです。

場合 gcc-4.6.4 -Os (0.709秒で実行)では、何もアライメントされていないにもかかわらず add() は256バイトの境界を飛び越える必要がなく、ターゲットはちょうど32バイト先にあります。

  4004f2:       e8 db ff ff ff          call   4004d2 <_ZL3addRKiS0_.isra.0>
  4004f7:       01 c3                   add    ebx,eax
  4004f9:       ff cd                   dec    ebp
  4004fb:       75 ec                   jne    4004e9 <_ZL4workii+0x13>

これは3つの中で一番速いです。なぜ256バイトの境界線が彼のマシンで特殊なのか、それは彼に任せることにします。私はそのようなプロセッサを持っていません。

さて、私のマシンでは、この256バイトの境界の効果は得られません。私のマシンでは、関数とループのアライメントだけが影響します。もし私が g++ -O2 -falign-functions=16 -falign-loops=16 であれば、すべてが正常に戻ります。常に最速のケースが得られ、時間は -fno-omit-frame-pointer のフラグを立てるようになりました。私は g++ -O2 -falign-functions=32 -falign-loops=32 または16の倍数であっても、コードはそのことに敏感ではありません。

2009年に初めて気づいたのですが、gccは（少なくとも私のプロジェクトや私の の場合、明らかに速いコードを生成する傾向があります。 速度（-O2または-O3）ではなく、サイズ（-Os）に最適化し、私はずっとそれを見てきました。 それ以来、なぜなのか不思議でなりません。

考えられる説明は、この例にあるような、アライメントに敏感なホットスポットがあったということです。フラグをいじることで -Os の代わりに -O2 のように、偶然にもホットスポットが幸運な形で揃い、コードが高速化されました。 サイズの最適化とは関係ないのです。たまたまホットスポットがうまく配置されただけなのです。 これからは、自分のプロジェクトでアライメントの効果を確認することにします。

あ、あともうひとつ。 例のようなホットスポットはどうして発生するのでしょうか？のような小さな関数をインライン化することができるのでしょうか？ add() は失敗するのでしょうか？

考えてみてください。

// add.cpp
int add(const int& x, const int& y) {
    return x + y;
}

と別のファイルに記述します。

// main.cpp
int add(const int& x, const int& y);

const int LOOP_BOUND = 200000000;

__attribute__((noinline))
static int work(int xval, int yval) {
    int sum(0);
    for (int i=0; i<LOOP_BOUND; ++i) {
        int x(xval+sum);
        int y(yval+sum);
        int z = add(x, y);
        sum += z;
    }
    return sum;
}

int main(int , char* argv[]) {
    int result = work(*argv[1], *argv[2]);
    return result;
}

とコンパイルされます。 g++ -O2 add.cpp main.cpp .

gcc はインライン化しません。 add() !

以上、意図せずしてOPのようなホットスポットができてしまうということです。 もちろん、私のせいでもあります。gccは優れたコンパイラです。 として、上記をコンパイルすると。 g++ -O2 -flto add.cpp main.cpp ということです。 リンク時の最適化を行うと、0.19秒で実行されるようになりました

(OPではインライン化を人為的に無効にしており、そのためOPのコードは2倍遅くなっています)。