<div style="margin: 2em 0; font-size: 3rem">
# Tree-shaking 付きの <br /> 競プロ用 C++ バンドラーを <br /> 作った話
</div>
りすりす/TwoSquirrels
----
<img src="https://github.com/TwoSquirrels.png" alt="" style="height: 6em; float: right;" />
## 1. 自己紹介
<span class="note">
<早口>
traP っていう競プロやゲーム開発や Web 開発からグラフィックやサウンドまで、PC でできる創作すべてをやっているクソデカサークルに所属しているりすりすと申します。
AtCoder はここ 2 年以上ずっと水で停滞していてそろそろ青になりたいという感じです。プログラミング全般が趣味です。
</早口>
それでは本題に入らせていただきます。
(0:30)
</span>
- 名前: **りすりす/TwoSquirrels**
- 所属:
- **VRC 競プロ部**
- 東京科学大学 経営工学系
- 東京科学大学デジタル創作同好会 **traP**
- 趣味: <img src="https://md.trap.jp/uploads/upload_8a74855b5a0d204bb1f9441b3fb85ef2.png" alt="" style="height: 5em; float: right;" />
- **プログラミング全般**
- 深夜アニメ
- お絵描き
----
## 2. バンドラーとは
<span class="note">
突然ですがみなさん、バンドラーという物を知っていますか？
Web 開発とかしてるとよく使うんですが、複数ファイルにまたがったソースコードを 1 つとか少数のファイルにまとめるツールのことをバンドラーと呼ぶんですね。
Web 開発では通信量を削減するってのがめちゃくちゃ大事なので、読み込むファイル数は少ない方が嬉しくて、そのために開発者があらかじめバンドルして、さらにコードを短くする minify とかして限界まで軽くしたファイルをサーバーに置いておくとかしてるんですね。
そしてこのバンドラーっていうのは Web 開発とはかけ離れた競プロでも使われていて、C++ で競プロしてる人なら使ったことある人多そうなんですが、競プロでジャッジサーバーにインストールされていないライブラリを使いたいってときに、もちろん include するだけじゃジャッジはコンパイルに失敗するので、ライブラリのコードを提出コードに埋め込みたいんですね。こういう時に競プロ用のバンドラーが活躍します。
まずはこの C++ のバンドラーがどういう仕組みで動いているのかを解説したいのですが、まずはその前提知識を...
(2:00)
</span>
- **複数ファイルにまたがるソースコード**を、
何らかの目的のために**まとめる**もの
- Web 開発でよく使われる
- 通信量削減のため
- ついでに minify 等の圧縮をすることも
- 競プロでも使われる
- **ライブラリを使った解答を提出するため**
----
## 3. C++ の `#include` の仕組み
<span class="note">
C++、まぁ C からなんですが、実は include って単なるファイル展開にすぎないんですね。知ってましたか？
たとえばこんな main.c と pi.csv があったとして、なんとこれはコンパイルが通ります。配列の初期化部分に csv の数列が展開されるって感じですね。
別に今回作ったバンドラーはこういう include には対応してないですけどね。
ただこの仕様を使えば、実は C++ のバンドラーって結構簡単に作れちゃうんですね。
(2:30)
</span>
実は C/C++ の **`#include` は単なるファイル展開**
<table style="width: 100%;"><thead><tr><th>
`main.c`
</th><th>
`pi.csv`
</th></tr></thead><tbody><tr style="font-size: 1.25em;"><td>
```c=
int pi_decimal[] = {
#include "pi.csv"
};
```
</td><td>
```csv=
3, 1, 4, 1, 5,
9, 2, 6, 5, 3,
5, 8, 9, 7, 9,
```
</td></tr></tbody></table>
なんと、これは C/C++ で valid！
----
## 4. C++ バンドラーの仕組み
<span class="note">
C++ のバンドラーはコンパイラの include の挙動を再現してあげればよくて、例えばこんな感じで main.cc が dsu と modint を include していて、modint は内部で internal_math を include してるよみたいな状況の場合、include が出てきた時点でそのファイル内に潜って同じことを再帰的にして展開すればいいんですね。要は DFS です。ACL に付属してる expander.py とか、有名な競プロ用 C++ バンドラーである oj-bundle はこの仕組みで実装されています。
(3:10)
</span>
コンパイラが行う **`#include` の展開を再現**する
```graphviz
digraph G {
rankdir=LR
bgcolor="transparent"
node [fontsize=24 color="white" fontcolor="white"]
edge [label="#include" fontsize=20 color="green" fontcolor="green"]
"main.cc" -> "dsu.hpp"
"main.cc" -> "modint.hpp"
"modint.hpp" -> "internal_math.hpp"
}
```
**DFS をしながら展開**すればよい！
実際に ACL の `expander.py` や oj-bundle はこれ
----
## 5. C++ バンドラーの問題点
<span class="note">
ただこの手のバンドラーって問題点があって、無駄な include をするとその分コードが無駄にでかくなるってことなんですよね。例えば ACL の全ヘッダーを一括で include できる atcoder/all を include しただけで、これ展開すると 60 キロバイトもいっちゃうんですね。ここには書いてないんですが ACL 入ってない Codeforces とかも 64 キロバイトまでしか提出できなかったりするので、解法含めると提出ができないとかよく聞くんですよね。yukicoder や AOJ は今は ACL に対応してるからそれはいいのですが、とはいえテンプレによく使う ACL 以外のライブラリをやみくもに include してたりすると同じ問題にあたると思います。
他にも提出コードに関係ないコードが沢山あって後から読みにくいだとか、ジャッジのコンパイル時間が長くなるだとか、そういう問題もあったりします。
なので、都度必要なライブラリの include を書いたり、もしくは include は普段はコメントアウトしておいて必要な時だけコメント外すとかしなきゃいけないんですが、まぁめんどくさいですね。
僕はこれが嫌で今までライブラリ整備をしていませんでした。しかし流石にそろそろテンプレに取捨選択して詰め込むのをやめてライブラリ盆栽をする必要性を感じてきたので、この問題を解決できるバンドラーを作ろうと思いました。
(4:30)
</span>
- **ライブラリは全部展開するものではない**
- <code style="font-size: 0.75em;">#include <atcoder/all></code> するだけで 60 KiB
- Nyaan Library は全部で約 900 KiB
- Codeforces, yukicoder, AOJ は**提出制限 64 KiB**
- コード長制限に収まって提出できても...
- **関係ないコード**が沢山あって**読みにくい**
- ジャッジでのコンパイルに時間がかかる
- 毎回適切に **`#include` を書き直す**必要がある
----
## 6. Tree-shaking がしたい！
<span class="note">
僕、Web 開発もしてるんで、Web のバンドラーをよく触るんですよね。Web のバンドラーって、Tree-shaking っていう、使われていないコードを自動で検出してその部分をバンドルから省いてくれるっていう機能があるんですよ。
そこで僕は、この Tree-shaking が競プロ用の C++ バンドラーでもできたらいいなーって思ったんですよ。でも調べてもそういうの見つからないんですね。それもそのはず、これちゃんとやろうとすると結構難易度高いんですよ。雑にやろうとすると、C++ って define マクロとかいうののせいで、そもそも正確なパースが難しかったり、他にも ifdef 周りの扱いも考えなきゃいけなくて、難しいと。
でも、ひらめいてしまったんですね。プリプロセス後の C++ コードを使えば行けるんじゃね？ って。あ、でもいま、プリプロセスってなんぞやって思った人もいると思うので、一応解説しておきます。
(5:30)
</span>
- Web バンドラーでは **「Tree-shaking」**
という技術でバンドルサイズを削減している
- これを競プロ用 C++ バンドラーに輸入したい
- 雑にやると**マクロ等に弱い**
- **プリプロセス後**なら扱いやすいのでは？
- マクロや `#pragma` の考慮が不要に
----
## 7. プリプロセスとは
<span class="note">
C/C++ のビルドコマンドを叩いたとき、内部ではざっくり 4 つのフェーズが走ってるんですね。その内一番最初のフェーズがこのプリプロセスで、何してるかって言うと、# から始まる行、こういうのディレクティブって言ったりするんですが、これの処理をします。define の置き換えだったり、include の展開だったりをやります。なので、まぁこれも一種のバンドラと言えるかも？
で、clang とか gcc って、E オプションってのがあって、これ使えばプリプロセスだけができるようになってるんですよ。これ使えばマクロとかいうめんどくさい物が全部処理された状態のコードが出てくるんで、これを元にコードを解析すればそこそこ正確にできるんじゃないかなって。具体的にはこんな感じでやろうと思いました。
(6:20)
</span>
- C/C++ のビルドは大きく 4 つのフェーズから成る
1. **プリプロセス:** ディレクティブ `#` を処理
2. **コンパイル:** アセンブリに変換
3. **アセンブル:** 機械語に変換
4. **リンク:** 実行できるように仕上げ
- `clang` や `gcc` は `-E` オプションで
プリプロセスだけが可能
----
## 8. ファイル単位の Tree-shaking
<span class="note">
まずあらかじめ、Tree-shaking したいライブラリに入ってるヘッダファイルそれぞれについて、そのヘッダでどんな識別子が作られてるか、つまりそのヘッダによってつくられている関数やクラスの名前の一覧を持っておきます。
そしてバンドル時にはまずプリプロセスをするのですが、プリプロセスって元のファイルの境界部分に、ここから下はもともとこのファイルの何行目からだったよーってメモを残してくれるんですよ。これを頼りに、まずは main ファイルで使ってる識別子一覧を列挙します。
そうすると、依存してるヘッダーがどれかってのが分かるんですよ。そしたら、プリプロセス結果から、依存してるヘッダーと、そのヘッダーが include してるファイルだけを残して、それ以外のファイルだった部分は全部消してくんですね。
こうすればある程度は Tree-shaking が実現できるのではないかと。というわけでこれ、実際に作ってみました。
もちろんこの方法だと main で使ってる変数名がライブラリ内部用の変数名と被って誤検知とかも普通にありえるので、完璧な Tree-shaking ではないんですけど、一応そういう微妙なのは全部、コードが壊れないのが第一ということで過剰検出側に倒して設計してます。
(7:40)
</span>
- 予め、**ライブラリの**それぞれのファイルで
定義されている**識別子一覧を持っておく**
- **main の**コードで使われている**識別子から、
依存ヘッダーを列挙 (間接依存も)**
- プリプロセスがファイルの境目に残す
ファイルパスを元に**不要ファイル部分を削除**
- 識別子頼りなので正確な依存判定は難しい
- 安全な過剰検出側に倒した
----
## 9. risundle v1.0.0 完成！
<span class="note">
実際作るにあたって、せっかくなので言語は Rust を採用してみました。とはいっても、僕が書いた仕様案を Claude Code にぶん投げて、細かい仕様や設計なんかを議論し合いながら Claude に Rust を書いてもらったって感じで自分はほとんど Rust 書いてないんですがね。
ただ、結構ちゃんとしたツールが出来上がって、バンドルも Tree-shaking も想定通りちゃんと動いてくれたんで、公開してみました！ Rust が入ってるなら cargo install risundle でインストールできるはずです！ みなさん使ってみて欲しいです。細かいことは README とか見てください。
(8:20)
</span>
- oj-bundle のように使える CLI が欲しい
- せっかくなので高速・安全な Rust で作った
- 実装はほとんど Claude Code に任せた
- **`cargo install risundle`** でインストール
- **C++ 競プロ勢は是非使ってみてね**
- 使い方など詳細は `README.md` 参照
----
## 10. risundle のデモ
<span class="note">
では実際に使ってみるとどんな感じなのか見てみましょう！
</span>
ACL の登録をするコマンド
<img src="https://md.trap.jp/uploads/upload_fb0a784b0af9138cf21c721ca1af1724.png" width="100%" />
----
## 10. risundle のデモ
<code style="font-size: 0.75em;">#include <atcoder/all></code> したが <code style="font-size: 0.75em;">modint</code> しか使わない例
<img src="https://md.trap.jp/uploads/upload_cc72d0c1e2a6a5b64a2239ccad8f60bc.png" width="50%" style="float: right;" />
- 全ヘッダー結合は
**約 36500 行**
- 初回実行時は std の
登録処理が走るが
2 回目以降は**超高速**
- バンドル結果は...？
----
## 10. risundle のデモ
risundle ならなんと **600 行！**
<img src="https://md.trap.jp/uploads/upload_c54c233ceff9aa739a68f2a644a7ed57.png" width="75%" />
----
## ご清聴ありがとうございました
<center style="margin-top: 4em; font-size: 0.5em;">
**`cargo install risundle`** してね！
</center>
<style>
div:has(> .note) {
text-align: left;
.note {
position: absolute;
font-size: 0.4em;
background-color: #333c;
color: #fff;
}
}
.reveal {
/* background-color: #000000; .slides { background-color: #191919; } */
section {
text-align: left;
padding: 0;
}
ul {
display: block;
}
strong {
color: #ff99cc;
}
.graphviz {
background-color: transparent;
}
.note {
display: none;
}
}
</style>