競技プログラミングでRuntime Errorを防ぐためのvalgrindとfsanitizeオプション

この記事は Competitive Programming (1) Advent Calendar 2018 1日目の記事として書かれたものです。
それと、僕がこのツイートで大きい騒ぎを起こしてしまったことへの贖罪です。

##C++のプログラムの「不確かさ」
C++では配列の長さなどが静的であり、配列外参照をした場合に条件によってはランタイムエラー (RE) を起こしてしまいます。また、変数を未初期化の状態で使ってしまうと、REを起こさずにプログラムが誤った出力を返してしまう可能性があります。必ずREを起こすならば、そのような場所を特定することは容易ですが、エラーが起きたり起きなかったりする場合はデバッグが困難になってしまいます。このことから、REによるバグには時間が取られてしまう傾向にあります。

配列外参照や未初期化変数参照が起きる可能性のある場所が事前にわかれば、バグを特定して直すことは簡単になります。これを実現するツールとして、valgrindと-fsanitizeオプションを紹介します。

-fsanitize, valgrindの重要な点は、REするかどうかを事前に知ることができることです。これらで事前チェックした時にエラーが発生している場合は必ずバグっています。特にペナルティのあるコンテストでは、必ずREするコードを提出せずに済みます。

この記事では実際に競技プログラミングでREを起こした提出を-fsanitizeオプションとvalgrindで解析し、実際にデバッグしてみます。

##記事を書いた動機と先行事例
現代的には、valgrindではなくコンパイルオプションに-sanitizeをすればよいという言及があります。これは、プログラムの重大なミスを検出するだけならば正しいと思います。一方、valgrindでは配列外参照がメモリの読み書きのどちらで起きたのかをも検出できます。また、未初期化変数の参照を検出することもできます。更に、warningでメモリリークを検出する機能があるので、競技プログラミングでは使えないかも知れませんが、実用的には利用されると思います。

今までにも、競技プログラミングでのREの自動検出は言及されてきました(ブログ1、ブログ2)。しかし、実際のREした問題に対してどのような挙動をするのかについては説明がされてきていませんでした。

-D_GLIBCXX_DEBUGを使って落ちたらgdbなどのデバッグツールを利用する方法があります(ブログ2)。-fsanitize, valgrindでは、gdbを利用するまでもなく問題の箇所が行レベルで解析できる点がメリットだと思います。

valgrindはgdbに比べると詳細な変数の中身の取得ができませんが、問題の箇所を全列挙することができて便利です。僕はvalgrindで見つけたバグの箇所を直すためにソースコードを眺めても、どういう条件で落ちているのかわからない時にgdbを使います。

「慣れると目で当てる方が早くなってくる人が一定数いる」という問題もあります。超優秀なエンジニアが小さいプログラムを組む時はそうかもしれません。しかし、競技プログラミングから少し離れて、複数人数で多少大きなC++プログラムを作る時はvalgrindでエラーと警告を監視し、それを徹底的に潰すことをルールにすると、安心感が全然違います。valgrindは歴史あるツールなので、使えるようになっておくと良いと思います（KotlinだのSwiftだのポンポン出てくる謎ツールと違って）。

その他の方法としては、assertやSTLのat関数も利用可能です。競技プログラミングでは、at関数を使うと複数次元DPの添字の表記が爆散することや、数学を直接コードに移すときに冗長な表記を除外したいため不便です。assertは配列外参照を起こしそうな位置全てにチェックを入れる必要があり、それが可能なほどの注意力を持っているならば配列外参照をそもそも起こさないプログラムを作ることもできてしまうと思います。

##-fsanitize, valgrindの使い方

• a.cppを用意します。
• a.cppのコンパイルの際に、-g -fsanitize=undefinedを付けてコンパイルします。僕はいつもclang++-3.5 -std=c++11 -g -Wall -fsanitize=undefined -Wno-deprecated -Wno-unneeded-internal-declaration a.cppでコンパイルしています。
• a.outが生成されます。
• ./a.outで実行します。この時、-fsanitize=undefinedが付いている場合、ランタイムエラーの原因を行番号付きで報告してくれます。

• valgrind ./a.outで実行します。この時、配列外参照が起きているメモリで、その読込時でエラーが起きているか書込時にエラーが起きているかを区別できます。また、どの関数から呼び出された時にエラーが起きているのかがわかります。

##-fsanitize, valgrindの比較
これらのRE防止ツールにはメリット・デメリットがあります。これらを以下にリスト表記でまとめました。+がメリット、-がデメリットです。

-fsanitize=undefined

• • 配列外参照が検知できる
• • 0除算、returnのない戻り値を要求する関数の終了、オーバーフローが検知できる。
• • 配列外参照が読みで起きているのか書きで起きているのかわからない
• • 未初期化変数の使用を検知できない
• • メモリリークを検出できない
• • 異常動作を起こす行の行番号しかわからない（どのような経路でそこに到達したかがわからない）
• • REする原因となりえる部分を全列挙できる（gdbでは1箇所見つけると止まってしまう）
• • プログラム実行が高速

