Re: [racket-users] Is this parameters-using code O(n^2)?
Matthew Flatt writes: > At Sun, 11 Nov 2018 13:55:32 -0500, Christopher Lemmer Webber wrote: >> It struck me recently that I tend to think of parameters as O(1) when in >> reality they're O(n), where n is the number of frames on the stack, >> right? > > No, parameter lookup is amoritzed O(1). > > Well, actually it's up to O(log N) for N parameters and distinct > continuation-mark keys. But thinking of it as O(1) is normally > justified, unless you create extremely many distinct parameters or > extrmely many distinct continuation-mark keys. > >> Due to that reason, I figured the following code would absolutely trash >> my computer: >> >> (let ([limit-param (make-parameter 100)]) >>(let lp ([n 1]) >> (if (= n (limit-param)) >> '() >> (cons n >>(lp (add1 n) >>(void)); return void just to avoid printing that all out >> >> Nope, runs almost instantaneously. >> >> What's going on? It's nice to see my computer *not* trashed, but now >> I'm unsure about my understanding of how parameters work. > > A parameterization is stored in a continuation mark. If > continuation-mark lookup has to traverse N continuation frames to find > a value, then it stashes the result half-way at N/2 frames away, and so > on. > > The stash and a parameterization are both implemented using immutable > hash tables, so that's where the O(log N) part shows up. Oh ok! That's very helpful. I thought it was actually walking back up frames of the stack, but I see now that was a misconception. Thanks! -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: [racket-users] Is this parameters-using code O(n^2)?
On 11/11/2018 1:55 PM, Christopher Lemmer Webber wrote: It struck me recently that I tend to think of parameters as O(1) when in reality they're O(n), where n is the number of frames on the stack, right? I was considering writing some code that cons'ed itself on its natural recursion, but in the process was checking the parameter. But then I realized it would be O(n^2) in the sense that it's the number of steps of the application times the number of frames on the stack... right? Due to that reason, I figured the following code would absolutely trash my computer: (let ([limit-param (make-parameter 100)]) (let lp ([n 1]) (if (= n (limit-param)) '() (cons n (lp (add1 n) (void)); return void just to avoid printing that all out Nope, runs almost instantaneously. What's going on? It's nice to see my computer *not* trashed, but now I'm unsure about my understanding of how parameters work. - Chris Your code isn't providing different parameter values to different iterations of the loop - there is only one value which the loop accesses each cycle. All you are actually doing is constructing a 1M element list. If you (re)parameterize the loop each cycle, it runs ~5x slower on my machines, but I expect the difference simply is maintenance of the parameter data structure - not searching it. Parameters are, conceptually at least, a stack [not sure the actual implementation] - they are modeled somewhat after Lisp's special variables. At any point, code can see only the current top-of-stack value for a given parameter. George -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: [racket-users] Is this parameters-using code O(n^2)?
At Sun, 11 Nov 2018 13:55:32 -0500, Christopher Lemmer Webber wrote: > It struck me recently that I tend to think of parameters as O(1) when in > reality they're O(n), where n is the number of frames on the stack, > right? No, parameter lookup is amoritzed O(1). Well, actually it's up to O(log N) for N parameters and distinct continuation-mark keys. But thinking of it as O(1) is normally justified, unless you create extremely many distinct parameters or extrmely many distinct continuation-mark keys. > Due to that reason, I figured the following code would absolutely trash > my computer: > > (let ([limit-param (make-parameter 100)]) >(let lp ([n 1]) > (if (= n (limit-param)) > '() > (cons n >(lp (add1 n) >(void)); return void just to avoid printing that all out > > Nope, runs almost instantaneously. > > What's going on? It's nice to see my computer *not* trashed, but now > I'm unsure about my understanding of how parameters work. A parameterization is stored in a continuation mark. If continuation-mark lookup has to traverse N continuation frames to find a value, then it stashes the result half-way at N/2 frames away, and so on. The stash and a parameterization are both implemented using immutable hash tables, so that's where the O(log N) part shows up. -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: [racket-users] Is this parameters-using code O(n^2)?
I completely agree with Matthias in the sense that you should get a design that focuses on clarity before worrying about performance, but just in general terms, looking up a parameter's value is roughly proportional to the number of parameterize uses you are inside. Not other context information (like "the stack"). So O(1) is probably a better rule of thumb. Robby On Sun, Nov 11, 2018 at 1:12 PM Matthias Felleisen wrote: > > > On Nov 11, 2018, at 1:55 PM, Christopher Lemmer Webber < > cweb...@dustycloud.org> wrote: > > > > It struck me recently that I tend to think of parameters as O(1) when in > > reality they're O(n), where n is the number of frames on the stack, > > right? I was considering writing some code that cons'ed itself on its > > natural recursion, but in the process was checking the parameter. > > But then I realized it would be O(n^2) in the sense that it's the number > > of steps of the application times the number of frames on the stack... > > right? > > > > Due to that reason, I figured the following code would absolutely trash > > my computer: > > > > (let ([limit-param (make-parameter 100)]) > > (let lp ([n 1]) > > (if (= n (limit-param)) > > '() > > (cons n > > (lp (add1 n) > > (void)); return void just to avoid printing that all out > > > > Nope, runs almost instantaneously. > > > > What's going on? It's nice to see my computer *not* trashed, but now > > I'm unsure about my understanding of how parameters work. > > > It is somewhat futile to figure out the exact performance characteristics > of programs in high-level languages. Here are two ways to think about what > the compiler really runs: > > (define N 100) > > (= N >(length > (let ([P (make-parameter N)]) > (let lp ([n 0]) > (if (= n (P)) '() (cons n (lp (add1 n > > ;; possibility 1: lambda lifted (constant-time function call) > > (define P (make-parameter N)) > > (= N >(length > (let lp ([n 0]) > (if (= n (P)) '() (cons n (lp (add1 n))) > > > ;; possibility 2: constant folded (we notice that there's no call (P v)) > > (= N >(length > (let ([P (make-parameter N)]) > (let lp ([n 0]) > (if (= n N) '() (cons n (lp (add1 n > > I suspect it is neither and that there are 3 more in addition to the true > program. > > If it is any of the above, you can’t generalize much about things.for > other programs. Even decompiling won’t tell you exactly what will happen in > a different context. > > I conjecture that even at the ASM level you no longer have precise > predictions. So I wait and see when I write larger programs. > > — Matthias > > > > > -- > You received this message because you are subscribed to the Google Groups > "Racket Users" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to racket-users+unsubscr...@googlegroups.com. > For more options, visit https://groups.google.com/d/optout. > -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: [racket-users] Is this parameters-using code O(n^2)?
> On Nov 11, 2018, at 1:55 PM, Christopher Lemmer Webber > wrote: > > It struck me recently that I tend to think of parameters as O(1) when in > reality they're O(n), where n is the number of frames on the stack, > right? I was considering writing some code that cons'ed itself on its > natural recursion, but in the process was checking the parameter. > But then I realized it would be O(n^2) in the sense that it's the number > of steps of the application times the number of frames on the stack... > right? > > Due to that reason, I figured the following code would absolutely trash > my computer: > > (let ([limit-param (make-parameter 100)]) > (let lp ([n 1]) > (if (= n (limit-param)) > '() > (cons n > (lp (add1 n) > (void)); return void just to avoid printing that all out > > Nope, runs almost instantaneously. > > What's going on? It's nice to see my computer *not* trashed, but now > I'm unsure about my understanding of how parameters work. It is somewhat futile to figure out the exact performance characteristics of programs in high-level languages. Here are two ways to think about what the compiler really runs: (define N 100) (= N (length (let ([P (make-parameter N)]) (let lp ([n 0]) (if (= n (P)) '() (cons n (lp (add1 n ;; possibility 1: lambda lifted (constant-time function call) (define P (make-parameter N)) (= N (length (let lp ([n 0]) (if (= n (P)) '() (cons n (lp (add1 n))) ;; possibility 2: constant folded (we notice that there's no call (P v)) (= N (length (let ([P (make-parameter N)]) (let lp ([n 0]) (if (= n N) '() (cons n (lp (add1 n I suspect it is neither and that there are 3 more in addition to the true program. If it is any of the above, you can’t generalize much about things.for other programs. Even decompiling won’t tell you exactly what will happen in a different context. I conjecture that even at the ASM level you no longer have precise predictions. So I wait and see when I write larger programs. — Matthias -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
[racket-users] Is this parameters-using code O(n^2)?
It struck me recently that I tend to think of parameters as O(1) when in reality they're O(n), where n is the number of frames on the stack, right? I was considering writing some code that cons'ed itself on its natural recursion, but in the process was checking the parameter. But then I realized it would be O(n^2) in the sense that it's the number of steps of the application times the number of frames on the stack... right? Due to that reason, I figured the following code would absolutely trash my computer: (let ([limit-param (make-parameter 100)]) (let lp ([n 1]) (if (= n (limit-param)) '() (cons n (lp (add1 n) (void)); return void just to avoid printing that all out Nope, runs almost instantaneously. What's going on? It's nice to see my computer *not* trashed, but now I'm unsure about my understanding of how parameters work. - Chris -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
