gprofを使ってみた

Cで10分とか20分とか時間のかかる処理の高速化をやってみたけど、何よりまずはプロファイリングせよということで、gprofを使ってみた。gprofというツールがあることすら知らなかった。

% gcc -pg -Wall -lm -lpthread paint.c

のように「-pg」を付けてコンパイルする。で、

% gprof a.out

とするだけで、以下のように詳細な説明とともに各関数でどのぐらい時間がかかっていて、何度呼ばれてるか、というようなことが出てくる。コールグラフも表示される。

Flat profile:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls  us/call  us/call  name    
 70.71     38.24    38.24                             p_fill_circle
 27.29     53.00    14.76                             p_diff_buffers
  1.96     54.06     1.06     3720   284.95   284.95  clear_buf
  0.04     54.08     0.02                             main
  0.00     54.08     0.00   372000     0.00     0.00  fill_circle
  0.00     54.08     0.00     1001     0.00     0.00  delta_mutate_circle
  0.00     54.08     0.00     1000     0.00     0.00  full_mutate_circle
  0.00     54.08     0.00     1000     0.00     0.00  item_mutate_circle
  0.00     54.08     0.00        7     0.00     0.00  save_buf
  0.00     54.08     0.00        3     0.00   284.95  init_buf
  0.00     54.08     0.00        1     0.00   284.95  load_buf

 %         the percentage of the total running time of the
time       program used by this function.

cumulative a running sum of the number of seconds accounted
 seconds   for by this function and those listed above it.

           :
           :
           :

で、例えばclear_bufが無駄だと気づいて以下のように書き直したのだけど、

int clear_buf (buf *b) {
  int i, j;
  for (i = 0; i < b->height; i++) {
    for (j = 0; j < b->width; j++) {
      b->raw[i][j] = BGCOLOR;
    }
  }
  return 0;
}

#define clear_buf(b) memset(b->raw[0], BGCOLOR, sizeof(int) * b->width * b->hei
ght)

これによる高速化は、

  %   cumulative   self              self     total           
 time   seconds   seconds    calls  us/call  us/call  name    
 70.71     38.24    38.24                             p_fill_circle
 27.29     53.00    14.76                             p_diff_buffers
  1.96     54.06     1.06     3720   284.95   284.95  clear_buf
  0.04     54.08     0.02                             main
  0.00     54.08     0.00   372000     0.00     0.00  fill_circle
  0.00     54.08     0.00     1001     0.00     0.00  delta_mutate_circle
  0.00     54.08     0.00     1000     0.00     0.00  full_mutate_circle
  0.00     54.08     0.00     1000     0.00     0.00  item_mutate_circle
  0.00     54.08     0.00        7     0.00     0.00  save_buf
  0.00     54.08     0.00        3     0.00   284.95  init_buf
  0.00     54.08     0.00        1     0.00   284.95  load_buf

---

  %   cumulative   self              self     total           
 time   seconds   seconds    calls  us/call  us/call  name    
 71.62     36.87    36.87                             p_fill_circle
 28.27     51.41    14.55                             p_diff_buffers
  0.06     51.45     0.03                             main
  0.04     51.47     0.02   376300     0.05     0.05  fill_circle
  0.01     51.47     0.01        7   714.29   714.29  save_buf
  0.00     51.47     0.00     3763     0.00     0.00  clear_buf
  0.00     51.47     0.00     1001     0.00     0.00  delta_mutate_circle
  0.00     51.47     0.00     1000     0.00     0.00  full_mutate_circle
  0.00     51.47     0.00     1000     0.00     0.00  item_mutate_circle
  0.00     51.47     0.00        3     0.00     0.00  init_buf
  0.00     51.47     0.00        1     0.00     0.00  load_buf

1.06秒かかっていたものが計測不能（0.01秒以下）と100倍以上も高速化されたわけだけど、なんか全体からするとどうでもいい感じ。この例では明らかにマクロで済むところを2重ループの関数でやっていたので、そもそもコード自体も冗長だったから、マクロ化して悪いことは何もないけど、高速化という意味ではガッカリなぐらい効果は限定的。

結局のところ、このプログラムではピクセル単位で色々やってるところを高速化できないとどうしようもないということが分かった。

で、2枚の画像の差分を計算するときに、1ピクセル単位じゃなくて、適当に間引いてざっくり計算するようにしてみた。最初のほうはざっくりの計算でも、それなりに目的は達するだろうという予想だったけど、やってみると全然ダメで、画像の近似の仕方がめちゃくちゃになった。

あと考えられるのは、塗り替えた場所（毎回円が1つ分）だけを比較することだけど、これは面倒そうだし、差分を覚えておくためのオーバーヘッドも考えると高速化できたとしても5％程度じゃないかという気がする。

円の代わりに三角形にしたものを作ってみたかったけど、外積の計算が面倒くさそうだし、そろそろ飽きてきたしで、円を楕円にして近似精度が上がったことで満足して終わりにしよう。

オリジナル画像
円による近似（4万9000世代）
楕円による近似（3万世代）。エリの感じやおでこの雰囲気がだいぶでている