Yığının derin kullanımı neden basit bir tercüman için süper-doğrusal zaman davranışına yol açıyor?

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 

Performans davranışlarımı daha iyi anlamaya çalıştığım daha büyük bir yorumlayıcım var. Eminim ki, bazı örneklerde gördüğüm süper lineer zaman ölçeklendirmesi, yığının kullanıldığı yöntemle ilgilidir, ancak bunun neden böyle olduğundan emin değilim, bu yüzden burada sormak istedim.

Gördüğünüz gibi, n'u 2x değiştirdiğimde, zaman bundan çok daha fazla değişiyor ve ölçeklendirme üssel olarak bana benziyor. Ayrıca CPS'd yorumlayıcısının yığına dayalı olandan daha hızlı olması şaşırtıcıdır. Neden?

Ayrıca, .NET ile aynı olmayan bir dilde veya hatta C'de yukarıdakilerin eşdeğerini kodlarsam aynı davranışı görüp görmeyeceğimi de sormak isterim.

Answer 1

Ölçüm yaptığınız şeyin çoğunun veri yapısını oluşturduğu anlaşılıyor. Zaman ölçümü dışında

let data = add n 

çarpanlarına (ve içeride data ile add n değiştirin) ve CPS doğrusal gidiyor.

Kalanları açıklamak için büyük yığınlar ve bellek performansına sahip iş parçacıkları hakkında yeterince bilgi sahibi değilim ve herhangi bir his elde etmek için belleği biçimlendirmemişsiniz.

Answer 2

Bazı dedektif çalışmalar yaptım ve yığın tabanlı yorumlayıcının aşırı uzun çalışma sürelerinin nedeninin GC olduğunu söyleyebilirim. Gördüğünüz gibi

Lit 500000 
n_500000_std = 00:00:00.3964533 
Lit 500000 
n_500000_cps = 00:00:00.0945109 
Lit 1000000 
n_1000000_std = 00:00:01.6021848 
Lit 1000000 
n_1000000_cps = 00:00:00.2143892 
Lit 2000000 
n_2000000_std = 00:00:08.0540017 
Lit 2000000 
n_2000000_cps = 00:00:00.3823931 

, yığın tabanlı tercüman 2x daha hızlı 64-bit ile karşılaştırılır: Ben 32 bit modunda programı derliyordu denenmiş ve ilk şey bu zamanlamaları var olduğunu öğrenmek için sürpriz oldu modu. CPS'd yorumlayıcısını kıyaslamadan kaldırdım ve programı PerfView tool ile çalıştırdım. Benim ilk hipotezim, aşırı çalışma sürelerinin GC'nin neden olduğuydu.

CommandLine: "IntepreterBenchmark.exe" 
Runtime Version: V 4.0.30319.0 (built on 6/6/2017 10:30:00 PM) 
CLR Startup Flags: CONCURRENT_GC 
Total CPU Time: 19,306 msec 
Total GC CPU Time: 17,436 msec 
Total Allocs : 202.696 MB 
GC CPU MSec/MB Alloc : 86.020 MSec/MB 
Total GC Pause: 17,421.9 msec 
% Time paused for Garbage Collection: 90.2% 
% CPU Time spent Garbage Collecting: 90.3% 

Aslında doğruydu. GC'nin her koleksiyondan önce yığında yürümesi gerektiğini ve programın .NET'te yapılandırılması için güçlü sonuçları olduğunu okudum, ancak GC'nin veri türleri arasındaki bağımlılıkların neden yalnız bırakıldığına dair yorum yapmak için yeterince iyi bir şekilde anlayamıyorum.

Yukarıdaki ölçüm, 32 bit mod içindir. PerfView aracı ile 64-bit ölçümler bozuldu ve bilinmeyen bir nedenle bitirmek için 15 kez uzun sürdü.

Ayrıca, 32 bit modun neden orijinal karşılaştırmada 2x daha hızlı olduğunu açıklayamıyorum, çünkü yığının 64-bit moduna göre 2 kat daha büyük olması gibi değil.