Hello,
this ugly benchmark was just mentioned again on sci.math.num-analysis and I
looked at one of the entries, namely "nsieve". It occured to me that the
CMUCL contribution could be written much nicer in the following way:
nsieve.lisp (a shortened version of the version there):
---------------------------------------------------------------------------
(defun nsieve (m)
(let ((a (make-array m :initial-element t :element-type 'boolean)))
(loop for i from 2 to (1- m) when (aref a i) do
(loop for j from (+ i i) to (1- m) by i
do (setf (aref a j) nil))
count (aref a i))))
(defun main (n)
(let ((m (* 10000 (expt 2 n))))
(format t "Primes up to~T~8<~d~>~T~8<~d~>~%" m (nsieve m))))
---------------------------------------------------------------------------
Together with the compilation command:
lisp -noinit -eval "(progn (compile-file \"nsieve.lisp\") (ext:quit))"
and the run command (one line, %A is some number):
lisp -noinit -eval "(progn (load \"nsieve\") (main (parse-integer (car (last extensions:*command-line-strings*)))) (ext:quit))" %A
I would suggest that people contributing to this shootout should follow
this pattern, such that we do not clutter nice CL programs with argument
parsing.
Probably Bagley won't like this, but other languages have complicated
invocation lines, too.
Yours, Nicolas.
P.S.: What concerns myself, I do not want to communicate any more with this
guy (Bagley). I have tried it once, without much success.
Nicolas Neuss wrote:
> Hello,
>
> this ugly benchmark was just mentioned again on sci.math.num-analysis and I
> looked at one of the entries, namely "nsieve". It occured to me that the
> CMUCL contribution could be written much nicer in the following way:
>
> nsieve.lisp (a shortened version of the version there):
> ---------------------------------------------------------------------------
> (defun nsieve (m)
> (let ((a (make-array m :initial-element t :element-type 'boolean)))
> (loop for i from 2 to (1- m) when (aref a i) do
> (loop for j from (+ i i) to (1- m) by i
> do (setf (aref a j) nil))
> count (aref a i))))
>
> (defun main (n)
> (let ((m (* 10000 (expt 2 n))))
> (format t "Primes up to~T~8<~d~>~T~8<~d~>~%" m (nsieve m))))
> ---------------------------------------------------------------------------
In CMUCL, :element-type 'boolean is equivalent to :element-type T.
If you're trying to save memory, consider a bit vector, or an
array of element type (unsigned-byte 8) (and make corresponding
changes in the logic.)
Paul
Paul Dietz wrote:
>
> In CMUCL, :element-type 'boolean is equivalent to :element-type T.
> If you're trying to save memory, consider a bit vector, or an
> array of element type (unsigned-byte 8) (and make corresponding
> changes in the logic.)
>
I was thinking the same thing (and a few other things), try...
(defconstant +p+ 0)
(defconstant +not-p+ 1)
(defun nsieve (m)
(let ((a (make-array m :initial-element +p+ :element-type '(unsigned-byte 8))))
(declare (type (simple-array (unsigned-byte 8) (*)) a)
(optimize (speed 3) (safety 0)))
(loop for i from 2 below m
when (= +p+ (aref a i)) do
(loop for j from (+ i i) below m by i
do (setf (aref a j) +not-p+))
and count 1)))
Wade
Hello,
Paul's suggestion yields a performance gain of 20%. Adding more type and
optimization declarations in the direction of Wade's suggestion yields a
version which is more than twice as fast (see the CLIKI page below).
This idiotic benchmark should measure (1) the length of the shortest
program achieving the goals, (2) the time the fastest possible program
needs, and should (3) be made easily improvable. For this purpose, I have
generated my first CLIKI pages under
<http://www.cliki.net/Improved%20CMUCL%20Shootout>
<http://www.cliki.net/ICS-nsieve>
and hope that many people will contribute. [Unfortunately, I have not been
able to link this page correctly from <http://www.cliki.net/Benchmarks>.
Could someone tell me what I did wrong or simply correct it?]
Have a nice weekend,
Nicolas.
Nicolas Neuss <·······@iwr.uni-heidelberg.de> writes:
> [Unfortunately, I have not been able to link this page correctly from
> <http://www.cliki.net/Benchmarks>. Could someone tell me what I did
> wrong or simply correct it?]
OK, corrected it myself. It was a simple typo.
Nicolas.
First, the link: http://shootout.alioth.debian.org
Second, correct program with the same output as the original:
---------------------------------------------------------------------------
(defun nsieve (m)
(let ((a (make-array m :initial-element t :element-type 'boolean)))
(loop for i from 2 below m when (aref a i) do
(loop for j from (+ i i) below m by i
do (setf (aref a j) nil))
count (aref a i))))
(defun test (n)
(let ((m (* 10000 (expt 2 n))))
(format t "Primes up to~T~8<~d~>~T~8<~d~>~%" m (nsieve m))))
(defun main (n)
(loop for k from n downto (- n 2) do (test k)))
---------------------------------------------------------------------------
>>>>> "NN" == Nicolas Neuss <·······@iwr.uni-heidelberg.de> writes:
[...]
NN> P.S.: What concerns myself, I do not want to communicate any
NN> more with this guy (Bagley). I have tried it once, without
NN> much success.
When he was activaly maintaining his shootout pages, Doug Bagley was
easy and pleasant to communicate with. I probably exchanged a few
dozen e-mails with him back then and had no complaints. It looks like
he's no longer interested in the shootout though. Perhaps you should
try to contact the new team?
cheers,
BM
Bulent Murtezaoglu <··@acm.org> writes:
>>>>>> "NN" == Nicolas Neuss <·······@iwr.uni-heidelberg.de> writes:
> [...]
> NN> P.S.: What concerns myself, I do not want to communicate any
> NN> more with this guy (Bagley). I have tried it once, without
> NN> much success.
>
> When he was activaly maintaining his shootout pages, Doug Bagley was
> easy and pleasant to communicate with. I probably exchanged a few
> dozen e-mails with him back then and had no complaints. It looks like
> he's no longer interested in the shootout though. Perhaps you should
> try to contact the new team?
OK, probably I have expressed myself too strongly. When I contacted him
some years ago he was already not anymore interested in his shootout, and
the new team was not yet active.
Thank you for the information,
Nicolas.
Nicolas Neuss wrote:
> > When he was activaly maintaining his shootout pages, Doug Bagley was
> > easy and pleasant to communicate with. I probably exchanged a few
> > dozen e-mails with him back then and had no complaints. It looks like
> > he's no longer interested in the shootout though. Perhaps you should
> > try to contact the new team?
>
> OK, probably I have expressed myself too strongly. When I contacted him
> some years ago he was already not anymore interested in his shootout, and
> the new team was not yet active.
The FAQ provides step-by-step instructions on how to contribute
programs:
http://shootout.alioth.debian.org/faq.php?sort=fullcpu#contribute