リソースは限られている

もう半年近く取り組んでいるアルバイトの案件が未だに終わらない。
大量のツイートの中かからパクリツイートを検出したい。
そのためのプログラムを作ってくれと言われたのが確か１０月頃だったろうか。
始めはPythonでたたき台を作り、それをC++で書き直した。どちらも初めて触れる言語だった。
１２月にはプロトタイプが出来た。ただし、この時はまだ一つのツイートに対してのパクリツイートを探す機能しかなかった。
これを全てのツイートに対してのパクリツイートを、つまり１対多の検索を多対多にしてくれと言われて年を終えた。

新年、期末試験を乗り越えた後にはプログラムの評価テストが待っていた。
何度もテストデータでプログラムを走らせていく内にソースコードは改良が加えられていった。
特に一番劇的だったのはデータの型を変えた時だ。

エラーや不良動作を起こした時にソースコードを見直しても変更点はそう多くない。
元々EmacsのFlymakeを使ってソースを書いているのでコンパイルは常に通るものとして動かしている。大体エラーの原因は文法的には正しい構造上の間違いや論理的なミスだった。for文を一個抜いたのにbreakを消し忘れて外のfor文を中断してしまっただとか、そんな形。
こういったデバッグ作業はコードの前でにらめっこしながらウンウン唸って探すしかない。
たまにエラー出力でcheck文を挟んだりしてソースのどこが問題なのか絞りながら、どうしてそこがおかしいのかを考えこむ。ようやくミスに気がついて、手を加える時はちょこちょこ行をいじるだけだ。

デバッグ作業とは対照的に、ソースを改良すると換骨奪胎の様相を見せる。
なんというか、コードの風景が変わるんだ。
処理が遅い、ソースがスパゲッティになってしまった。こういう時にアルバイトをさせてもらってる研究室の先生に教えを請う。すると「そういうときはmapを使うといい」「それならsetがいいんじゃないかな」と適切なアドバイスをしてもらえる。
するとどうだろう、あれほど入り組んでいた面倒な処理がたった２，３行で済んでしまうのだ。
for文を２回も３回も書く必要はないし、無駄なソートをすることもない。
僕が「ここはどうしよう」とか「こういう処理をしたいんだけどなぁ」と考えていたことは既にデータの構造がうまく処理してくれている。
しかも得られるメリットはそれだけじゃない。
intが整数でstringが文字列だというように、そのデータの型を見れば大体の見当がつく。
ごちゃごちゃと長い処理を書く必要もなくなり、僅かな変数の宣言とメソッドが全てを可能にしてくれる。
短いコード、明確なデータ構造は僕が何をしたいのか、それを全て簡潔に表してくれる。
この作業によって僕のソースコードからはコメント行がかなり減ったと思う。

僕がプログラミングを好きだと言えるのは、この経験とあともうひとつ、実行速度がグンと上がったのを直に見れるからだと思う。
プログラムの処理速度はとても重要な問題だ。
実際問題僕が取り組んでいる課題は最終的には１億8000万ツイートを処理にかける予定になっている。
テスト用の小さなデータにちんたら時間をかけているようでは話にならない。
わざわざPythonで書いたものをC++に書きなおしたのもそれが理由だ。
僕が一番最初に書いたソースは、悲しいほどに遅いプログラムだった。
何回か行った計測から予測したところ、10年経っても終わらない計算になってしまう。
なんとしてでも速度は上げなければいけなかった。
小手先のテクニックでもなんでもいいから、C++の速度を上げる方法を僕はかき集めなければならなかった。
ここでもやっぱり一番効果を発揮したのはデータ構造だった。
そもそもさっき書いたソースの改良というのは、元々は速度向上のための作業だった。
それがどうしたことだろう、いざ書き上げてみればコードが一変している。
その上速度も上がっているのだからもはや言う事は何もない。
手始めに行った１０００ツイートのテストは、若干低速ながらも順調に進んだ。

