I've recently implemented a little cryptography in Common Lisp and got
somewhat depressed by the C-ishness of the published algorithms - they
usually rely heavily on 32 bit integers. Some of the operations (esp.
XOR) are easily decomposed into two 16 bit operations, but still that
means that my CL program would at least use twice as many clock cycles
as a highly optimized program utilizing 32 bit integers.
I was wondering if this problem will be solved when we move to 64 bit
architectures: Do the already existing 64 bit lisp implementations
support fixnums bigger than 32 bit?
--
(espen)
From: Christophe Rhodes
Subject: Re: fixnum size in 64 bit lisps?
Date:
Message-ID: <sqeligvrhy.fsf@cam.ac.uk>
Espen Vestre <·····@*do-not-spam-me*.vestre.net> writes:
> I've recently implemented a little cryptography in Common Lisp and got
> somewhat depressed by the C-ishness of the published algorithms - they
> usually rely heavily on 32 bit integers. Some of the operations (esp.
> XOR) are easily decomposed into two 16 bit operations, but still that
> means that my CL program would at least use twice as many clock cycles
> as a highly optimized program utilizing 32 bit integers.
>
> I was wondering if this problem will be solved when we move to 64 bit
> architectures: Do the already existing 64 bit lisp implementations
> support fixnums bigger than 32 bit?
I'll let someone who knows talk about Allegro's 64-bit
implementations, which are the only ones on the market that I know of.
Raymond Toy is looking at implementing large fixnums on CMUCL/SPARC --
you might wish to contact him for more details about those. I'll just
mention that I think that sbcl (or indeed cmucl), given proper
declarations, can usually manage to do unboxed 32-bit arithmetic
without any fudging except in the case of byte-rotation, which I have
addressed in the past, giving performance comparable to C (certainly
less than a factor of 2 between the implementations)
Christophe
--
Jesus College, Cambridge, CB5 8BL +44 1223 510 299
http://www-jcsu.jesus.cam.ac.uk/~csr21/ (defun pling-dollar
(str schar arg) (first (last +))) (make-dispatch-macro-character #\! t)
(set-dispatch-macro-character #\! #\$ #'pling-dollar)
Christophe Rhodes <·····@cam.ac.uk> writes:
> Espen Vestre <·····@*do-not-spam-me*.vestre.net> writes:
>
> > I've recently implemented a little cryptography in Common Lisp and got
> > somewhat depressed by the C-ishness of the published algorithms - they
> > usually rely heavily on 32 bit integers. Some of the operations (esp.
> > XOR) are easily decomposed into two 16 bit operations, but still that
> > means that my CL program would at least use twice as many clock cycles
> > as a highly optimized program utilizing 32 bit integers.
> >
> > I was wondering if this problem will be solved when we move to 64 bit
> > architectures: Do the already existing 64 bit lisp implementations
> > support fixnums bigger than 32 bit?
>
> I'll let someone who knows talk about Allegro's 64-bit
> implementations, which are the only ones on the market that I know of.
CL-USER(1): most-positive-fixnum
1152921504606846975
CL-USER(2): (format t "~x" *)
fffffffffffffff
NIL
CL-USER(3):
> Raymond Toy is looking at implementing large fixnums on CMUCL/SPARC --
> you might wish to contact him for more details about those. I'll just
> mention that I think that sbcl (or indeed cmucl), given proper
> declarations, can usually manage to do unboxed 32-bit arithmetic
> without any fudging except in the case of byte-rotation, which I have
> addressed in the past, giving performance comparable to C (certainly
> less than a factor of 2 between the implementations)
Allegro CL also does unboxed compilation of 32-bit integers.
--
Duane Rettig Franz Inc. http://www.franz.com/ (www)
1995 University Ave Suite 275 Berkeley, CA 94704
Phone: (510) 548-3600; FAX: (510) 548-8253 ·····@Franz.COM (internet)
From: Christophe Rhodes
Subject: Re: fixnum size in 64 bit lisps?
Date:
Message-ID: <sqadt4vpdk.fsf@cam.ac.uk>
Duane Rettig <·····@franz.com> writes:
> Christophe Rhodes <·····@cam.ac.uk> writes:
>
> > I'll let someone who knows talk about Allegro's 64-bit
> > implementations, which are the only ones on the market that I know of.
>
> CL-USER(1): most-positive-fixnum
> 1152921504606846975
> CL-USER(2): (format t "~x" *)
> fffffffffffffff
> NIL
Oh, good :)
> > Raymond Toy is looking at implementing large fixnums on CMUCL/SPARC --
> > you might wish to contact him for more details about those. I'll just
> > mention that I think that sbcl (or indeed cmucl), given proper
> > declarations, can usually manage to do unboxed 32-bit arithmetic
> > without any fudging except in the case of byte-rotation, which I have
> > addressed in the past, giving performance comparable to C (certainly
> > less than a factor of 2 between the implementations)
>
> Allegro CL also does unboxed compilation of 32-bit integers.
I suspected as much.
Is Allegro CL able to detect the following idiom or anything like it
as a rotation, and do unboxed arithmetic?
(locally
(declare (type (unsigned-byte 32)) x)
(logand #xffffffff (logior (ash x -1) (ash x 31))))
gcc does detect the analogue as a rotation, but gcc does have the
advantage that the C language doesn't do sensible things with integer
overflow...
This is something that I've looked at, on and off, and I haven't been
able to come up with a credible way of making SBCL smart enough to
detect anything like this. Optimizing a ROTATE-BYTE function is
simple enough, but detecting user-written rotation is another
matter...
Christophe
--
Jesus College, Cambridge, CB5 8BL +44 1223 510 299
http://www-jcsu.jesus.cam.ac.uk/~csr21/ (defun pling-dollar
(str schar arg) (first (last +))) (make-dispatch-macro-character #\! t)
(set-dispatch-macro-character #\! #\$ #'pling-dollar)