Rustで末尾再帰が保証されるのはいつですか?

21
uben 2019-12-10 12:23.

C言語

Cプログラミング言語では、末尾再帰を使用するのは簡単です。

int foo(...) {
    return foo(...);
}

再帰呼び出しの戻り値と同じように返します。この再帰が1000回または100万回繰り返される可能性がある場合は、特に重要です。スタック上で大量のメモリを使用します

さび

今、私は自分自身を何百万回も再帰的に呼び出すかもしれないRust関数を持っています:

fn read_all(input: &mut dyn std::io::Read) -> std::io::Result<()> {
    match input.read(&mut [0u8]) {
        Ok (  0) => Ok(()),
        Ok (  _) => read_all(input),
        Err(err) => Err(err),
    }
}

(これは最小限の例であり、実際の例はより複雑ですが、主要なアイデアを捉えています)

ここでは、再帰呼び出しの戻り値はそのまま返されますが、次のようになります。

Rustコンパイラが末尾再帰を適用することを保証しますか?

たとえば、のように破棄する必要がある変数を宣言した場合std::Vec、再帰呼び出しの直前(末尾再帰を許可)または再帰呼び出しが戻った後(末尾再帰を禁止)に破棄されますか?

2 answers

18
Shepmaster 2019-12-10 13:35.

再帰関数が末尾位置(基本的には関数の最後のステートメント)で呼び出されるたびに、末尾呼び出しが保証されます。

末尾呼び出しの最適化は、オプティマイザー実行することを選択する場合がありますが、Rustによって保証されることはありません。

破棄する必要のある変数を宣言した場合

破壊されたスタック変数の場所を変更することは論争になるので、これが問題の1つであると私は理解しています。

参照:

  • 階乗を計算する再帰関数はスタックオーバーフローにつながります
  • RFC 81:末尾呼び出しの除去が保証されています
  • RFC 1888:適切な末尾呼び出し
21
trentcl 2019-12-20 15:15.

Shepmasterの回答は、末尾呼び出しの最適化(末尾呼び出しの除去と呼ぶことを好む)がRustで発生することが保証されていないことを説明しています。しかし、それだけではありません。「決して起こらない」と「保証される」の間には多くの可能性があります。コンパイラが実際のコードで何をするかを見てみましょう。

この関数で発生しますか?

現在、Compiler Explorerで利用可能なRustの最新リリースは1.39であり、の末尾呼び出しを排除するものではありませread_all

example::read_all:
        push    r15
        push    r14
        push    rbx
        sub     rsp, 32
        mov     r14, rdx
        mov     r15, rsi
        mov     rbx, rdi
        mov     byte ptr [rsp + 7], 0
        lea     rdi, [rsp + 8]
        lea     rdx, [rsp + 7]
        mov     ecx, 1
        call    qword ptr [r14 + 24]
        cmp     qword ptr [rsp + 8], 1
        jne     .LBB3_1
        movups  xmm0, xmmword ptr [rsp + 16]
        movups  xmmword ptr [rbx], xmm0
        jmp     .LBB3_3
.LBB3_1:
        cmp     qword ptr [rsp + 16], 0
        je      .LBB3_2
        mov     rdi, rbx
        mov     rsi, r15
        mov     rdx, r14
        call    qword ptr [rip + example::[email protected]]
        jmp     .LBB3_3
.LBB3_2:
        mov     byte ptr [rbx], 3
.LBB3_3:
        mov     rax, rbx
        add     rsp, 32
        pop     rbx
        pop     r14
        pop     r15
        ret
        mov     rbx, rax
        lea     rdi, [rsp + 8]
        call    core::ptr::real_drop_in_place
        mov     rdi, rbx
        call    [email protected]
        ud2

この行に注意してください:call qword ptr [rip + example::[email protected]]。それが再帰呼び出しです。その存在からわかるように、それは排除されませんでした。

これを、明示的なloop:を使用した同等の関数と比較してください。

pub fn read_all(input: &mut dyn std::io::Read) -> std::io::Result<()> {
    loop {
        match input.read(&mut [0u8]) {
            Ok (  0) => return Ok(()),
            Ok (  _) => continue,
            Err(err) => return Err(err),
        }
    }
}

これは、削除する末尾呼び出しがないため、1つだけを含む関数にコンパイルさcallれます(の計算されたアドレスにinput.read)。

しかたがない。たぶん、錆はCほど良くないでしょう。それともそうですか?

それはCで起こりますか?

これは、非常によく似たタスクを実行するCの末尾再帰関数です。

int read_all(FILE *input) {
    char buf[] = {0, 0};
    if (!fgets(buf, sizeof buf, input))
        return feof(input);
    return read_all(input);
}

