関数の呼び出し回数（力技編）

gprofを使って，計算する方法を模索してみました．
基本的な方針は，fib(n)という，1引数関数でフィボナッチ数を求めるのではなく，fib(1)と同じ値を返す0引数関数fib1() *1，fib(2)と同じ値を返す0引数関数fib2()，…，fib(n)と同じ値を返す0引数関数fibn()を定義するというものです．そうすれば，fib1，fib2，…，fibnそれぞれの実行回数は，gprofで出せるわけです．
n=5で，手作業で作ったコードはこう．

/* fib5.c */
#include <stdio.h>

int fib1(void) {return 1;}
int fib2(void) {return 1;}
int fib3(void) {return fib2() + fib1();}
int fib4(void) {return fib3() + fib2();}
int fib5(void) {return fib4() + fib3();}

int main(void){
  printf("%d\n", fib5());

  return 0;
}

実行します．

$ gcc -pg fib5.c -o fib5
$ ./fib5
5
$ gprof --exec-counts fib5
<unknown>:0: (_fib1:0x401180) 2 executions
<unknown>:0: (_fib2:0x40118f) 3 executions
<unknown>:0: (_fib3:0x40119e) 2 executions
<unknown>:0: (_fib4:0x4011b9) 1 executions
<unknown>:0: (_fib5:0x4011d4) 1 executions

gprofを使って，mainを除く関数名ごとの実行回数を出力するには，--exec-countsオプションが手っ取り早いようです．Cygwinでも，Linuxでも，うまくいきました．
では次に，fib(n)のnを可変にしましょう．そのためには，プログラムを生成するプログラムを作ることにします．こうなりました．

/* fib+c.c */

#include <stdio.h>
#include <stdlib.h>

#define BINFILE "fib+p"

void make_cfile(int n)
{
  FILE *fp;
  int i;
  int digit = (n >= 10) ? 2 : 1;

  if ((fp = fopen(BINFILE ".c", "w")) == NULL) {
    printf("make_cfile: can't open\n");
    exit(1);
  }

  fprintf(fp, "#include <stdio.h>\n");
  fprintf(fp, "\n");

  for (i = 1; i <= n; i++) {
    if (i <= 2) {
      fprintf(fp, "int fib%d(void) {return 1;}\n", i);
    } else {
      fprintf(fp, "int fib%d(void) {return fib%d() + fib%d();}\n",
              i, i - 1, i - 2);
    }
  }

  fprintf(fp, "\n");
  fprintf(fp, "int main(void)");
  fprintf(fp, "{\n");
  fprintf(fp, "  printf(\"%%d\\n\", fib%d());\n", n);
  fprintf(fp, "\n");
  fprintf(fp, "  return 0;\n");
  fprintf(fp, "}\n");

  fclose(fp);
}

void profile_cfile(void)
{
  system("gcc -pg " BINFILE ".c -o " BINFILE);
  system("./" BINFILE);
  system("gprof --exec-counts " BINFILE);
}

int main(int argc, char *argv[])
{
  int n = 10;

  if (argc >= 2) {
    int n_tmp;

    n_tmp = atoi(argv[1]);
    if (n_tmp >= 1 && n_tmp <= 46) {
      n = n_tmp;
    }
  }

  make_cfile(n);
  profile_cfile();

  return 0;
}

実行すると…

