bits/stdc++.hのインクルードを高速化しよう！（MacOS版）

# 前書き

競技プログラミングで有名なヘッダファイルである`bits/stdc++.h`[^1]ですが、正しい使い方をしないとコンパイルに時間がかかります。この記事では正しい使い方によりコンパイルを高速化するための**環境依存でない方法**を紹介します。

但し、`bits/stdc++.h`はGCCで使えるヘッダファイル[^1]なので、Clangなどの別のコンパイラで使うことは非推奨です。そのため、以下では**GCCの環境で行うことを想定**しています。

# 環境

Intel MacにHomebrewを用いてインストールしたGCCを本記事では用いています。

```
MacOS 11.0.1
```

# `bits/stdc++.h`のインクルードの高速化のために？

結論から言えば、`bits/stdc++.h`を**プリコンパイルする**のが効果的です。以下で解説をしますが、とりあえず高速化したい場合は次の章を見てください。

## [1] プリコンパイルとは

プリコンパイルとは、GCCの標準ライブラリのような**滅多に変更をしないヘッダファイルを予めコンパイルすること**です。これにより、ヘッダファイルのインクルードを高速化することができます。

## [2] PCHファイルとは

**以降ではプリコンパイル済みヘッダファイルをPCHファイルと略記**します。

ヘッダファイル(hoge.h)をプリコンパイルする[^4]とPCHファイル(hoge.h.gch)ができ、通常のヘッダファイルと同様にインクルードすることができます[^5]。

## [3] PCHファイルの使用での注意点

