.net - 为什么堆栈的深度使用会导致简单解释器的超线性时间行为？

Question

type Expr =
    | Lit of int
    | Add of Expr * Expr

let rec intr = function
    | Lit _ as x -> x
    | Add(Lit a,Lit b) -> Lit <| a + b
    | Add(a,b) -> intr <| Add(intr a, intr b)

let rec intr_cps x ret =
    match x with
    | Lit _ as x -> ret x
    | Add(Lit a,Lit b) -> Lit (a + b) |> ret
    | Add(a,b) -> 
        intr_cps a <| fun a ->
            intr_cps b <| fun b ->
                intr_cps (Add(a, b)) ret

let rec add n =
    if n > 1 then Add(Lit 1, add (n-1))
    else Lit 1

open System.Threading

let mem = 1024*1024*512 // ~536mb
// It stack overflows without being spun on a separate thread.
// By default, the program only has a few mb of stack memory at its disposal.
let run f = Thread(ThreadStart f,mem).Start() 

run <| fun _ ->
    let f n =
        let x = add n
        let stopwatch = System.Diagnostics.Stopwatch.StartNew()
        printfn "%A" (intr x)
        printfn "n_%i_std = %A" n stopwatch.Elapsed

        stopwatch.Restart()
        printfn "%A" (intr_cps x id)
        printfn "n_%i_cps = %A" n stopwatch.Elapsed
    f <| 1000*1000/2
    f <| 1000*1000
    f <| 1000*1000*2

//Lit 500000
//n_500000_std = 00:00:00.7764730
//Lit 500000
//n_500000_cps = 00:00:00.0800371
//Lit 1000000
//n_1000000_std = 00:00:02.9531043
//Lit 1000000
//n_1000000_cps = 00:00:00.1941828
//Lit 2000000
//n_2000000_std = 00:00:13.7823780
//Lit 2000000
//n_2000000_cps = 00:00:00.2767752

我有一个更大的解释器，我试图更好地理解它的性能行为，所以我做了上面的事情。我现在确信我在一些示例中看到的超线性时间缩放与它使用堆栈的方式有关，但我不确定为什么会发生这种情况，所以我想在这里问。

正如您所看到的，当我将 n 改变 2 倍时，时间变化远不止于此，而且似乎缩放是指数级的，这令我感到惊讶。同样令人惊讶的是，CPS 的解释器比基于堆栈的解释器更快。这是为什么？

我还想问，如果我用非 .NET 语言甚至 C 语言编写与上述内容等效的代码，是否会看到相同的行为？

Answer 1

看起来您正在测量的大部分内容都是在构建数据结构。因式分解

let data = add n

在时间测量之外(并将add n 替换为data)，CPS 呈线性。

我对具有大堆栈的线程和内存性能了解不够，无法立即解释其余部分，也没有分析内存来获得任何感觉。