Re: Does Duff Device break C compilers

> > On the other hand, wouldn't be surprised if the resulting code wasn't
> > that great. Why? It makes an irreducible loop ...


Yep. Tom Duff was hand-optimizing for a particular machine and a particular
compiler when he originally wrote it, one where it did work.


> > Better is to rewrite it, like this
> >
> > /* no assumptions made about count */
> > for (n = 0; n < count; n++)
> > to[n] = from[n];
> >
> > which is correct, obvious, maintainable, parallelizable, vectorizable,
> > software pipelinable, and in all other ways superior.


In all other ways superior except that it *does the wrong thing*!
The correct translation is


for (n = 0; n < count; n++)
*to = from[n];


because "to" was pointing to an output register, specifically "the Pro-
grammed IO data register of an Evans & Sutherland Picture System II".
Note that this also means that the loop really has to be executed serially!


> Better yet...
>
> memcpy(from, to, count*(sizeof *from));


Worse yet -- it cannot be trivially corrected as the "for" version can.
If we were talking about a block copy, THEN memcpy() or memmove() would
of course generally be best.


> [Oh, right. Duh. It was still a great hack on the PDP-11. -John]


Tom was working on a VAX, actually. The *to = *from++ compiled to
a single instruction.


For greater clarity: Tom wrote in 1988 "I do not claim to have invented
loop unrolling, merely this particular expression of it in C." And it
was in 1983 that he did it.


--
Mark Brader
msb@sq.com
SoftQuad Inc., Toronto


My text in this article is in the public domain.


--

Return to the comp.compilers page.
Search the comp.compilers archives again.