3

私はF＃でいくつかの小さな文字列解析関数を作成しました。これは、F＃の感触を良くし、F＃を使用してそのようなタスクを解決する方法を確認するためです。文字列の上を歩き、再帰を介して特定の文字を検索しようとします。

ロジックは機能しますが、リリースビルド（最適化がオンになっている）の生成されたILコードは、私の意見では少し奇妙に見えます。したがって、F＃でこのようなものをパフォーマンスの高い方法で作成するためのより良い方法があると思います。

これは、解析関数がどのように見えるかです。

let eatTag (input : string) index =
    let len = input.Length
    let nothing = 0, null, TagType.Open

    // more functions used in the same way
    // ...

    let rec findName i =
        if i >= len then nothing
        else
            let chr = input.[i]
            if isWhitespace chr then
                findName (i+1)
            elif chr = '/' then
                getName (i+1) (i+1) true
            else getName (i+1) i false

    let rec findStart i =
        if i >= len then nothing
        elif input.[i] = '<' then findName (i+1)
        else findStart (i+1)

    findStart index

findStart関数用に生成されたILコードは次のようになります。

 // loop start
    IL_0000: nop
    IL_0001: ldarg.2
    IL_0002: ldarg.1
    IL_0003: blt.s IL_000e

    IL_0005: ldc.i4.0
    IL_0006: ldnull
    IL_0007: ldc.i4.0
    IL_0008: newobj instance void class [mscorlib]System.Tuple`3<int32, string, valuetype TagType>::.ctor(!0, !1, !2)
    IL_000d: ret

    IL_000e: ldarg.0
    IL_000f: ldarg.2
    IL_0010: call instance char [mscorlib]System.String::get_Chars(int32)
    IL_0015: ldc.i4.s 60
    IL_0017: bne.un.s IL_0024

    IL_0019: ldarg.0
    IL_001a: ldarg.1
    IL_001b: ldarg.2
    IL_001c: ldc.i4.1
    IL_001d: add
    IL_001e: call class [mscorlib]System.Tuple`3<int32, string, valuetype TagType> findName@70(string, int32, int32)
    IL_0023: ret

    IL_0024: ldarg.0
    IL_0025: ldarg.1
    IL_0026: ldarg.2
    IL_0027: ldc.i4.1
    IL_0028: add
    IL_0029: starg.s i
    IL_002b: starg.s len
    IL_002d: starg.s input
    IL_002f: br.s IL_0000
// end loop

この関数のC＃ビュー（ILSpy）には、次のコードが表示されます。これが、ここで何か間違ったことをしていると思う理由です。明らかに、関数の引数はどういうわけかそれ自体に割り当てられています...？！

internal static Tuple<int, string, TagType> findStart@80(string input, int len, int i)
{
        while (i < len)
        {
                if (input[i] == '<')
                {
                        return findName@70(input, len, i + 1);
                }
                string arg_2D_0 = input;
                int arg_2B_0 = len;
                i++;
                len = arg_2B_0;
                input = arg_2D_0;
        }
        return new Tuple<int, string, TagType>(0, null, TagType.Open);
}

同じ問題は、継続スタイルで処理される他の関数にも見られます。私がしていること、または間違っていると想定していることへのポインタは大歓迎です:-)

4

3 に答える 3

7

これは末尾呼び出しの除去です。

末尾呼び出しを削除し、末尾呼び出しを関数の開始への「ジャンプ」に変えるプロセス。（iowwhile(true) { }コンストラクト）。

「同じ」割り当てが表示される理由は、関数を通常どおりに呼び出している場合と同じセマンティクスを維持するためです。ある割り当てが別の割り当てに効率的に影響を与える可能性があるかどうかを判断することはほぼ不可能です。したがって、一時変数を使用してから、それらに割り当てを戻します。

于 2012-05-23T11:24:43.810 に答える
5

すでに述べたように、この場合、コンパイラーは再帰関数を非再帰関数に変換します。これは、再帰呼び出しが「末尾呼び出し」の位置に表示され、関数がそれ自体を呼び出す場合にのみ可能です。一般に、コンパイラには次のオプションがあります。

  • 関数をループとしてコンパイルします-関数がそれ自体を呼び出し、呼び出しが末尾呼び出しの位置にある場合。これは、新しいスタックフレームの作成を排除し、標準ループを使用するため、最も効率的な代替手段です。

  • .tail callIL命令を使用して関数をコンパイルします-呼び出しが末尾呼び出しの位置に表示されているが、別の関数を呼び出している場合（たとえば、let rec foo () = ... and bar () = ...構文を使用して2つの相互再帰関数が宣言されている場合）。.tail callこれにより、新しいスタックフレームの作成が回避されます（スタックオーバーフローは発生しません）が、.NETの命令がそれほど最適化されていないため、効率が低下します。

  • 通常の再帰を使用してコンパイルする-関数がそれ自体を再帰的に呼び出してからさらに計算を行う場合、コードは末尾呼び出しではなく標準の再帰呼び出しを使用してコンパイルされます（呼び出しごとに新しいスタックフレームを割り当てる必要があるため、次のようになります。スタックオーバーフロー）

最初のケース（あなたの例では）で行われる最適化は次のようになります。一般に、末尾再帰関数は次のようになります。

let rec foo x = 
  if condition then 
    let x' = calculateNewArgument x // Run some computation
    foo x'                          // (Tail-)recursively calls itself
  else 
    calculateResult x               // Final calculation in the branch that returns

コードは、引数を可変変数に格納する次のループに変換されます。

let foo x = 
  let mutable x = x
  while condition do                // Check condition using current argument value
    x <- calculateNewArgument x     // Instead of recursion, run next iteration
  calculateResult x                 // Final calculation in the branch that returns
于 2012-05-23T11:39:08.457 に答える
2

基本的に、のようなチェーンを作成する代わりに

findstart(findstart(findstart(findstart.....

コンパイラは、関数呼び出しを排除するループに変換します。

これは、かなり標準的な関数型プログラミングの最適化である末尾呼び出しの除去です。これは、関数への引数への再署名のオーバーヘッドが、新しいスタックフレームを生成する新しい関数を呼び出すよりも低いために機能します。

于 2012-05-23T11:11:18.993 に答える