>Paul Foley wrote:
>
> Aside from the horrible formatting, this is a mind-numbingly stupid
> implementation.
>
> (defun every-other (list &key (start 0))
> (let ((test (if (evenp start) #'evenp #'oddp)))
> (loop for x in list as i upfrom 0
> when (and (>= i start) (funcall test i)) collect x)))
>
> On Mon, 15 Feb 1999 06:11:29 +0000, SLong wrote:
>
> > Sometimes the penalty of verbosity pays is not so great as the confusion
> > of obfuscation.
>
> > (defun every-other
> > (list-in
> > &key (start 0)
> > )
> > (if (listp list-in)
> > (do* ((theList (if (listp list-in) list-in (list list-in)))
> > (limit (- (length theList) 1))
> > (n start (+ n 2))
> > (elements-out nil)
> > )
> > ((> n limit) (return (reverse elements-out)))
> > (push (nth n theList) elements-out)
> > )
> > nil
> > )
> > )
>
> It helps if you actually know some Lisp.
>
>
> First, it should be formatted like this:
>
> (defun every-other (list-in &key (start 0))
> (if (listp list-in)
> (do* ((theList (if (listp list-in) list-in (list list-in)))
> (limit (- (length theList) 1))
> (n start (+ n 2))
> (elements-out nil))
> ((> n limit) (return (reverse elements-out)))
> (push (nth n theList) elements-out))
> nil))
>
> [Notice the lack of lines containing only parentheses.]
>
> Second, the first line in the DO* tests if (listp list-in), which you
> already know to be true (see the test in the previous line).
>
> Third, there's no need to use RETURN, and there's no need to make
> another copy of the elements-out list; use NREVERSE.
>
> Fourth, using NTH to find each element of the list means it has to
> walk down the entire cdr chain every time around the loop.
>
> Fifth, a minor point, use WHEN instead of IF in the (outer) test.
>
> How about
>
> (defun every-other (list &key (start 0))
> (let ((test (if (evenp start) #'evenp #'oddp)))
> (loop for x in list as i upfrom 0
> when (and (>= i start) (funcall test i)) collect x)))
>
> I timed both over a list of 50000 items:
>
> Your version: 103.03 seconds
> My version: 0.13 seconds
>
> No wonder you think Lisp is slow.
>
> --
> (setq reply-to
> (concatenate 'string "Paul Foley " "<mycroft" '(··@) "actrix.gen.nz>"))
I normally call someone misinformed if they don't know, or stupid if
they choose ignorance. Paul seems to have a rudimentary understanding
of LISP, but the form of his response suggests that he is a jerk. He is
correct in stating that this implementation is not efficient, and even
looks like it was written in a hurry, but had his response been a little
less cocky, perhaps we could see some merit in his suggestions.
The original implementation of this ran less than a second on a 100MHz
Mac, with freeware LISP, half a meg of swap-space, on a 6700-node list.
Paul's also ran less than a second.
Get a better compiler.
As far as using avoiding "nth" or "do*" or "reverse", by using the loop
macro, Paul has added all the overhead and redundancy back in that you
saved by NOT using them. On my system, however, there was little
notieable effect other than a microscopic increase in file size.
Accessing a linked-list data structure (which is what LISP lists are,
doubly-linked, circular linked-lists) always requires one to
"march-down-the-list" unless you have the address of the element (cell)
as in
a hash table or a C linked-list.
Paul missed the most important point, which was not whether the defun
was the most efficient implementation. For those who haven't worked in
groups: code should be easy to comprehend. The greatest cost IS the
human factor. This is a constant in the software industry, whether one
usea C++, Java, or LISP. Finally, the look of the code doesn't have
anything to do with its execution (lines with only parenthesis).
-funcall of nil-
In article <·············@boeing.com>,
funcall-of-nil <··············@boeing.com> wrote:
>As far as using avoiding "nth" or "do*" or "reverse", by using the loop
>macro, Paul has added all the overhead and redundancy back in that you
>saved by NOT using them. On my system, however, there was little
>notieable effect other than a microscopic increase in file size.
>
>Accessing a linked-list data structure (which is what LISP lists are,
>doubly-linked, circular linked-lists) always requires one to
>"march-down-the-list" unless you have the address of the element (cell)
>as in
>a hash table or a C linked-list.
Of course you have to march down the list. However, using NTH means that
you have to march down the list from the beginning each time through the
loop. LOOP, MAPxxx, and DOLIST simply step a reference to the next cons
cell. Thus, an O(n^2) routine becomes O(n) when you use appropriate
iteration constructs.
LOOP's COLLECT verb also usually avoids the overhead of NREVERSE. Most
systems implement this by having a reference to the last cons cell of the
result list, and simply RPLACD it.
It's very unlikely that you can code more efficient ways to traverse a list
and collect a resulting list than what most LOOP implementations use
(they're mostly derived from the original code at MIT, which had these
optimizations 20 years ago).
>Paul missed the most important point, which was not whether the defun
>was the most efficient implementation. For those who haven't worked in
>groups: code should be easy to comprehend. The greatest cost IS the
Agreed. But even though I caution against premature optimizations, there
are some well-known performance bugaboos that people should be aware of in
general. NTH on lists shouldn't be avoided totally (it's convenient for
small lists or functions that need to operate on sequences), but it's a
signal that your data structure and algorithm may not match up. Calling
NTH in an inner loop is usually a sign of poor design: either you're using
a list when you should have used an array, or you should be walking the
list with an iteration construct rather than indexing it.
>human factor. This is a constant in the software industry, whether one
>usea C++, Java, or LISP. Finally, the look of the code doesn't have
>anything to do with its execution (lines with only parenthesis).
If you're presenting the code in public, looks matter. Even if you aren't,
other programmers may need to take over maintenance of your code, so you
should try to adhere to common style so that they'll be able to understand
it.
--
Barry Margolin, ······@bbnplanet.com
GTE Internetworking, Powered by BBN, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Don't bother cc'ing followups to me.
In article <·············@boeing.com>,
funcall-of-nil <··············@boeing.com> wrote:
>As far as using avoiding "nth" or "do*" or "reverse", by using the loop
>macro, Paul has added all the overhead and redundancy back in that you
>saved by NOT using them.
No, he didn't. Loop doesn't use NTH or REVERSE (the typical
implementation of COLLECT either RPLACDs onto the end of the
growing list, or pushes onto a stack list with an NREVERSE
at the end.)
The original program takes O(n^2) on a list of length n.
Paul's revised version takes linear time, even with the
loop macro.
>Accessing a linked-list data structure (which is what LISP lists are,
>doubly-linked, circular linked-lists)
You are mistaken. Lisp lists are singly linked and noncircular.
>Paul missed the most important point, which was not whether the defun
>was the most efficient implementation. For those who haven't worked in
>groups: code should be easy to comprehend. The greatest cost IS the
>human factor.
Lisp is unlike C, in that it is easy to write very inefficient
programs. Understandability *and* efficiency are important
when programming in Lisp. Efficiency often cannot be retrofitted
without major changes to the program.
-- Another Paul
* funcall-of-nil <··············@boeing.com>
| Accessing a linked-list data structure (which is what LISP lists are,
| doubly-linked, circular linked-lists) always requires one to
| "march-down-the-list" unless you have the address of the element (cell)
| as in a hash table or a C linked-list.
are you saying that doubly-linked lists require sequential access and
singly-linked lists don't? that's pretty amusing. considering that you
don't even know how Lisp's lists are represented, maybe it isn't amusing.
(how does CONS know which cell to point backwards at? does it traverse
the entire circular list to find the one that points to its argument?)
why _is_ it so hard to get this stuff right?
| Paul missed the most important point, which was not whether the defun
| was the most efficient implementation. For those who haven't worked in
| groups: code should be easy to comprehend. The greatest cost IS the
| human factor. This is a constant in the software industry, whether one
| usea C++, Java, or LISP. Finally, the look of the code doesn't have
| anything to do with its execution (lines with only parenthesis).
since the human factor is the most important, you hire good people and
get rid of the incompetent fools. that means "easy to comprehend"
changes meaning drastically from compulsory groups such as you have to
deal with during your education. if someone doesn't "get it" too
frequently, he's simply removed from the group.
since the human factor is the most important, you ensure that _people_
aren't unduly annoyed by ugly, stupid, or ignorant coding styles. those
who, are not welcome in voluntary groups, and if forced on people, case
the group performance to go down so much the _manager_ should be fired if
he doesn't clean up.
Lisp programmers are generally more expensive than C++ programmers. (I
don't know the Java market.) quite often, a project can succeed with one
or a tiny group of expert Lisp programmers (you just don't do Lisp for a
living if you aren't an expert�), but would require a large group of
average C++ programmers (the C++ experts are more expensive than almost
all Lisp programmers). and as we all know, group interaction is a _cost_
that increases with the number of members in the group, so the less talk
you can get away with, the better. this means style is _very_ important.
#:Erik
-------
� it takes _much_ less to become an expert in Common Lisp than in C++.
funcall-of-nil wrote:
>The original implementation of this ran less than a second on a 100MHz
>Mac, with freeware LISP, half a meg of swap-space, on a 6700-node
>list. Paul's also ran less than a second.
Unfortunately the (nth n theList) call really does slow things down.
Note that the ratio of operations for an n^2 algorithm with n of 6700
and n of 50000 is about 55. The ratio of the sizes of the input is
about 7.5. That means that the longer the lists are, the bigger the
difference between an order-n algorithm and an order-n^2 algorithm
will be.
Here's a standard kind of recursive solution that pre-processes the
input list.
(defun every-other (list-in &key (start 0))
(if (not (listp list-in))
nil
(let ((work-list (nthcdr start list-in)))
(every-other-aux work-list nil 0))))
(defun every-other-aux (list-in list-out count)
(if (null list-in)
(nreverse list-out)
(progn
(when (evenp count)
(push (car list-in) list-out))
(every-other-aux (cdr list-in) list-out (1+ count)))))
This will traverse the original list once (regardless of what the
:start argument is) and then reverse the pointers, so its run time
will be about 2n.
Here are some timings (PII-300 machine running CMUCL with default
optimization settings):
1) The original version on a 50000-element list:
(defun every-other (list-in &key (start 0))
(if (listp list-in)
(do* ((theList (if (listp list-in) list-in (list list-in)))
(limit (- (length theList) 1))
(n start (+ n 2))
(elements-out nil))
((> n limit) (return (reverse elements-out)))
(push (nth n theList) elements-out))
nil))
* (time (progn (every-other *test-list*) (values)))
Compiling LAMBDA NIL:
Compiling Top-Level Form:
Evaluation took:
17.46 seconds of real time
16.83377 seconds of user run time
0.007439 seconds of system run time
0 page faults and
401408 bytes consed.
*
2) Using the recursive version above I get
* (time (progn (every-other *test-list*) (values)))
Compiling LAMBDA NIL:
Compiling Top-Level Form:
Evaluation took:
0.01 seconds of real time
0.013694 seconds of user run time
0.0 seconds of system run time
0 page faults and
196520 bytes consed.
*
Note that these run times indicate that something is REALLY wrong with
the original version---the ratio of user run times is about 1200:1.
This is in line with Paul's results, which show a ratio of about
800:1.
3) Trying out the `loop' version:
(defun every-other (list &key (start 0))
(let ((test (if (evenp start) #'evenp #'oddp)))
(loop for x in list as i upfrom 0
when (and (>= i start) (funcall test i)) collect x)))
I get the following:
(time (progn (every-other *test-list*) (values)))
Compiling LAMBDA NIL:
Compiling Top-Level Form:
Evaluation took:
0.01 seconds of real time
0.017054 seconds of user run time
3.8e-5 seconds of system run time
0 page faults and
196608 bytes consed.
which is a bit SLOWER than the recursive version....
(Yes! Yes!) :-)
--
Fred Gilham ······@csl.sri.com
The vicissitudes of history, however, have not dissuaded them from
their earnest search for a "third way" between socialism and
capitalism, namely socialism. --- Fr. Richard John Neuhaus
Okay, okay. I hate to get drawn into these discussions about "Who
can write the 'best' version of this algorithm?" But in this case,
the answer just seemed so obvious to me:
(defun every-other (list &key (start 0))
(loop for item in (nthcdr start list) by #'cddr
collect item))
I don't see how one can get much better than this: compact, fast,
and comprehensible. I'm not generally a fan of LOOP, but in this
case it seems so simple as to be the preferred solution. Have I
missed anything?
If you want the numbers, keep reading. Otherwise, skip to the
next message.... :)
;;; -*- Mode: Lisp; Package: CL-USER -*-
(in-package "CL-USER")
;;; Original version, SLong <·········@isomedia.com>:
(defun every-other_1 (list-in &key (start 0))
(if (listp list-in)
(do* ((theList (if (listp list-in) list-in (list list-in)))
(limit (- (length theList) 1))
(n start (+ n 2))
(elements-out nil))
((> n limit) (return (reverse elements-out)))
(push (nth n theList) elements-out))
nil))
;;; Iterative version, Paul Foley <·······@actrix.gen.nz>:
(defun every-other_2 (list &key (start 0))
(let ((test (if (evenp start) #'evenp #'oddp)))
(loop for x in list as i upfrom 0
when (and (>= i start) (funcall test i)) collect x)))
;;; Recursive version, Fred Gilham <······@snapdragon.csl.sri.com>:
(defun every-other_3 (list-in &key (start 0))
(if (not (listp list-in))
nil
(let ((work-list (nthcdr start list-in)))
(every-other-aux work-list nil 0))))
(defun every-other-aux (list-in list-out count)
(if (null list-in)
(nreverse list-out)
(progn
(when (evenp count)
(push (car list-in) list-out))
(every-other-aux (cdr list-in) list-out (1+ count)))))
;;; Iterative version, Phil Stubblefield <····@rpal.rockwell.com>:
(defun every-other_4 (list &key (start 0))
(loop for item in (nthcdr start list) by #'cddr
collect item))
;;; Testing:
#||
(defvar *test-list* (loop for i from 0 below 50000 collect i)
"The common test list.")
(time (progn (every-other_1 *test-list*) (values)))
(time (progn (every-other_2 *test-list*) (values)))
(time (progn (every-other_3 *test-list*) (values)))
(time (progn (every-other_4 *test-list*) (values)))
Results on an UltraSparc 2 running Allegro CL 5.0:
USER(10): (time (progn (every-other_1 *test-list*) (values)))
; cpu time (non-gc) 33,720 msec user, 0 msec system
; cpu time (gc) 0 msec user, 0 msec system
; cpu time (total) 33,720 msec user, 0 msec system
; real time 34,417 msec
; space allocation:
; 50,001 cons cells, 0 symbols, 32 other bytes, 0 static bytes
USER(11): (time (progn (every-other_2 *test-list*) (values)))
; cpu time (non-gc) 80 msec user, 0 msec system
; cpu time (gc) 0 msec user, 0 msec system
; cpu time (total) 80 msec user, 0 msec system
; real time 97 msec
; space allocation:
; 25,002 cons cells, 0 symbols, 32 other bytes, 0 static bytes
USER(12): (time (progn (every-other_3 *test-list*) (values)))
; cpu time (non-gc) 50 msec user, 10 msec system
; cpu time (gc) 0 msec user, 0 msec system
; cpu time (total) 50 msec user, 10 msec system
; real time 81 msec
; space allocation:
; 25,001 cons cells, 0 symbols, 32 other bytes, 0 static bytes
USER(13): (time (progn (every-other_4 *test-list*) (values)))
; cpu time (non-gc) 20 msec user, 10 msec system
; cpu time (gc) 0 msec user, 0 msec system
; cpu time (total) 20 msec user, 10 msec system
; real time 54 msec
; space allocation:
; 25,002 cons cells, 0 symbols, 32 other bytes, 0 static bytes
||#
Phil Stubblefield
Rockwell Palo Alto Laboratory 650/325-7165
http://www.rpal.rockwell.com/~phil ····@rpal.rockwell.com
Phil Stubblefield wrote:
----------------------------------------
(defun every-other_4 (list &key (start 0))
(loop for item in (nthcdr start list) by #'cddr
collect item))
----------------------------------------
That's good. Even using the `cddr' trick in the recursive version it
is still more than 10% slower.
(defun every-other_3 (list-in &key (start 0))
(if (not (listp list-in))
nil
(let ((work-list (nthcdr start list-in)))
(every-other-aux work-list nil 0))))
(defun every-other-aux (list-in list-out count)
(if (null list-in)
(nreverse list-out)
(progn
(push (car list-in) list-out)
(every-other-aux (cddr list-in) list-out (1+ count)))))
;;;
;;; CMUCL, PII-300, (optimize (speed 3) (safety 0))
;;;
;;;Loop version
* (time (progn (every-other_4 *test-list*) (values)))
Compiling LAMBDA NIL:
Compiling Top-Level Form:
Evaluation took:
0.01 seconds of real time
0.008646 seconds of user run time
2.9999998e-5 seconds of system run time
0 page faults and
195520 bytes consed.
;;; Recursive version
* (time (progn (every-other_3 *test-list*) (values)))
Compiling LAMBDA NIL:
Compiling Top-Level Form:
Evaluation took:
0.01 seconds of real time
0.009531 seconds of user run time
7.2e-5 seconds of system run time
0 page faults and
203712 bytes consed.
(I ran these a bunch of times and the results above seem
representative.)
The moral, of course, is that sometimes when you get a better
algorithm you can start quibbling about milliseconds instead of
seconds.
--
Fred Gilham ······@csl.sri.com
The vicissitudes of history, however, have not dissuaded them from
their earnest search for a "third way" between socialism and
capitalism, namely socialism. --- Fr. Richard John Neuhaus
In article <··············@snapdragon.csl.sri.com>,
Fred Gilham <······@snapdragon.csl.sri.com> wrote:
>
>----------------------------------------
>(defun every-other_4 (list &key (start 0))
> (loop for item in (nthcdr start list) by #'cddr
> collect item))
>----------------------------------------
>
>That's good. Even using the `cddr' trick in the recursive version it
>is still more than 10% slower.
>
>(defun every-other_3 (list-in &key (start 0))
> (if (not (listp list-in))
> nil
> (let ((work-list (nthcdr start list-in)))
> (every-other-aux work-list nil 0))))
>
>(defun every-other-aux (list-in list-out count)
> (if (null list-in)
> (nreverse list-out)
> (progn
> (push (car list-in) list-out)
> (every-other-aux (cddr list-in) list-out (1+ count)))))
>
>
From your timings (which I deleted) you can see that the recursive
version conses more than the loop-based one. 'Nreverse' is not
necessary, as is the 'count' parameter.
A modified recursive version given below conses exactly the same number
of cons cells and other bytes (using ACL 4.3 on Solaris 5.6) and
there is not difference in speed. Basically you just measure allocation
and garbage collection times. Here's two datapoints each to give an
impression of the varying gc times for *both* versions:
USER(36): (length (time (EVERY-OTHER_3 *test-list* )))
; cpu time (non-gc) 1,700 msec user, 380 msec system
; cpu time (gc) 22,640 msec user, 1,610 msec system
; cpu time (total) 24,340 msec user, 1,990 msec system
; real time 33,175 msec
; space allocation:
; 5,000,002 cons cells, 0 symbols, 32 other bytes
5000000
USER(37): (length (time (EVERY-OTHER_3 *test-list* )))
; cpu time (non-gc) 1,540 msec user, 340 msec system
; cpu time (gc) 4,380 msec user, 600 msec system
; cpu time (total) 5,920 msec user, 940 msec system
; real time 6,991 msec
; space allocation:
; 5,000,002 cons cells, 0 symbols, 32 other bytes
5000000
USER(38): (length (time (EVERY-OTHER_4 *test-list* )))
; cpu time (non-gc) 1,650 msec user, 140 msec system
; cpu time (gc) 4,580 msec user, 30 msec system
; cpu time (total) 6,230 msec user, 170 msec system
; real time 7,877 msec
; space allocation:
; 5,000,002 cons cells, 0 symbols, 32 other bytes
5000000
USER(39): (length (time (EVERY-OTHER_4 *test-list* )))
; cpu time (non-gc) 1,690 msec user, 0 msec system
; cpu time (gc) 29,530 msec user, 110 msec system
; cpu time (total) 31,220 msec user, 110 msec system
; real time 43,249 msec
; space allocation:
; 5,000,002 cons cells, 0 symbols, 32 other bytes
5000000
Here is the modified every-other_3
(defun every-other_3 (list-in &key (start 0))
(when (listp list-in)
(let ((work-list (nthcdr start list-in))
(list-out (cons nil nil)))
(every-other-aux work-list list-out list-out))))
(defun every-other-aux (list-in list-out tail)
(if (null list-in)
(rest list-out)
(every-other-aux (cddr list-in)
list-out
(setf (rest tail) (cons (first list-in) nil)))))
Still I'd prefer the loop-based version in this case, because
it is easier to comprehend, i.e. saves (valuable) human time.
cheers, Bernhard
--
--------------------------------------------------------------------------
Bernhard Pfahringer
Austrian Research Institute for http://www.ai.univie.ac.at/~bernhard/
Artificial Intelligence ········@ai.univie.ac.at
Hey, benchmarkers...
I've got a really simple LISP compiler that doesn't have all of the
bells-and-whistles (no timing, no optimizing, minimal stream functions,
etc.) Can someone tell me how this one runs and give me an estimate of
the relative cost of reversing a large list like I do in this one.
Thanks,
Steve Long
PS- Parentheses arranged to suit the nit-picky.
(defun every-other (list-in &key (start 0))
(labels ((every-other-aux (list-in list-out)
(if (null list-in)
(reverse list-out)
(every-other-aux
(cddr list-in) (cons (car list-in) list-out)))))
(let ((list-out nil))
(every-other-aux (nthcdr start list-in) list-out))))
SLong wrote:
>
> Hey, benchmarkers...
>
> I've got a really simple LISP compiler that doesn't have all of the
> bells-and-whistles (no timing, no optimizing, minimal stream functions,
> etc.)
Any specific reason why you need to use such restricted tools? Most CL
providers these days have cheap or free implementations available for
private use on most platforms.
> Can someone tell me how this one runs and give me an estimate of
> the relative cost of reversing a large list like I do in this one.
> (defun every-other (list-in &key (start 0))
> (labels ((every-other-aux (list-in list-out)
> (if (null list-in)
> (reverse list-out)
> (every-other-aux
> (cddr list-in) (cons (car list-in) list-out)))))
> (let ((list-out nil))
> (every-other-aux (nthcdr start list-in) > list-out))))
Some timings on a 180 MHz PPro, ACL 4.3.2. ll is a list of 30 elements.
(time (dotimes (i 10000) (every-other ll)))
; cpu time (non-gc) 300 msec user, 0 msec system
; cpu time (gc) 870 msec user, 0 msec system
; cpu time (total) 1,170 msec user, 0 msec system
; real time 1,171 msec
; space allocation:
; 380,004 cons cells, 0 symbols, 32 other bytes
NIL
- The same program as yours, with reverse replaced by nreverse:
(time (dotimes (i 10000) (every-other2 ll)))
; cpu time (non-gc) 310 msec user, 0 msec system
; cpu time (gc) 371 msec user, 0 msec system
; cpu time (total) 681 msec user, 0 msec system
; real time 681 msec
; space allocation:
; 230,004 cons cells, 0 symbols, 32 other bytes
- A simpler program, done with loop:
(time (dotimes (i 10000) (every-other3 ll)))
; cpu time (non-gc) 180 msec user, 0 msec system
; cpu time (gc) 311 msec user, 0 msec system
; cpu time (total) 491 msec user, 0 msec system
; real time 491 msec
; space allocation:
; 240,004 cons cells, 0 symbols, 32 other bytes
NIL
(defun every-other3 (data)
(loop for item in data
by #'cddr
collect item))
--
Martti Halminen wrote:
> Some timings on a 180 MHz PPro, ACL 4.3.2. ll is a list of 30 elements.
>
> (time (dotimes (i 10000) (every-other ll)))
> ; cpu time (non-gc) 300 msec user, 0 msec system
> ; cpu time (gc) 870 msec user, 0 msec system
> ; cpu time (total) 1,170 msec user, 0 msec system
> ; real time 1,171 msec
> ; space allocation:
> ; 380,004 cons cells, 0 symbols, 32 other bytes
> NIL
>
> - The same program as yours, with reverse replaced by nreverse:
>
> (time (dotimes (i 10000) (every-other2 ll)))
> ; cpu time (non-gc) 310 msec user, 0 msec system
> ; cpu time (gc) 371 msec user, 0 msec system
> ; cpu time (total) 681 msec user, 0 msec system
> ; real time 681 msec
> ; space allocation:
> ; 230,004 cons cells, 0 symbols, 32 other bytes
>
> - A simpler program, done with loop:
>
> (time (dotimes (i 10000) (every-other3 ll)))
> ; cpu time (non-gc) 180 msec user, 0 msec system
> ; cpu time (gc) 311 msec user, 0 msec system
> ; cpu time (total) 491 msec user, 0 msec system
> ; real time 491 msec
> ; space allocation:
> ; 240,004 cons cells, 0 symbols, 32 other bytes
> NIL
>
>
> (defun every-other3 (data)
> (loop for item in data
> by #'cddr
> collect item))
A few more data points, on CMU CL 18a running on a P133-or-so box
and doing the same calculation 100000 times instead of 10000:
SLong's original:
7.72 seconds of real time
6.0569 seconds of user run time
0.483846 seconds of system run time
[Run times include 3.25 seconds GC run time]
0 page faults and
24811008 bytes consed.
SLong's, with NREVERSE:
3.95 seconds of real time
3.276089 seconds of user run time
0.266723 seconds of system run time
[Run times include 1.63 seconds GC run time]
0 page faults and
12406272 bytes consed.
Martti's LOOP-based version:
3.94 seconds of real time
3.102218 seconds of user run time
0.321196 seconds of system run time
[Run times include 1.64 seconds GC run time]
0 page faults and
13232128 bytes consed.
A simple recursive version:
3.94 seconds of real time
3.155438 seconds of user run time
0.304647 seconds of system run time
[Run times include 1.61 seconds GC run time]
0 page faults and
12406784 bytes consed.
(defun every-other-g (list)
(and list
(cons (car list)
(every-other-g (cddr list)))))
Note that neither Martti's version nor mine handles the :start
argument, as SLong's does. Note also that if you're short of
memory or handling very large lists, mine is probably inferior
because of the recursion.
For a list of length 1000, I got:
SLong's original:
257.0 seconds of real time
201.97758 seconds of user run time
20.289389 seconds of system run time
[Run times include 113.44 seconds GC run time]
0 page faults and
827153408 bytes consed.
SLong's, with NREVERSE:
132.92 seconds of real time
107.43328 seconds of user run time
10.57091 seconds of system run time
[Run times include 56.72 seconds GC run time]
0 page faults and
413553152 bytes consed.
Martti's LOOP-based version:
131.47 seconds of real time
104.354706 seconds of user run time
10.875814 seconds of system run time
[Run times include 56.47 seconds GC run time]
0 page faults and
414404096 bytes consed.
The simple recursive version:
142.09 seconds of real time
114.34683 seconds of user run time
12.627802 seconds of system run time
[Run times include 56.09 seconds GC run time]
0 page faults and
413575168 bytes consed.
--
Gareth McCaughan Dept. of Pure Mathematics & Mathematical Statistics,
·····@dpmms.cam.ac.uk Cambridge University, England.
From: Steve Long
Subject: Re: Benchmarking (was Re: horrible formatting)
Date:
Message-ID: <36F2E272.79E0@isomedia.com>
Very educational.
The ability to specify starting position was essential to the
implementation of every-other.
But I'm afraid that I'm missing something. (1) Why does it take longer
to run the defun with 1000 items than with 100000 items? (2) Why do you
think that your short recursive method will run out of memory faster
than the loop method? (I don't see the data to support this).
SLong
Gareth McCaughan wrote:
>
> Martti Halminen wrote:
>
> > Some timings on a 180 MHz PPro, ACL 4.3.2. ll is a list of 30 elements.
> >
> > (time (dotimes (i 10000) (every-other ll)))
> > ; cpu time (non-gc) 300 msec user, 0 msec system
> > ; cpu time (gc) 870 msec user, 0 msec system
> > ; cpu time (total) 1,170 msec user, 0 msec system
> > ; real time 1,171 msec
> > ; space allocation:
> > ; 380,004 cons cells, 0 symbols, 32 other bytes
> > NIL
> >
> > - The same program as yours, with reverse replaced by nreverse:
> >
> > (time (dotimes (i 10000) (every-other2 ll)))
> > ; cpu time (non-gc) 310 msec user, 0 msec system
> > ; cpu time (gc) 371 msec user, 0 msec system
> > ; cpu time (total) 681 msec user, 0 msec system
> > ; real time 681 msec
> > ; space allocation:
> > ; 230,004 cons cells, 0 symbols, 32 other bytes
> >
> > - A simpler program, done with loop:
> >
> > (time (dotimes (i 10000) (every-other3 ll)))
> > ; cpu time (non-gc) 180 msec user, 0 msec system
> > ; cpu time (gc) 311 msec user, 0 msec system
> > ; cpu time (total) 491 msec user, 0 msec system
> > ; real time 491 msec
> > ; space allocation:
> > ; 240,004 cons cells, 0 symbols, 32 other bytes
> > NIL
> >
> >
> > (defun every-other3 (data)
> > (loop for item in data
> > by #'cddr
> > collect item))
>
> A few more data points, on CMU CL 18a running on a P133-or-so box
> and doing the same calculation 100000 times instead of 10000:
>
> SLong's original:
> 7.72 seconds of real time
> 6.0569 seconds of user run time
> 0.483846 seconds of system run time
> [Run times include 3.25 seconds GC run time]
> 0 page faults and
> 24811008 bytes consed.
>
> SLong's, with NREVERSE:
> 3.95 seconds of real time
> 3.276089 seconds of user run time
> 0.266723 seconds of system run time
> [Run times include 1.63 seconds GC run time]
> 0 page faults and
> 12406272 bytes consed.
>
> Martti's LOOP-based version:
> 3.94 seconds of real time
> 3.102218 seconds of user run time
> 0.321196 seconds of system run time
> [Run times include 1.64 seconds GC run time]
> 0 page faults and
> 13232128 bytes consed.
>
> A simple recursive version:
> 3.94 seconds of real time
> 3.155438 seconds of user run time
> 0.304647 seconds of system run time
> [Run times include 1.61 seconds GC run time]
> 0 page faults and
> 12406784 bytes consed.
>
> (defun every-other-g (list)
> (and list
> (cons (car list)
> (every-other-g (cddr list)))))
>
> Note that neither Martti's version nor mine handles the :start
> argument, as SLong's does. Note also that if you're short of
> memory or handling very large lists, mine is probably inferior
> because of the recursion.
>
> For a list of length 1000, I got:
>
> SLong's original:
> 257.0 seconds of real time
> 201.97758 seconds of user run time
> 20.289389 seconds of system run time
> [Run times include 113.44 seconds GC run time]
> 0 page faults and
> 827153408 bytes consed.
>
> SLong's, with NREVERSE:
> 132.92 seconds of real time
> 107.43328 seconds of user run time
> 10.57091 seconds of system run time
> [Run times include 56.72 seconds GC run time]
> 0 page faults and
> 413553152 bytes consed.
>
> Martti's LOOP-based version:
> 131.47 seconds of real time
> 104.354706 seconds of user run time
> 10.875814 seconds of system run time
> [Run times include 56.47 seconds GC run time]
> 0 page faults and
> 414404096 bytes consed.
>
> The simple recursive version:
> 142.09 seconds of real time
> 114.34683 seconds of user run time
> 12.627802 seconds of system run time
> [Run times include 56.09 seconds GC run time]
> 0 page faults and
> 413575168 bytes consed.
>
> --
> Gareth McCaughan Dept. of Pure Mathematics & Mathematical Statistics,
> ·····@dpmms.cam.ac.uk Cambridge University, England.
Steve Long wrote:
> But I'm afraid that I'm missing something. (1) Why does it take longer
> to run the defun with 1000 items than with 100000 items?
I was running it a different number of times. I didn't make that
clear; sorry.
> (2) Why do you
> think that your short recursive method will run out of memory faster
> than the loop method? (I don't see the data to support this).
Because the recursive method will use stack space proportional
to the length of the list, whereas using LOOP should only need
a bounded amount of stack space. On some systems, the amount of
stack available is relatively small; on most systems, the amount
of stack you need for a recursive function call is more than
the amount of space taken up by a single cons cell!
--
Gareth McCaughan Dept. of Pure Mathematics & Mathematical Statistics,
·····@dpmms.cam.ac.uk Cambridge University, England.
From: Steve Long
Subject: Re: Benchmarking (was Re: horrible formatting)
Date:
Message-ID: <36F2DFD2.58E1@isomedia.com>
Thanks to all for the analyses. I was hoping (though I forgot to ask)
for someone to replace reverse with nreverse. Further investigation
confirms that the implementation of the loop macro varies widely not
only between compilers, but between the same compiler running on
different machines!. When I finally got to try it with Allegro CL, I
found _different ratios_ between Martti's loop and my recursive
implementation when compared on IBM 43P, HP C110, and Sun workstations.
It has been stipulated that iterative methods are not significantly more
efficient (time or resource-wise) than recursive ones, but as Martti
demonstrated, there are exceptions.
Does anyone have a rule-of-thumb concerning when to use recursion vs.
iteration?
SLong
Martti Halminen wrote:
>
> SLong wrote:
> >
> > Hey, benchmarkers...
> >
> > I've got a really simple LISP compiler that doesn't have all of the
> > bells-and-whistles (no timing, no optimizing, minimal stream functions,
> > etc.)
>
> Any specific reason why you need to use such restricted tools? Most CL
> providers these days have cheap or free implementations available for
> private use on most platforms.
>
> > Can someone tell me how this one runs and give me an estimate of
> > the relative cost of reversing a large list like I do in this one.
>
> > (defun every-other (list-in &key (start 0))
> > (labels ((every-other-aux (list-in list-out)
> > (if (null list-in)
> > (reverse list-out)
> > (every-other-aux
> > (cddr list-in) (cons (car list-in) list-out)))))
> > (let ((list-out nil))
> > (every-other-aux (nthcdr start list-in) > list-out))))
>
> Some timings on a 180 MHz PPro, ACL 4.3.2. ll is a list of 30 elements.
>
> (time (dotimes (i 10000) (every-other ll)))
> ; cpu time (non-gc) 300 msec user, 0 msec system
> ; cpu time (gc) 870 msec user, 0 msec system
> ; cpu time (total) 1,170 msec user, 0 msec system
> ; real time 1,171 msec
> ; space allocation:
> ; 380,004 cons cells, 0 symbols, 32 other bytes
> NIL
>
> - The same program as yours, with reverse replaced by nreverse:
>
> (time (dotimes (i 10000) (every-other2 ll)))
> ; cpu time (non-gc) 310 msec user, 0 msec system
> ; cpu time (gc) 371 msec user, 0 msec system
> ; cpu time (total) 681 msec user, 0 msec system
> ; real time 681 msec
> ; space allocation:
> ; 230,004 cons cells, 0 symbols, 32 other bytes
>
> - A simpler program, done with loop:
>
> (time (dotimes (i 10000) (every-other3 ll)))
> ; cpu time (non-gc) 180 msec user, 0 msec system
> ; cpu time (gc) 311 msec user, 0 msec system
> ; cpu time (total) 491 msec user, 0 msec system
> ; real time 491 msec
> ; space allocation:
> ; 240,004 cons cells, 0 symbols, 32 other bytes
> NIL
>
> (defun every-other3 (data)
> (loop for item in data
> by #'cddr
> collect item))
>
> --
In article <·············@isomedia.com>,
Steve Long <·········@isomedia.com> writes:
> Does anyone have a rule-of-thumb concerning when to use recursion vs.
> iteration?
Start by selecting for clarity and maintainability. If the resulting
program is too slow, try to find a better algorithm. If it's still too
slow, only then should you start thinking about smaller details of
optimisation (the amount you cons, choice of recursion or iteration, etc.)
--
Aaron Crane <···········@pobox.com> <URL:http://pobox.com/~aaronc/>
** Please send on-topic followups by Usenet, not email **
From: Christopher R. Barry
Subject: Ahhh yes, more recursion vs. iteration. (was Re: Benchmarking (was Re: horrible formatting))
Date:
Message-ID: <874snfgc0j.fsf_-_@2xtreme.net>
···········@pobox.com (Aaron Crane) writes:
> In article <·············@isomedia.com>,
> Steve Long <·········@isomedia.com> writes:
> > Does anyone have a rule-of-thumb concerning when to use recursion vs.
> > iteration?
>
> Start by selecting for clarity and maintainability. If the resulting
> program is too slow, try to find a better algorithm. If it's still too
> slow, only then should you start thinking about smaller details of
> optimisation (the amount you cons, choice of recursion or iteration, etc.)
The last time we had this thread, I remember the verdict (or my
interpretation of it at least) being something along the lines of:
Problems which cannot be viewed using the recursive paradigm without
the problem of the nessecary accumulation of increased storage over
time are so-called "problems most usefully viewed recursively."
The reasoning was along the lines that converting recursive code to
iterative code isn't too dificult if storage doesn't increase over
time, since state information doesn't need to be pushed onto a stack -
so you need not simulate a stack with your own data structures and
push your state data onto the stack and reinitialize it and loop when
you otherwise would normally make a recursive call with such problems.
So as for the rule-of-thumb Steve Long wants - since Common Lisp
doesn't guarantee tail-call optimization, you may want to use LOOP or
DO instead for recursive problems which don't suffer from the
"nessecary accumulation of increased storage over time.", while for
clarity's sake you may want to leave "problems most usefully viewed
recursively" recursive unless performance truly is critical and there
is an advantage gained by house-keeping the stack data yourself
instead of letting the compiler do it.
Christopher
In article <·············@isomedia.com> , SLong <·········@isomedia.com>
wrote:
> Hey, benchmarkers...
>
> I've got a really simple LISP compiler that doesn't have all of the
> bells-and-whistles (no timing, no optimizing, minimal stream functions,
> etc.) Can someone tell me how this one runs and give me an estimate of
> the relative cost of reversing a large list like I do in this one.
>
> Thanks,
> Steve Long
>
> PS- Parentheses arranged to suit the nit-picky.
>
> (defun every-other (list-in &key (start 0))
> (labels ((every-other-aux (list-in list-out)
> (if (null list-in)
> (reverse list-out)
> (every-other-aux
> (cddr list-in) (cons (car list-in) list-out)))))
> (let ((list-out nil))
> (every-other-aux (nthcdr start list-in) list-out))))
MCL 4.2 on a Rev A. iMac (233 MHz PowerPC)
List of length 30, running 10,000 iterations
Average 181 ms runtime, including average 95 ms GC time
Allocated 2,400,000 bytes of memory
? (gc)
NIL
? (let ((l (make-list 30))) (time (dotimes (i 10000) (every-other l))))
(DOTIMES (I 10000) (EVERY-OTHER L)) took 184 milliseconds (0.184 seconds) to
run.
Of that, 113 milliseconds (0.113 seconds) was spent in GC.
2,400,000 bytes of memory allocated.
NIL
? (let ((l (make-list 30))) (time (dotimes (i 10000) (every-other l))))
(DOTIMES (I 10000) (EVERY-OTHER L)) took 195 milliseconds (0.195 seconds) to
run.
Of that, 124 milliseconds (0.124 seconds) was spent in GC.
2,400,000 bytes of memory allocated.
NIL
? (let ((l (make-list 30))) (time (dotimes (i 10000) (every-other l))))
(DOTIMES (I 10000) (EVERY-OTHER L)) took 199 milliseconds (0.199 seconds) to
run.
Of that, 127 milliseconds (0.127 seconds) was spent in GC.
2,400,000 bytes of memory allocated.
NIL
? (let ((l (make-list 30))) (time (dotimes (i 10000) (every-other l))))
(DOTIMES (I 10000) (EVERY-OTHER L)) took 163 milliseconds (0.163 seconds) to
run.
Of that, 97 milliseconds (0.097 seconds) was spent in GC.
2,400,000 bytes of memory allocated.
NIL
? (let ((l (make-list 30))) (time (dotimes (i 10000) (every-other l))))
(DOTIMES (I 10000) (EVERY-OTHER L)) took 168 milliseconds (0.168 seconds) to
run.
Of that, 1 milliseconds (0.001 seconds) were spent in The Cooperative
Multitasking Experience.
100 milliseconds (0.100 seconds) was spent in GC.
2,400,000 bytes of memory allocated.
NIL
? (let ((l (make-list 30))) (time (dotimes (i 10000) (every-other l))))
(DOTIMES (I 10000) (EVERY-OTHER L)) took 178 milliseconds (0.178 seconds) to
run.
Of that, 108 milliseconds (0.108 seconds) was spent in GC.
2,400,008 bytes of memory allocated.
NIL
? (/ (+ 184 195 199 163 168 178) 6.0) ;; avg runtime
181.16666666666666
? (/ (+ 113 124 127 97 1 108) 6.0) ;; avg gc time
95.0
?
--
David B. Lamkins <http://www.teleport.com/~dlamkins/>
Recently undead Isabelle to the archangel Gabriel in "The Prophecy II":
"So, you're keeping me alive because you don't know DOS?"
Frank Adrian wrote:
> I did my benchmarking using Corman Lisp (a new kid on the block - see
> http://www.corman.net/ ). It seems to hold up pretty well against the
> others:
>
> Timing 10000 runs using the original code:
> Total Execution time: 0.204824 seconds
> Time spent garbage collecting: 0.0256055 seconds
>
> Timing 10000 runs using the code with reverse replaced by nreverse:
> Total Execution time: 0.157446 seconds
> Time spent garbage collecting: 0.0131833 seconds
>
> Timing 10000 runs using Martti Halminen's looping version:
> Total Execution time: 0.226175 seconds
> Time spent garbage collecting: 0.0881066 seconds
>
> And, timing 10000 runs using Gareth McCaughan's simple recursive version:
> Total Execution time: 0.119784 seconds
> Time spent garbage collecting: 0.0600622 seconds
Not bad, but I'm a little worried about the factor of 2
between the LOOP implementation and the recursive one.
This suggests that Corman Lisp's LOOP could do with a bit
of improvement...
--
Gareth McCaughan Dept. of Pure Mathematics & Mathematical Statistics,
·····@dpmms.cam.ac.uk Cambridge University, England.
Marco Antoniotti <·······@copernico.parades.rm.cnr.it> writes:
> funcall-of-nil <··············@boeing.com> writes:
>
> > -funcall of nil-
>
> Ahem! Who are you?
I have fresh memories of a Lisper working at Boeing (lead contractor
for the International Space Station!!! Woo hoo.) using his real name.
Christopher
Marco Antoniotti schrieb:
>
> funcall-of-nil <··············@boeing.com> writes:
>
> > -funcall of nil-
>
> Ahem! Who are you?
the BORG have begun to assimilate comp.lang.lisp. Resistance is
futile...
--
Johannes Beck ····@informatik.uni-wuerzburg.de
http://www-info6.informatik.uni-wuerzburg.de/~beck/
Tel.: +49 931 312198
Fax.: +49 931 7056120
PGP Public Key available by ·············@informatik.uni-wuerzburg.de