a potential lisp convert, and interpreting the shootout
in [Lisp]
|
Prev: Pocket Lisp Machine
Next: Next Generation of Language
From: Isaac Gouy on 2 Oct 2006 16:29 Wade Humeniuk wrote: > Henry Bigelow wrote: > > Wade Humeniuk wrote: > >> Speaking of which. By modifying the original somewhat (I do not have SBCL) > >> I do not have the patience to code it like C, so.... > >> > > > > wow, thanks wade! > > You're welcome. The fastest version I have tried (so far) of fannkuch > is the algorithm I translated (yesterday) from the GCC entry (most > others use the same approach). > > (defun fannkuch (n) > (declare (optimize (speed 3) (safety 0) (debug 0) #+lispworks(fixnum-safety 0)) > (type (integer 0 128) n)) > (if (< n 1) (return-from fannkuch 0)) > (let ((perm (make-array n :element-type '(integer 0 128))) > (perml (make-array n :element-type '(integer 0 128))) > (count (make-array n :element-type '(integer 0 128))) > (flips 0) (flipsmax 0) (r n) (nl (1- n)) (perm0 0) > (check 0) > (k 0) (i 0)) > (declare (type (simple-array (integer 0 128) (*)) perm perml count) > (type (integer 0 256) flips flipsmax nl perm0 check k i) > (type (integer 0 128) r)) > > (loop for i from 0 below n do (setf (aref perml i) i)) > > (loop > (when (< check 30) > (loop for i from 0 below n do (princ (1+ (aref perml i)))) > (terpri) > (incf check)) > > (loop while (> r 1) do > (setf (aref count (1- r)) r) > (decf r)) > > (unless (or (= (aref perml 0) 0) (= (aref perml nl) nl)) > (setf flips 0) > (loop for i fixnum from 0 below n do (setf (aref perm i) (aref perml i))) > (setf k (aref perml 0)) > (loop while (/= k 0) do > (loop for j fixnum downfrom (1- k) > for i fixnum from 1 > while (< i j) do (rotatef (aref perm i) (aref perm j))) > (incf flips) > (rotatef k (aref perm k))) > (when (< flipsmax flips) > (setf flipsmax flips))) > > (loop do > (when (= r n) (return-from fannkuch flipsmax)) > (setf i 0 perm0 (aref perml 0)) > (loop while (< i r) do > (setf k (1+ i) > (aref perml i) (aref perml k) > i k)) > (setf (aref perml r) perm0) > (when (> (decf (aref count r)) 0) (loop-finish)) > (incf r))))) > > I finally loaded SBCL 0.9.17 onto one of my FreeBSD machines. > On the lowly PIIIx2 500MHz (time (fannkuch 10)) > > SBCL 0.9.17 3.01s > LWL 4.3.7 4.75s > gcc 1.80s > (from the Shootout Site gcc -O3 -fomit-frame-pointer -march=pentium3) > > Scaling that to the results on the shootout site puts gcc=0.47, > LW=1.24 and SBCL=0.79. > > Why the shootout site would have removed the previous faster Lisp > version is beyond me. > > Wade Incidentally, if you would like this program or any variant you might author from Juho Snellman's program to appear on the computer language shootout, you should follow the FAQ instructions http://shootout.alioth.debian.org/gp4/faq.php#help > > > > > > i'm going to test this out and compare it to the original too. so far > > i've just downloaded slime and sbcl and am stumbling my way around it > > all. > > > > what sort of things do you use lisp for, by the way? and do you use > > other languages too? > > > > Not anything numerically intensive. Currently at work I use it to write > testers/emulators. At home, my first CL program written and delivered as > a complete app was... (I did it to learn CL). If you want to learn CL > I would suggest you try something non-trivial like that. Nothing like > getting your feet wet and to to see how CL makes development so much easier. > > http://www.download.com/The-Runner-s-Log/3000-2136_4-6893549.html?tag=lst-0-1 > > Wade
From: Wade Humeniuk on 2 Oct 2006 20:52 Isaac Gouy wrote: > Wade Humeniuk wrote: >> Henry Bigelow wrote: >>> Wade Humeniuk wrote: >>>> Speaking of which. By modifying the original somewhat (I do not have SBCL) >>>> I do not have the patience to code it like C, so.... >>>> >>> wow, thanks wade! >> You're welcome. The fastest version I have tried (so far) of fannkuch >> is the algorithm I translated (yesterday) from the GCC entry (most >> others use the same approach). >> >> (defun fannkuch (n) >> (declare (optimize (speed 3) (safety 0) (debug 0) #+lispworks(fixnum-safety 0)) >> (type (integer 0 128) n)) >> (if (< n 1) (return-from fannkuch 0)) >> (let ((perm (make-array n :element-type '(integer 0 128))) >> (perml (make-array n :element-type '(integer 0 128))) >> (count (make-array n :element-type '(integer 0 128))) >> (flips 0) (flipsmax 0) (r n) (nl (1- n)) (perm0 0) >> (check 0) >> (k 0) (i 0)) >> (declare (type (simple-array (integer 0 128) (*)) perm perml count) >> (type (integer 0 256) flips flipsmax nl perm0 check k i) >> (type (integer 0 128) r)) >> >> (loop for i from 0 below n do (setf (aref perml i) i)) >> >> (loop >> (when (< check 30) >> (loop for i from 0 below n do (princ (1+ (aref perml i)))) >> (terpri) >> (incf check)) >> >> (loop while (> r 1) do >> (setf (aref count (1- r)) r) >> (decf r)) >> >> (unless (or (= (aref perml 0) 0) (= (aref perml nl) nl)) >> (setf flips 0) >> (loop for i fixnum from 0 below n do (setf (aref perm i) (aref perml i))) >> (setf k (aref perml 0)) >> (loop while (/= k 0) do >> (loop for j fixnum downfrom (1- k) >> for i fixnum from 1 >> while (< i j) do (rotatef (aref perm i) (aref perm j))) >> (incf flips) >> (rotatef k (aref perm k))) >> (when (< flipsmax flips) >> (setf flipsmax flips))) >> >> (loop do >> (when (= r n) (return-from fannkuch flipsmax)) >> (setf i 0 perm0 (aref perml 0)) >> (loop while (< i r) do >> (setf k (1+ i) >> (aref perml i) (aref perml k) >> i k)) >> (setf (aref perml r) perm0) >> (when (> (decf (aref count r)) 0) (loop-finish)) >> (incf r))))) >> >> I finally loaded SBCL 0.9.17 onto one of my FreeBSD machines. >> On the lowly PIIIx2 500MHz (time (fannkuch 10)) >> >> SBCL 0.9.17 3.01s >> LWL 4.3.7 4.75s >> gcc 1.80s >> (from the Shootout Site gcc -O3 -fomit-frame-pointer -march=pentium3) >> >> Scaling that to the results on the shootout site puts gcc=0.47, >> LW=1.24 and SBCL=0.79. >> >> Why the shootout site would have removed the previous faster Lisp >> version is beyond me. >> >> Wade > > Incidentally, if you would like this program or any variant you might > author from Juho Snellman's program to appear on the computer language > shootout, you should follow the FAQ instructions > http://shootout.alioth.debian.org/gp4/faq.php#help > Sure, I submitted a slightly modified version. It is only 30% slower than the gcc version. Wade ;;; The Computer Language Shootout ;;; http://shootout.alioth.debian.org/ ;;; Contributed by Wade Humeniuk ;;; ;;; fannkuch for Lisp (SBCL) ;;; ;;; Compile: sbcl --load fannkuch.lisp --eval "(save-lisp-and-die \"fannkuch.core\" :purify t :toplevel (lambda () (main) (quit)))" ;;; ;;; Run: sbcl --noinform --core fannkuch.core %A (defun write-permutation (perm) (loop for i across perm do (princ (1+ i))) (terpri)) (defun fannkuch (n) (declare (optimize (speed 3) (safety 0) (debug 0)) (fixnum n)) (assert (< 1 n 128)) (let ((perm (make-array n :element-type 'fixnum)) (perm1 (make-array n :element-type 'fixnum)) (count (make-array n :element-type 'fixnum)) (flips 0) (flipsmax 0) (r n) (check 0) (k 0) (i 0) (perm0 0)) (declare ((simple-array fixnum (*)) perm perm1 count) (fixnum flips flipsmax check k r i perm0)) (dotimes (i n) (setf (aref perm1 i) i)) (loop (when (< check 30) (write-permutation perm1) (incf check)) (loop while (> r 1) do (setf (aref count (1- r)) r) (decf r)) (unless (or (= (aref perm1 0) 0) (= (aref perm1 (1- n)) (1- n))) (setf flips 0) (dotimes (i n) (setf (aref perm i) (aref perm1 i))) (setf k (aref perm1 0)) (loop while (/= k 0) do (loop for j fixnum downfrom (1- k) for i fixnum from 1 while (< i j) do (rotatef (aref perm i) (aref perm j))) (incf flips) (rotatef k (aref perm k))) (setf flipsmax (max flipsmax flips))) (loop do (when (= r n) (return-from fannkuch flipsmax)) (setf i 0 perm0 (aref perm1 0)) (loop while (< i r) do (setf k (1+ i) (aref perm1 i) (aref perm1 k) i k)) (setf (aref perm1 r) perm0) (when (> (decf (aref count r)) 0) (loop-finish)) (incf r))))) (defun main () (let ((n (parse-integer (second *posix-argv*)))) (format t "Pfannkuchen(~D) = ~D~%" n (fannkuch n))))
From: Henry Bigelow on 2 Oct 2006 21:51 hi jon, > You may be interested in my ray tracer benchmarks: > > http://www.ffconsultancy.com/free/ray_tracer/languages.html thank you! very enlightening. i read the analysis. i have a few questions about this excerpt "However, the designers of the ML family of languages (including OCaml and SML) deliberately avoided some of the functionality provided by Lisp in order to facilitate static type checking and improve performance." i guess i misunderstood something. does lisp not have any type inference? or does it have partial type inference if you explicitly declare the types for some variables and not others? "Specifically, Lisp provides macros to customise syntax and allows them to be entwined with ordinary code, and provides run-time code manipulation. SML provides neither macros nor run-time code generation." "OCaml provides camlp4 macros, a limited form that are separate from the language, and the derived language MetaOCaml also provides run-time code generation" are camlp4 macros as powerful as lisp macros? and, is the run-time code generation of MetaOCaml as powerful as lisp's 'compile' function? in the bigger picture, do you foresee any advancements to either lisp or ocaml that would improve either of them, maybe by sharing ideas? thanks, henry > > On my computer, those benchmarks show Lisp to be roughly twice as slow and > twice as verbose as OCaml. while i'm not surprised lisp is slower for this benchmark, i am confused why it would be more verbose. >However, the benchmark is quite specific. It > only tests data structures (trees) and floating point performance (ray > sphere). Also, timings vary considerably between architectures. Now that > Intel has a decent CPU, I'll be interested to see a Core Duo version of > this benchmark. > > -- > Dr Jon D Harrop, Flying Frog Consultancy > Objective CAML for Scientists > http://www.ffconsultancy.com/products/ocaml_for_scientists
From: Wade Humeniuk on 3 Oct 2006 09:16 Thank you Isaac for getting the benchmark up last night. Lisp SBCL #2 is now 5th on http://shootout.alioth.debian.org/gp4/benchmark.php?test=fannkuch&lang=all However there seems to be a problem getting it going on the Debian AMD Sempron test. Something is different about getting SBCL and CMUCL execed's (unexec'd) on those platforms. I assume it is Debian preventing execution. http://shootout.alioth.debian.org/debian/benchmark.php?test=fannkuch&lang=sbcl&id=2 http://shootout.alioth.debian.org/debian/benchmark.php?test=fannkuch&lang=cmucl&id=2 Wade
From: Isaac Gouy on 3 Oct 2006 12:51
Wade Humeniuk wrote: > Thank you Isaac for getting the benchmark up last night. > > Lisp SBCL #2 is now 5th on > > http://shootout.alioth.debian.org/gp4/benchmark.php?test=fannkuch&lang=all > > However there seems to be a problem getting it going on the > Debian AMD Sempron test. Something is different about getting > SBCL and CMUCL execed's (unexec'd) on those platforms. I assume > it is Debian preventing execution. > > http://shootout.alioth.debian.org/debian/benchmark.php?test=fannkuch&lang=sbcl&id=2 > http://shootout.alioth.debian.org/debian/benchmark.php?test=fannkuch&lang=cmucl&id=2 > > Wade We ask for push everything to go through the tracker, so we can um keep track of things... There's a bug tracker http://alioth.debian.org/tracker/?atid=411002&group_id=30402&func=browse |