これは、コンパイラが排除するのが非常に簡単なはずです。再帰呼び出しは関数の一番下にあり、Cはデストラクタの実行について心配する必要はありません。しかし、それにもかかわらず、その再帰的な末尾呼び出しがあり、迷惑なことに排除されていません。

        call    read_all

Cでも末尾呼び出しの最適化は保証されていないことがわかりました。さまざまな最適化レベルでClangとgccを試しましたが、この非常に単純な再帰関数をループに変えることはできませんでした。

それは今までに起こりますか?

さて、それは保証されていません。コンパイラはそれを行うことができますか?はい!末尾再帰内部関数を介してフィボナッチ数を計算する関数は次のとおりです。

pub fn fibonacci(n: u64) -> u64 {
    fn fibonacci_lr(n: u64, a: u64, b: u64) -> u64 {
        match n {
            0 => a,
            _ => fibonacci_lr(n - 1, a + b, a),
        }
    }
    fibonacci_lr(n, 1, 0)
}

末尾呼び出しが削除fibonacci_lrされるfibonacciだけでなく、関数全体がにインライン化され、12個の命令のみが生成されます(call見えない):

example::fibonacci:
        push    1
        pop     rdx
        xor     ecx, ecx
.LBB0_1:
        mov     rax, rdx
        test    rdi, rdi
        je      .LBB0_3
        dec     rdi
        add     rcx, rax
        mov     rdx, rcx
        mov     rcx, rax
        jmp     .LBB0_1
.LBB0_3:
        ret

あなたがいる場合、これは同等と比較whileループ、コンパイラが生成し、ほぼ同じアセンブリを。

ポイントは何ですか?

RustまたはCのいずれかで、末尾呼び出しを排除するために最適化に依存するべきではありません。それが発生した場合は便利ですが、関数がタイトループにコンパイルされることを確認する必要がある場合は、少なくともここで、ループを使用します。

Related questions

MORE COOL STUFF

Reba McEntire は、彼女が息子の Shelby Blackstock と共有する「楽しい」クリスマスの伝統を明らかにしました:「私たちはたくさん笑います」

Reba McEntire は、彼女が息子の Shelby Blackstock と共有する「楽しい」クリスマスの伝統を明らかにしました:「私たちはたくさん笑います」

Reba McEntire が息子の Shelby Blackstock と共有しているクリスマスの伝統について学びましょう。

メーガン・マークルは、自然な髪のスタイリングをめぐってマライア・キャリーと結ばれました

メーガン・マークルは、自然な髪のスタイリングをめぐってマライア・キャリーと結ばれました

メーガン・マークルとマライア・キャリーが自然な髪の上でどのように結合したかについて、メーガンの「アーキタイプ」ポッドキャストのエピソードで学びましょう.

ハリー王子は家族との関係を修復できるという「希望を持っている」:「彼は父親と兄弟を愛している」

ハリー王子は家族との関係を修復できるという「希望を持っている」:「彼は父親と兄弟を愛している」

ハリー王子が家族、特にチャールズ王とウィリアム王子との関係について望んでいると主張したある情報源を発見してください。

ワイノナ・ジャッドは、パニックに陥った休暇の瞬間に、彼女がジャッド家の家長であることを認識しました

ワイノナ・ジャッドは、パニックに陥った休暇の瞬間に、彼女がジャッド家の家長であることを認識しました

ワイノナ・ジャッドが、母親のナオミ・ジャッドが亡くなってから初めての感謝祭のお祝いを主催しているときに、彼女が今では家長であることをどのように認識したかを学びましょう.

セントヘレナのジェイコブのはしごを登るのは、気弱な人向けではありません

セントヘレナのジェイコブのはしごを登るのは、気弱な人向けではありません

セント ヘレナ島のジェイコブズ ラダーは 699 段の真っ直ぐ上る階段で、頂上に到達すると証明書が発行されるほどの難易度です。

The Secrets of Airline Travel Quiz

The Secrets of Airline Travel Quiz

Air travel is far more than getting from point A to point B safely. How much do you know about the million little details that go into flying on airplanes?

Where in the World Are You? Take our GeoGuesser Quiz

Where in the World Are You? Take our GeoGuesser Quiz

The world is a huge place, yet some GeoGuessr players know locations in mere seconds. Are you one of GeoGuessr's gifted elite? Take our quiz to find out!

バイオニック読書はあなたをより速く読むことができますか?

バイオニック読書はあなたをより速く読むことができますか?

BionicReadingアプリの人気が爆発的に高まっています。しかし、それは本当にあなたを速読術にすることができますか?

OxyLEDの新しい15ドルのモーションセンシング常夜灯はどこにでも貼り付けられますが、充電が簡単です

OxyLEDの新しい15ドルのモーションセンシング常夜灯はどこにでも貼り付けられますが、充電が簡単です