ようし、この調子で次の１００万ツイートのテストも！と思ったところで問題が生じた。
問題は速度じゃなかった。
１０００ツイートが終了した時点で既にこれ以上のツイート量では速度がネックになるのは目に見えていた。即座に改良にとりかかり無駄なデータや処理を取り除き、新たなデータ構造を取り入れることで一気にスピードの向上が実現した。
問題はメモリだった。
とりあえず一番軽い処理から順番に６つ一気にテストしよう、とアルバイト先のサーバに処理を投げ込んだらあっというまにメモリが枯渇した。
そんな馬鹿な、と思いつつ「でもメモリがなくてもスワップするだけだろうし、遅くなるだけで問題ないはず」とその時は悠長に構えていた。
１時間程度見守っていたところで気がついた。遅いどころの話ではない、処理が止まっている。
６つ同時に投げたプロセスの内、５つが死んでいた。残った一つも動いてるか怪しいような状況だった。
これはまずい、とすぐに全ての処理を停止させた。
頭を抱えたくなった。
テストは三つのパラメータをそれぞれ変えていき、５＊６＊６組、つまり１８０組のテストを実行しなければならない。
いくら速度を上げたとはいえ、一番早く済むものでも１時間はかかるはずだ。
だからこそ同時に処理を投げ込んだのだが、それが無理となると一つずつ実行するしかない。
仕方なく即興でシェルスクリプトを組んで前の処理が終了したら順次実行するようサーバに処理を投げた。シェルスクリプトに関しては付け焼刃だったがまぁ動けばいいだろう。
２日後、メールが届いた。
「サーバのメモリをこのプロセスが食い尽くしてほぼ死んでるのだが、これは君のだろうか。これから実験にサーバを使うので停止してもいいか」という内容だった。
寝耳に水どころの騒ぎじゃない。即座に止めてもらった。
ログはきちんと取っていたので調べたところ、３番目の処理で中断されていた。
つまり、軽い方から３番目の処理をする時点でメモリは食い尽くしていたことになる。
今度はメモリを減らさなければならない。

当初、あまり上手い方法は思いつかなかった。
試しにstringで数字を処理していたものをlong long intにしてみたり、どうにかこうにか内部にデータを溜め込まないよう外部へ吐き出す方法を考えたり。
どれもあまりうまくいかなかった。
けれどどうしても一つ、疑問に残る点があった。
そもそも動かしていたのは研究室で一番の実験用サーバだ。
いくら重い処理だからってそんな簡単に食いつぶすほどだろうか？
使えるメモリは２０Gを優に超えている。
処理に使う入力データは１Gもない。似ているツイートを探し出すためサイズが膨れ上がる出力データですら数G程度だ。なぜ何十Gもすぐに埋まってしまうのか？
long long int とstringを8byteと文字数*2byteのデータとして、総データサイズを計算しても数Gに収まる程度だった。
メモリが膨れ上がったのにはわけがある。どの処理の部分かを探すことにした。
すぐに見つかった、unordered_map >にツイートを挿入する処理だ。
先ほどの計算が正しいなら、挿入するツイートの量が多すぎるということはない。
では何がいけなかったのか。mapかset、どちらかに問題がある。
どちらか、といってどちらのほうがメモリを食うのかはわからなかった。
ただ、保持するデータ構造からいってmapの方がメモリを食いそうだなとなんとなく思った。

そういったわけでより少ないメモリで構築するmapを探し始めたのが今週の始めの話。
その省メモリmapを、なんとかかんとか実装して動かしてきたのが今日のこと。
結果は駄目だった。
手元の環境ではうまく動いた。サーバ側でも１０００ツイートなら一瞬だった。１万ツイートには数分かかった。１０万ツイートから様子がおかしくなった。１時間経っても終わらない。
いや、処理にかけるデータ量が増えたから時間がかかるだけだと自分に言い聞かせ、１２プロセスをサーバに投げ込んで帰宅した。
実際うまく動いた時は驚くほどメモリは使われなかった。本当にメモリを使ってるのかと疑わしいほどにサーバの使用メモリグラフは微動だにしなかった。
CPUの方には余裕があったから大量のプロセスを投げても問題はなかったが、それにしても12個ものプロセスを投げるのは初めてだった。
帰宅してからも1時間おきにサーバの稼働状況を確認した。
しかしCPUも、メモリも、全く変わらない。
4時間経って1プロセスも終わらないのをみて諦めた。
全プロセスを終了して、僕は自分が振り出しに戻ったような気になった。

これまで使っていたメモリを食いつぶすmapはBoost/unordered_map。
今回使用した省メモリmapはLokiライブラリのAssocVector。
まだ省メモリなmapとしてgoogle-sparsehashが残っている。
実はうまくいかなかった原因として、両方共ビルドがうまくいかなかったからじゃないかとも思っている。
動かしたプログラムはAssocVectorの中にあったヘッダファイルだけを抜き出してインクルードしている。きちんとビルドしたらまた違ったのかもしれない。
けれど、うまくいくかどうか自信はない。
この課題、本当に自分にやりおおせられるのだろうか。