Author |
Topic: What does the following code do???? (Read 885 times) |
|
johny_cage
Full Member
Gender: 
Posts: 155
|
 |
What does the following code do????
« on: Oct 23rd, 2007, 10:52am » |
 Quote  Modify
|
void duff(register char *to, register char *from, register int count)
{
register int 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);
}
}
Is the above valid C code? If so, what is it trying to acheive and why would anyone do something like the above?
|
| « Last Edit: Oct 23rd, 2007, 10:52am by johny_cage » |
 IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: What does the following code do????
« Reply #1 on: Oct 23rd, 2007, 11:15am » |
Quote Modify
|
It's Duff's Device and was used to perform a very fast copy operation in the days before optimizing compilers.
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
johny_cage
Full Member
Gender:
Posts: 155
|
|
Re: What does the following code do????
« Reply #2 on: Oct 23rd, 2007, 11:22am » |
Quote Modify
|
can u give us, example to show how it was used at that time ?
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: What does the following code do????
« Reply #3 on: Oct 23rd, 2007, 11:31am » |
Quote Modify
|
Just like you posted it. The function you posted copies count characters from the address pointed to by from to the address pointed to by to in an efficient manner. It uses the switch statement to copy the first count % 8 characters, then the do loop to copy in blocks of eight from there forward. By partially unrolling the loop, fewer branches are needed and the code runs faster. Modern compilers can automatically generate similar code from a simple loop.
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
johny_cage
Full Member
Gender:
Posts: 155
|
|
Re: What does the following code do????
« Reply #4 on: Oct 23rd, 2007, 1:05pm » |
Quote Modify
|
till now it is a bouncer for me. Please write a main function for this, so that i can understand how to call this...
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: What does the following code do????
« Reply #5 on: Oct 23rd, 2007, 1:14pm » |
Quote Modify
|
If you ignore the "register" bits:
int main()
{
char from[13] = {1,2,3,4,5,6,7,8,9,10,11,12,13};
char to[13]
duff(to, from, 13);
}
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: What does the following code do????
« Reply #6 on: Oct 23rd, 2007, 2:12pm » |
Quote Modify
|
on Oct 23rd, 2007, 1:05pm, johny_cage wrote:| till now it is a bouncer for me. Please write a main function for this, so that i can understand how to call this... |
|
Dude, it just copies characters from one string/array/memory location to another ... efficiently.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>
#include <time.h>
/* some data to copy */
const char * jabberwocky =
"'Twas brillig, and the slithy toves\n"
"Did gyre and gimble in the wabe:\n"
"All mimsy were the borogoves,\n"
"And the mome raths outgrabe.\n\n"
"\"Beware the Jabberwock, my son!\n"
"The jaws that bite, the claws that catch!\n"
"Beware the Jubjub bird, and shun\n"
"The frumious Bandersnatch!\"\n\n"
"He took his vorpal sword in hand:\n"
"Long time the manxome foe he sought--\n"
"So rested he by the Tumtum tree,\n"
"And stood awhile in thought.\n\n"
"And, as in uffish thought he stood,\n"
"The Jabberwock, with eyes of flame,\n"
"Came whiffling through the tulgey wood,\n"
"And burbled as it came!\n\n"
"One, two! One, two! And through and through\n"
"The vorpal blade went snicker-snack!\n"
"He left it dead, and with its head\n"
"He went galumphing back.\n\n"
"\"And hast thou slain the Jabberwock?\n"
"Come to my arms, my beamish boy!\n"
"O frabjous day! Callooh! Callay!\"\n"
"He chortled in his joy.\n\n"
"'Twas brillig, and the slithy toves\n"
"Did gyre and gimble in the wabe:\n"
"All mimsy were the borogoves,\n"
"And the mome raths outgrabe.\n\n";
/* a naive copy method */
void naive(char *to, const char *from, int count) {
int i;
for(i = 0; i < count; i++) {
to[i] = from[i];
}
}
/* an efficient copy method */
void duff(register char *to, register const char *from, register int count) {
register int 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);
}
}
/* copy some data using both methods and report timings */
int main(int argc, char *argv[]) {
char *dest;
int length, i, n;
time_t before, after;
/* check for correct usage */
if (argc != 2 || atoi(argv[1]) == 0) {
fprintf(stderr, "usage: %s n\n n: the number of times to copy\n\n", argv[0]);
return -1;
}
/* initialize variables */
length = strlen(jabberwocky) + 1;
dest = (char *)malloc(length);
n = atoi(argv[1]);
/* time the naive copy */
before = time(0);
for(i = 0; i < n; i++) {
naive(dest, jabberwocky, length);
}
after = time(0);
printf("Time to copy using naive method: %f seconds\n", difftime(after, before));
/* time the duff copy */
before = time(0);
for(i = 0; i < n; i++) {
duff(dest, jabberwocky, length);
}
after = time(0);
printf("Time to copy using Duff method: %f seconds\n", difftime(after, before));
return 0;
}
Running this on my computer gives:
D:\Personal\wwu>gcc -O0 duff.c -o duff
D:\Personal\wwu>duff 10000000
Time to copy using naive method: 42.000000 seconds
Time to copy using Duff method: 39.000000 seconds
So it's not even that much of an improvement in efficiency on modern hardware.
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
KWillets
Junior Member
Posts: 84
|
|
Re: What does the following code do????
« Reply #7 on: Oct 23rd, 2007, 4:51pm » |
Quote Modify
|
Just curious, try this:
case 0: do { to[0] = from[0];
case 7: to[1] = from[1];
...
case 1: to[7] = from[7];
to += 8; from += 8;
It's somewhat moot since char's are usually masked off from 32-64 bit words (IIRC) and are no longer simple operands, but an int version might show some differences. My guess above is that constant indices will allow the assignments to be ILP'ed.
|
|
IP Logged |
|
|
|
johny_cage
Full Member
Gender:
Posts: 155
|
|
Re: What does the following code do????
« Reply #8 on: Oct 24th, 2007, 2:40am » |
Quote Modify
|
Thanks SMQ for your wonderful program.
void duff(register char *to, register const char *from, register int count) {
register int 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);
}
}
Please explain me one thing, if length i.e. count is not a modulo of 8, then it will not going to enter into case 0, thus no do-while loop will going to execute. And all the other CASEs are count as LABEL in do-while loop not as an CASE of SWITCH. Then how it copies the data...
|
| « Last Edit: Oct 24th, 2007, 2:41am by johny_cage » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: What does the following code do????
« Reply #9 on: Oct 24th, 2007, 3:09am » |
Quote Modify
|
on Oct 24th, 2007, 2:40am, johny_cage wrote:| Please explain me one thing, if length i.e. count is not a modulo of 8, then it will not going to enter into case 0, thus no do-while loop will going to execute. |
|
Yes, it will, because you still encounter the while condition, which throws you back to do.
Quote:| And all the other CASEs are count as LABEL in do-while loop not as an CASE of SWITCH. |
|
No, they are still cases of the switch. You have to consider it in terms of how it translates, not in terms of the abstraction level you normally program on. You can freely mix the loop and the switch.
A rough sketch (from switch down; and I'm just guessing on how switch is actually implemented):
SWITCH_TABLE = {CASE_0, CASE_1, CASE_2, CASE_3, CASE_4, CASE_5, CASE_6, CASE_7};
GOTO SWITCH_TABLE[count %8]
CASE_0: DO_LBL: *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++;
IF (--n > 0) GOTO DO_LBL
|
| « Last Edit: Oct 24th, 2007, 3:13am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
johny_cage
Full Member
Gender:
Posts: 155
|
|
Re: What does the following code do????
« Reply #10 on: Oct 24th, 2007, 4:57am » |
Quote Modify
|
wow 
thats so nice of you towr....
thanks... now i got it right. 
|
|
IP Logged |
|
|
|
KWillets
Junior Member
Posts: 84
|
|
Re: What does the following code do????
« Reply #11 on: Oct 25th, 2007, 11:35am » |
Quote Modify
|
It's faster if the dependencies are removed:
void duff(register char *to, register const char *from, register int count) {
register int n = (count + 7) / 8;
register int incr = (count % 8 )||8;
switch (count % 8 ) {
case 0: do { to[7] = from[7];
case 7: to[6] = from[6];
case 6: to[5] = from[5];
case 5: to[4] = from[4];
case 4: to[3] = from[3];
case 3: to[2] = from[2];
case 2: to[1] = from[1];
case 1: to[0] = from[0];
to += incr; from += incr;
incr = 8;
} while (--n > 0);
}
}
$ ./duff 5000000
Time to copy using naive method: 21.000000 seconds
Time to copy using Duff method: 10.000000 seconds
|
| « Last Edit: Oct 25th, 2007, 11:36am by KWillets » |
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: What does the following code do????
« Reply #12 on: Oct 25th, 2007, 12:17pm » |
Quote Modify
|
True, but bear in mind that the "device" was originally written in 1983, on a VAX, and even then was more an implementation curiosity than a serious proposal for an optimized copy function. (For reference, here is Duff's take on it.) With modern architecture unrolling short loops is rarely profitable (the CPU's branch predictor removes much if not all of the overhead), and, as you note, there are better ways to optimize a copy. These days Duff's device is primarily noted for its 1) novelty, 2) compactness, and 3) ability to cause consternation. 
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
KWillets
Junior Member
Posts: 84
|
|
Re: What does the following code do????
« Reply #13 on: Oct 25th, 2007, 2:01pm » |
Quote Modify
|
It's a curiosity. It was interesting to see if it had any effect on newer processors.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: What does the following code do????
« Reply #14 on: Oct 26th, 2007, 2:20am » |
Quote Modify
|
On newer processors, you would probably want to take advantage of 32-bit or 64-bit transfers.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print