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

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

我有一个更大的翻译,其性能行为我试图更好地理解,所以我做了上述.我现在肯定的是,我在其中看到的超线性时间缩放在某些示例中与它使用堆栈的方式有关,但我不确定为什么会发生这种情况所以我想问这里.

正如你所看到的,当我改变n2倍时,时间变化远远大于此,并且看起来缩放是指数的,这对我来说是令人惊讶的.另外令人惊讶的是,CPS的解释器比基于堆栈的解释器更快.这是为什么？

我还想问一下,如果我用非.NET语言甚至C编写上述等价物,我是否会看到同样的行为？

Answer 1

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

let data = add n

在时间测量之外(并add n用data内部替换),CPS变为线性.

我不知道有足够的了解与大堆栈和内存性能的线程来解释其余的副手,并没有异形内存得到任何感觉.