toml11はしばらく前に開発して、最近も結構いじり続けており、それなりの数のユーザーがついてるっぽくて結構嬉しくなっているライブラリだ。そもそもが自分のために作ったものなので、自分の都合で結構改変することがある。これは、まあレポジトリのオーナーなので当然と思っているし、作者が困ることは大体ユーザーも困るだろうから、むしろ放置するより良いことだろうと考えている。*1
折角これを作っているので大体自作のアプリケーションではtomlを使っているのだが、そこに自動生成した5万行のtomlファイルをぶち込んだら、パースが終わるまでに3分ほどかかった。これは流石に遅い。実際の計算は何時間、何日というオーダーでかかるので3分は誤差なのだが、設定ファイルが正しくてちゃんと動くことを確認したいだけ、という場合が考えられる以上3分は遅すぎる。この5万行というファイルサイズはそのプロジェクトでそんなに例外的に大きいわけではなく、まあそういうこともあるよね、という程度なので、これくらいならせめて5秒以内くらいに終わって欲しい。
というわけで、3分を3秒まで高速化した。
雑感
元々のコードはどちらかというと、速度面に関しては深く気にしておらず、流石にアホすぎるコードは書かないようにしようくらいの気持ちでしかなかった。設定ファイルの読み込みがホットスポットになるケースはあまりないと思われるからだ。ホットスポットでないなら、求められるのは速度ではない。やっていることは設定ファイルのパースなので、どちらかというと求められるのはエラーメッセージのわかりやすさや、コードの書きやすさだと思っていたからだ。今もそう思っているが、遅いと感じた以上少しは高速化しなければならない。
既に結構最適化されているコードを追加で最適化するとなると長丁場になる。初期からある程度最適化が行われている以上、現在地点からあまり大きく変更せずにたどり着ける局所最適くらいまではたいてい既にたどり着いているからだ。プロファイルを取っても実行時間は均一でホットスポットはない。ここから速度を上げようとすると、ライブラリを変えるくらいで済めば良いほうで、コンポーネントのそれぞれを少しずつジリジリと高速化していって最終的に全体を速くするか、設計を変える（つまり書き直し）レベルの変更が必要になることが多い。時代背景が違うコードなどは最初のコードをほぼ完全に捨て去ることで2倍くらい速くできたケースは何度かあるが、遅くなってしまうこともなくはないので、結果が出るまでが長い博打になってしまってつらいものがある。それも2倍程度の高速化のために。100倍なら喜んで何週間かベットするんだけどな。
対して、最初はあまり速度のことを考えていなかったコードを高速化するのはかなり簡単だ。プロファイルを取れば大抵ホットスポットが明確に決まるし（一つの関数が実行時間の8割を占めているなどはザラだ）、そういう場合は始めてすぐに10倍とか100倍速くなったりする。世の中の最適化に対する教えや金言、曰く「早すぎる最適化は悪」とか、「80−20の法則」とか、「〇〇（不向きなデータ構造やアルゴリズム、ヒープアロケーション、割り算、etc）を避けよう」とかそういうやつは、大抵この場合のことを指している。そこを見誤ると一向に性能が上がらなかったりするので注意したい。速くなりようがないようなまずい設計で全体を作ってしまった場合は部分的にでもいいから設計からやり直すほか無いのだが、「動いてるコードに手を入れるな！」「一から書き換えるのは悪手！」みたいなのと共にそれを封じられる場合がある。
動いているコードに手を入れるコストを下げるために自動テストがある（「動いているコードに手を入れるな」、と思考停止で言ってくる人が権限を持っているレポジトリには大抵テストコードはない（偏見））。そもそも何かしらのテストがなければ、動いていることは何の保証にもならない。動いているが間違った答えを返し続けている可能性は普通にある。テストされている分しか実質的に保証できないなら、手を入れてテストが通ったなら、何の問題があろうか？ また、一から書き換えるのは確かに悪手であることが多いが、規模（機能の数など）が小さければ問題にならないし、速くするためには実質的に書き直すしかない場合もそれなりにある。その上で書き直しを選択するかどうかは議論が必要だが、即却下するよりは少しは考えてみたほうがよい。
「早すぎる最適化は悪」というのは、最適化の主戦場がアセンブリレベルのバイナリハックで、最適化するとマジで全く何をしているか何もわからないコードになっていた時代に発せられた金言であり、コンパイラがそのかなりの部分をこなせるようになった今となっては、誤った文脈で引用されて人々の動きを止めてしまうことの方が多いように感じる。最初に最適化しづらい構造にしてしまうと尾を引いてしまうので、細かいトリックはしなくていいから、全体の見通しの立てやすい、あとで取り替えの効く疎結合な設計のために最初に少しは時間を割いた方がいい。そもそも、「最初から変なトリックで最適化するよりもちゃんと綺麗でわかりやすいコード書いとけ」という話なので、設計をちゃんと考えようという主張にこれを持ち出して「何でもいいからとっとと書け」というのは筋が悪い。
設計を決めるときに一般的に適用できるソフトウェア的ツールや考え方はあまりない。ないものは伝えられないし、強いて言うと大規模なコードをメンテ・高速化した経験や計算機科学と低レイヤーの知識、コードが解こうとしている問題への理解度くらいしかないので、無理に言及すると「勉強しつつ経験を積み、コードの内容を理解しましょう」という身も蓋もない話になってしまう。なので簡単でバズるTipsは局所最適のためのツールに終止するわけだが、このせいで世の中のプログラムは鈍重になっているのではなかろうかとすら思う（私の観測範囲はかなり特殊な分野に限定されているので、真の”世の中の”プログラムはもっとまともだと信じたいが）。
本題
さて、金言に対してさんざんなことを書いてはみたが*2、今回は最初は何も考えていなかったケースなので、広く知れ渡っている金言が全部おもしろいくらいに当てはまる。普段既に結構最適化されているプログラムをさらにねじって絞り切るような最適化をしているので（手が痛くなってやめることが多い）、普通の最適化はこんなに簡単なのか！ と笑みすらこぼれた。
まず、こちらはいかなる場合でも常に成り立つ最適化の金言、「推測するな、計測せよ」を実行した。ただでさえ遅いコードをvalgrind --tool=callgrindに渡したので非常に時間がかかった（典型的には数十倍遅くなる）。だが待ってみただけのことはあった。
とはいえ何も考えずに待っているのも暇だし、勘を養うために（養えるかはともかくとして）予想は立ててみた。まず、toml11はエラーメッセージを綺麗にすることを目標の一つにしている。なのでエラーメッセージに比較的重めの処理が入ることを許容していた。さらに、toml11のそれぞれのサブパーサ、parse_valueやparse_integerなどは、失敗するとエラーメッセージを返すのだが、parse_valueはどの型の値が入っているか調べもせずに成功するまで全ての型のパーサを呼ぶ（これはトークナイザをしっかり作りこむのと比べてあまり賢くないというのはわかってはいる）。ここでは文字列の連結などの操作をたくさんするので、そこで小さなヒープアロケーションが頻発するのが主な問題なのではなかろうか、と考えていた。解決策としては、エラーメッセージの定型を整理して、前もってスタックに用意しておいたバッファにstd::snprintfなどで書き出してから、そのバッファをstd::stringに渡せばいいだろうか、と考えていた。
さて、蓋を開けてみたところ、この予想は半分外れていた。parse_valueがparse_stringやらparse_integerやらを手当り次第に呼ぶことによるエラーメッセージ地獄というのは当たっていたが、問題になっているのはヒープアロケーションではなかった。エラーメッセージに書き出すための行数カウンﾄだったのだ。これが全体の98％ちょいを占めていた。98％ちょいって全部じゃん。
基本的に、toml11はまずファイル全体を読み込んでおいて、それをtoml::valueで共有管理し、パースが終わった後もエラーメッセージのために定義箇所付近を辿り返せるようにしている。このためにパース途中もイテレータをラップしたlocationというものを関数間で受け渡しつつパースを進めているので、エラーメッセージは基本的にこれの位置に基づいて出力することになる。パースに成功したら、範囲を表すregionを作ってtoml::valueに渡している。
このlocationやregionからエラーメッセージを生成するとき、何行目でエラーが起きているかを表示するために、行数を取得するメンバメソッドを用意してある。これは単純な作りで、std::count(begin, current, '\n')を返すだけだった。そしてこれが実行時間の98％だった。5万行ともなれば、流石に一行に10回も改行文字の数を数えてたら時間も食いますわな。
というわけで、locationを少し改造し、イテレータを進める・戻す操作の際に必ず改行回数の増減をチェックし、行数を取得する関数は単にカウント済みの値を返すだけにした。するとこの98％ちょいがまるごと消え去り、全体が60倍速くなった。
な〜んだ、最適化って簡単じゃん！（既にある程度最適化済みの大規模な数値計算のコードを見て絶望する）
高速化後のプロファイルも見てみたが、これの他にはそこまで目立ったものはなかった。他に時間を食っているのは出力とヒープアロケーションのようで、まあ順当ではあるがずば抜けて時間を食っているわけではないのでもういいかな、という具合だった。
この手の高速化を1、2回やると、大体残りはどんぐりの背比べになってしまって、明確なホットスポットはなくなる。なのでこれ以降の最適化はつらく厳しい戦いになってしまい、難しい割に10倍も速くならないので、大体ここで引き返すことになる。だが、本気で最高に速くしたいならここからが本番でもあるのだ。一つ一つをジリジリ1.5倍くらいずつ速くして最終的に全体を1.4倍くらい速くする、みたいなのを2回根性でやり通せば、「2倍速くなりました！」と宣伝できる。とはいえ、最初のコードに例えばキャッシュヒット率やSIMDなどの特殊命令や冗長な演算などの考慮漏れがなければ、1.5倍高速化するのは不可能なのだが。
まあ、今回は十分速くなったので、これ以上はやらない。なのでここでとりあえずこの話は終えることができる。設定ファイルの読み込みが大抵のプロジェクトでホットスポットではないのは、その意味ではありがたいことかもしれない。