ここでは[GCC online documentation](https://gcc.gnu.org/onlinedocs/)の10.2.0の「Using Precompiled Headers」の章の必要な部分を列挙しているので、詳しくはこちらを参考にしてください[^2]。また、難しい場合は読み飛ばしてください。

### (1) 優先順位について

PCHファイルもヘッダファイルと同じサーチパスを探します。但し、優先順位はPCHファイルの方が優先順位が高いので、**優先順位の高い(2)の条件を満たすPCHファイルがある場合**はそちらが優先されます。

よって、C++でのインクルードの優先順位と合わせれば以下の順でヘッダファイルの読み込みは行われます。上にあるほど優先順位は高いです。

```
1-1 -Iオプションで指定されたディレクトリのPCHファイル
1-2 -Iオプションで指定されたディレクトリのヘッダファイル
2-1 環境変数(CPLUS_INCLUDE_PATH)で指定されたディレクトリのPCHファイル
2-2 環境変数(CPLUS_INCLUDE_PATH)で指定されたディレクトリのヘッダファイル
3-1 システムによって決まっているディレクトリのPCHファイル
3-2 システムによって決まっているディレクトリのヘッダファイル
```

また、ヘッダファイルと同様にPCHファイルでもインクルードガードは働くので、二重インクルードを気にする必要はありません。

### (2) PCHファイルの満たす条件について

PCHファイルをインクルードするには以下の**任意の条件を満たす**必要があります。満たさない場合はパスの通っている通常のヘッダファイルがインクルードされます。


- コンパイル単位で**インクルードできるPCHファイルは一つのみ**
- PCHファイルのインクルードより前にCトークン[^7]は現れてはならないが、プリプロセッサディレクティブ[^7]は現れても良い。
- PCHファイルの生成時と使用時の**プログラムの言語[^8]及びコンパイラのバイナリが同じ**。
- PCHファイルのインクルードより前に定義されるマクロはPCHファイルの生成時に同様に定義されているかPCHファイルに影響がない。
- -Dオプションで明示的にマクロを指定したり**-OやーWdeprecatedなどで暗黙的にマクロを指定したりする場合も**上記の条件に従う。
- オプションの中で変えて良いオプション(e.g. -o)と変えてはならないオプション(e.g. -m)があるが、それ以外の**ほとんどのオプションはPCHファイルの生成時と使用時で同じにした方が良い**。
- 但し、PCHファイルの生成時にデバッグオプションを用いた時はPCHファイルの使用時にデバッグオプションをつけなくても良い。

### (3) 使用されるPCHファイルについて

オプションの複数の組み合わせのPCHファイルを生成したい時は**PCHのファイル名のディレクトリ(hoge.h.gch)を用意**してそのディレクトリ内にPCHファイルを格納する必要があります。また、拡張子が.gchであればファイル名は何でも構いません。

そして、**(1)の優先順位が高く(2)の条件を全て満たすPCHファイルが複数ある場合**はPCHのファイル名のディレクトリにある中で適当なものが選ばれます。この時、複数ある中でどのPCHファイルが選ばれるかは決まっていません。

#実践

実際にインクルードの高速化を行います。

## [1] GCCのインストール

まず、「[MacでGCCを"正しく"環境構築しよう！](https://qiita.com/DaikiSuyama/items/09f5aa399aad37783146)」を参考にGCCをインストールしましょう。

## [2] C++のファイルの用意

プリコンパイル前後での速度を測定するために`#include<bits/stdc++.h>`を含むC++のファイルを用意してください。また、複数のコマンドオプションを使い分けている場合は**使いうる任意のコマンドオプションの組み合わせ**を試してください。

自分の環境では以下のようになりました。2種類のコマンドオプションの組み合わせに対して2回分の測定結果のみを示しています。何回か実験をしてCPU使用率が90%後半の時は常に1.5秒前後であることを確認しました。

```zsh
% time g++ hoge.cc 
g++ hoge.cc  1.52s user 0.52s system 55% cpu 3.699 total

% time g++ hoge.cc 
g++ hoge.cc  1.19s user 0.21s system 98% cpu 1.416 total

% time g++ -std=c++14 hoge.cc  
g++ -std=c++14 hoge.cc  1.41s user 0.65s system 44% cpu 4.688 total

% time g++ -std=c++14 hoge.cc 
g++ -std=c++14 hoge.cc  1.26s user 0.23s system 96% cpu 1.541 total
```

## [3] `bits/stdc++.h`の場所の確認

GCCのインストールのみで`bits/stdc++.h`を通常は利用できます。しかし、上記の測定の際にコンパイルエラーが出る場合、`bits/stdc++.h`へサーチパスが通ってないと思われます。

また、以降では利用可能な`bits/stdc++.h`の場所を確認する必要があるため、「[MacでのGCCのコンパイルエラーの対処法について](https://qiita.com/DaikiSuyama/items/d832b539abd15e3ea644)」を参考に、コンパイルエラーへの対処と`bits/stdc++.h`の場所の確認をしてください[^12]。

## [4] `bits/stdc++.h`のプリコンパイル

**以降では、先程確認した`bits`ディレクトリへと移動してから作業を行ってください。**

まず、PCHファイルを格納するディレクトリを作ります。

```zsh
% mkdir stdc++.h.gch
```

次に[0-1]と同様の**使いうる任意のコマンドオプションの組み合わせ**でのプリコンパイルを行って`stdc++.h.gch`に格納します。ファイル名については後から見てわかりやすいように適当な名前をつけてください。

```
% g++ stdc++.h -o stdc++.h.gch/(適当なファイル名).gch
```

上記のコマンドで生成されたPCHファイルを`ls stdc++.h.gch`で確認してください。


例えば、自分の場合は以下のような出力になります。

```zsh
% g++ stdc++.h -o stdc++.h.gch/stdc++_no.h.gch
% g++ stdc++.h -std=c++14 -o stdc++.h.gch/stdc++_c++14.h.gch
% ls stdc++.h.gch
stdc++_no.h.gch    stdc++_c++14.h.gch
```

## [5] インクルードできているかの確認

[0-1]と同様に**使いうる任意のコマンドオプションの組み合わせ**でのコンパイルを行って高速化されるか試してください。

自分の環境では以下のようになりました。オプション及び試行回数については[0-1]と同じ回数分を添付しています。ここでも何回か実験をしてCPU使用率が90%後半の時は常に0.4秒前後であることを確認しました。

環境にもよると思いますが、<font color="red">1~1.5秒前後は高速化することができる</font>ようです。

```zsh
% time g++ hoge.cc 
g++ hoge.cc  0.28s user 0.08s system 85% cpu 0.430 total
% time g++ hoge.cc 
g++ hoge.cc  0.28s user 0.08s system 96% cpu 0.368 total
% time g++ -std=c++14 hoge.cc 
g++ -std=c++14 hoge.cc  0.28s user 0.13s system 88% cpu 0.468 total
% time g++ -std=c++14 hoge.cc 
g++ -std=c++14 hoge.cc  0.30s user 0.10s system 96% cpu 0.420 total
```

[^1]: [で、結局 #include <bits/stdc++.h> って何?](https://qiita.com/hakatashi/items/f9d9abf05a002b5c4dc5)に`bits/stdc++.h`を使っても良いのかの議論がまとまっているので、参考になります。

[^2]: GCCのC++コンパイラのバージョンのあったものを参照してください。GCCのC++コンパイラへのパスが通っていれば`g++ -v`のコマンドで確認できます。

[^4]: コマンドの例:`g++ hoge.h`

[^5]: インクルードの例:`#include"hoge.h"`,`#include<hoge.h>`

[^7]: わからない場合は調べてください。

[^8]: CとC++であっても異なる言語とします。

[^12]: 自分のMacの環境では`/usr/local/Cellar/gcc/10.2.0/include/c++/10.2.0/x86_64-apple-darwin20/bits/stdc++.h`にありました。

[^13]: 自分のUbuntuの環境では`/usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h`にありました。