Path: archiver1.google.com!news1.google.com!newsfeed.stanford.edu!canoe.uoregon.edu!arclight.uoregon.edu!news.tufts.edu!uunet!dca.uu.net!ash.uu.net!prodigy.com!newsmst01.news.prodigy.com!prodigy.com!postmaster.news.prodigy.com!newssvr14.news.prodigy.com.POSTED!351d80e2!not-for-mail
From: Duane Rettig <du...@franz.com>
Newsgroups: comp.lang.lisp
Subject: Re: Common Lisp wish list item
Organization: Franz Inc.
Lines: 75
Message-ID: <4d6scky2d.fsf@beta.franz.com>
References: <3238779012022126@naggum.no> <ey3znvh2n70.fsf@cley.com> <47kilcd2l.fsf@beta.franz.com> <86fzx87e4m.fsf@gondolin.local.net>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
User-Agent: Gnus/5.0807 (Gnus v5.8.7) XEmacs/21.1 (Channel Islands)
NNTP-Posting-Host: 67.119.196.186
X-Complaints-To: abuse@prodigy.net
X-Trace: newssvr14.news.prodigy.com 1029945600 ST000 67.119.196.186 (Wed, 21 Aug 2002 12:00:00 EDT)
NNTP-Posting-Date: Wed, 21 Aug 2002 12:00:00 EDT
X-UserInfo1: [[PAPDCAOPWWSVPXTJIX_WTDEB\@PD\MNPWZKB]MPXHBTWICYFWUQBKZQLYJX\_ITFD_KFVLUN[DOM_A_NSYNWPFWNS[XV\I]PZ@BQ[@CDQDPCL^FKCBIPC@KLGEZEFNMDYMKHRL_YYYGDSSODXYN@[\BK[LVTWI@AXGQCOA_SAH@TPD^\AL\RLGRFWEARBM
Date: Wed, 21 Aug 2002 16:00:01 GMT

Alain Picard <apicard+die-spammer-...@optushome.com.au> writes:

> I recently had the fun (!) of discovering how hard it can
> be to really optimize CL code while implementing BLOWFISH.
> What an eye opener!
> 
> Duane Rettig <du...@franz.com> writes:
> 
> > But what happens then when the "naturally 32 bit" algorithms start
> > becoming "naturally 64 bit"?

I should have placed a smiley here.  Encryption algorithms
are _already_ greater than 32 bits naturally.  Some are 128 bits.

> Which they will --- Bruce Schneier states that making blowfish run
> fast on "typical 32 bit hardware"(*) was an _explicit_ design goal.
> So we'll be back to square one.

Blowfish may have been designed to fit into 32-bit hardware (C mentality)
but it is a 64-bit algorithm.  The 32-bit-ness comes from breaking up
each block into 32-bits at a time.

> For the record, the CMUCL hacks (to unbox 32bit modulo adds and xors)
> make blowfish run 120 times faster than the bignum calls in Lispworks 4.2.

There's the carrot ...

> Even then, I'm surely missing something basic, because Schneier says
> blowfish should run at 8 Mb/s on a 150Mhz pentium (18 clock
> cycles/byte), and mine runs at 3 Mb/s on a 433Mhz Celeron.
> 
> I've read that in Lisp you can write slow code fast, and then
> have to work for the speed.  I didn't realize just _how_ _hard_,
> however.  :-)

And there's the work to get the carrot.  If the carrot is very tasty,
then one works for it.

However, I wonder just how muuch work it really is, compared to the
same algorithm in C.  Bear with me here, because the answer might not
be as intuitive as one might think:

I've seen Lisp/C coders (people who know both languages) bend over
backwards to make C code work (and of course, work fairly fast.  When
asked how hard it was, they'll say "it was no big deal".  But then those
same people will complain vociferously at all of the terrible extra work
requuuired to optimize som already-working lisp code (it worked right
away, of course) even if that extra effort consisted of placing a single
declaration in the code.

So it would be interesting to figure out (probably necessarily by
measurement of actual time spent rather than by estimation based on
intuition) how much time it took you to do this optimization _as_
_oppoesed_ to implementing the same algorithm in C.  Bear in mind
also that Lispers aren't used to having to make such optimizations
(they usually simply aren't necessary), and so one would have to
mitigate the times based on being an expert C coder vs a novice
fast-lisp coder.  All things considered and factored in, I'd suspect
that the times are pretty similar, if not _still_ tipping the scales
in Lisp's favor, even with all of the warts of trying to shoehorn a
64-bit (or 128-bit) algorithm into 32 bits using the same shoehorn
as C is using...

> (*) Interestingly, Schneier conjectures that blowfish is _probably_ strong
>     using 16 bit blocks (which _would_ fit into fixnums of essentially
>     all current lisps).  I ran out of enthusiasm and didn't write that
>     code to benchmark it.

But if the 32-bit technique can be used, why dumb down to 16 bits?
Or, why not use 29 bits instead?  Three fixnums per block might work...

-- 
Duane Rettig    du...@franz.com    Franz Inc.  http://www.franz.com/
555 12th St., Suite 1450               http://www.555citycenter.com/
Oakland, Ca. 94607        Phone: (510) 452-2000; Fax: (510) 452-0182