余算→加算・減算 - その２。

前回では、改善比率のみを示したが今回はより詳細を見ていく。

まず環境から。

graph：USA-road-d.USA.gr
query：ramdom P2P x 32

CPU : Xeon X5460 3.16 GHz (cache size 6MB)
Mem : 48GB
OS : CentOS 5.2 x86_64
GCC : GCC 4.1.2


続いて、ルーチン呼出回数である。
32 クエリ分の合計値であるので、かなりの回数を呼び出されていることが分かる。
427,087,609(delete + insert) = 26,557,718(delete) + 400,529,891(insert)

平均値を出しても、やはり大きい。
13,346,488 [times/query] = 829,929 [times/query] + 12516559[times/query]

余算を行う回数は、この値 427,087,609 (ave. 13,346,488) と等しい。


また「余算→加算・減算」としたことにより、
430,365,619 回の加算・減算、427,087,609 回の分岐が増えることになる。

平均を求めると、次の回数分演算が増えることになる。
13,448,926 [count/query]、 13,346,488 [times/query]


よって、次のようになる。
13,346,488 回の余算　＞　13,448,926 回の加減算 ＋ 13,346,488 回の分岐


こんなにも演算数増えてるにも拘らず 2.67 ％ 改善されていることを考えると、いかに余算のコストが高いのかがよくわかる。しかしながら、このままでもどの部分がどれだけ効いているのか判らないので、別にサンプルプログラムを作成し、演算コストも計測してみよう。