Performance (would you believe BYTE?)

[michaelg@Xenon.Stanford.EDU (Michael Greenwald)]

This is a non-urgent comment on performance of some MCL code.  (I'm
not an MCL user, so perhaps this is already well-documented.)

Someone was flaming in the hall here about how slow lisp was, and how
he'd always use C -- he'd given Lisp its chance.  The application he
described sounded like it should have been reasonably fast, but
apparently this was taking minutes when the entire operation should
have taken a couple of seconds.  I was curious, so I decided to look
into it.

Apparently he learned Lisp for some class here, and later used MCL on
a Mac.  He took me to a Mac, and showed me a program that did
something like the following:

He took an array of bits that was stored in some Macintosh data
structure, and read it out using something like sys:%p-contents-offset
(I think the actual call was something like %read-word or %get-word, I
won't swear to it).  His routine was supposed to read it out N bits at
a time (N being a parameter, not necessarily a power of 2), but he
didn't know how to do it from Lisp.  So he read it out a byte (or a
word, or an integer, whatever) at a time, and put it into a bignum
(!!) using something like:

(DOTIMES (I NBYTES)
  (SETQ BITS (DPB (%READ-BYTE PTR (- NBYTES IDX 1))
	          (BYTE 8 (* I 8))
		  BITS)))

(I'm not sure of the exact form, but this was the general form) and
then extracted it in another pass using LDB and BYTE, and put the
numbers into an array for processing.  (It was some data compression
or analysis routine, that he didn't go into detail on).

This was >slow<.

Anyway, when I tried this for a large NBytes, it raised an error,
eventually, because DPB was getting a vector instead of a number.  (I
don't know if this was a bug, or if he somehow corrupted memory
getting the bits into the Macintosh data structure.  I assume
everything he did on the Mac end was kosher, but who knows?)
Apparently, when the value of 'I got large enough (BYTE 8 (* I 8))
generated some humongoid number.

Sure enough, the implementation of BYTE on MCL conses some amazingly
large numbers.  Using ASH sped up his application (still not fast
enough, and by then he was bored, and disappeared.)  This was on MCL
2.0b3, and I understand that it is past beta now, although I doubt the
implementation of BYTE was changed.

I tried to argue that extracting the numbers out of an array of bits
wasn't that much different then he'd have to do in C, (two operations
for when the extraction crossed a word boundary, for example).  But he
did have a point that numerical manipulation of bignum shouldn't be
consing so much more than it had to (I still think his >application<
was wrong (why into a bignum?), but his complaint about BYTE was right
on the money).

(And, BTW, is there some better way to extract unaligned bits from a
long bitstring?  (Again, I have no pressing need for the answer, I'm
just curious)).