私たちの読者は、何千ものOxyLEDのT-02モーションセンサーライトストリップを何年にもわたって購入してきましたが、充電するのが面倒だと感じた場合、新しいT-04は素晴らしいアップグレードのように見えます。T-02のように、 T-04は、付属の粘着ストリップを介して基本的にあらゆる表面に取り付けることができ、暗闇での動きを検出すると自動的に点灯します。

ハンソロ映画セットの写真は、新しいスーツと新しい乗り物を明らかにします

ハンソロ映画セットの写真は、新しいスーツと新しい乗り物を明らかにします

ユニバーサルは、フランケンシュタインの怪物を見つけるのに近いかもしれません。新しい撮影映像でアクマンの舞台裏をご覧ください。

ドナルド・トランプが解雇されたばかりのFBI長官ジェームズ・コミー

ドナルド・トランプが解雇されたばかりのFBI長官ジェームズ・コミー

写真:AP大統領ドナルド・トランプは、連邦捜査局長官のジェームズ・コミーを解雇したばかりです。火曜日の声明で、ホワイトハウスは、トランプが「両方の副検事総長ロッドの明確な勧告に基づいて行動するコミーをオフィスから削除したと述べましたローゼンスタインと司法長官のジェフセッション。

テオドリック大王は、過去の言語と政治的概念に隠された野蛮な将軍でした

テオドリック大王は、過去の言語と政治的概念に隠された野蛮な将軍でした

ウィキメディア・コモンズ経由西部のローマ帝国の中央機関が崩壊し、5世紀の間に州が分裂し、独自の道を進んだとき、新しい王国が出現しました。今日、私たちはこれらの新しい政治単位を特定の野蛮人グループで特定する傾向があります:ガリア南西部の西ゴート族、ガリア北部のフランク人、英国のアングロサクソン人、北アフリカのヴァンダル人。

バレンタインデーにユーカリのシャワースチーマーで「最高の睡眠」を贈りましょう。

バレンタインデーにユーカリのシャワースチーマーで「最高の睡眠」を贈りましょう。

BodyRestore ユーカリ シャワー スチーマーは、Amazon で 11,000 を超える 5 つ星の評価を得ています。セルフケアが必要な人へのバレンタインデーのギフトとして、ホームスパ製品を贈りましょう。

この「邪悪な吸引力」を備えたこの250ドルのハンドヘルド掃除機は、Amazonで75%オフになりました

この「邪悪な吸引力」を備えたこの250ドルのハンドヘルド掃除機は、Amazonで75%オフになりました

多くのAmazonの買い物客がUmlo H6ハンドヘルド掃除機を推奨しており、現在スーパーセール中です. ハンドヘルド デバイスには HEPA フィルターが装備されており、複数のアタッチメントが付属しています。Amazonで75%オフのときにハンドヘルド掃除機を購入する

オクタヴィア・スペンサー、「ザ・ヘルプ」共演者のシシー・スペイセクが17歳で映画のインターンをした後、彼女のことを「実際に」思い出したと語る

オクタヴィア・スペンサー、「ザ・ヘルプ」共演者のシシー・スペイセクが17歳で映画のインターンをした後、彼女のことを「実際に」思い出したと語る

オクタヴィア・スペンサーは、ヘルプで一緒に共演するずっと前に、シシー・スペイセク主演の 1990 年の映画「ロング・ウォーク・ホーム」でインターンとして働いていました。

ジュリア・フォックス、「マスカラ」がTikTokユーザーの性的暴行コードだったことを知らなかったことを謝罪

ジュリア・フォックス、「マスカラ」がTikTokユーザーの性的暴行コードだったことを知らなかったことを謝罪

ジュリア・フォックスは、彼女のTikTokで共有された応答ビデオで、「本当に申し訳ありません。今、本当に年齢を示しています」と述べました。

メリック・ガーランドはアメリカに失敗しましたか?

バイデン大統領の任期の半分以上です。メリック・ガーランドは何を待っていますか?

メリック・ガーランドはアメリカに失敗しましたか?

人々にチャンスを与えることは、人生で少し遅すぎると私は信じています。寛大に。

良いものと醜いもの: 2022

良いものと醜いもの: 2022

もうわからない。何が「ヒット」かを正確に判断することは、もはやほとんど不可能に思えます。

楽しみのために — 2022 年のトップの新しい音楽再生

楽しみのために — 2022 年のトップの新しい音楽再生

ついに!私の 2022 年のトップ ニューミュージック プレイへようこそ。私は毎年これを共有して、友達とつながります。

ヒーズ・オール・アイヴ・ガット

ヒーズ・オール・アイヴ・ガット

あなたの心をチェックしてください。私たちの心はしばしば迷います。

Language