My Writings - Programming

Duff's Device

Last Updated (Tuesday, 30 November 1999 00:00) Saturday, 24 July 2004 23:09

Duff used this piece to speed up a loop that copied an array of shorts in a real time animation program that was running about half as slow as it should have.

Duff used this piece to speed up a loop that copied an array of shorts in a real time animation program that was running about half as slow as it should have. Initially, he used something like this

 
  	send(to, from, count)
	register short *to, *from;
	register count;
	{
		do
			*to = *from++;
		while(--count>0);
	}

To understand what he did next, you have to remember two important facts about the C language:

• First, that in the absence of a break the code "falls through" each of the case statements in a switch/case construct
• Second, that you can, by a proper arrangement of statements, step right into the middle of a do loop.

His implementation is something like this

	send(to, from, count)
	register short *to, *from;
	register count;
	{
		register n=(count+7)/8;
		switch(count%8)
		{
			/*Remember that the control will fall through*/
			case 0:	do{	*to = *from++; /*Note the start of the do loop*/
			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);
		}
	}
	

< Prev		Next >