f# - (前向)管道运算符能否阻止尾部调用优化？

对于工作中的参数优化问题，我编写了一个遗传算法来找到一些好的设置，因为暴力解决方案是不可行的。不幸的是，当我早上返回时，大多数时候我都会遇到 StackOverflowException。

我已经使用 F# 有一段时间了，因此我了解 TCO 以及对带有累加器参数的函数的需求，并且通常使用这种形式。

经过大量搜索，我认为我能够确定触发异常的代码:

breedPopulation alive |> simulate (generation + 1) lastTime ewma

breedPopulation 从当前存活个体中生成新一代。然后通过调用simulate开始下一轮/一代。当我查看反汇编代码时(完全菜鸟)，我发现了一些 pop 和 ret，所以它看起来不像是对我的常规(非尾部)调用。

mov         rcx,qword ptr [rbp+10h]  
mov         rcx,qword ptr [rcx+8]  
mov         rdx,qword ptr [rbp-40h]  
cmp         dword ptr [rcx],ecx  
call        00007FFA3E4905C0  
mov         qword ptr [rbp-0F0h],rax  
mov         r8,qword ptr [rbp-0F0h]  
mov         qword ptr [rbp-80h],r8  
mov         r8,qword ptr [rbp-78h]  
mov         qword ptr [rsp+20h],r8  
mov         r8d,dword ptr [rbp+18h]  
inc         r8d  
mov         rdx,qword ptr [rbp+10h]  
mov         r9,qword ptr [rbp-20h]  
mov         rcx,7FFA3E525960h  
call        00007FFA3E4A5040  
mov         qword ptr [rbp-0F8h],rax  
mov         rcx,qword ptr [rbp-0F8h]  
mov         rdx,qword ptr [rbp-80h]  
mov         rax,qword ptr [rbp-0F8h]  
mov         rax,qword ptr [rax]  
mov         rax,qword ptr [rax+40h]  
call        qword ptr [rax+20h]  
mov         qword ptr [rbp-100h],rax  
mov         rax,qword ptr [rbp-100h]  
lea         rsp,[rbp-10h]  
pop         rsi  
pop         rdi  
pop         rbp  
ret

扔掉管道操作符并将breeding放在正常参数位置后，反汇编就不一样了。

//    simulate (generation + 1) lastTime ewma (breedPopulation alive)
mov         ecx,dword ptr [rbp+18h]  
inc         ecx  
mov         dword ptr [rbp-30h],ecx  
mov         rcx,qword ptr [rbp-20h]  
mov         qword ptr [rbp-38h],rcx  
mov         rcx,qword ptr [rbp-80h]  
mov         qword ptr [rbp-0F0h],rcx  
mov         rcx,qword ptr [rbp+10h]  
mov         rcx,qword ptr [rcx+8]  
mov         rdx,qword ptr [rbp-48h]  
cmp         dword ptr [rcx],ecx  
call        00007FFA3E4605C0  
mov         qword ptr [rbp-0F8h],rax  
mov         rax,qword ptr [rbp-0F8h]  
mov         qword ptr [rbp+30h],rax  
mov         rax,qword ptr [rbp-0F0h]  
mov         qword ptr [rbp+28h],rax  
mov         rax,qword ptr [rbp-38h]  
mov         qword ptr [rbp+20h],rax  
mov         eax,dword ptr [rbp-30h]  
mov         dword ptr [rbp+18h],eax  
nop  
jmp         00007FFA3E47585B

这绝对更短，并且最后的 jmp 甚至比尾部调用更好。

因此，我想了解是否以及为什么 |> 似乎是问题所在，以及它何时确实产生了影响 - 毕竟，这是第一次多年后咬我。什么情况下会出现这种情况，需要注意什么？

<小时/>

更新: Guy之后指出我的 list 不是 IL，而是汇编，我首先改写了问题。这是我通过 ILSpy 发现的:

使用 |> 运算符

看反编译后的C#，代码似乎在之间来回跳转

internal static FSharpFunc<Types.Genome[], System.Tuple<System.Tuple<float, float>, LbpArea[]>[]> simulate@265-1(Universe x, System.Threading.ManualResetEvent pleaseStop, int generation, System.DateTime lastTime, FSharpOption<double> ewma)
{
    return new $Universe.simulate@267-2(x, pleaseStop, generation, lastTime, ewma);
}

和

// internal class simulate@267-2
public override System.Tuple<System.Tuple<float, float>, LbpArea[]>[] Invoke(Types.Genome[] population)
{
    LbpArea[][] array = ArrayModule.Parallel.Map<Types.Genome, LbpArea[]>(this.x.genomeToArray, population);
    FSharpFunc<System.Tuple<System.Tuple<float, float>, LbpArea[]>, float> accessFitness = this.x.accessFitness;
    System.Tuple<System.Tuple<float, float>, LbpArea[]>[] array2 = ArrayModule.Filter<System.Tuple<System.Tuple<float, float>, LbpArea[]>>(new $Universe.alive@274(accessFitness), ArrayModule.Parallel.Map<LbpArea[], System.Tuple<System.Tuple<float, float>, LbpArea[]>>(new $Universe.alive@273-1(this.x), array));
    if (array2 == null)
    {
        throw new System.ArgumentNullException("array");
    }
    System.Tuple<System.Tuple<float, float>, LbpArea[]>[] array3 = ArrayModule.SortWith<System.Tuple<System.Tuple<float, float>, LbpArea[]>>(new $Universe.alive@275-2(), array2);
    this.x.Population = array3;
    System.Tuple<System.DateTime, FSharpOption<double>> tuple = this.x.printProgress<float, LbpArea[]>(this.lastTime, this.ewma, this.generation, array3);
    System.DateTime item = tuple.Item1;
    FSharpOption<double> item2 = tuple.Item2;
    if (this.pleaseStop.WaitOne(0))
    {
        return array3;
    }
    Types.Genome[] func = this.x.breedPopulation(array3);
    return $Universe.simulate@265-1(this.x, this.pleaseStop, this.generation + 1, item, item2).Invoke(func);
}

在 new 调用的 IL 中，找不到 tail. op。另一方面，Invoke 的最后几行的 IL 读取

IL_00d3: call class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<class BioID.GeneticLbp.Types/Genome[], class [mscorlib]System.Tuple`2<class [mscorlib]System.Tuple`2<float32, float32>, valuetype [BioID.Operations.Biometrics]BioID.Operations.Biometrics.LbpArea[]>[]> '<StartupCode$BioID-GeneticLbp>.$Universe'::'simulate@265-1'(class BioID.GeneticLbp.Universe, class [mscorlib]System.Threading.ManualResetEvent, int32, valuetype [mscorlib]System.DateTime, class [FSharp.Core]Microsoft.FSharp.Core.FSharpOption`1<float64>)
IL_00d8: ldloc.s 7
IL_00da: tail.
IL_00dc: callvirt instance !1 class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<class BioID.GeneticLbp.Types/Genome[], class [mscorlib]System.Tuple`2<class [mscorlib]System.Tuple`2<float32, float32>, valuetype [BioID.Operations.Biometrics]BioID.Operations.Biometrics.LbpArea[]>[]>::Invoke(!0)
IL_00e1: ret

我不知道该怎么办。

没有 |> 运算符

另一个版本确实很不一样。以

开头

internal static System.Tuple<System.Tuple<float, float>, LbpArea[]>[] simulate@264(Universe x, System.Threading.ManualResetEvent pleaseStop, Unit unitVar0)
{
    FSharpFunc<int, FSharpFunc<System.DateTime, FSharpFunc<FSharpOption<double>, FSharpFunc<Types.Genome[], System.Tuple<System.Tuple<float, float>, LbpArea[]>[]>>>> fSharpFunc = new $Universe.simulate@265-2(x, pleaseStop);
    (($Universe.simulate@265-2)fSharpFunc).x = x;
    (($Universe.simulate@265-2)fSharpFunc).pleaseStop = pleaseStop;
    System.Tuple<System.Tuple<float, float>, LbpArea[]>[] population = x.Population;
    Types.Genome[] func;
    if (population != null && population.Length == 0)
    {
        func = x.lengthRandomlyIncreasing(x.laws@53.PopulationSize@);
        return FSharpFunc<int, System.DateTime>.InvokeFast<FSharpOption<double>, FSharpFunc<Types.Genome[], System.Tuple<System.Tuple<float, float>, LbpArea[]>[]>>(fSharpFunc, 0, System.DateTime.Now, null).Invoke(func);
    }
    FSharpFunc<LbpArea[], Types.Genome> arrayToGenome = x.arrayToGenome;
    func = ArrayModule.Parallel.Map<System.Tuple<System.Tuple<float, float>, LbpArea[]>, Types.Genome>(new $Universe.simulate@296-3(arrayToGenome), population);
    return FSharpFunc<int, System.DateTime>.InvokeFast<FSharpOption<double>, FSharpFunc<Types.Genome[], System.Tuple<System.Tuple<float, float>, LbpArea[]>[]>>(fSharpFunc, 0, System.DateTime.Now, null).Invoke(func);
}

它去

// internal class simulate@265-2
public override System.Tuple<System.Tuple<float, float>, LbpArea[]>[] Invoke(int generation, System.DateTime lastTime, FSharpOption<double> ewma, Types.Genome[] population)
{
    return $Universe.simulate@265-1(this.x, this.pleaseStop, generation, lastTime, ewma, population);
}

最后

internal static System.Tuple<System.Tuple<float, float>, LbpArea[]>[] simulate@265-1(Universe x, System.Threading.ManualResetEvent pleaseStop, int generation, System.DateTime lastTime, FSharpOption<double> ewma, Types.Genome[] population)
{
    while (true)
    {
        // Playing evolution...
        if (pleaseStop.WaitOne(0))
        {
            return array3;
        }
        // Setting up parameters for next loop...
    }
    throw new System.ArgumentNullException("array");
}

tl;博士

所以毫无疑问，管道运算符的使用极大地改变了程序流程。我的猜测是两个函数之间的来回最终导致了异常。

我已经读过Tail Calls in F#但我认为它不适用于这种情况，因为我没有使用返回单位作为值的一流函数(在我的 F# 代码中)。

所以问题仍然存在:为什么管道运算符在这里会产生这种破坏性的影响？我怎么能事先知道/我需要注意什么？

<小时/>

更新2:

您可以在GitHub找到该示例的简化版本。。请亲自查看 inline 运算符 |> 更改生成的 IL，这不是我所期望的。

在减少示例的同时，幸运的是我能够找到异常的真正来源。您可以查看branch对于更小的变体。毕竟，它与管道没有任何关系，但我仍然不明白，因为恕我直言，那里是尾递归。

但我原来的问题仍然存在。我只是再添加一个。 :)

最佳答案

根据所提供的最小情况，如果代码在 64 位的 Release模式下运行，则会因堆栈溢出而失败。如果代码在 32 位模式下以 Release模式运行，则会成功。

注意:在 32 位和 64 位之间进行选择的选项是 Prefer 32-bit如下图所示。

增加堆栈大小将导致代码在 64 位 Release模式下成功。这是通过使用 Thread constructor 来完成的.

[<EntryPoint>]
let main _ =

    let test () =
        let r = KissRandom()
        let n = r.Normal()
        Seq.item 20000 n |> printfn "%f"

    /// The greatest maximum-stack-size that should be used
    /// with the 'runWithStackFrame' function.
    let STACK_LIMIT = 16777216

    /// Run a function with a custom maximum stack size.
    /// This is necessary for some functions to execute
    /// without raising a StackOverflowException.
    let runWithCustomStackSize maxStackSize fn =
        // Preconditions
        if maxStackSize < 1048576 then
            invalidArg "stackSize" "Functions should not be executed with a \
                maximum stack size of less than 1048576 bytes (1MB)."
        elif maxStackSize > STACK_LIMIT then
            invalidArg "stackSize" "The maximum size of the stack frame should \
                not exceed 16777216 bytes (16MB)."

        /// Holds the return value of the function.
        let result = ref Unchecked.defaultof<'T>

        // Create a thread with the specified maximum stack size,
        // then immediately execute the function on it.
        let thread = System.Threading.Thread ((fun () -> result := fn()), maxStackSize)
        thread.Start ()

        // Wait for the function/thread to finish and return the result.
        thread.Join ()
        !result

    /// Runs a function within a thread which has an enlarged maximum-stack-size.
    let inline runWithEnlargedStack fn =
        runWithCustomStackSize STACK_LIMIT fn


//    test ()       // Fails with stack overflow in 64-bit mode, Release
                    // Runs successfully in 32-bit mode, Release

    runWithEnlargedStack test
    
    printf "Press any key to exit: "
    System.Console.ReadKey() |> ignore
    printfn ""

    0

此代码来自FSharp-logic-examples尤其是 Anh-Dung Phan

虽然我没有检查根本原因，但我怀疑这是因为 64 位的项目大小大于 32 位的项目大小，即使放入的项目数量两个版本的堆栈和堆栈大小保持相同，项目大小的增加将堆栈所需的内存推至超过 1 MB 限制。

TL;博士

这是一个有趣且富有启发性的问题。我很高兴有人问我这个问题。

最初，该问题似乎与 |> 的使用有关。和 TCO，因为这仍然有值(value)，所以我将其留在答案中。我还要感谢 OP 的回应和帮助，很高兴能够帮助与您合作而不是与您作对的人。

在以下递归代码中，有 |>在 Visual Studio 中以 Debug模式运行会导致 StackOverflow。

如果是从命令行启动的话 bin\release目录它不会导致 StackOverflow。

使用 Visual Studio 15 社区

[<EntryPoint>]
let main argv = 

    let largeList = 
        printfn "Creating large list"
        [
            for i in 1 .. 100000000 do
                yield i
        ]

    // causes StackOverflow in Debug
    // No StackOverflow in Release
    let sum4 l =
        printfn "testing sum4"
        let rec sumInner4 l acc =
            match l with
            | h::t -> 
                let acc = acc + h
                acc |> sumInner4 t
            | [] -> acc
        sumInner4 l 0

    let result4 = sum4 largeList
    printfn "result4: %A" result4

Visual Studio 工具栏中“发布”或“调试”的设置位置

Debug模式下项目的选项是

Release模式下项目的选项是

tldr;

在测试过程中，我创建了 16 个不同的测试，并在调试和 Release模式下构建它们，并验证它们是否运行完成或引发堆栈溢出。这 16 件被分成 4 件一组，每件 4 个箱子。情况 1、5、9、13 是否定的，会产生堆栈溢出，以确保可以创建堆栈溢出。情况 2、6、10、14 是肯定的，表明尾部调用正在工作并且不会导致堆栈溢出。案例 3、7、11、15 显示了尾部调用，其操作在与尾部调用相同的语句中完成，并且与使用 |> 的测试用例进行了一次分解。 ;这些按预期工作。案例4、8、12、16使用|>并显示它何时在 Debug模式下工作和不工作，这可能会让很多人感到惊讶。情况 1-4 和 9-12 使用 f x y 形式的函数，情况 8-11 使用 f x 形式的函数案例 12-16 使用 f x y z 形式的函数。我最初做了前 8 个测试用例，但在 Keith 的评论之后又做了 4 个测试用例，其中不使用列表，但仍然使用 f x y 的函数。并呈现出意想不到的结果，然后又做了 4 个使用 f x y z 形式的函数的操作.

要运行测试，您必须注释掉除计划运行的一个测试之外的所有测试，并在 Debug模式下构建一次，然后可以从 Visual Studio 中运行该测试，然后再次在 Release模式下构建它，运行。我从命令行运行它以确保我正在运行发布版本。

[<EntryPoint>]
let main argv = 

    let largeList = 
        printfn "Creating large list"
        [
            for i in 1 .. 100000000 do
                yield i
        ]

    // causes StackOverflow in Debug
    // causes StackOverflow in Release
    //   Negative confirmation
    //   A supposed tail call that DOES cause a stack overflow in both debug and release mode
    //   options: f x y
    let sum1 l = 
        printfn "test 01: "
        let rec sum1Inner l acc =
            match l with
            | h::t -> 
                let acc = acc + h
                1 + sum1Inner t acc
            | [] -> acc
        sum1Inner l 0
        
    // No StackOverflow in Debug
    // No StackOverflow in Release
    //   Positive confirmation
    //   A tail call that DOES NOT cause a stack overflow in both debug and release mode
    //   options: f x y
    let sum2 l =
        printfn "test 02: "
        let rec sum2Inner l acc =
            match l with
            | h::t -> 
                let acc = acc + h
                sum2Inner t acc
            | [] -> acc
        sum2Inner l 0
        
    // No StackOverflow in Debug
    // No StackOverflow in Release
    //   A test case
    //   options: f x y and no |>
    let sum3 l =
        printfn "test 03: "
        let rec sum3Inner l acc =
            match l with
            | h::t -> 
                sum3Inner t (acc + h)
            | [] -> acc
        sum3Inner l 0
        
    // causes StackOverflow in Debug
    // No StackOverflow in Release
    //   A test case
    //   options: f x y and |>
    let sum4 l =
        printfn "test 04: "
        let rec sum4Inner l acc =
            match l with
            | h::t -> 
                let acc = acc + h
                acc |> sum4Inner t
            | [] -> acc
        sum4Inner l 0
        
    // causes StackOverflow in Debug
    // causes StackOverflow in Release
    //   Negative confirmation
    //   A supposed tail call that DOES cause a stack overflow in both debug and release mode
    //   options: f x
    let sum5 () =
        printfn "test 05: "
        let rec sum5Inner x =
            match x with 
            | 10000000 -> x
            | _ -> 
                let acc = x + 1
                1 + sum5Inner acc
        sum5Inner 0
        
    // No StackOverflow in Debug
    // No StackOverflow in Release
    //   Positive confirmation
    //   A tail call that DOES NOT cause a stack overflow in both debug and release mode
    //   options: f x
    let sum6 () =
        printfn "test 06: "
        let rec sum6Inner x =
            match x with 
            | 10000000 -> x
            | _ -> 
                let acc = x + 1
                sum6Inner acc
        sum6Inner 0
        
    // No StackOverflow in Debug
    // No StackOverflow in Release
    //  A test case
    //  options: f x and no |>
    let sum7 l =
        printfn "test 07: "
        let rec sum7Inner x =
            match x with 
            | 10000000 -> x
            | _ -> sum7Inner (x + 1)
        sum7Inner 0
        
    // No StackOverflow in Debug
    // No StackOverflow in Release
    //   A test case
    //   options: f x and |>
    let sum8 () =
        printfn "test 07: "
        let rec sumInner8 x =
            match x with
            | 10000000 -> x
            | _ -> 
                let acc = x + 1
                acc |> sumInner8 
        sumInner8 0

    // causes StackOverflow in Debug
    // causes StackOverflow in Release
    //   Negative confirmation"
    //   A supposed tail call that DOES cause a stack overflow in both debug and release mode"
    //   options: f x y"
    let sum9 () = 
        printfn "test 09: "
        let rec sum9Inner x y =
            match y with
            | 10000000 -> y
            | _ -> 
                let acc = x + y
                1 + sum9Inner x acc
        sum9Inner 1 0   
        
    // No StackOverflow in Debug
    // No StackOverflow in Release
    //   Positive confirmation
    //   A tail call that DOES NOT cause a stack overflow in both debug and release mode
    //   options: f x y
    let sum10 () =
        printfn "test 10: "
        let rec sum10Inner x y =
            match y with
            | 10000000 -> y
            | _ -> 
                let acc = x + y
                sum10Inner x acc
        sum10Inner 1 0

    // No StackOverflow in Debug
    // No StackOverflow in Release
    //   A test case
    //   options: f x y and no |>
    let sum11 () =
        printfn "test 11: "
        let rec sum11Inner x y =
            match y with
            | 10000000 -> y
            | _ -> 
                sum11Inner x (x + y) 
        sum11Inner 1 0
        
    // causes StackOverflow in Debug
    // No StackOverflow in Release
    //   A test case
    //   options: f x y and |>
    let sum12 () =
        printfn "test 12: "
        let rec sum12Inner x y =
            match y with
            | 10000000 -> y
            | _ -> 
                let acc = x + y
                acc |> sum12Inner x
        sum12Inner 1 0

    // causes StackOverflow in Debug
    // No StackOverflow in Release
    //   A test case"
    //   options: f x y and |>"
    let sum12 () =
        printfn "test 12: "
        let rec sum12Inner x y =
            match y with
            | 10000000 -> y
            | _ -> 
                let acc = x + y
                acc |> sum12Inner x
        sum12Inner 1 0

    // causes StackOverflow in Debug
    // causes StackOverflow in Release
    //   Negative confirmation"
    //   A supposed tail call that DOES cause a stack overflow in both debug and release mode"
    //   options: f x y"
    let sum13 () = 
        printfn "test 13: "
        let rec sum13Inner x z y =
            match y with
            | 10000000 -> y
            | _ -> 
                let acc = x + y
                1 + sum13Inner x z acc 
        sum13Inner 1 "z" 0
        
    // No StackOverflow in Debug
    // No StackOverflow in Release
    //   Positive confirmation"
    //   A tail call that DOES NOT cause a stack overflow in both debug and release mode"
    //   options: f x y"
    let sum14 () =
        printfn "test 14: "
        let rec sum14Inner x z y =
            match y with
            | 10000000 -> y
            | _ -> 
                let acc = x + y
                sum14Inner x z acc
        sum14Inner 1 "z" 0

    // No StackOverflow in Debug
    // No StackOverflow in Release
    //   A test case"
    //   options: f x y and no |>"
    let sum15 () =
        printfn "test 15: "
        let rec sum15Inner x z y =
            match y with
            | 10000000 -> y
            | _ -> 
                sum15Inner x z (x + y) 
        sum15Inner 1 "z" 0

    // causes StackOverflow in Debug
    // No StackOverflow in Release
    //   A test case"
    //   options: f x y and |>"
    let sum16 () =
        printfn "test 16: "
        let rec sum16Inner x z y =
            match y with
            | 10000000 -> y
            | _ -> 
                let acc = x + y
                acc |> sum16Inner x z
        sum16Inner 1 "z" 0

    let result1 = sum1 largeList
    printfn "result1: %A" result1

    let result2 = sum2 largeList
    printfn "result2: %A" result2

    let result3 = sum3 largeList
    printfn "result3: %A" result3

    let result4 = sum4 largeList
    printfn "result4: %A" result4

    let result5 = sum5 ()
    printfn "result5: %A" result5

    let result6 = sum6 ()
    printfn "result6: %A" result6

    let result7 = sum7 ()
    printfn "result7: %A" result7

    let result8 = sum8 ()
    printfn "result8: %A" result8

    let result9 = sum9 ()
    printfn "result9: %A" result9

    let result10 = sum10 ()
    printfn "result10: %A" result10

    let result11 = sum11 ()
    printfn "result11: %A" result11

    let result12 = sum12 ()
    printfn "result12: %A" result12

    let result13 = sum13 ()
    printfn "result13: %A" result13

    let result14 = sum14 ()
    printfn "result14: %A" result14

    let result15 = sum15 ()
    printfn "result15: %A" result15

    let result16 = sum16 ()
    printfn "result16: %A" result16
    
    printf "Press any key to exit: "
    System.Console.ReadKey() |> ignore
    printfn ""

    0 // return an integer exit code

其他新信息

编辑:This thread Github 上有 F# 的创建者 Don Syme，specifically mention that :

[...] Second, you are correct, we don't guarantee to optimize uses of f <| x or x |> f or any similar to first-calling tailcalls even if f x is a tailcall.

关于f# - (前向)管道运算符能否阻止尾部调用优化？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/35722526/

f# - (前向)管道运算符能否阻止尾部调用优化？

使用 |> 运算符

没有 |> 运算符

tl;博士

其他新信息

上一篇：java - JSF 2.x + Spring 3.2 集成？

下一篇：.net - 在 Webkit .NET 中打开本地文件