$ make fib+c
$ ./fib+c
55
<unknown>:0: (_fib1:0x401180) 21 executions
<unknown>:0: (_fib2:0x40118f) 34 executions
<unknown>:0: (_fib3:0x40119e) 21 executions
<unknown>:0: (_fib4:0x4011b9) 13 executions
<unknown>:0: (_fib5:0x4011d4) 8 executions
<unknown>:0: (_fib6:0x4011ef) 5 executions
<unknown>:0: (_fib7:0x40120a) 3 executions
<unknown>:0: (_fib8:0x401225) 2 executions
<unknown>:0: (_fib9:0x401240) 1 executions
<unknown>:0: (_fib10:0x40125b) 1 executions
$ ./fib+c 30
832040
<unknown>:0: (_fib1:0x401180) 317811 executions
<unknown>:0: (_fib2:0x40118f) 514229 executions
<unknown>:0: (_fib3:0x40119e) 317811 executions
<unknown>:0: (_fib4:0x4011b9) 196418 executions
<unknown>:0: (_fib5:0x4011d4) 121393 executions
<unknown>:0: (_fib6:0x4011ef) 75025 executions
<unknown>:0: (_fib7:0x40120a) 46368 executions
<unknown>:0: (_fib8:0x401225) 28657 executions
<unknown>:0: (_fib9:0x401240) 17711 executions
<unknown>:0: (_fib10:0x40125b) 10946 executions
<unknown>:0: (_fib11:0x401276) 6765 executions
<unknown>:0: (_fib12:0x401291) 4181 executions
<unknown>:0: (_fib13:0x4012ac) 2584 executions
<unknown>:0: (_fib14:0x4012c7) 1597 executions
<unknown>:0: (_fib15:0x4012e2) 987 executions
<unknown>:0: (_fib16:0x4012fd) 610 executions
<unknown>:0: (_fib17:0x401318) 377 executions
<unknown>:0: (_fib18:0x401333) 233 executions
<unknown>:0: (_fib19:0x40134e) 144 executions
<unknown>:0: (_fib20:0x401369) 89 executions
<unknown>:0: (_fib21:0x401384) 55 executions
<unknown>:0: (_fib22:0x40139f) 34 executions
<unknown>:0: (_fib23:0x4013ba) 21 executions
<unknown>:0: (_fib24:0x4013d5) 13 executions
<unknown>:0: (_fib25:0x4013f0) 8 executions
<unknown>:0: (_fib26:0x40140b) 5 executions
<unknown>:0: (_fib27:0x401426) 3 executions
<unknown>:0: (_fib28:0x401441) 2 executions
<unknown>:0: (_fib29:0x40145c) 1 executions
<unknown>:0: (_fib30:0x401477) 1 executions

それぞれの呼び出し回数は，Rubyで計算した先日の結果と，一致しています．
ここまでは，Cygwin，より具体的には

$ gcc --version
gcc (GCC) 4.3.4 20090804 (release) 1
Copyright (C) 2008 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
$ gprof --version
GNU gprof (GNU Binutils) 2.19.51.20090704
Based on BSD gprof, copyright 1983 Regents of the University of California.
This program is free software.  This program has absolutely no warranty.

を使用して実行しました．ちなみにオーバーフローしない最大値の46でも，時間はかかりました*2が結果は出ました．
なのですが，Linux環境では期待する出力になりません．Ubuntuの

$ gcc --version
gcc (Ubuntu 4.4.3-4ubuntu5) 4.4.3
Copyright (C) 2009 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
$ gprof --version
GNU gprof (GNU Binutils for Ubuntu) 2.20.1-system.20100303
Based on BSD gprof, copyright 1983 Regents of the University of California.
This program is free software.  This program has absolutely no warranty.

のほか，Vine Linux 5.1で試したところ，ともに，n=26までは問題ないのですが，それよりも大きくなると，フィボナッチ数は正しいのですが，gprofの結果が不自然です．
よく見ると，n≧27のときには，gmon.outの出力がなく，そのため，gprofを実行したときには，gmon.outがないと言うか，あったとしたらそれより前に（n≦26で）実行したときにできたgmon.outを参照しているようです．
原因はgprof以前にあるわけで，gccのオプションを調べてみたものの，良い解決策が見つかりませんでした．

*1:普段のポリシーには反しますが，この文だけは分かりやすさのため，関数名のあとにカッコ・カッコ閉じをつけています．

*2:生成されるfib+p.cには，再帰呼び出しをする関数がありません．それでもnに応じて比例より大きな実行時間がかかるというのは，対話の『「ということは，このプログラムでちょっと時間がかかる原因は，再帰を使っているからではないってことですか?」「再帰は共犯者ですかね．主犯は，fibの同じ引数の値を，ほしいと言われたらそのたびに計算しているところです」』を裏付けるものとなっています．

わさっきhb

大学（教育研究）とか，親馬鹿とか，和歌山とか，とか，とか．

関数の呼び出し回数（力技編）