7 Sep 17:49
reverse and nreverse in nset performance review
From: Stavros Macrakis <macrakis <at> alum.mit.edu>
Subject: reverse and nreverse in nset performance review
Newsgroups: gmane.comp.mathematics.maxima.general
Date: 2008-09-07 15:53:18 GMT
Subject: reverse and nreverse in nset performance review
Newsgroups: gmane.comp.mathematics.maxima.general
Date: 2008-09-07 15:53:18 GMT
Andreas,
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 -> 1.21 (March 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?
Thanks,
-s
(*) 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?
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 -> 1.21 (March 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?
Thanks,
-s
(*) 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?
_______________________________________________ Maxima mailing list Maxima <at> math.utexas.edu http://www.math.utexas.edu/mailman/listinfo/maxima
RSS Feed