valgrind

• • 配列外参照が検知できる
• • 0除算、returnのない戻り値を要求する関数の終了、オーバーフローが検知できない
• • 配列外参照が読みで起きているのか書きで起きているのかがわかる
• • 未初期化変数の使用を検知できる
• • メモリリークを検出できる
• • 異常動作を起こす行に到達した関数の経路がわかる（スタックトレース的な）
• • REする原因となりえる部分を全列挙できる（gdbでは1箇所見つけると止まってしまう）
• • プログラム実行が低速（体感10倍程度遅い）

##競技プログラミングでの利用場面
サンプルを-fsanitize=undefined, valgrindで確認して問題がなければ、かなり安心して提出できます。注意点としては、$n$行$m$列の盤面問題では、極端に$n \ne m$としたテストケースでないとバグが検出できない場合が多いです。

##デバッグテスト
ここでは、AtCoderでいくつかRE (Runtime Error)が出ているプログラムを手当たり次第にvalgrindにかけてサンプルを動かしてみます。それを元に、デバッグを試しに行ってみたいと思います。なお、コンパイルオプションはclang++-3.5 -std=c++11 -g -Wall -fsanitize=undefined -Wno-deprecated -Wno-unneeded-internal-declarationです。

AtCoder Beginner Contest 114 D - 756

https://beta.atcoder.jp/contests/abc114/submissions/3708441

valgrindを使うレベルの問題ではありませんでした。なお、Floating point exception時に、division by zeroの行数が出ています。これは-fsanitize=undefinedオプションによるものです。おすすめ。

AtCoder Beginner Contest 114 C - 755

https://beta.atcoder.jp/contests/abc114/submissions/3704470

valgrindを使うレベルの問題ではありませんでした。returnがないまま関数が終わってしまっているようです。ちなみにこのruntime errorでの説明文は、-fsanitize=undefinedオプションによるものです。このオプションがない場合、以下のように非常に不親切になります。

Dwango Programming Contest V / 第5回 ドワンゴからの挑戦状 予選 - C - k-DMC

https://beta.atcoder.jp/contests/dwacon5th-prelims/submissions/3655162

ランタイムエラーが一つのケースだけで出ていますが、検出できませんでした。こういうのは割とどうしようもないです。こうなるとvalgrindのメリットは、愚直解不要でテストケースジェネレータさえあればvalgrindを回すことができるくらいです。

Dwango Programming Contest V / 第5回 ドワンゴからの挑戦状 予選 - C - k-DMC

https://beta.atcoder.jp/contests/dwacon5th-prelims/submissions/3679762

valgrindを使うレベルの問題ではありませんでした。returnが無いまま関数が終わってしまっているようです。ちなみにこのruntime errorでの説明文は、-fsanitize=undefinedオプションによるものです。

AtCoder Beginner Contest 113 D - Number of Amidakuji

https://beta.atcoder.jp/contests/abc113/submissions/3537267

範囲外参照をしています。ちなみにこのruntime errorでの説明文は、-fsanitize=undefinedオプションによるものです。これによると、何らかの二次元配列の配列外参照を起こしています。15行目を見ると、そのような型のものはdpのみなので、dpが配列外参照していることがわかります。このことから、配列サイズを110くらいにしてやれば通ります。このvalgrindの出力を見ると、以下のように「配列外のメモリを読んでいるよ」という細かな情報を得ることができます。

###デバッグのまとめ
大多数は、基本的には-fsanitizeで十分であることがわかりました。valgrindは補助ツール程度に考えれば良いと思います。また、REしているケースがコーナーケースなど特殊な場合は、ランダムテストケースジェネレータとの併用が必要になることもわかりました。

##実際的な運用
僕は、信頼性が高い必要があるプログラミング（研究やロボットプログラミングや長い間動作するプログラム）では、valgrindでエラーもワーニングも出ないことを確認してからコミットしています。例えば、ロボットでは誤った挙動が物理的な実世界不確かさによるのか、未定義動作によるのか、確率的アルゴリズムの暴走なのか、そういうのを切り分けるのが大変なので、valgrindでの確認は重要です。また、長い時間動作するプログラムでは、メモリリークがあるとメモリをいつの日か使い果たしてしまう可能性があるので、ワーニングも消すようにしています。これは経験則ですが、ワーニングが出るようなC++コードは往々にして予期せぬバグを埋め込んでいるので、それを事前に除外することができることもメリットの一つです。

まとめ

この記事では、C++でランタイムエラーを防ぐための方法として、valgrindと-fsanitizeを紹介しました。REしたコードをいくつかデバッグする限りでは、基本的には-fsanitizeだけで競技プログラミング上十分ですが、valgrindを併用するとより詳細な情報が手に入るので、デバッグが容易になる可能性を示しました。REするコードを提出してペナルティを食らう前に、これらのツールで確認してから提出してはいかがでしょうか。