Include-what-you-useを使って過剰Includeを防ぐ【競技プログラミング】 #IWYU

Include-what-you-useとは

Include-what-you-use(IWYU)は、C-like言語(C,C++)のソースコードに登場する#includeを解析し、不要な#includeの削除や適切なインクルードタグの順番を提案指摘してくれるツールです。

Clangでのコンパイル用に作られていますが、競プロでよく使われるg++にも使えています。

この記事では、Include-what-you-useの利点からインストール方法、そしてどのくらい早くなるのかを紹介します。

何がうれしいのか

競技プログラミングは普段のコーディング作業に比べ、コードをテストする機会・回数が多いと思います。C++など実行するのにコンパイルが必要な言語では「ちょっとここをデバッグしたい」と思ったときに数秒のコンパイルを挟まなければなりません。

「数秒ならいいじゃん．．．」と思ったあなた。正直そうです。

ただ、コードが巨大になるにつれコンパイルの問題はコーディング作業により影響を与えると思います。

競プロでの`#include<bits/stdc++.h>`問題

AtCoderの記事(APG4b)にある通り#include<bits/stdc++.h>は「C++の機能を「全て」読み込むための命令」です。そのため、これを読み込むことによるコンパイル時間の増加が懸念されます。

一方で、同記事には「業務におけるプログラミングでは推奨されないことがありますが、競技プログラミングやAPG4bで利用する場合は全く問題ありません。」とあるように、競技プログラミングではコードを簡潔化させるため、またインクルードのし忘れの観点から推奨されています。

競技プログラミングでIWYUを使うことの意義はこの「#include<bits/stdc++.h>」で読み込まれたC++の機能の全てから必要なものだけを抽出することにあります。

環境

Ubuntu 22.04.4 LTS (WSL2)
g++ 11.4.0

$ cat /etc/lsb-release
DISTRIB_ID=Ubuntu
DISTRIB_RELEASE=22.04
DISTRIB_CODENAME=jammy
DISTRIB_DESCRIPTION="Ubuntu 22.04.4 LTS"

$ apt --version
apt 2.4.12 (amd64)

