効率的な実装を自動的に見つけることは可能か

研究

最近は新しいアルゴリズムが提案されると，素早く実装する人が沢山いる．また，色々な実装を比較して情報を公開している人もたくさんいる．いずれにせよ，そこに多分の労力が割かれていることは間違いない．利用者側の立場からすると，「取り敢えず公開されていたから」という理由で，非効率的な実装を運悪く選択し，ボトルネックになっていると気がつかないで使い続けたりするのはなるべく避けたい．実装する側からすると，高級言語が隠蔽するライブラリの落とし穴にどういうものがあるのかは，把握しておきたい．
さて，なるべく労力を使わず，（非）効率的な実装を自動的に判別することは可能だろうか．例えばプログラム言語を限定して (C++ とか)，ある特定の問題を解く実装の中から，（例えば機械学習などを用いて）時間／空間効率の良い（悪い）実装を見つけることはできるだろうか．あるいは逆に，時間／空間効率の良い（悪い）実装を示唆する素性にはどのようなものがあるだろうか．
まず，直接的な素性としては，次のようなものがありそう（C++ での素性の例; 空間・時間効率のどちらに相関があるかは略）．

  • アルゴリズム: クラス名・関数名をアルゴリズムの signature として素性にする．性能を示唆する最も直接的な素性になりうるけど，問題ごとに対応するアルゴリズムの集合が違うので，うまく汎化できないかもしれない．部品（基礎的なアルゴリズム）の素性なら入るかな．例えば，ハッシュ関数が MurmurHash3 であるとか，文字列のソートに multikey quicksort を使っているとか．流行りものが好きなだけかもしれないけど．
  • データ構造: 変数の型を素性にする．連想配列で，キーの順序が不要なところで std::map を使ってるとか，std::vector を使ってるとか．文字列に std::string しか使っていないとか，キーが整数で密なのに連想配列にしてるとか，多次元配列を一次元配列で実装してるとか．
  • ささやかな工夫: 部分文字列を素性にする．局所的な文字列で捉えられる工夫は少ないかも知れないけど．後置インクリメントしかないとか，動的にサイズを変更するコンテナに基本型・ポインタ以外の型の要素が入っているとか．コンテナの要素のアクセスに Iterator を使っていないとか．dynamic_cast, virtual などが頻出するとか，構造体のメンバがバイト境界を無視して並べてあるとか．std::map の検索＋挿入で lower_bound を使ってるとか．オブジェクトを代入で初期化してるとか，コンストラクタで初期化リストを使っていないとか．関数の基本型・ポインタ以外の引数が参照渡しになっていないとか．コンテナで reserve, rehash してないとか．シフト演算が頻出するとか．iostream で大量の入出力を行っているとか．const 修飾子の数とか．多次元配列の要素をアクセスするループで局所性を考慮してるかどうかとか，else if がひたすら連続してるとか，動的メモリ確保を繰り返す・・・キリがない．細かいところを気にする人は，アルゴリズム／データ構造の選択も意識してやっていそう（単に蛸壺的な状態かもしれないが）．

さらに，間接的な素性としては以下のようなものがありそう．

  • 実装者: 実装者名を素性にしてみる．実装能力の高い人は有限の教師つきデータでも有意に観測されるかも知れない．関与したソフトウェアで二部グラフを作って Random Walk（ワンパターンか）．
  • コンパイル情報: コンパイルして warning が出るのに放置されてるとか (gcc なら -Weffc++ で Warning が出ないとか)．構文木に対して Tree kernel を使ってみたり．最適化オプションを変えた際のバイナリのサイズの変化とか．
  • ドキュメント: プログラムの完成度と相関がありそう．
  • バージョン: 時系列的に見て開発が active か inactive か，相対的に見てバージョンが初期より十分上がっているか，など．
  • その他: 公開サイトから得られるダウンロード数など．

教師つきデータには，ベンチマークの結果（実装と空間／時間効率の指標のペア）を直接入れてもいいし，いつも速い実装をする人，あるいは実際に高速な実装を少数入力して半教師あり学習で解いても良いと思う．
研究室の壁を壊す物凄い音にさらされながら，そんなことを妄想していました．
[追記] スクリプト言語は，地雷だらけ（各プリミティブの守備範囲が広く，高機能で，かつ互いに重複することもあったりして，使い方によっては激しく遅い）という印象なので，未知の素性が相当数見つかりそう．split 使わず正規表現で区切ってるとか，正規表現をコンパイルしていないとか（とても把握しきれないし，そもそもスクリプト言語で効率に関するエンジニアリングを細かいところまでやるのは無駄）．多様性は善とする perl の方が例えば python などに比べると，地雷（効率に負の相関を持つ素性）はたくさん見つかりそうな予感．