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 が多く呼び出されているか見ていく。
すべて通常の関数
heap_node_swap() のみ static inline で、インライン展開する。
heap_node_swap() に占めていた時間(3.99s)のうち、そのほとんどが heap_delete_min() に加算されているのがわかる。(6.64s→10.30s)
また heap_node_swap() の呼び出し回数を見ていく。
やはりそのほとんどが heap_delete_min() から呼び出されているようだ。この部分をどうにか減らすことができれば、まだまだ高速化可能だといえる。insert, decrease が今よりも多少増えたとしても、heap_delete_min() 内の swap を大幅に減らせるようなデータ構造であれば純粋なヒープでなくても良いだろう。
・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 を大幅に減らせるようなデータ構造であれば純粋なヒープでなくても良いだろう。