ボトルネックの検出 - その１。

grof は関数ごとの呼び出し回数・実行時間を計測してくれるとても便利なものである。gprof を用いて、ボトルネックを見つけていく。今回は p2p タイプを 10 クエリ解かせたので、dijkstra_with_heap が 10 回呼び出されている。各関数の説明は以下のようになっている。

・dijkstra_with_heap はダイクストラ法そのもので、関数の初めで作業領域を初期化している。
・heap_delete_min は次の探索点を決定する操作。ヒープから最少ポテンシャル点を削除する。
・heap_insert はヒープへ点を挿入する操作。
・heap_decrease はポテンシャルの更新に伴って、ヒープ内での位置を更新する。
・heap_node_swap ヒープ内で swap する関数


またヒープ法では swap の呼び出し回数と実行時間との関係は密接であるため、swap の最適化や、そもそも回数を減らすことが重要な課題と言える。そのため heap_node_swap() を 通常の関数、static inline と変化させることで、どの関数で swap が多く呼び出されているか見ていく。

すべて通常の関数

  %   cumulative   self                 self     total           
 time   seconds   seconds      calls   s/call   s/call  name    
 46.19     10.91    10.91         10     1.09     2.24  dijkstra_with_heap
 28.11     17.56     6.64  114552768     0.00     0.00  heap_delete_min
 16.87     21.54     3.99 1085558423     0.00     0.00  heap_node_swap
  2.86     23.17     0.68  114574250     0.00     0.00  heap_insert
  0.64     23.64     0.15    8103701     0.00     0.00  heap_decrease

heap_node_swap() のみ static inline で、インライン展開する。

  %   cumulative   self                self     total           
 time   seconds   seconds     calls   s/call   s/call  name    
 46.45     10.54    10.54        10     1.05     2.18  dijkstra_with_heap
 45.39     20.85    10.30 114552768     0.00     0.00  heap_delete_min
  3.37     22.55     0.77 114574250     0.00     0.00  heap_insert
  0.66     22.70     0.15   8103701     0.00     0.00  heap_decrease

heap_node_swap() に占めていた時間（3.99s）のうち、そのほとんどが heap_delete_min() に加算されているのがわかる。(6.64s→10.30s)
また heap_node_swap() の呼び出し回数を見ていく。

-----------------------------------------------
                0.02    0.00    4211496/1085558423     heap_decrease [11]
                0.11    0.00   29542100/1085558423     heap_insert [9]
                3.86    0.00 1051804827/1085558423     heap_delete_min [5]
[6]     16.9    3.99    0.00            1085558423     heap_node_swap [6]
-----------------------------------------------

やはりそのほとんどが heap_delete_min() から呼び出されているようだ。この部分をどうにか減らすことができれば、まだまだ高速化可能だといえる。insert, decrease が今よりも多少増えたとしても、heap_delete_min() 内の swap を大幅に減らせるようなデータ構造であれば純粋なヒープでなくても良いだろう。