Dlaczego głębokie użycie stosu powoduje nadmierne zachowanie czasu dla prostego interpretatora?

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 

Mam znacznie większy interpreter, którego zachowanie wydajności staram się lepiej zrozumieć, więc zrobiłem powyższe. Jestem pewna, że ​​teraz superlinearne skalowanie czasu, które widzę na niektórych przykładach, wiąże się ze sposobem, w jaki używa stosu, ale nie jestem pewien, dlaczego tak się dzieje, więc chciałem zapytać tutaj.

Jak widać, ponieważ zmieniam n przez 2x, czas zmienia się znacznie więcej, i wydaje się, że skalowanie ma charakter wykładniczy, co jest dla mnie zaskakujące. Zaskakujące jest również to, że interpreter CPS jest szybszy niż ten oparty na stosie. Dlaczego?

Chcę również zapytać, czy widzę to samo zachowanie, jeśli zakodowałem odpowiednik powyższego w języku .NET, a nawet C?

Answer 1

Wygląda na to, że większość pomiarów polega na budowaniu struktury danych. Czynnik poza

let data = add n 

poza pomiarem czasu (i zastąpić add n z data wewnątrz) i CPS idzie liniowych.

Nie wiem wystarczająco dużo o wątkach z dużymi stosami i wydajnością pamięci, aby wytłumaczyć resztę z offhandu i nie sprofilować pamięci, żeby się poczuć.

Answer 2

Zrobiłem trochę pracy detektywistycznej i mogę odpowiedzieć, że powodem zbyt długich czasów pracy dla tłumacza opartego na stosie jest GC. Pierwszą rzeczą, jaką próbowałem była kompilacja program w 32-bitowym trybie i był zaskoczony, aby dowiedzieć się, że mam te czasy:

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 

Jak widać, interpreter stos bazie jest 2x szybciej w porównaniu do 64-bit tryb. Usunąłem interpreter CPS z benchmarka i uruchomiłem program pod numerem PerfView tool. Moja początkowa hipoteza głosiła, że ​​nadmierny czas pracy jest spowodowany przez GC.

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% 

To było w rzeczywistości poprawne. Czytałem, że GC musi przejść stos przed każdą kolekcją i to ma silne implikacje dla sposobu, w jaki program powinien być zbudowany w .NET, ale nie rozumiem GC na tyle dobrze, aby komentować, dlaczego zależności między typami danych są pozostawione same sobie.

Powyższy pomiar dotyczy trybu 32-bitowego. Dzięki narzędziu PerfView 64-bitowe pomiary są przerywane i trwały 15 razy dłużej, aby zakończyć z nieznanego powodu.

Nie mogę również wyjaśnić, dlaczego tryb 32-bitowy jest 2x szybszy od pierwotnego testu porównawczego, ponieważ nie jest tak, że stos byłby 2 razy większy w porównaniu z trybem 64-bitowym.