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
मेरे पास एक बहुत बड़ा दुभाषिया है जिसका प्रदर्शन व्यवहार मैं बेहतर समझने की कोशिश कर रहा हूं इसलिए मैंने उपर्युक्त बनाया। मुझे निश्चित रूप से यकीन है कि कुछ उदाहरणों पर मैं उस सुपरलाइनर स्केलिंग को देख रहा हूं, जिस तरह से यह स्टैक का उपयोग करता है, लेकिन मुझे यकीन नहीं है कि यह क्यों हो रहा है इसलिए मैं यहां पूछना चाहता था।स्टैक का गहरा उपयोग क्यों एक साधारण दुभाषिया के लिए superlinear समय व्यवहार का कारण बनता है?
जैसा कि आप देख सकते हैं, क्योंकि मैं n 2x से भिन्न होता हूं, समय उस समय से कहीं अधिक भिन्न होता है, और ऐसा लगता है कि स्केलिंग घातीय है जो मेरे लिए आश्चर्यजनक है। यह भी आश्चर्य की बात है कि सीपीएसड दुभाषिया ढेर आधारित एक से तेज है। ऐसा क्यों है?
मैं यह भी पूछना चाहता हूं कि क्या मैं उपरोक्त के बराबर कोड को गैर .NET भाषा या यहां तक कि सी में कोडित करता हूं?
वाह, यह अच्छी तरह से देखा गया है। मैं निश्चित रूप से पेड़ के निर्माण को मापने का इरादा नहीं रखता था। मुझे खुशी है कि मैंने अब इस सवाल को पोस्ट किया है। इसके अलावा मुझे यह जानकर बहुत खुशी हुई कि मैं अपने दुभाषिया को सीपीएस में परिवर्तित करके बेहतर प्रदर्शन कर सकता हूं। सवाल यह है कि स्टैक संस्करण इतना लंबा क्यों लेता है अभी भी पकड़ने के लिए है। –