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
Tôi có một thông dịch viên lớn hơn nhiều, có hành vi hiệu suất mà tôi đang cố hiểu rõ hơn vì vậy tôi đã thực hiện ở trên. Bây giờ tôi chắc chắn rằng quy mô siêu thời gian tôi thấy trong một số ví dụ liên quan đến cách nó sử dụng chồng, nhưng tôi không chắc tại sao điều này lại xảy ra nên tôi muốn hỏi ở đây.Tại sao việc sử dụng sâu của ngăn xếp gây ra hành vi thời gian siêu tuyến tính cho một thông dịch viên đơn giản?
Như bạn có thể thấy, khi tôi thay đổi n x 2 lần, thời gian thay đổi nhiều hơn thế và có vẻ như tỷ lệ là số mũ gây ngạc nhiên cho tôi. Ngoài ra nó là đáng ngạc nhiên rằng các thông dịch viên CPS'd là nhanh hơn so với stack dựa trên một. Tại sao vậy?
Tôi cũng muốn hỏi xem liệu tôi có thể thấy hành vi tương tự này nếu tôi mã hóa tương đương với ở trên bằng ngôn ngữ không phải .NET hoặc thậm chí là C không?
Chà, điều này cũng được phát hiện. Tôi chắc chắn không có ý định đo tòa nhà của cây. Tôi rất vui vì tôi đã đăng câu hỏi này ngay bây giờ. Ngoài ra tôi rất vui khi nhận ra rằng tôi có thể đạt được hiệu suất tốt hơn nhiều bằng cách chuyển đổi thông dịch viên của tôi sang CPS. Các câu hỏi về lý do tại sao phiên bản stack mất quá lâu vẫn còn cho lấy. –