2018-04-23

C++入門書で再帰について解説しようとしたら思わぬ最適化できないコードに出くわした

C++入門書を書き始めて早数カ月、すでに文章量が「江添亮の詳説C++17」の半分近くに達しているが、まだようやくループを説明したところだ。

ループの章を一通り書き終えて、ついでに再帰によってループを実現する方法について軽く触れて章を閉じようと、以下のようなコードを書いた。

void hello()
{
    std::cout << "hello\n"s ;
    hello() ;
}

すると何故かsegmentation faultを起こすではないか。GCCでもClangでも同じ挙動になる。なぜC++コンパイラーはこの程度の末尾再帰を最適化できないのだろうか。

不思議に思って以下のコードも試すと、こちらは問題なく末尾再帰の最適化が行われる。

void hello()
{
    std::cout << "hello\n" ;
    hello() ;
}

違いは文字列だ。今回の入門書では、初心者に簡単にするために、文字列はすべてstd::stringを返すユーザー定義リテラルのoperator "" sを使っているのだ。これにより初心者は、"hello\n"sとかけばstd::stringとして使える。つまり、

auto s = "hello"s ;
s.size() ;

などと書ける。難しいことを一切考えなくてもよい。わたしの本が書き上がって出版されるまでにまだ1年はかかるだろうし、その頃にはC++17が普及している。C++17を使って初心者でも学びやすい記述をすることで、私のC++入門書は初心者にも優しい本になるだろう。そう考えていた矢先に何ということだ。

どうもstd::stringがあると末尾再帰の最適化が行われないらしい。しかしおかしい。一時オブジェクトの寿命はリファレンスにより寿命延長されない場合はfull-expressionの中までのはずだ。したがってこのコードはまだ末尾再帰のはずだ。再帰呼び出し後に何かする必要は何もないはずだ。

不思議に思って以下のコードを試してみたが、やはり末尾再帰の最適化はされていない。

void hello()
{
    {
        std::string s = "hello\n" ;
        std::cout << s ;
    }
    hello() ;
}

これなら一時オブジェクトでもないしブロックスコープを明示的に使っているし問題はないだろうと思ったが、なぜかコンパイラーは末尾再帰の最適化を諦めてしまう。

では関数で包んでしまうというのはどうか。

void hello()
{
    []{ std::cout << "hello\n"s ; }() ;
    hello() ;
}

これはうまくいった。関数で包んだ場合、コンパイラーは末尾再帰を最適化する。

コンパイラーの気持ちはよくわからない。

7 comments:

  1. この時のコンパイラの気持ちを100字以内で述べなさい。

    ReplyDelete
  2. MSVCでも同じく。

    ただしoperator""sは使えなかった、というオマケつき。

    ReplyDelete
  3. // OK
    struct a
    {
    a() : p(new int){}
    ~a() { delete p; }
    int* p;
    };

    void hello()
    {
    {
    a a;
    }
    hello();
    }

    // NG (これは仕方ない)
    struct a
    {
    a() : p(new int){}
    ~a() { delete p; }
    int* p;
    };

    void hello()
    {
    a a;
    hello();
    }

    // OK(当然)
    struct a
    {
    a() { delete new int; }
    ~a() {}
    };

    void hello()
    {
    {
    a a;
    }
    hello();
    }

    // OK(当然)
    struct a
    {
    a() { delete new int; }
    ~a() {}
    };

    void hello()
    {
    {
    a a;
    }
    hello();
    }

    // NG(???)
    struct a
    {
    a() {}
    ~a() { delete new int; }
    };

    void hello()
    {
    {
    a a;
    }
    hello();
    }

    ReplyDelete
  4. [Clang C++コンパイラはデストラクタのある構造体が確保された場合末尾呼び出し最適化を行わない? - ncaq]: https://www.ncaq.net/2018/04/26/13/08/22/

    ReplyDelete
  5. これは、引数がないので、末尾再帰の例として失格

    ReplyDelete
  6. 例えば sum(n,accum) = if (n<=0) accum sum(n-1,accum+n)
    のように定義しても、最初の2つの引数のスタックしか消費しない
    それらだけを操作するコードに変換するのが、末尾再帰最適化です。
    これができるほど賢いCなどのコンパイラは、見たことないです。

    ReplyDelete
  7. >>April 25, 2018 at 1:30 PM
    using namespace std::literals::string_literals; を忘れる阿呆

    ReplyDelete

You can use some HTML elements, such as <b>, <i>, <a>, also, some characters need to be entity referenced such as <, > and & Your comment may need to be confirmed by blog author. Your comment will be published under GFDL 1.3 or later license with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts.