recursion - F# 递归与迭代速度/开销

Question

我一直在研究 Riccardo Terrell 的 Akka.NET 分形演示 (https://github.com/rikace/akkafractal) 以尝试理解它。 (这很棒，顺便说一句)

作为对自己的一个小挑战，我尝试的一件事是以更实用的方式重写它的一些部分。我已经让它工作了，但它比原来的慢很多。

这是(或多或少)为测试而改编的原始 Mandelbrot 集计算:

    let mandelbrotSet (xp : int) (yp : int) (w : int) (h :int) (width : int) (height : int)
                  (maxr : float) (minr : float) (maxi : float) (mini : float) : List<int> =

    let mutable zx = 0.
    let mutable zy = 0.
    let mutable cx = 0.
    let mutable cy = 0.
    let mutable xjump = ((maxr - minr) / ( float width))

    let yjump = ((maxi - mini) / (float height))

    let mutable tempzx = 0.
    let loopmax = 1000
    let mutable loopgo = 0

    let outputList: int list = List.empty

    for x = xp to (xp + w) - 1 do
        cx <- (xjump * float x) - abs(minr)

        for y = yp to (yp + h) - 1 do
            zx <- 0.
            zy <- 0.
            cy <- (yjump * float y) - abs(mini)
            loopgo <- 0

            while (zx * zx + zy * zy <= 4. && loopgo < loopmax) do
                loopgo <- loopgo + 1
                tempzx <- zx
                zx <- (zx * zx) - (zy * zy) + cx
                zy <- (2. * tempzx * zy) + cy

            (List.append outputList [loopgo]) |> ignore

    outputList

这是我使用递归 mbCalc 函数执行的版本:

let mandelbrotSetRec (xp : int) (yp : int) (w : int) (h :int) (width : int) (height : int)
    (maxr : float) (minr : float) (maxi : float) (mini : float) : List<int> =

    let xjump = ((maxr - minr) / (float width))
    let yjump = ((maxi - mini) / (float height))
    let loopMax = 1000
    let outputList: int list = List.empty

    let rec mbCalc(zx:float, zy:float, cx:float, cy:float, loopCount:int) = 
        match (zx * zx + zy * zy), loopCount with //The square of the magnitude of z
          | a,b when a > 4. || b = loopMax -> loopCount
          | _ -> mbCalc((zx * zx) - (zy * zy) + cx, (2. * zx * zy) + cy, cx, cy, loopCount+1) //iteration is the next value of z^2+c

    [|0..w-1|] //For each x...
        |> Array.map (fun x ->  let cx = (xjump * float (x+xp) - abs(minr))
                                [|0..h-1|] ///and for each y...
                                    |> Array.map (fun y -> let cy = (yjump * float (y+yp) - abs(mini))
                                                           let mbVal = mbCalc(0., 0., cx, cy,0)  //Calculate the number of iterations to convergence (recursively)
                                                           List.append outputList [mbVal]))|>ignore

    outputList

这是否只是预料之中的，毫无意义地加载一个具有大量递归调用的 Actor，还是我只是在做一些非常低效的事情？非常感谢收到任何指示!

如果你想运行它们，那么这里有一个小测试脚本:

let xp = 1500
let yp = 1500
let w = 200
let h = 200
let width = 4000
let height = 4000

let timer1 = new System.Diagnostics.Stopwatch()
timer1.Start()
let ref = mandelbrotSet xp yp w h width height 0.5 -2.5 1.5 -1.5
timer1.Stop()

let timer2 = new System.Diagnostics.Stopwatch()
timer2.Start()
let test = mandelbrotSetRec xp yp w h width height 0.5 -2.5 1.5 -1.5
timer2.Stop

timer1.ElapsedTicks;;
timer2.ElapsedTicks;;
ref = test;;

编辑:根据 Philip 在下面的回答，我快速(太快了!)添加了列表输出，以制作无需任何导入即可在脚本中运行的内容。这是返回图像的代码:

    let mandelbrotSetRec (xp : int) (yp : int) (w : int) (h :int) (width : int) (height : int)
        (maxr : float) (minr : float) (maxi : float) (mini : float) : Image<Rgba32> =

        let img = new Image<Rgba32>(w, h)
        let xjump = ((maxr - minr) / (float width))
        let yjump = ((maxi - mini) / (float height))
        let loopMax = 1000

        //Precalculate the possible colour list
        let palette = List.append  ([0..loopMax - 1] |> List.map(fun c -> Rgba32(byte(c % 32 * 7), byte(c % 128 * 2), byte(c % 16 * 14)))) [Rgba32.Black]

        let rec mbCalc(zx:float, zy:float, cx:float, cy:float, loopCount:int) = 
            match (zx * zx + zy * zy), loopCount with //The square of the magnitude of z
              | a,b when a > 4. || b = loopMax -> loopCount
              | _ -> mbCalc((zx * zx) - (zy * zy) + cx, (2. * zx * zy) + cy, cx, cy, loopCount+1) //iteration is the next value of z^2+c

        [|0..w-1|] //For each x...
            |> Array.map (fun x ->  let cx = (xjump * float (x+xp) - abs(minr))
                                    [|0..h-1|] ///and for each y...
                                        |> Array.map (fun y -> let cy = (yjump * float (y+yp) - abs(mini))
                                                               let mbVal = mbCalc(0., 0., cx, cy,0)  //Calculate the number of iterations to convergence (recursively)
                                                               img.[x,y] <- palette.[mbVal]))|>ignore
        img

Answer 1

首先，两个函数都返回 []因此即使计算正确，也不会返回 mandlebrot 集。 List.append返回一个列表，它不会改变现有列表。

使用下面的快速 BenchmarkDotNet 程序，其中每个函数都在其自己的模块中:

open BenchmarkDotNet.Attributes
open BenchmarkDotNet.Running
open ActorTest

[<MemoryDiagnoser>]
type Bench() =
    let xp = 1500
    let yp = 1500
    let w = 200
    let h = 200
    let width = 4000
    let height = 4000    

    [<Benchmark(Baseline=true)>]
    member _.Mutable() =
        Mutable.mandelbrotSet xp yp w h width height 0.5 -2.5 1.5 -1.5

    [<Benchmark>]
    member _.Recursive() =
        Recursive.mandelbrotSet xp yp w h width height 0.5 -2.5 1.5 -1.5

[<EntryPoint>]
let main argv =
    let summary = BenchmarkRunner.Run<Bench>()
    printfn "%A" summary
    0 // return an integer exit code

您的代码给出了这些结果:

|    Method |     Mean |     Error |    StdDev | Ratio | RatioSD |    Gen 0 |    Gen 1 | Gen 2 | Allocated |
|---------- |---------:|----------:|----------:|------:|--------:|---------:|---------:|------:|----------:|
|   Mutable | 1.356 ms | 0.0187 ms | 0.0166 ms |  1.00 |    0.00 | 406.2500 |        - |     - |   1.22 MB |
| Recursive | 2.558 ms | 0.0303 ms | 0.0283 ms |  1.89 |    0.03 | 613.2813 | 304.6875 |     - |   2.13 MB |

我注意到您正在使用 Array.map但是在任何地方都没有捕获结果，因此将其更改为 Array.iter让您的代码几乎相同:

|    Method |     Mean |     Error |    StdDev | Ratio |    Gen 0 | Gen 1 | Gen 2 | Allocated |
|---------- |---------:|----------:|----------:|------:|---------:|------:|------:|----------:|
|   Mutable | 1.515 ms | 0.0107 ms | 0.0094 ms |  1.00 | 406.2500 |     - |     - |   1.22 MB |
| Recursive | 1.652 ms | 0.0114 ms | 0.0101 ms |  1.09 | 607.4219 |     - |     - |   1.82 MB |

这种差异可能可以通过映射调用完成的额外分配来解释。分配很昂贵，尤其是当它是较大的数组时，因此最好尽可能避免使用它们。确切的时间因机器而异，但我希望在使用 BenchmarkDotNet 时会有类似的前后比率。

这可能会通过避免列表分配和预分配您填写的列表或数组来进一步优化。迭代调用也是如此。还循环遍历 Span<'T>将比数组更快，因为它省略了边界检查，但您可能必须大量更改代码的形状才能做到这一点。

最后，始终使用像 BenchmarkDotNet 这样的统计基准测试工具来衡量这样的微基准测试中的性能。快速脚本作为起点很好，但它们不能替代考虑机器执行时间可变性的工具。