前書き

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

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

環境

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

MacOS 11.0.1

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

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

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

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

[2] PCHファイルとは

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

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

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

ここではGCC online documentationの10.2.0の「Using Precompiled Headers」の章の必要な部分を列挙しているので、詳しくはこちらを参考にしてください⁴。また、難しい場合は読み飛ばしてください。

(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トークン⁵は現れてはならないが、プリプロセッサディレクティブ⁵は現れても良い。
PCHファイルの生成時と使用時のプログラムの言語⁶及びコンパイラのバイナリが同じ。
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を"正しく"環境構築しよう！」を参考にGCCをインストールしましょう。

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

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

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

% 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のコンパイルエラーの対処法について」を参考に、コンパイルエラーへの対処とbits/stdc++.hの場所の確認をしてください⁷。

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

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

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

% mkdir stdc++.h.gch

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

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

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

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

% 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秒前後であることを確認しました。

環境にもよると思いますが、1~1.5秒前後は高速化することができるようです。

% 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

で、結局 #include って何?にbits/stdc++.hを使っても良いのかの議論がまとまっているので、参考になります。 ↩
コマンドの例:g++ hoge.h ↩
インクルードの例:#include"hoge.h",#include<hoge.h> ↩
GCCのC++コンパイラのバージョンのあったものを参照してください。GCCのC++コンパイラへのパスが通っていればg++ -vのコマンドで確認できます。 ↩
わからない場合は調べてください。 ↩
CとC++であっても異なる言語とします。 ↩
自分のMacの環境では/usr/local/Cellar/gcc/10.2.0/include/c++/10.2.0/x86_64-apple-darwin20/bits/stdc++.hにありました。 ↩

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

前書き

環境

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