Tuesday, May 01, 2007

Duff's Device

This is a neat little trick for copying data containers that I don't see mentioned nearly as often in modern-day forums as in old Usenet posts. Whether this is because most STL implementations now include some similar contraption or because it's been superseded by fancier things is unclear, but I thought I'd publish it here in any case.

Quoting Wikipedia, "Duff's Device is an optimized implementation of a serial copy that uses a technique widely applied in assembly language for loop unwinding". Basically, a standard for-loop copy, e.g.
*to++ = *from++;
can be unrolled to minimize the amount of branches by using a while loop nested into a switch-statement:
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++;
Many sources, including Wikipedia, claim that Duff's Device is a waste of optimization time and that sticking to library routines is always better. Others claim it has its uses though, albeit not as a general replacement to memcpy or std::copy. To quote Tom Duff himself, "If your code is too slow, you must make it faster. If no better algorithm is available, you must trim cycles."

No comments:

Post a Comment