From: eirik@elf.TN.Cornell.EDU (Eirik Fuller)
Newsgroups: alt.hackers
Subject: fun with BitBlt
Date: 11 Sep 1992 06:27:58 GMT
Organization: Cornell Theory Center
NNTP-Posting-Host: localhost

Years ago, in another time zone, I was asked to participate in an
effort to speed up a user interface written in Smalltalk.  At the
meeting where it was decided who would attack what, the first item to
catch my attention was code that searched for data which matched
certain logical conditions.

My first question, after hearing some sketchy details, was "is the
data rectangular?"  I knew better than to phrase it that way; what I
really asked was whether each time slice had exactly the same amount
of information.  The answer, happily, was yes.  It was even word
aligned, more or less.

The data in question lived in multi-megabyte files; the searches only
actually scanned a couple hundred K or so, but even so that's a lot of
data for bit fiddling done in interpreted code, method lookup and all.
I didn't have to look very closely at the original code before
realizing it should be scrapped and replaced.  I did, however, spend
nearly a week's worth of spare time reading it, just to the get the
problem statement straight.

My mental model of the search space was a very tall rectangle.  The
width of the rectangle was the size of one time slice, and the height
was the number of time slices to search.  For practical reasons, I
sliced the tall rectangle into chunks of manageable height, and looped
over the slices.  Among other things, that meant if the data being
sought occurred early in the interval, lots of other data could be
completely ignored.

I was practically snickering to myself as I wrote the code; I pulled
out all of the stops.  The first thing I did was to use the bitmap of
the Form object in which I stored the data slice as the buffer for the
system call that read it from the file.  No point in reading the data
into the wrong place, only to have to copy it elsewhere ...

The next step was to massage this rectangular data into a form
suitable for searching.  Among other things, this involved masking out
those columns which were entirely irrelevant, and normalizing the
columns of interest so that I was always searching for the same thing.

One of the reasons for the appeal of Smalltalk is the glitzy bitmap
interface which has been part of its programming environment for more
than a decade.  The backbone of this interface is BitBlt, a class
whose copyBits primitive is (or, at least was, in days of slower CPUs)
essential for bearable graphical performance.  It's doubtful that
Smalltalk would ever have caught on if every pixel blitted on the
screen had yet another message send behind it.  Then again, perhaps
it's debatable whether Smalltalk ever caught on ...

But I digress.  The truth is, someone (probably at Xerox PARC) did an
excellent job of designing the innards of Smalltalk's display system.
I'm not sure whether they envisioned some of the demented potential
ways of using it.

One of the nice things about BitBlt is that it supports all 16 logical
functions of two input variables.  The and function zeroes out
irrelevant data, and the exclusive nor function, with a halftone of
the data value being sought, turns all occurrences of such data to all
ones (and all other data to something else).  The function which
echoes one of the inputs just copies one of the input forms.

So, after a small number of copyBits operations, each of them a single
call to a highly optimized primitive carefully crafted in assembly
language (at least in the Smalltalk implementation I was using then),
my rectangular read system call buffer was transformed into a
collection of normalized four bit values, intermingled with zeroed out
irrelevant four bit values.

Of course, since Smalltalk is a programming environment, much of what
it needs to display is text.  Displaying text in a bitmap interface is
just a whole lot of tiny copyBits operations; even if each one is
blindingly fast thanks to copyBits, that still leaves a lot of looping
overhead, for which bytecoded arithmetic is less than ideal.  Again,
to make Smalltalk's display performance bearable, another primitive
was necessary.  Enter CharacterScanner, a subclass of BitBlt.  A
single call to its main primitive would display an entire row of text.
Exit from that primitive required either a non-printing character
(like a backspace or a line feed), or bumping into the right margin.

This primitive had one argument that told whether or not to display.
An example of why this is necessary is for justified text.  A first
scan finds the last word to clear the right margin, and a second scan
stops at each space to advance some fraction of the leftover space.

Another argument to this primitive was an array of stop conditions.
For sane programmers, this array had non-nil elements for such things
as tab, back space, newline, escape character, etc.  For me, it had
whatever I felt inclined to put there.  In this particular case, it
had only three non-nil elements, at 11110000, 00001111, and 11111111.
Those are the three possible ways of finding all ones in a four bit
field when looking at a byte at a time.  Each had its own stop
condition which, if memory serves, I named #high, #low, and #both.
The last just called each of the other two.

Another argument listed the offset in the font glyphs; two adjacent
elements of this array could be subtracted to find the width of the
corresponding character.  My characters were all of width zero; this
meant I never hit the right margin while searching.

Each search for the data of interest consisted of one call to this
primitive, which returned either when interesting data triggered a
stop condition, or when the search ran off the end of the buffer.
The primitive raced past all of the boring data with considerable
speed, particularly since it bypassed its most interesting part, the
outer loop on copyBits.

I debugged this code by displaying the data in a window, and
refreshing that window after each call to copyBits.  Not only did I
visualize the data as rectangular, the debugging interface was able to
display it that way for me.

My first version of the code timed out at roughly 100x faster than the
original code.  Just to be obnoxious, I profiled it.  I was expecting
to see over 90% of the time spent in the graphical primitives (which,
in actual runtime, never displayed anything, the way I was using
them).  Not surprisingly, the profiling showed that practically all of
the time was being spent in the BitBlt and CharacterScanner
primitives, but I was a little puzzled to see how that split. I'd
expected to see more of the time spent searching, rather than masking
and normalizing.

Then it hit me.  In the particular data I was scanning, the irrelevant
data was on both ends of each time slice.  In fact, the relevant data
was contained in a vertical slice which was only about half the total
width.  I reordered the copyBits operations to first copy from the
read buffer into a narrower rectangle (keeping track of the left
offset for later, for when I found something), then fiddle with what
remained.  Since the runtime of copyBits operations is roughly
proportional to the area being copied (or otherwise mangled), that
meant I'd cut the remaining copyBit operations in half, in this case.
I guess my mistake in the original code was treating each call to
copyBits as one unit of time, rather than a variable unit of time.

In any case, that reordering of copyBits calls increased my speedup to
150x over the original code.  Not bad, 50% speedup for two minutes work.
As before, the profiling showed essentially zero time outside of the
invisible graphical primitives, but the balance between the two was
closer to what I'd expected.

Another possible search target was a pair of values in adjacent time
slices.  For that one, I used an additional copyBits call which copied
each value upward and sideways, into the other half of its byte.  The
xnor halftone was the pair of values being sought, and the only
non-nil stop condition was at 11111111.  I also had to see to it that
buffer boundaries were handled correctly; I did that by making sure
the first row of each buffer load was the same as the last row of the
prior one.  I don't remember for sure, but it seems as though I did
that with a backwards seek on the file.

It's possible that a future posting will explain how it came to pass
that all this was two weekend's work, rather than the six months it
might have taken a sane person.  It's less likely that any future
posting will address the issue of whether a sane person would ever
have considered doing anything like this ...

Why alt.hackers?  After writing that code, I was firmly convinced that
I'd done the right thing, but attempts to convince anyone else of that
invariably met with responses containing the word "hack".  I seem to
recall it was about that general time frame that people started
calling me Mr. Blt ...
Newsgroups: alt.hackers