3

我在 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

这是尾调用消除。

删除尾调用并将尾调用转换为“跳转”到函数开头的过程。(iow 一个while(true) { }构造)。

您看到“相同”分配的原因是为了保持语义与正常调用函数一样。几乎不可能确定一个赋值是否可以有效地影响另一个，因此使用临时变量，然后将赋值返回给它们。

于 2012-05-23T11:24:43.810 回答
5

如前所述，在这种情况下，编译器将递归函数转换为非递归函数。这只有在递归调用出现在“尾调用”位置并且函数调用自身时才有可能。一般来说，编译器有以下选项：

  • 将函数编译为循环- 当函数调用自身并且调用处于尾调用位置时。这是最有效的替代方案，因为它消除了创建新堆栈帧并使用标准循环。

  • .tail call使用IL 指令编译函数- 当调用出现在尾调用位置时，但您正在调用不同的函数（例如，如果您有两个使用let rec foo () = ... and bar () = ...语法声明的相互递归函数）。这样可以避免创建新的堆栈帧（不会出现堆栈溢出），但效率较低，因为.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 回答