ついカッとなって実行バイナリにパッチ - memologueとある都合で、ソフトウェア開発の際にソースコードの提供されていないツールを使うことになりました。x86なLinux上で動く、ちょっとしたtoolchainです。が、そのツールの処理速度が遅く、入力サイズに対して、結果が出てくるまでの時間がどうもO(N^2)かそれよりひどい。遅くてイライラするので、昨晩ついカッとなってパッチを当てました。そのメモです。また、ありがちな事態(?)な気もするので、みなさんどうしてるのかなー的なお伺いも兼ねて。 ボトルネックの特定 そのツール(以下A)の実行バイナリはstripされておらず.symtabが残っていました。のでまず、どこが遅いのかgoogle-perftoolsをLD_PRELOADしてそのソフトウェアを実行し、実行プロファイルを取りました。すると、嬉しいことにある一つの関数(以下F)で全体の90%以上の時間を消費していることがわかりました。関数Fは
