 |
|
05.20.10 Dissecting Duff's Device  By
Bryan YoungOne of the most confusing pieces of code I have ever had a chance to look at is Duff's Device. At first glance, it seems that your compiler would laugh at you for attempting such a feat. For those of you who haven't yet been introduced to this programming marvel, I suggest you sit down before reading on. send(to, from, count) register short *to, *from; register count; { register n=(count + 7)/8; switch(count % 8) { case 0: do { *to = *from++; case 7: *to = *from++; case 6: *to = *from++; case 5: *to = *from++; case 4: *to = *from++; case 3: *to = *from++; case 2: *to = *from++; case 1: *to = *from++; } while (--n >0); } } Okay, say it with me..."huh?" Believe it or not, this is actual, compile-able C code. But what does it do? Let us first look at the purpose for which it was written. According to Tom Duff, while working for Lucasfilm there was a need for a more efficient way to copy an array of data into registers. This is the code that was being used. send(to, from, count) register short *to, *from; register count; { do { *to = *from++; } while (--count >0); } This creates a bottleneck by forcing a comparison call for every register that is written to. In order to speed up the process, conventional coding calls for unwinding the loop a few times, meaning that for each iteration of the loop, there are eight copies for each comparison made. send(to, from, count) register short *to, *from; register count; { do { *to = *from++; *to = *from++; *to = *from++; *to = *from++; *to = *from++; *to = *from++; *to = *from++; *to = *from++; } while (--count >0); } Of course, the obvious problem with this is the case where the number of copies is not evenly divisible by eight. In order to fix this, you need a separate piece of code to handle the remainder of the copies, typically using a switch in this fashion. switch (count % 8) { case 7: *to = *from++; case 6: *to = *from++; case 5: *to = *from++; case 4: *to = *from++; case 3: *to = *from++; case 2: *to = *from++; case 1: *to = *from++; } This is of course follows the do-while loop described above. Duff simply took the loop and the switch and combined them, creating the single piece of code shown at the top of this article. The device, utilizing the fall-through property of the switch statement and the ability for C code to jump directly into the middle of a loop, boggles the mind while compiling and running flawlessly. For these reasons, Duff's Device goes down in the books as a staple for students who want to learn more about code optimization.
|
|
| ||
 |
|
-- CProgrammingTrends is an iEntry,
Inc. publication -- iEntry, Inc. 2549 Richmond Rd. Lexington KY, 40509 2010 iEntry, Inc. All Rights Reserved Privacy Policy Legal archives | advertising info | news headlines | free newsletters | comments/feedback | submit article |
