[Maxima] reverse and nreverse in nset performance review
macrakis at alum.mit.edu
Sun Sep 7 10:53:18 CDT 2008
In reviewing the performance of the set functions, I noticed that there was
a call to "reverse" in do-merge-asym where an "nreverse" would make more
sense. I wrote this code, so I was embarrassed to see this elementary
oversight. But then I checked the revision log of nset, and discovered that
it was you who had made this change in nset.lisp 1.20 ->
2007). Barton had also pointed this out to me last year, but I wasn't
focussed on nset at the time.
Nreverse is of course a destructive operation and reverse is a
non-destructive (copy) operation, so nreverse is suitable when it is known
that a list structure is unshared (e.g. (nreverse (mapcar ...))) while
reverse is suitable when a list structure may be shared. Nreverse has the
advantage of not cons'ing new list structure unnecessarily and in most
implementations should be much faster than reverse.(*)
I had used nreverse in do-merge-asym because the list structure here is
supposed to be guaranteed to be unshared. I assume you changed it to
reverse in the belief that there are cases where it might be shared. If that
is true, then there is a bug in do-merge-asym which should be corrected at
the source, not symptomatically. If it is not true, the only effect will be
to increase the amount of cons'ing, which is generally considered a bad
thing. WHich is it?
(*) In some implementations, like the old Lisp Machine Zetalisp, nreverse
may actually be less efficient because of special data representations for
linear lists. Do any current Lisp implementations have such a property?
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Maxima