Prev: hunchentoot doesn't show a picture
Next: Emacs Form Feed (^L) Display Suggestion and Tips
From: Norbert_Paul on 25 Jun 2010 05:09
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.
That's a matter of taste.
I almost always use nreverse for this.
From: Nicolas Neuss on 25 Jun 2010 06:07
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.
> That's a matter of taste.
> I almost always use nreverse for this.

(nreverse (list 'taste 'strange 'a 'have 'you))

Nicolas
From: Pascal J. Bourguignon on 25 Jun 2010 06:19
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/


>> 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.

And speed often equates to efficiency, which nowadays equates to
energy sparing, which is considered good.


--
__Pascal Bourguignon__ http://www.informatimago.com/
From: Tamas K Papp on 25 Jun 2010 07:41
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".

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).

>>> 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*))

The timing output was

timing (LIST-ITER *N*)
Evaluation took:
0.937 seconds of real time
0.930000 seconds of total run time (0.630000 user, 0.300000 system)
[ Run times consist of 0.790 seconds GC time, and 0.140 seconds non-GC time. ]
99.25% CPU
2,366,979,007 processor cycles
160,013,648 bytes consed

timing (LIST-LOOP *N*)
Evaluation took:
1.122 seconds of real time
1.120000 seconds of total run time (0.780000 user, 0.340000 system)
[ Run times consist of 1.020 seconds GC time, and 0.100 seconds non-GC time. ]
99.82% CPU
2,836,058,779 processor cycles
160,015,312 bytes consed

timing (LIST-REVERSE *N*)
Evaluation took:
2.570 seconds of real time
2.570000 seconds of total run time (1.870000 user, 0.700000 system)
[ Run times consist of 2.290 seconds GC time, and 0.280 seconds non-GC time. ]
100.00% CPU
6,493,731,431 processor cycles
320,038,384 bytes consed

timing (LIST-NREVERSE *N*)
Evaluation took:
1.207 seconds of real time
1.210000 seconds of total run time (0.960000 user, 0.250000 system)
[ Run times consist of 0.850 seconds GC time, and 0.360 seconds non-GC time. ]
100.25% CPU
3,048,737,103 processor cycles
160,016,688 bytes consed

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.

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.

Tamas
From: Nicolas Neuss on 25 Jun 2010 08:04
pjb(a)informatimago.com (Pascal J. Bourguignon) writes:

> 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/

The following is from the conclusion section of your article:

"The best thing to do is to avoid writing code that conses lists
altogether. Whenever possible, you should use standard parts of
Common Lisp that do the consing for you. In particular, you should
use functions like replace, map, reduce, remove, union,
etc. whenever they are appropriate. Beyond this, you should take
advantage of looping macro packages such as loop and Series."

So your reference argues in favor of loop!

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