Lenny Gray <········@netcom.com> wrote:
>Bruno Haible (······@ma2s2.mathematik.uni-karlsruhe.de) wrote:
>
>: ...
>: some integer array hacking
>: C 4.2 sec
>: Mjolner 111 sec
>: GCL 288 sec
>: CLISP 415 sec
>: (All timings on a 486/33.)
>: ...
>
> Are these numbers right? I've seriously used GCL and CLISP myself and
> had some arguments with a "true believer Lisper" who thought "Lisp _does_
> compete reasonably with C for numeric stuff", but I never bothered to do
> the timing tests, and always assumed it wasn't this bad. Is it, really?
Of course these numbers are right. Here is another set of figures, for
the same integer array hacking benchmark:
C 7.7 sec
Lucid CL 3.0 production mode 47 sec
Lucid CL 3.0 development mode 226 sec
CLISP 512 sec
(All timings on a Sun Sparcstation IPC, this time.)
Lisp compilers produce good code, but they can't compete with good C
compilers in this case.
Here's the code, if you want to convince yourself:
(defun fannkuch (&optional (n (progn
(format *query-io* "n = ?")
(parse-integer (read-line *query-io*))
) ) )
(unless (and (> n 0) (<= n 100)) (return-from fannkuch))
(let ((n n))
(declare (fixnum n))
(let ((perm (make-array n :element-type 'fixnum))
(perm1 (make-array n :element-type 'fixnum))
(zaehl (make-array n :element-type 'fixnum))
(permmax (make-array n :element-type 'fixnum))
(bishmax -1))
(declare (type (simple-array fixnum (*)) perm perm1 zaehl permmax))
(declare (fixnum bishmax))
(dotimes (i n) (setf (svref perm1 i) i))
(prog ((\t n))
(declare (fixnum \t))
Kreuz
(when (= \t 1) (go standardroutine))
(setf (svref zaehl (- \t 1)) \t)
(decf \t)
(go Kreuz)
Dollar
(when (= \t n) (go fertig))
(let ((perm0 (svref perm1 0)))
(dotimes (i \t) (setf (svref perm1 i) (svref perm1 (+ i 1))))
(setf (svref perm1 \t) perm0)
)
(when (plusp (decf (svref zaehl \t))) (go Kreuz))
(incf \t)
(go Dollar)
standardroutine
(dotimes (i n) (setf (svref perm i) (svref perm1 i)))
(let ((Spiegelungsanzahl 0) (k 0))
(declare (fixnum Spiegelungsanzahl k))
(loop
(when (= (setq k (svref perm 0)) 0) (return))
(let ((k2 (ceiling k 2)))
(declare (fixnum k2))
(dotimes (i k2) (rotatef (svref perm i) (svref perm (- k i))))
)
(incf Spiegelungsanzahl)
)
(when (> Spiegelungsanzahl bishmax)
(setq bishmax Spiegelungsanzahl)
(dotimes (i n) (setf (svref permmax i) (svref perm1 i)))
) )
(go Dollar)
fertig
)
(format t "The maximum was ~D.~% at " bishmax)
(format t "(")
(dotimes (i n)
(when (> i 0) (format t " "))
(format t "~D" (+ (svref permmax i) 1))
)
(format t ")")
(terpri)
(values)
) ) )
Bruno Haible
······@ma2s2.mathematik.uni-karlsruhe.de
On 9 Sep 1994, Bruno Haible wrote:
> Lenny Gray <········@netcom.com> wrote:
> >
> > Are these numbers right? I've seriously used GCL and CLISP myself and
>
> Of course these numbers are right....
"Right" or wrong, they are meaningless and should be ignored in the
absence of additional information. See below.
> Here's the code, if you want to convince yourself:
OK, I have convinced myself not to pay any attention to your results.
See below.
> (defun fannkuch (&optional (n (progn
> (format *query-io* "n = ?")
> (parse-integer (read-line *query-io*))
> ) ) )
> (unless (and (> n 0) (<= n 100)) (return-from fannkuch))
> (let ((n n))
> (declare (fixnum n))
> (let ((perm (make-array n :element-type 'fixnum))
> (perm1 (make-array n :element-type 'fixnum))
> (zaehl (make-array n :element-type 'fixnum))
> (permmax (make-array n :element-type 'fixnum))
> (bishmax -1))
> (declare (type (simple-array fixnum (*)) perm perm1 zaehl permmax))
> (declare (fixnum bishmax))
> (dotimes (i n) (setf (svref perm1 i) i))
> (prog ((\t n))
> (declare (fixnum \t))
> Kreuz
> (when (= \t 1) (go standardroutine))
> (setf (svref zaehl (- \t 1)) \t)
> (decf \t)
> (go Kreuz)
> Dollar
> (when (= \t n) (go fertig))
> (let ((perm0 (svref perm1 0)))
> (dotimes (i \t) (setf (svref perm1 i) (svref perm1 (+ i 1))))
> (setf (svref perm1 \t) perm0)
> )
> (when (plusp (decf (svref zaehl \t))) (go Kreuz))
> (incf \t)
> (go Dollar)
> standardroutine
> (dotimes (i n) (setf (svref perm i) (svref perm1 i)))
> (let ((Spiegelungsanzahl 0) (k 0))
> (declare (fixnum Spiegelungsanzahl k))
> (loop
> (when (= (setq k (svref perm 0)) 0) (return))
> (let ((k2 (ceiling k 2)))
> (declare (fixnum k2))
> (dotimes (i k2) (rotatef (svref perm i) (svref perm (- k i))))
> )
> (incf Spiegelungsanzahl)
> )
> (when (> Spiegelungsanzahl bishmax)
> (setq bishmax Spiegelungsanzahl)
> (dotimes (i n) (setf (svref permmax i) (svref perm1 i)))
> ) )
> (go Dollar)
> fertig
> )
> (format t "The maximum was ~D.~% at " bishmax)
> (format t "(")
> (dotimes (i n)
> (when (> i 0) (format t " "))
> (format t "~D" (+ (svref permmax i) 1))
> )
> (format t ")")
> (terpri)
> (values)
> ) ) )
So where and how is the timing measurement taken? This is crucial; you
cannot expect anyone to glean useful information from a timing test
unless you can demonstrate that it was taken in a reasonable fashion,
which means limiting the test to the things you are claiming to measure
by it. Unless you were careful to exclude other processes while the test
was running, you may have also measured things completely extraneous to the
code you intended to measure. I'm not saying that you don't know these
things, but you need to be explicit about them when you publish a
so-called benchmark.
Also, the above code includes all sorts of stuff that has nothing to do
with integer array hacking, such as parsing, formatting (which involves
printed output and most likely conses), array allocation, and so on. This
is a *terrible* benchmark - it's quite possible that the timings you
published even include time waiting for a window to become exposed for
output, as well as the time taken by the user to type input.
In article <········································@swim5.eng.sematech.org> "William D. Gooch" <······@swim5.eng.sematech.org> writes:
>On 9 Sep 1994, Bruno Haible wrote:
>
>> Lenny Gray <········@netcom.com> wrote:
>> >
>> > Are these numbers right? I've seriously used GCL and CLISP myself and
>>
>> Of course these numbers are right....
>
>"Right" or wrong, they are meaningless and should be ignored in the
>absence of additional information. See below.
>
>> Here's the code, if you want to convince yourself:
>> (dotimes (i n) (setf (svref perm1 i) i))
BTW, you can't just use dotimes even if n is declared to be a fixnum.
I think this is explained in the comp.lang.lisp FAQ. If not, it was
explained in the list of "pitfalls" I posted a while back and perhaps
should update?
-- jeff
In article <··········@nz12.rz.uni-karlsruhe.de>,
Bruno Haible <······@ma2s2.mathematik.uni-karlsruhe.de> wrote:
>
>Of course these numbers are right. Here is another set of figures, for
>the same integer array hacking benchmark:
> C 7.7 sec
> Lucid CL 3.0 production mode 47 sec
> Lucid CL 3.0 development mode 226 sec
> CLISP 512 sec
>(All timings on a Sun Sparcstation IPC, this time.)
>
>Lisp compilers produce good code, but they can't compete with good C
>compilers in this case.
May not be the case: I've timed your function using both CMUCL 17c and
Lucid CL 4.0.0, CMUCL is 3 times faster than Lucid, so:
CMUCL (estimate!) 15 sec
which is just a factor of 2 off of C. And here is a possible explanation
of that remaining factor: I *guess* svref still checks, if the index is
within the bounds of the vector, whereas there is probably no such check
in the binary produced by the C compiler.
regards, Bernhard
--------------------------------------------------------------------------
Bernhard Pfahringer
Austrian Research Institute for
Artificial Intelligence ········@ai.univie.ac.at
Schottengasse 3 Fax: (+43 1) 532-0652
A-1010 Vienna, Austria Phone: (+43 1) 533-6112
········@ai.univie.ac.at (Bernhard Pfahringer) writes:
> May not be the case: I've timed your function using both CMUCL 17c and
> Lucid CL 4.0.0, CMUCL is 3 times faster than Lucid, so:
> CMUCL (estimate!) 15 sec
>
> which is just a factor of 2 off of C. And here is a possible explanation
> of that remaining factor: I *guess* svref still checks, if the index is
> within the bounds of the vector, whereas there is probably no such check
> in the binary produced by the C compiler.
>
> regards, Bernhard
> --------------------------------------------------------------------------
> Bernhard Pfahringer
> Austrian Research Institute for
> Artificial Intelligence ········@ai.univie.ac.at
> Schottengasse 3 Fax: (+43 1) 532-0652
> A-1010 Vienna, Austria Phone: (+43 1) 533-6112
>
Howdy,
SVREF bounds checks an index with (SAFETY 0)? Weird. Of all
things to optimize, you'd think that "field dereferencing" functions
, e.g., SVREF, SCHAR, <STRUCT>-<SLOT> references, and their builtin
counter parts like SYMBOL-NAME, would not type check and would not
bound's check.
I'd think that it would be pretty easy to group these
functions where the compiler can see'em and generate a single
machine instruction on most processors.
=============================================
Scott McLoughlin
Conscious Computing
=============================================
Bernhard Pfahringer <········@ai.univie.ac.at> wrote:
>> Lisp compilers produce good code, but they can't compete with good C
>> compilers in this case.
>
> May not be the case: I've timed your function using both CMUCL 17c and
> Lucid CL 4.0.0, CMUCL is 3 times faster than Lucid, so:
> CMUCL (estimate!) 15 sec
>
> which is just a factor of 2 off of C.
This agrees with some figures measured by Simon Leinen:
Sun 4/670MP, 40MHz SuperSPARC acc -fast 1.5 sec user
Sun 4/670MP, 40MHz SuperSPARC CMU CL 17e 3.08 sec user
Sun 4/670MP, 40MHz SuperSPARC LispWorks 3.2 15.58 sec user
Sun 4/670MP, 40MHz SuperSPARC Allegro 4.1 33.87 sec user
Indeed CMUCL is only a factor of 2 off of C. I am happy to eat my words
about Lisp compiler's code.
Bruno Haible
······@ma2s2.mathematik.uni-karlsruhe.de
In article <·················@polaris.ih.att.com> ···@polaris.ih.att.com (Lawrence G. Mayka) writes:
>I have attached the again-modified version of the benchmark.
> (dotimes (i n)
> (declare (fixnum i))
> (setf (svref perm1 i) i))
I should perhaps point out again that that is not always enough
to get a fully fixnum loop. I normally use macros like these:
;;; Fixnum iterations
(defmacro fix-dotimes ((var count &optional (result nil))
&body body)
(let ((count-var (gensym)))
`(let ((,count-var ,count))
(declare (fixnum ,count-var))
(do ((,var 0 (fix+ ,var 1)))
((fix>= ,var ,count-var)
,result)
(declare (fixnum ,var))
,@body))))
(defmacro do-vector-indices ((var vec &optional (result nil))
&body body)
`(fix-dotimes (,var (length (the vector ,vec))
,@(if result (list result)))
,@body))
fix+, fix>=, etc are defined like this:
(defmacro fix+ (i j)
`(the fixnum (+ (the fixnum ,i) (the fixnum ,j))))
(defmacro fix>= (i j)
`(>= (the fixnum ,i) (the fixnum ,j)))
The root problem seems to be that some Lisps worry that 1 + i may
not be a fixnum even though i is. I don't think you can always
win even by saying (dotimes (i (the fixnum n)) ...).
It's very easy to see what will happen in KCL, BTW. Define
the fns and call disassemble. The C code is sufficiently readable,
because the stuff that's what you'd do in C looks like it is.
-- jeff
In article <··········@nz12.rz.uni-karlsruhe.de> ······@ma2s2.mathematik.uni-karlsruhe.de (Bruno Haible) writes:
Of course these numbers are right. Here is another set of figures, for
the same integer array hacking benchmark:
C 7.7 sec
Lucid CL 3.0 production mode 47 sec
Lucid CL 3.0 development mode 226 sec
CLISP 512 sec
(All timings on a Sun Sparcstation IPC, this time.)
I added some type declarations (and removed some), in order to make
sure that no functions (at least, according to the disassembler) are
being called in the inner parts. I've attached the resulting source
code. (Note again that I am not asserting that =all= those type
declarations are necessary, only that I didn't want to take chances.)
The benchmark result on LispWorks 3.2, on an old Sparc LX, for
(fannkuch-fast 10)
is
57.3 sec
You didn't say what argument you passed to the function, by the way;
10 was as high as I was willing to go!
-----------------------------
(in-package :cl-user)
(defun fannkuch-fast (&optional (n (progn
(format *query-io* "n = ?")
(parse-integer (read-line *query-io*))
) ) )
(declare (optimize (safety 0) (speed 3) (space 0) (debug 0)))
(unless (and (> n 0) (<= n 100)) (return-from fannkuch-fast))
(let ((n n))
(declare (fixnum n))
(let ((perm (make-array n :initial-element 0))
(perm1 (make-array n :initial-element 0))
(zaehl (make-array n :initial-element 0))
(permmax (make-array n :initial-element 0))
(bishmax -1))
(declare (type simple-vector perm perm1 zaehl permmax))
(declare (fixnum bishmax))
(dotimes (i n)
(declare (fixnum i))
(setf (svref perm1 i) i))
(prog ((\t n))
(declare (fixnum \t))
Kreuz
(when (= \t 1) (go standardroutine))
(setf (svref zaehl (the fixnum (1- \t))) \t)
(setf \t (the fixnum (1- \t)))
(go Kreuz)
Dollar
(when (= \t n) (go fertig))
(let ((perm0 (svref perm1 0)))
(dotimes (i \t)
(declare (fixnum i))
(setf (svref perm1 i) (svref perm1 (the fixnum (1+ i)))))
(setf (svref perm1 \t) perm0)
)
(when (> (the fixnum
(setf (the fixnum (svref zaehl \t))
(the fixnum (1- (the fixnum (svref zaehl \t))))))
0)
(go Kreuz))
(setf \t (the fixnum (1+ \t)))
(go Dollar)
standardroutine
(dotimes (i n)
(declare (fixnum i))
(setf (svref perm i) (svref perm1 i)))
(let ((Spiegelungsanzahl 0) (k 0))
(declare (fixnum Spiegelungsanzahl k))
(loop
(when (= (the fixnum (setq k (svref perm 0))) 0) (return))
(let ((k2 (ash (the fixnum (1+ k)) -1)))
(declare (fixnum k2))
(dotimes (i k2)
(declare (fixnum i))
(rotatef (svref perm i) (svref perm (the fixnum (- k i)))))
)
(setf Spiegelungsanzahl (the fixnum (1+ Spiegelungsanzahl)))
)
(when (> Spiegelungsanzahl bishmax)
(setq bishmax Spiegelungsanzahl)
(dotimes (i n)
(declare (fixnum i))
(setf (svref permmax i) (svref perm1 i)))
) )
(go Dollar)
fertig
)
(format t "The maximum was ~D.~% at " bishmax)
(format t "(")
(dotimes (i n)
(declare (fixnum i))
(when (> i 0) (format t " "))
(format t "~D" (the fixnum (1+ (the fixnum (svref permmax i)))))
)
(format t ")")
(terpri)
(values)
) ) )
--------------------------------
--
Lawrence G. Mayka
AT&T Bell Laboratories
···@ieain.att.com
Standard disclaimer.