wanted: information on Duff's Device -

[John R. Levine]

In article <1990Dec25.135417.27999 at news.cs.indiana.edu> you write:
>[a letter from Tom Duff in which he reports that he invented his device
>in 1983.]

I have personal knowledge of a previous, entirely independent invention of
this technique, unrolling a loop into a C switch statement, at Yale in 1977 or
1978.

In the early 1970's the Yale computer science department built the GEM system
one of the earlier bit-mapped graphics systems based on then state-of-the-art
2K RAMs that Intel had given us.  (Part of the appeal was that the fact that
the RAMs weren't very reliable didn't matter, the worst that would happen
would be a little screen bit rot.)  It had a total of 256K 16-bit words of
screen memory, 16K for each of 16 screens.  Each screen also had a keyboard
with a multiplexor feeding all the keystrokes back to the host.  The host
system was two loosely coupled computers, a PDP-11/45 which was the main
system, and a PDP-11/05 that ran the terminal emulator and handled the
keyboards.  Both hosts could map chunks of screen memory into their address
spaces, and there was a 12 bit wide serial link between them that looked
enough like a paper tape reader/punch to fool the boostrap ROMs.

Originally both machines ran homebrew code written in a homebrew language
called IMP11, a relative of Irons' IMP10 and IMP72.  In 1974-75 we decided to
ditch the local operating system on the 11/45 and switch to 5th edition Unix
which was already in use at Harvard and Princeton.  We still used the IMP11
terminal emulator, though.  In the 1975-76 academic year, I was working for
the department maintaining the Gem system, and one of the things that I did
was to rewrite the terminal emulator from scratch in C, saving only the
character bitmaps from the IMP11 code.  Even though the 11/05 only implemented
a subset of the 11/45's instruction set, I used the regular Ritchie PDP-11 C
compiler, having discovered that it was fairly easy to write code so that the
C compiler didn't generate any of the instructions that the 11/05 didn't have.
(It mainly lacked multiply and divide.)

The new C terminal emulator was about twice as fast as the IMP11 version,
partly because it was a lot simpler, having no task switcher but instead
processing each character to completion as it arrived from the host, and
partly because the C compiler had a better code generator.  It processed about
700 characters per second, which seemed pretty fast at the time, and I went on
to add lots of bells and whistles such as multiple character sets, area
scrolls, and an "editor mode" for our local full-screen editor, a cousin of
the Rand editor, that did all the simple character processing in the 11/05,
only waking up the editor program on the 11/45 when it needed to do something
non-trivial.  This made the system load from the full screen editor comparable
to that from "ed" which was important when we were trying to time-share ten
students on a poor little 11/45.

The following year, 1977-78, I became a graduate student and Gem management
was taken over by John Mostenan, an undergraduate, supervised Bob Tuttle, a
former grad student who was the facility manager, and had been my boss, too.
One of the things they did was to speed up my emulator not by any fundamental
changes but by careful recoding and tuning, trading size for speed since the
emulator came nowhere near filling the 24K words available to it on the 11/05.
For example, they went from line by line scrolling to jump scrolling, and from
a block to a line cursor.

Another thing they did was to use what is now known as Duff's device to unroll
the code for arbitrary area scrolls.  I think I had unrolled full-screen
scrolls where I knew in advance that the screen was 72 characters and hence 36
words wide, but had the usual tight loop for other scrolls.  By unrolling the
area scrolls into switches they greatly increased scrolling speed.  When they
were done, their emulator was twice as fast as mine, a very noticable
improvement.

For various not very good reasons, the entire Gem project went almost entirely
undocumented.  Yale's CS department was very late to get on the Arpanet or any
other network, and there was little incentive to publish anything other than
one's thesis.  I wrote a short overview as a departmental tech report in 1979
which appeared as an article in Software Practice and Experience in 1982.  As
far as I can tell, no other publications or theses resulted from it, though
there was considerable good work.  (We used xor-mode drawing all over the
place from the beginning but thought it was so obvious that we never published
anything about it, to my later regret.)

The last notable thing that happened on the Gem system was that I used its
11/45 as a host to port 4BSD to the Vax 11/750 at Yale about the same time as
Bill Joy was doing the same thing at Berkeley on an 11/780.  (The 11/750 had a
lot of microcode bugs that made the 11/780 code fail, most notably one that
broke the inner loop in printf().  The Vax assembler code for printf probably
still has Joy's comment "comet sucks" where he patched around it.)  In about
1984, after I had left, all of the Gem listings and a lot of its hardware went
into a dumpster when the department was running out of space.)

I have no reason to doubt that Tom Duff did independently invent the
unrolling technique in 1983, and he deserves considerable credit for bringing
it to the attention of the C community.  But I wouldn't be surprised to hear
that it had been invented and lost several more times between the dawn of C
in about 1970 and Duff's invention in 1983.

Regards,
John Levine, johnl at iecc.cambridge.ma.us, {spdcc|ima|world}!iecc!johnl