why REVAPPEND?
in [Lisp]
|
Prev: tagbody vs. defun
Next: A Fateman paper
From: Pillsy on 28 Oct 2009 15:45 On Oct 28, 1:36 pm, Chris Riesbeck <Chris.Riesb...(a)gmail.com> wrote: > Pascal Costanza wrote: [...] > > A typical situation in an interpreter is that you want to process a list > > of conses that are supposed to end up as new variable bindings, and put > > them on top of existing variable bindings. The idiom is this: > > (let ((new-bindings '())) > > (dolist (binding source-of-new-bindings) > > (push (process binding) new-bindings)) > > (revappend new-bindings existing-bindings)) > > You would actually use nreconc here, but this is the motivation for > > those two operators. The reversal of the first argument is necessary > > because the push leads to a list of new-bindings that is in the wrong > > order initially. [...] > And I take it you can't just push onto existing-bindings directly? Not if you don't want them to wind up in reverse order at the front of EXISTING-BINDINGS! Cheers, Pillsy
From: Kaz Kylheku on 28 Oct 2009 17:51 On 2009-10-28, Chris Riesbeck <Chris.Riesbeck(a)gmail.com> wrote: > Pascal Costanza wrote: >> I am not aware of a more efficient, but still elegant solution for this >> particular use case. > > And I take it you can't just push onto existing-bindings directly? No, because that will be backwards. Existing-bindings are in the proper order, but your pushes will be reversed.
From: Kaz Kylheku on 28 Oct 2009 18:48 On 2009-10-28, Pascal Costanza <pc(a)p-cos.net> wrote: > vippstar wrote: >> On Oct 28, 4:55 am, Joshua Taylor <tay...(a)cs.rpi.edu> wrote: >>> Chris Riesbeck wrote: >>>> Is there some actual usefulness to REVAPPEND? In pre-Common Lisp days, I >>>> assumed it was a utility created to define REVERSE, but it made it into >>>> CL unscathed. Anyone know why? >>> If REVERSE and APPEND each traverse their first argument once, then >>> (APPEND (REVERSE l1) l2) requires O(2*length(l1)) time. REVAPPEND can >>> combine the traversals and bring it down to O(length(l1)). //JT >> >> Still, it occurs often that an (f (g x)) form would be using half >> operations if f and g are implemented into a single function. Was >> REVAPPEND standing out so much from all the other cases that it was >> included in the spec? > > A typical situation in an interpreter is that you want to process a list > of conses that are supposed to end up as new variable bindings, and put > them on top of existing variable bindings. The idiom is this: > > (let ((new-bindings '())) > (dolist (binding source-of-new-bindings) > (push (process binding) new-bindings)) > (revappend new-bindings existing-bindings)) > > You would actually use nreconc here, but this is the motivation for > those two operators. The reversal of the first argument is necessary > because the push leads to a list of new-bindings that is in the wrong > order initially. Even with NRECONC, are you sure this is more efficient than: (nconc (mapcar #'process source-of-new-bindings) existing-bindings) ? MAPCAR gives us the conses in order. NCONC has to walk through them, but this access is read-only except for editing the last CDR to point it to EXISTING-BINDINGS. NRECONC has to rewrite the CDR's in order to reverse the list. That's extra memory accesses, and writes too: cache-line dirtying. MAPCAR can avoid writing the conses twice. Using an internal function in the Lisp implementation's kernel, it can allocate conses which are uninitialized. It can keep a pointer to the previous cons in each new iteration, and set that cons's CDR field when it knows the next cons (or reaches the end, when it finalized the list by storing the terminating NIL). > I am not aware of a more efficient, but still elegant solution for this > particular use case. Unlikely to be efficient at all, but seems worth mentioning: (reduce #'cons source-of-new-bindings :key #'process :initial-value existing-bindings :from-end t) I'd like to see some reduce hack which does left-associatively. I'm not up to it. :)
From: Pascal Costanza on 31 Oct 2009 18:42 Kaz Kylheku wrote: > On 2009-10-28, Pascal Costanza <pc(a)p-cos.net> wrote: >> vippstar wrote: >>> On Oct 28, 4:55 am, Joshua Taylor <tay...(a)cs.rpi.edu> wrote: >>>> Chris Riesbeck wrote: >>>>> Is there some actual usefulness to REVAPPEND? In pre-Common Lisp days, I >>>>> assumed it was a utility created to define REVERSE, but it made it into >>>>> CL unscathed. Anyone know why? >>>> If REVERSE and APPEND each traverse their first argument once, then >>>> (APPEND (REVERSE l1) l2) requires O(2*length(l1)) time. REVAPPEND can >>>> combine the traversals and bring it down to O(length(l1)). //JT >>> Still, it occurs often that an (f (g x)) form would be using half >>> operations if f and g are implemented into a single function. Was >>> REVAPPEND standing out so much from all the other cases that it was >>> included in the spec? >> A typical situation in an interpreter is that you want to process a list >> of conses that are supposed to end up as new variable bindings, and put >> them on top of existing variable bindings. The idiom is this: >> >> (let ((new-bindings '())) >> (dolist (binding source-of-new-bindings) >> (push (process binding) new-bindings)) >> (revappend new-bindings existing-bindings)) >> >> You would actually use nreconc here, but this is the motivation for >> those two operators. The reversal of the first argument is necessary >> because the push leads to a list of new-bindings that is in the wrong >> order initially. > > Even with NRECONC, are you sure this is more efficient than: > > (nconc (mapcar #'process source-of-new-bindings) existing-bindings) > > ? > > MAPCAR gives us the conses in order. NCONC has to walk through them, but > this access is read-only except for editing the last CDR to point it > to EXISTING-BINDINGS. > > NRECONC has to rewrite the CDR's in order to reverse the list. > That's extra memory accesses, and writes too: cache-line dirtying. > > MAPCAR can avoid writing the conses twice. Using an internal function in the > Lisp implementation's kernel, it can allocate conses which are uninitialized. > It can keep a pointer to the previous cons in each new iteration, and set that > cons's CDR field when it knows the next cons (or reaches the end, when it > finalized the list by storing the terminating NIL). Yes, that's the classic distinction between collecting in reverse order, and then performing an nreverse, vs. collecting in 'correct' order by way of 'pointer chasing.' See http://doi.acm.org/10.1145/181889.181892 for a (pretty old) discussion of that topic. That paper concludes that (a) the nreverse solution is usually faster (which is indeed somewhat counter-intuitive), but also that (b) the difference is usually not large, so in practice it doesn't matter much, which of the two versions you use. Without having investigated this any further, I just assume that NRECONC is equally good as NREVERSE. Note that in your example there may be additional overhead by using MAPCAR, which requires additional function calls (to #'process in this case). But this can easily avoided by using LOOP: (nconc (loop for binding in source-of-new-bindings collect ... inline processing of binding ...) existing-bindings) There is, however, the additional overhead of one more iteration through the processed bindings, which could be avoided by manual 'pointer chasing.' It would be nice if LOOP had a way to define 'tails' for COLLECT, NCONC, APPEND, etc. - it could then optimize this case internally, and would look more elegant, IMHO. >> I am not aware of a more efficient, but still elegant solution for this >> particular use case. > > Unlikely to be efficient at all, but seems worth mentioning: > > (reduce #'cons source-of-new-bindings > :key #'process > :initial-value existing-bindings > :from-end t) Neat. :) > I'd like to see some reduce hack which does left-associatively. > I'm not up to it. :) Pascal -- My website: http://p-cos.net Common Lisp Document Repository: http://cdr.eurolisp.org Closer to MOP & ContextL: http://common-lisp.net/project/closer/
From: Thomas F. Burdick on 3 Nov 2009 07:45
On Oct 28, 12:14 pm, Pascal Costanza <p...(a)p-cos.net> wrote: > vippstar wrote: > > On Oct 28, 4:55 am, Joshua Taylor <tay...(a)cs.rpi.edu> wrote: > >> Chris Riesbeck wrote: > >>> Is there some actual usefulness to REVAPPEND? In pre-Common Lisp days, I > >>> assumed it was a utility created to define REVERSE, but it made it into > >>> CL unscathed. Anyone know why? > >> If REVERSE and APPEND each traverse their first argument once, then > >> (APPEND (REVERSE l1) l2) requires O(2*length(l1)) time. REVAPPEND can > >> combine the traversals and bring it down to O(length(l1)). //JT > > > Still, it occurs often that an (f (g x)) form would be using half > > operations if f and g are implemented into a single function. Was > > REVAPPEND standing out so much from all the other cases that it was > > included in the spec? > > A typical situation in an interpreter is that you want to process a list > of conses that are supposed to end up as new variable bindings, and put > them on top of existing variable bindings. The idiom is this: > > (let ((new-bindings '())) > (dolist (binding source-of-new-bindings) > (push (process binding) new-bindings)) > (revappend new-bindings existing-bindings)) > > You would actually use nreconc here, but this is the motivation for > those two operators. The reversal of the first argument is necessary > because the push leads to a list of new-bindings that is in the wrong > order initially. > > I am not aware of a more efficient, but still elegant solution for this > particular use case. I think the historical alternative would have been to use tconc and lconc: (let ((new-bindings (list nil))) (dolist (binding source-of-new-bindings) (tconc new-bindings (process binding))) (car (lconc new-bindings existing-bindings))) |