wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> What does the following code do????
        
(Message started by: johny_cage on Oct 23rd, 2007, 10:52am)
Title: What does the following code do????
Post by johny_cage on Oct 23rd, 2007, 10:52am
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?
Title: Re: What does the following code do????
Post by SMQ on Oct 23rd, 2007, 11:15am
It's Duff's Device (http://en.wikipedia.org/wiki/Duff%27s_device) and was used to perform a very fast copy operation in the days before optimizing compilers.

--SMQ
Title: Re: What does the following code do????
Post by johny_cage on Oct 23rd, 2007, 11:22am
can u give us, example to show how it was used at that time????
Title: Re: What does the following code do????
Post by SMQ on Oct 23rd, 2007, 11:31am
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
Title: Re: What does the following code do????
Post by johny_cage on Oct 23rd, 2007, 1:05pm
till now it is a bouncer for me. Please write a main function for this, so that i can understand how to call this...
Title: Re: What does the following code do????
Post by towr on Oct 23rd, 2007, 1:14pm
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);
}
Title: Re: What does the following code do????
Post by SMQ on Oct 23rd, 2007, 2:12pm

on 10/23/07 at 13:05:23, 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
Title: Re: What does the following code do????
Post by KWillets on Oct 23rd, 2007, 4:51pm
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.  
Title: Re: What does the following code do????
Post by johny_cage on Oct 24th, 2007, 2:40am
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...??? ???
Title: Re: What does the following code do????
Post by towr on Oct 24th, 2007, 3:09am

on 10/24/07 at 02:40:58, 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
Title: Re: What does the following code do????
Post by johny_cage on Oct 24th, 2007, 4:57am
wow :o
thats so nice of you towr....
thanks... now i got it right.  :)
Title: Re: What does the following code do????
Post by KWillets on Oct 25th, 2007, 11:35am
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
Title: Re: What does the following code do????
Post by SMQ on Oct 25th, 2007, 12:17pm
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 (http://www.lysator.liu.se/c/duffs-device.html).)  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
Title: Re: What does the following code do????
Post by KWillets on Oct 25th, 2007, 2:01pm
It's a curiosity.  It was interesting to see if it had any effect on newer processors.  
Title: Re: What does the following code do????
Post by Grimbal on Oct 26th, 2007, 2:20am
On newer processors, you would probably want to take advantage of 32-bit or 64-bit transfers.


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board