Zenn
🧐

疑問：末尾呼び出し最適化(goto)をCで書いたらスタックは少なく消費されるのか？

2024/10/05に公開2件
C
メモリ
C言語
スタック
末尾呼び出し最適化
tech

経緯とお題

人と話していて以下のように疑問を抱いた。

  • 本当に再帰はスタックを多く消費するのか？
  • 末尾再起で良くなるのか？
  • C言語で末尾呼び出し最適化ぽいことをしたらどうなるのか？

なので、以下のようなコマンドライン引数として関数（ループ、再帰、末尾再起、末尾呼び出し最適化(goto))とNの指定が出来るようなフィボナッチ計算をするコードを使用し、スタックメモリの消費率を計測してみた。

実験の流れ

  1. コンパイル
    gcc -o fib_compare fib_compare.c

  2. デフォルトではヒープメモリのみ計測するようになっていて、スタックメモリの計測はオフになっているので以下のようにオプション指定しながら、valgrindでmassif指定で実行し、指定名のファイルを作成するようにした。
    ex.)
    valgrind --tool=massif --heap=no --stacks=yes --massif-out-file=fib_loop.txt ./fib_compare 0 30
    valgrind --tool=massif --heap=no --stacks=yes --massif-out-file=fib_rec.txt ./fib_compare 1 30
    ...

  3. ms_printだと見にくいので、massif-visualizerで可視化
    massif-visualizer *.txt

結果

  • fib_loop.txt
  • fib_rec.txt
  • fib_tail_rec.txt
  • fib_goto.txt

疑問

  1. なぜそのタイミングでピーク時なのか？
  2. Nの値を大きくしてもなぜピークはずっと7.7KiB？

7.7KiBにはこれが影響していそう
https://valgrind.org/docs/manual/ms-manual.html#ms-manual.using-visualizer

--peak-inaccuracy=<m.n> [default: 1.0]
Massif does not necessarily record the actual global memory allocation peak; by default it records a peak only when the global memory allocation size exceeds the previous peak by at least 1.0%. This is because there can be many local allocation peaks along the way, and doing a detailed snapshot for every one would be expensive and wasteful, as all but one of them will be later discarded. This inaccuracy can be changed (even to 0.0%) via this option, but Massif will run drastically slower as the number approaches zero.

もしかして、massifを使用したのが間違い？
詳しく出る動的解析ツールある？
https://interrupt.memfault.com/blog/measuring-stack-usage#static-analysis-with--fstack-usage
https://stackoverflow.com/questions/46413593/calculating-stack-memory-in-c

実行時間も計測してみた

f(n), n=46がintの範囲内に収まる最大値を計算できる。
./measure_time.bash 46
bashの内容は以下の通り。
https://gist.github.com/hrak0x59/d7633a137ad3a79fb0aa417c986cf1ff#file-measure_time-bash

ループ: fib(46) = 1836311903
実行時間: real	0m0.001s
user	0m0.001s

再帰: fib(46) = 1836311903
実行時間: real	0m7.968s
user	0m7.967s

末尾再帰: fib(46) = 1836311903
実行時間: real	0m0.001s
user	0m0.001s

末尾呼び出し最適化 (goto): fib(46) = 1836311903
実行時間: real	0m0.000s
user	0m0.000s

goto文が一番早かった。

参考

https://koji-genba.hateblo.jp/entry/2023/01/20/183336
https://zenn.dev/termoshtt/articles/valgrind-massif-tutorial
https://stackoverflow.com/questions/28488554/how-to-measure-a-functions-stack-usage-in-c
https://docs.redhat.com/ja/documentation/red_hat_enterprise_linux/6/html/performance_tuning_guide/ch05s03s03#idm140189355882208
https://caddi.tech/archives/2251
https://qiita.com/QGv/items/d7857cb0fff80ecbe41d
https://valgrind.org/docs/manual/ms-manual.html

Discussion