$ g++ --version
g++ (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0

インストール

以下のコマンドを実行します。

$ sudo apt-get update
$ sudo apt-get upgrade  # 必要に応じて
$ sudo apt-get install iwyu

バージョンを確認してインストールされているっぽい感じなら大丈夫です。

$ include-what-you-use --version
include-what-you-use 0.17 based on Ubuntu clang version 13.0.1-2ubuntu2.2

使い方

基本形

$ include-what-you-use <your_cpp_file.cpp>

ほとんどの場合、インクルードパスの不足で失敗します。インクルードパスを追加するには以下のように入力します。

$ include-what-you-use -I/path/to/your/includes -I/another/include/path <your_cpp_file.cpp>

この場合は/path/to/your/includesと/another/include/pathがインクルードパスとして探索されます。

パスの指定がわからない or エラー

以下のようなエラーが発生することがあります。パスの指定が適切にできていない可能性があります。

$ include-what-you-use main.cpp 

<path>::fatal error: 'float.h' file not found
#include <float.h>
         ^~~~~~~~~

以下のコマンドを実行して、いつも使っているコンパイラで使用しているインクルードパスを取得します。(g++の場合)

$ g++ -E -v -
    ~~~ (略) ~~~
#include <...> search starts here:
 /usr/lib/gcc/x86_64-linux-gnu/11/include
 /usr/local/include
 /usr/include/x86_64-linux-gnu
 /usr/include
End of search list.

#include <...> search starts here:から始まるパスがインクルード時に使用しているパスになります。上のほうが強いです。

したがってこの例では

$ include-what-you-use \
    -I/usr/lib/gcc/x86_64-linux-gnu/11/include \
    -I/usr/local/include \
    -I/usr/include/x86_64-linux-gnu \
    -I/usr/include \
    main.cpp

のようにすることで正しくパスを指定できます。AtCoder-Libraryを使用している場合はそのパスを指定しましょう。(/usr/include/にac-libraryのディレクトリを置くといちいち書かなくて済みます。)

使ってみる

簡単なプログラムで実験してみます。

main.cpp

// author: TsuruNoTsurugi
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;

int main()
{
    int N, K;
    cin >> N >> K;
    vector<int> A(N);
    map<int, int> mp;
    atcoder::dsu d(N);
}

このプログラムではiostreamのcin、vectorのvector、mapのmap(C++日本語リファレンスより)、さらにatcoderのdsuをプログラム内で使用しています。

$ include-what-you-use -I/usr/lib/gcc/x86_64-linux-gnu/11/include main.cpp

main.cpp should add these lines:
#include <atcoder/dsu.hpp>  // for dsu
#include <iostream>         // for basic_istream::operator>>, basic_istream<...
#include <map>              // for map
#include <vector>           // for vector

main.cpp should remove these lines:
- #include <bits/stdc++.h>  // lines 2-2
- #include <atcoder/all>  // lines 3-3

The full include-list for main.cpp:
#include <atcoder/dsu.hpp>  // for dsu
#include <iostream>         // for basic_istream::operator>>, basic_istream<...
#include <map>              // for map
#include <vector>           // for vector
---

上から、「追加したほうがいいやつ」「消したほうがいいやつ」→「それを踏まえた最終的なリスト」です。しっかりと使用しているライブラリのみインクルードする設定になっています。なお、順番も処理ができる限り軽くなるような順番にしてくれています。

どのくらい早くなるのか

timeコマンドを使って計測してみました。

$ time g++ main.cpp  # 変更前

real    0m1.506s
user    0m1.313s
sys     0m0.091s

$ time g++ main.cpp  # 変更後

real    0m0.449s
user    0m0.306s
sys     0m0.042s

実時間で1秒近く短くなっています。すごい。~~ま、Pythonには敵いませんが…~~

欠点

IWYUの実行にまあまあ時間がかかります。(←は?)
ただ、これを「コーディング→終わったらIWYU実行」ではなくコーディングしながら解析してもらう、とすることである程度改善します。

また、実装内容を大きく変更しないなら1回目の実装の終わりに一度だけ実行してインクルードを減らすという方法があります。

結果取得 & 自動改変

fix_includes.pyをダウンロードします。

$ wget https://raw.githubusercontent.com/include-what-you-use/include-what-you-use/master/fix_includes.py
$ chmod +x fix_includes.py

fix_includes.pyの112行目が

_INCLUDE_RE = re.compile(r'\s*#\s*include\s+([<"][^">]+[>"])')

となっていますが、

_INCLUDE_RE = re.compile(r'\s*#\s*include ?([<"][^">]+[>"])')

にしたほうがいいと思います。
そのままだと#include <bits/stdc++.h>が許容、#include<bits/stdc++.h>が不可になります。(それか、コード整形ツールを使うか)

fix_include.py使い方

まず、include-what-you-useの結果をテキストファイルなどに保存します。パイプラインを使うと便利です。
include-what-you-useのファイル指定はフルパスを推奨します。

$ include-what-you-use -I/usr/lib/gcc/x86_64-linux-gnu/11/include /home/ubuntu/main.cpp > iwyu_output.txt

結果が、iwyu_output.txtに保存されます。

> iwyu_output.txtは標準出力を取得(?)して保存します。私の環境ではinclude-what-you-useがエラーコードをはいて標準出力ではうまく取得できませんでした。その場合は、標準エラー出力から取得するといいです。

2> iwyu_output.txtと前に2をつけましょう。

つぎに、Python3環境でfix_includes.pyを実行します。

$ python3 fix_includes.py /home/ubuntu/main.cpp < iwyu_output.txt

fix_includes.pyを見ると、途中でパスを確認する部分がある(同ファイル2200行あたり)のですが、どうやらフルパスでないと通らないっぽいのでフルパスで書くのをお勧めします。

まとめ

#include<bits/stdc++.h>から本当に使うライブラリだけ、インクルードするとコンパイル時間がかなり短縮された。
実は、IWYUが遅い。
- いつ実行させるかを選ぶ必要がある。

私はAtCoder-CLIの機能をGUI化し(?)、パネルにまとめて使っています。ここにIWYUの機能を追加してみようと思います。

Include-what-you-useを使って過剰Includeを防ぐ【競技プログラミング】