Before people tell there is already a gcd function - I'm well aware.
I was just playing around to see if I could match it's performance - I
think it's pretty clear they use an algorithm much more optimized than
Euclid's old trick that I'm implementing. However, my question
remains as to why a declaration statement inside my do loop transforms
it into a consing garbage collecting monster? I always thought a
declaration helped speed things up a bit as it eliminated guess work
for the interpreter. However, I'm also ridiculously ignorant as I'm
new to the LISP game and despite reading about the declare function, I
can't see why this is occuring.
CL-USER> (defun gcf (a b)
(declare (integer a)
(integer b))
(do ((tmp 0))
((= a 0) b)
(if (< a b)
(setf tmp a a b b tmp))
(decf a b)))
GCF
CL-USER> (time (dotimes (i 100000)
(gcf 12 24)))
Real time: 0.71875 sec.
Run time: 0.609375 sec.
Space: 768 Bytes
NIL
CL-USER> (defun gcf2 (a b)
(declare (type integer a)
(type integer b))
(do ((tmp 0))
((= a 0) b)
(declare (type integer tmp))
(if (< a b)
(setf tmp a a b b tmp))
(decf a b)))
GCF2
CL-USER> (time (dotimes (i 100000)
(gcf2 12 24)))
Real time: 0.640625 sec.
Run time: 0.640625 sec.
Space: 800768 Bytes
GC: 1, GC time: 0.015625 sec.
NIL
NIL
> CL-USER> (time (dotimes (i 100000)
> (gcf 12 24)))
>
Realized this was the result printed was actually *faster* than
"slower" version. However this was a goof in copying and pasting:
CL-USER> (time (dotimes (i 100000)
(gcf 12 24)))
Real time: 0.578125 sec.
Run time: 0.578125 sec.
Space: 768 Bytes
NIL
jrwats wrote:
>> CL-USER> (time (dotimes (i 100000)
>> (gcf 12 24)))
>>
> Realized this was the result printed was actually *faster* than
> "slower" version. However this was a goof in copying and pasting:
> CL-USER> (time (dotimes (i 100000)
> (gcf 12 24)))
>
> Real time: 0.578125 sec.
> Run time: 0.578125 sec.
> Space: 768 Bytes
> NIL
Either way, gcf showed a faster "run time" than gcf2. You didn't
mention which CL you're using; SBCL 1.0.19 runs both at roughly the
same speed on my system.
(defun gcf3 (a b)
(declare (type fixnum a)
(type fixnum b))
(do ((tmp 0))
((= a 0) b)
(declare (type fixnum tmp))
(if (< a b)
(setf tmp a a b b tmp))
(decf a b)))
is substantially faster than either gcf or gcf2 (~3/8 as long). And
the built-in gcd is 10x faster than gcf3. But some source
transformations occurred; SBCL identified the gcd had constant
arguments and precomputed the value; thus its just timing the dotimes
loop.
Moving the values out of the loop (to reduce optimizations) leaves gcf
and gcf2 in a dead heat, with gcf3 still 55% faster and gcd 6x faster yet.
(defparameter *a* 12)
(defparameter *b* 24)
(time (dotimes (i #.(expt 10 8))
(gcf2 *a* *b*)))
FWIW, I think the built-in gcd is being rewritten to use
(in-package "SB!KERNEL")
;;; Do the GCD of two integer arguments. With fixnum arguments, we use the
;;; binary GCD algorithm from Knuth's seminumerical algorithms (slightly
;;; structurified), otherwise we call BIGNUM-GCD. We pick off the
special case
;;; of 0 before the dispatch so that the bignum code doesn't have to worry
;;; about "small bignum" zeros.
(defun two-arg-gcd (u v)
(cond ((eql u 0) (abs v))
((eql v 0) (abs u))
(t
(number-dispatch ((u integer) (v integer))
((fixnum fixnum)
(locally
(declare (optimize (speed 3) (safety 0)))
(do ((k 0 (1+ k))
(u (abs u) (ash u -1))
(v (abs v) (ash v -1)))
((oddp (logior u v))
(do ((temp (if (oddp u) (- v) (ash u -1))
(ash temp -1)))
(nil)
(declare (fixnum temp))
(when (oddp temp)
(if (plusp temp)
(setq u temp)
(setq v (- temp)))
(setq temp (- u v))
(when (zerop temp)
(let ((res (ash u k)))
(declare (type sb!vm:signed-word res)
(optimize (inhibit-warnings 3)))
(return res))))))
(declare (type (mod #.sb!vm:n-word-bits) k)
(type sb!vm:signed-word u v)))))
((bignum bignum)
(bignum-gcd u v))
((bignum fixnum)
(bignum-gcd u (make-small-bignum v)))
((fixnum bignum)
(bignum-gcd (make-small-bignum u) v))))))
- Daniel
jrwats wrote:
>> CL-USER> (time (dotimes (i 100000)
>> (gcf 12 24)))
>>
> Realized this was the result printed was actually *faster* than
> "slower" version. However this was a goof in copying and pasting:
> CL-USER> (time (dotimes (i 100000)
> (gcf 12 24)))
>
> Real time: 0.578125 sec.
> Run time: 0.578125 sec.
> Space: 768 Bytes
> NIL
Oh, Christ, you are timing interpreted code? (depending on the compiler.)
I'd like to see as much as possible compiled, tho I dount there is any
harm in: (time (gcf-times 1000000))
kt
--
$$$$$: http://www.theoryyalgebra.com/
Cells: http://common-lisp.net/project/cells/
BSlog: http://smuglispweeny.blogspot.com/
> Oh, Christ, you are timing interpreted code? (depending on the compiler.)
>
Forgive my naivety. I've gotten rusty with lisp and all - completely
forgot about interpreter/compiler/etc ... here's the verdict
(everything done in clisp)
;;;gcf.lisp
(defun gcf (a b)
(declare (type integer a)
(type integer b))
(do ((tmp 0))
((= a 0) b)
(if (< a b)
(setf tmp a a b b tmp))
(decf a b)))
(defun gcf2 (a b)
(declare (type integer a)
(type integer b))
(do ((tmp 0))
((= a 0) b)
(declare (type integer tmp))
(if (< a b)
(setf tmp a a b b tmp))
(decf a b)))
(defun gcf3 (a b)
(declare (type fixnum a)
(type fixnum b))
(do ((tmp 0))
((= a 0) b)
(declare (type fixnum tmp))
(if (< a b)
(setf tmp a a b b tmp))
(decf a b)))
;;;EOF
;back to SLIME...
CL-USER> (compile-file "c:/cygwin/home/administrator/lisp/gcf.lisp")
;; Compiling file C:\cygwin\home\administrator\lisp\gcf.lisp ...
;; Wrote file C:\cygwin\home\administrator\lisp\gcf.fas
0 errors, 0 warnings
#P"C:\\cygwin\\home\\Administrator\\lisp\\gcf.fas"
NIL
NIL
CL-USER> (load "c:/cygwin/home/administrator/lisp/gcf.fas")
;; Loading file C:\cygwin\home\administrator\lisp\gcf.fas ...
WARNING: DEFUN/DEFMACRO: redefining function GCF in
C:\cygwin\home\Administrator\lisp\gcf.fas, was defined in top-
level
WARNING: DEFUN/DEFMACRO: redefining function GCF2 in
C:\cygwin\home\Administrator\lisp\gcf.fas, was defined in top-
level
WARNING: DEFUN/DEFMACRO: redefining function GCF3 in
C:\cygwin\home\Administrator\lisp\gcf.fas, was defined in top-
level
;; Loaded file C:\cygwin\home\administrator\lisp\gcf.fas
T
CL-USER> (time (dotimes (i 100000)
(gcf3 12 24)))
Real time: 0.140625 sec.
Run time: 0.140625 sec.
Space: 768 Bytes
NIL
CL-USER> (time (dotimes (i 100000)
(gcf2 12 24)))
Real time: 0.140625 sec.
Run time: 0.140625 sec.
Space: 768 Bytes
NIL
CL-USER> (time (dotimes (i 100000)
(gcf 12 24)))
Real time: 0.140625 sec.
Run time: 0.140625 sec.
Space: 768 Bytes
NIL
CL-USER> (time (dotimes (i 100000)
(gcd 12 24)))
Real time: 0.125 sec.
Run time: 0.125 sec.
Space: 768 Bytes
NIL
CL-USER> (/ (- .140625 .125) .125)
0.125
Only a 12.5% time increase compared to built-in gcd. Not bad for a
400 year old algorithm... and sorry I wasted everyone's time with the
interpreter timing!!!
jrwats wrote:
>> Oh, Christ, you are timing interpreted code? (depending on the compiler.)
>>
> Forgive my naivety. I've gotten rusty with lisp and all - completely
> forgot about interpreter/compiler/etc ...
Naivete? No problem!
jrwats opened with:
> However, I'm also ridiculously ignorant as I'm
> new to the LISP game ....
Lying? Tim, you get the helicopters, I'll get the hounds.
here's the verdict
> (everything done in clisp)
>
> ;;;gcf.lisp
> (defun gcf (a b)
> (declare (type integer a)
> (type integer b))
> (do ((tmp 0))
> ((= a 0) b)
> (if (< a b)
> (setf tmp a a b b tmp))
> (decf a b)))
>
> (defun gcf2 (a b)
> (declare (type integer a)
> (type integer b))
> (do ((tmp 0))
> ((= a 0) b)
> (declare (type integer tmp))
> (if (< a b)
> (setf tmp a a b b tmp))
> (decf a b)))
>
> (defun gcf3 (a b)
> (declare (type fixnum a)
> (type fixnum b))
> (do ((tmp 0))
> ((= a 0) b)
> (declare (type fixnum tmp))
> (if (< a b)
> (setf tmp a a b b tmp))
> (decf a b)))
>
> ;;;EOF
>
> ;back to SLIME...
>
> CL-USER> (compile-file "c:/cygwin/home/administrator/lisp/gcf.lisp")
>
> ;; Compiling file C:\cygwin\home\administrator\lisp\gcf.lisp ...
> ;; Wrote file C:\cygwin\home\administrator\lisp\gcf.fas
> 0 errors, 0 warnings
> #P"C:\\cygwin\\home\\Administrator\\lisp\\gcf.fas"
> NIL
> NIL
> CL-USER> (load "c:/cygwin/home/administrator/lisp/gcf.fas")
> ;; Loading file C:\cygwin\home\administrator\lisp\gcf.fas ...
> WARNING: DEFUN/DEFMACRO: redefining function GCF in
> C:\cygwin\home\Administrator\lisp\gcf.fas, was defined in top-
> level
> WARNING: DEFUN/DEFMACRO: redefining function GCF2 in
> C:\cygwin\home\Administrator\lisp\gcf.fas, was defined in top-
> level
> WARNING: DEFUN/DEFMACRO: redefining function GCF3 in
> C:\cygwin\home\Administrator\lisp\gcf.fas, was defined in top-
> level
> ;; Loaded file C:\cygwin\home\administrator\lisp\gcf.fas
> T
> CL-USER> (time (dotimes (i 100000)
> (gcf3 12 24)))
>
>
> Real time: 0.140625 sec.
> Run time: 0.140625 sec.
> Space: 768 Bytes
> NIL
> CL-USER> (time (dotimes (i 100000)
> (gcf2 12 24)))
>
>
> Real time: 0.140625 sec.
> Run time: 0.140625 sec.
> Space: 768 Bytes
> NIL
> CL-USER> (time (dotimes (i 100000)
> (gcf 12 24)))
>
>
> Real time: 0.140625 sec.
> Run time: 0.140625 sec.
> Space: 768 Bytes
> NIL
> CL-USER> (time (dotimes (i 100000)
> (gcd 12 24)))
>
>
> Real time: 0.125 sec.
> Run time: 0.125 sec.
> Space: 768 Bytes
> NIL
> CL-USER> (/ (- .140625 .125) .125)
> 0.125
>
> Only a 12.5% time increase compared to built-in gcd. Not bad for a
> 400 year old algorithm... and sorry I wasted everyone's time with the
> interpreter timing!!!
>
<sigh> You must now write on the board 100000 times "dotimes is being
interpreted". Hmmm, that is a little too easy. How about?:
His Kennyness did not suggest "(time (gcf-times 1000000))" by accident.
Now about that new/rusty combo....
kzo
--
$$$$$: http://www.theoryyalgebra.com/
Cells: http://common-lisp.net/project/cells/
BSlog: http://smuglispweeny.blogspot.com/
> His Kennyness did not suggest "(time (gcf-times 1000000))" by accident.
CL-USER> (time (gcf-times 1000000))
Real time: 0.8125 sec.
Run time: 0.8125 sec.
Space: 0 Bytes
NIL
CL-USER> (time (gcf2-times 1000000))
Real time: 0.78125 sec.
Run time: 0.78125 sec.
Space: 0 Bytes
NIL
CL-USER> (time (gcf3-times 1000000))
Real time: 0.796875 sec.
Run time: 0.78125 sec.
Space: 0 Bytes
NIL
CL-USER> (time (gcd-times 1000000))
Real time: 0.09375 sec.
Run time: 0.09375 sec.
Space: 0 Bytes
NIL
There. done. I'm going home.
jrwats wrote:
>> His Kennyness did not suggest "(time (gcf-times 1000000))" by accident.
> CL-USER> (time (gcf-times 1000000))
>
> Real time: 0.8125 sec.
> Run time: 0.8125 sec.
> Space: 0 Bytes
> NIL
> CL-USER> (time (gcf2-times 1000000))
>
> Real time: 0.78125 sec.
> Run time: 0.78125 sec.
> Space: 0 Bytes
> NIL
> CL-USER> (time (gcf3-times 1000000))
>
>
> Real time: 0.796875 sec.
> Run time: 0.78125 sec.
> Space: 0 Bytes
> NIL
> CL-USER> (time (gcd-times 1000000))
>
>
> Real time: 0.09375 sec.
> Run time: 0.09375 sec.
> Space: 0 Bytes
> NIL
>
> There. done. I'm going home.
Wait! What have we learned?
1. Yeah, the built-in is faster (9x so)
2. No, declares did not degrade performance
3. Time only (a) a single call to (b) a compiled function
What have we not learned?
1. How you can be new to lisp and rusty at the same time.
:)
kt
--
$$$$$: http://www.theoryyalgebra.com/
Cells: http://common-lisp.net/project/cells/
BSlog: http://smuglispweeny.blogspot.com/
> 1. How you can be new to lisp and rusty at the same time.
>
let's say you forced yourself to learn lisp last fall for a "Chess &
AI" class @ U of AZ by building your project entirely in it (aside
from the javascript ajax GUI), didn't really get involved in "lispy"
coding, but learned enough about functional programming to have (even
used macros! oooohhhh... ahhh.....) one of the only implementations
that worked, as well as the smallest line count (everyone else had C++/
Java). Then let's say over the summer you decided to get back into
Lisp... since you graduated and entered the industry, you're bored and
want to use something that ISN'T C++.
1. you were never experienced with Lisp in the first place = new
2. with the little you did know, you managed to forget it = rusty
new to begin with, and rusty once back in.
And as Lisp threads tend to go, we're arguing about the mundane and
trivial - I do remember that part!
jrwats wrote:
>> 1. How you can be new to lisp and rusty at the same time.
>>
>
> let's say you forced yourself to learn lisp last fall for a "Chess &
> AI" class @ U of AZ by building your project entirely in it (aside
> from the javascript ajax GUI), ...
Damn. We gotta get Andy going again on OpenAIR.
>... didn't really get involved in "lispy"
> coding, but learned enough about functional programming to have (even
> used macros! oooohhhh... ahhh.....) one of the only implementations
> that worked, as well as the smallest line count (everyone else had C++/
> Java). Then let's say over the summer you decided to get back into
> Lisp... since you graduated and entered the industry, you're bored and
> want to use something that ISN'T C++.
>
> 1. you were never experienced with Lisp in the first place = new
> 2. with the little you did know, you managed to forget it = rusty
>
> new to begin with, and rusty once back in.
Fair enough. Sorry about the hounds, not to worry, they've had their
shots. Lucky Bradshaw was slow on the choppers.
>
> And as Lisp threads tend to go, we're arguing about the mundane and
> trivial - I do remember that part!
It is what we do best. But Early Troll Detection is a bit of a sport
around these parts, if only for me.
Meanwhile, did you want to thank me for answering your question and
helping you understand how to apply time? It did take me two tries to
get through to you, I'm exhausted.
You can make it up to me by testing my damn Algebra software, no one
else will.*
kt
* Thx to thems that did.
--
$$$$$: http://www.theoryyalgebra.com/
Cells: http://common-lisp.net/project/cells/
BSlog: http://smuglispweeny.blogspot.com/
jrwats wrote:
> Before people tell there is already a gcd function - I'm well aware.
RTFM: http://clhs.lisp.se/Body/f_gcd.htm
This response brought to you by The c.l.l Committee for the Inability to
Read.
kt
ps. Sorry, I have never understood the optimizing declarations. k
--
$$$$$: http://www.theoryyalgebra.com/
Cells: http://common-lisp.net/project/cells/
BSlog: http://smuglispweeny.blogspot.com/
> This response brought to you by The c.l.l Committee for the Inability to
> Read.
>
Haha. Ummmmm.... thanks? Thanks for the expeditious response at
least.
jrwats <······@gmail.com> writes:
> Before people tell there is already a gcd function - I'm well aware.
> I was just playing around to see if I could match it's performance - I
> think it's pretty clear they use an algorithm much more optimized than
> Euclid's old trick that I'm implementing. However, my question
> remains as to why a declaration statement inside my do loop transforms
> it into a consing garbage collecting monster? I always thought a
> declaration helped speed things up a bit as it eliminated guess work
> for the interpreter. However, I'm also ridiculously ignorant as I'm
> new to the LISP game and despite reading about the declare function, I
> can't see why this is occuring.
It all depends on the implementation.
In the case of clisp, there is no way to make it faster than the
hand-optimized C code implementing CL "primitives" from the lisp
level. You didn't even _compile_ your code, so clisp will just
interpret it. And clisp just doesn't take into account most
declarations, so their mere presence will indeed slow down the
interpreter (but not the compiler so go ahead, put declarations for
the benefit of other implementations, and for their self documenting
aspect).
If you want to try to beat implementers from within their
implementation, try a natively compiled implementation such as sbcl.
--
__Pascal Bourguignon__ http://www.informatimago.com/
"You question the worthiness of my code? I should kill you where you
stand!"