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 1000000)]) >> (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.
