Prev: hunchentoot doesn't show a picture
Next: Emacs Form Feed (^L) Display Suggestion and Tips
From: Norbert_Paul on 25 Jun 2010 08:10
Nicolas Neuss wrote:
> (nreverse (list 'taste 'strange 'a 'have 'you))
T
From: Pascal J. Bourguignon on 25 Jun 2010 08:23
Tamas K Papp <tkpapp(a)gmail.com> writes:

> On Fri, 25 Jun 2010 12:19:43 +0200, Pascal J. Bourguignon wrote:
>
>> Nicolas Neuss <lastname(a)kit.edu> writes:
>>
>>> Norbert_Paul <norbertpauls_spambin(a)yahoo.com> writes:
>>>
>>>> Tamas K Papp wrote:
>>>>> Collecting via loop/iter is usually at least as fast as using
>>>>> nreverse (in my experience, on SBCL). Given that the former provide
>>>>> a more natural idiom, I rarely every use nreverse for this.
>>
>> If by collecting via loop/iter you mean keeping and updating a pointer
>> to the last cons, to build the list in order, then all you can say that
>> it can be made at MOST as fast as using nreverse. But using nreverse is
>> at LEAST as fast as that. See Chapter 3 of:
>> http://www.merl.com/papers/TR93-17/
>
> I don't see how that paper supports your argument above. The author
> says "the facts suggest that neither approach is obviously faster",
> then does some instruction counting on a particular machine. Given
> that the article is from 1993, I don't see how this is extremely
> relevant to performance today, with memory access dominating
> performance in a lot of cases. The author also makes the observation
> that "[cache performance] could tilt the performance balance in favor
> of the rplacd approach".

In my workstation I've got 8 MB of L-3 cache.
How long a list do I need to build before RPLACA demonstrate an advantage?


> So I don't see how you establish the inequalities you claim above. I
> think that the only way to see what is faster is via benchmarking (see
> below).

The fact is that the inequality doesn't hold. But almost. It's more
like this:

faster slower
nreverse ---------------------------------|
rplaca |------------------------------

than the reverse.



Ok you may argue that it's really more like:

faster slower
nreverse |--------|
rplaca |--------|


and indeed I agree that it doesn't make a difference in practice.


>>>> That's a matter of taste.
>>>> I almost always use nreverse for this.
>>>
>>> (nreverse (list 'taste 'strange 'a 'have 'you))
>>
>> As long as you consider taste for speed a strange taste.
>
> Your "taste for speed" is better phrased here as "taste for a priori
> beliefs untainted by actual benchmarking".
>
> I ran the following in SBCL (everything compiled):
>
> (declaim (optimize speed))
>
> (defmacro silent-time (form)
> `(progn
> (format t "~&timing ~A~%" ',form)
> (sb-ext:gc)
> (time ,form)
> (values)))
>
> (defun list-nreverse (n)
> (declare (fixnum n))
> (let (list)
> (dotimes (i n)
> (push i list))
> (nreverse list)))
>
> (defun list-reverse (n)
> (declare (fixnum n))
> (let (list)
> (dotimes (i n)
> (push i list))
> (reverse list)))
>
> (defun list-loop (n)
> (declare (fixnum n))
> (loop
> for i from 0 below n
> collect i))
>
> (defun list-iter (n)
> (declare (fixnum n))
> (iterate:iter
> (iterate:for i :from 0 :below n)
> (declare (iterate:declare-variables))
> (iterate:collect i)))
>
> (defparameter *n* (expt 10 7))
>
> (silent-time (list-iter *n*))
> (silent-time (list-loop *n*))
> (silent-time (list-reverse *n*))
> (silent-time (list-nreverse *n*))
>
> Apparently, GC dominates the timing, as expected. Note that if I
> rerun the benchmarks, +/- 10% time differences happen, so the only
> conclusion one can make is that for this particular implementation,
> ITER/LOOP is as fast as NREVERSE, so there is no optimization reason
> to use the latter if one prefers the style of iteration macros.
>


clisp seems to give more stable run times and demonstrates a slight
advantage for nreverse.

;; Compiling file /home/pjb/time-iter.lisp ...
;; Wrote file /home/pjb/time-iter.fas
;; Loading file /home/pjb/time-iter.fas ...
timing (LIST-ITER *N*)
Real time: 2.007607 sec.
Run time: 2.005694 sec.
Space: 160000144 Bytes
GC: 12, GC time: 0.919861 sec.
timing (LIST-LOOP *N*)
Real time: 1.838736 sec.
Run time: 1.836721 sec.
Space: 160000144 Bytes
GC: 12, GC time: 0.972853 sec.
timing (LIST-REVERSE *N*)
Real time: 2.580004 sec.
Run time: 2.576608 sec.
Space: 320000144 Bytes
GC: 15, GC time: 1.719739 sec.
timing (LIST-NREVERSE *N*)
Real time: 1.826898 sec.
Run time: 1.824723 sec.
Space: 160000144 Bytes
GC: 12, GC time: 0.976853 sec.
;; Loaded file /home/pjb/time-iter.fas


> If there is any systematic difference either way, it is unlikely to be
> significant in real life code. I would rather make my code readable
> and worry about optimizations that actually make sense.

Indeed.


--
__Pascal Bourguignon__ http://www.informatimago.com/
From: Norbert_Paul on 25 Jun 2010 08:32
Norbert_Paul wrote:
> Nicolas Neuss wrote:
>> (nreverse (list 'taste 'strange 'a 'have 'you))
> T

Some say so to me, when I tell them I'm using LISP
("What's that?").
I was once called "snob" by a former principal for
preferring LaTeX over Word, Linux over Windows...
From: Tamas K Papp on 25 Jun 2010 08:33
On Fri, 25 Jun 2010 14:23:27 +0200, Pascal J. Bourguignon wrote:

>> So I don't see how you establish the inequalities you claim above. I
>> think that the only way to see what is faster is via benchmarking (see
>> below).
>
> The fact is that the inequality doesn't hold. But almost. It's more
> like this:
>
> faster slower
> nreverse ---------------------------------| rplaca
> |------------------------------
>
> than the reverse.
>
>
>
> Ok you may argue that it's really more like:
>
> faster slower
> nreverse |--------| rplaca
> |--------|
>
>
> and indeed I agree that it doesn't make a difference in practice.

I must have missed the arguments that support these claims. In any
case, please forgive me but I am very bad at a priori reasoning about
performance on today's machines (I find that my expectations are
frequently refuted), so I tend to rely on benchmarking/profiling.

> clisp seems to give more stable run times and demonstrates a slight
> advantage for nreverse.

Not when compared to loop:

> timing (LIST-LOOP *N*)
> Real time: 1.838736 sec.
> Run time: 1.836721 sec.
> Space: 160000144 Bytes
> GC: 12, GC time: 0.972853 sec.
> timing (LIST-NREVERSE *N*)
> Real time: 1.826898 sec.
> Run time: 1.824723 sec.
> Space: 160000144 Bytes
> GC: 12, GC time: 0.976853 sec.

And I wonder how large the noise is: if you consider a 10% measurement
error, then iter, loop and nreverse are equally good.

Personally, I find loop/iter constructs more readable than nreverse,
especially in nontrivial loops with multiple collections. And given
that there is no significant advantage to nreverse in practice, I
don't see why people advocate its use.

Tamas
First  |  Prev  | 
Pages: 1 2 3 4
Prev: hunchentoot doesn't show a picture
Next: Emacs Form Feed (^L) Display Suggestion and Tips