問題解説: 永遠の国 第三のトラブル
問題文
村で様々なトラブルを解決したあなた達の評判を知り、トラブルを抱えているエルフの長の妻から依頼が来た。
長の妻「わざわざ来てもらってありがとう。今、娘の勉強用に新たな魔法を試してみているんだけど、何故か失敗しちゃうの。実験のときには動いていたんだけど……お願いできるかしら？」
エイト「この魔法っていうのはPHPのプログラムのことみたいね。長の奥様の頼みなんだからいつも以上に頑張りなさい！」
注意事項
- プログラムの編集は許可されている。ただし、プログラムで求めた平方根の二乗と真の値が、小数点以下8桁まで一致することを保証しなければならない。
- プログラムは最適化されている方が望ましい。
達成すべき事項
- プログラムを正常に動作させ、原因を特定する。
問題内容
サーバのアドレスにアクセスすると、以下のソースコードの Web ページが動作しています。
これは、トップページでフォームに値を入力するとその平方根を計算する PHP のプログラムです。平方根の計算にはニュートン法を使っています。
しかし、このプログラムのままではうまく動作しません。フォームに値を入力すると画面遷移が起こるのですが、ページが真っ白なまま何も出力しません。これが解決すべきトラブルになっています。
解説
メモリが枯渇している
まず、 /etc/php.ini で log_errors = Off になっているため、エラーログが出力されません。これを On にすると /var/log/httpd/error_log でエラーの内容を見ることができます。
PHP Fatal error: Allowed memory size of 33554432 bytes exhausted
このようなエラーが出るはずです。メモリが枯渇して確保できなかったと言っていますね。ここで Allowed memory size というのは、 php.ini で設定する PHP が使用できるメモリ量です。
というわけで、 php.ini を編集して memory_limit を適当に大きな値にしてやれば問題は解決する……のですが、トラブルの本質はここではありません。確かにそれで動作はするのですが、これではトラブルの原因を特定したことにはなっていません。
循環参照が起きている
では、なぜメモリの枯渇が起こるのでしょうか。その答えはソースコードにあります。 result.php を読んでください。これは、繰り返し計算の途中の値を画面に出力するための Result クラスを定義しているファイルです。
result.php の10行目を見ると、$this->val = $this; という部分があります。これはコンストラクタの中に書かれているので、 output.php の22行目で実行されます。ソースコードを読めばわかるように、これはプログラムの動作にとって論理的にはなんの意味もありません。うっかりミスで残ってしまった書き損じ（という設定）です。
論理的には意味がないこの文ですが、実はメモリ枯渇の原因になっています。というのは、ここで循環参照が発生してしまっているからです。循環参照とは、オブジェクトからオブジェクトへの参照を辿っていくと元のオブジェクトに戻ってしまうような状態です。オブジェクトが自分自身を参照している時や、複数のオブジェクトが相互に参照し合っている時に発生します。このプログラムでは Result クラスの val フィールドに $this が入ることでオブジェクトが自分自身を参照するので、循環参照になっています。
循環参照によってメモリリークが発生し、メモリの枯渇が起こってしまうプログラミング言語もあります。今回のトラブルで用いられている PHP 5.2 もそんな言語の一つです。よって result.php の10行目を削除するだけで問題は解決します。
参照カウント法では循環参照しているオブジェクトを回収できない
Ruby や Python をはじめとして多くのプログラミング言語にはガベージコレクション（GC）の機能がついています。 GC とは、いらなくなったメモリを自動的に解放する仕組みです。その手法はいくつかありますが、 PHP 5.2 には「参照カウント法」というアルゴリズムのみが実装されています。
参照カウント法では、全てのオブジェクトについて、それを参照するオブジェクトの数を数えメモリのどこかに保存しておきます。このカウントが 0 になった時、そのオブジェクトの使用していたメモリを解放するというアルゴリズムです。つまり C++ でいう shared_ptr にあたります。
参照カウント法は単純で実装しやすい手法なのですが、循環参照を起こしているオブジェクトのメモリを回収できないという欠点があります。そのオブジェクトのメモリが解放されない限りは、そのオブジェクトへの参照の数が 0 にならないからです。
PHP 5.3 以降ではこの循環参照に対する対策として、別の GC 手法を実装しています。したがってこのトラブルは PHP をアップデートするだけでも解決します。
ループによってメモリリークが蓄積する
今回、メモリの枯渇を発生させたかったので、プログラムは少々無理のあるものとなっています。ニュートン法で平方根を求めるプログラムですが、ループの回数が100000回と異常に多いです。さらに、10000回に1回しか途中経過を出力しないのに、毎ループで Result オブジェクトを作成しています。 Result オブジェクトは循環参照を起こしているので、ループの次の繰り返しで $result 変数の中身が置き換わってもメモリが回収されません。これによってメモリリークが蓄積し、メモリが枯渇します。
ループ回数を減らせばメモリが枯渇するほどはメモリリークが起こらなくなります。ニュートン法は収束が速いので、小数点以下8桁までなら10回程度のループで十分です。あるいは while ループにしても良いでしょう。
解答
ここまでをまとめると、解答は以下のようになります。
- 循環参照の起こる文を削除する
- 循環参照によるメモリリークを指摘する
加えて、ループの回数を減らしてプログラムの動作を速くすれば得点が追加されます。
参考
講評
永遠の国 第二のトラブルを解けたチームが uecmma だけであったため、解答は一つしかきませんでした。 uecmma の解答は満点の出来でした。また、プログラムの最適化をかなり頑張っていくれていました。
ただ欲を言えば、この問題が PHP 5.2 だけで発生するということを指摘してしてもらえると嬉しかったです。
トラブルシューティングコンテストでプログラミング言語を主題とした問題を出すのは場違いな感じがあります。しかし、メモリリークとその解決というのはトラブルとして面白いかなと思い出題しました。