Open-Source Internship opportunity by OpenGenus for programmers. Apply now.
In this article, we will discuss about duff device in C++ with help of example. This is an optimization technique related to Loop Unrolling.
Duff's device is a method for manually performing loop unrolling in the C or C++ programming languages that avoids the need for additional code to handle the remaining partial loop with help of do-while loop, and switch statement.
befor moving lets underatand what is loop unrolling?
Loop Unrolling
Loop unrolling is a technique in which reduce the number of loop controls by manually unrolling the loop data.
The "Duff's Device" is a combination of a switch statement and a while loop that replicates memory contents from one source to the other destination.
You can accomplish it as follows:
send(src, desc, count)
register short *src, *desc;
register count;
{
do
{
*src = *desc++;
} while (--count > 0);
}
The basic concept behind Duff's device in C and C++ is to run multiple computations in the same loop and only evaluate one of them rather than each one individually.
Advanatge
- Increase Excution Speed
Disadvantge
- Extra memory require as code become large .
Example 1:
Without Uisng Duff device :
void execute_loop(int & data, const size_t loop_size)
{
for (int i = 0 ; i < loop_size ; ++i)
{
computation(data);
}
}
Now, let's look at how duff devices function in C++. Consider a loop that prints N data points.
Uisng Duff device :
void execute_loop(int & data, const size_t loop_size)
{
for (int i = 0 ; i < loop_size/4 ; ++i)
{
computation(data);
computation(data);
computation(data);
computation(data);
}
}
In this example, the function makes the incorrect number of calls to computation, if loop size is not a multiple of 4 or any given specific number. ().
To rectify this problem, Duff’s device uses the C switch and while statement.
We may solve the issue of performing the incorrect number of calculations when loop size is not a multiple of 4 or any other particular number by using this Duff device.
You can accomplish it as follows:
void execute_loop(int & data, const size_t loop_size)
{
size_t i = 0;
switch(loop_size%4)
{
do{
case 0: computation(data);
case 3: computation(data);
case 2: computation(data);
case 1: computation(data);
++i;
} while (i < (loop_size+3)/4);
}
}
Here, when a user enters a loop, a condition is checked and a switch case is executed.
The do while() loop is encountered after the falling case, and the program then returns to the do statement to resume the loop.
Lets take an another example :
Example 2 :
Without Duff device in C++
//Without Duff's Device example in C++
//inlcude header files
#include<stdio.h>
#include<string.h>
#include <stdlib.h>
// Copies memory content source to destination array
void copyBoolArray(bool src[], bool dest[],int count)
{
int n = count / 8;
int i = 0;
switch (count % 8)
{
do
{
case 0:
dest[i] = src[i];
i = i + 1;
case 7:
dest[i] = src[i];
i = i + 1;
case 6:
dest[i] = src[i];
i = i + 1;
case 5:
dest[i] = src[i];
i = i + 1;
case 4:
dest[i] = src[i];
i = i + 1;
case 3:
dest[i] = src[i];
i = i + 1;
case 2:
dest[i] = src[i];
i = i + 1;
case 1:
dest[i] = src[i];
i = i + 1;
n=n-1;
}while (!(n == 0));
}
}
// main code
int main()
{
int count = 20;
bool dest[count], src[count];
int i;
for (i=0; i< count; i++)
//rand() generate a series of random numbers and assign to source
src[i] = rand()%2;
copyBoolArray(src, dest, count);
for (i=0; i< count; i++)
//print result
printf("src=%d\tdesc=%d\n", src[i], dest[i]);
}
Output :
src=1 desc=1
src=0 desc=0
src=1 desc=1
src=1 desc=1
src=1 desc=1
src=1 desc=1
src=0 desc=0
src=0 desc=0
src=1 desc=1
src=1 desc=1
src=0 desc=0
src=1 desc=1
src=0 desc=0
src=1 desc=0
src=1 desc=0
src=0 desc=0
Duff's Device example in C++
//Duff's Device example in C++
//inlcude header files
#include<stdio.h>
#include<string.h>
#include <stdlib.h>
// Copies memory content source to destination array
void copyBoolArray(bool src[], bool dest[],int count)
{
int n = count / 8;
int i = 0;
switch (count % 8)
{
case 0:
while (!(n == 0))
{
n = n - 1;
dest[i] = src[i];
i = i + 1;
case 7:
dest[i] = src[i];
i = i + 1;
case 6:
dest[i] = src[i];
i = i + 1;
case 5:
dest[i] = src[i];
i = i + 1;
case 4:
dest[i] = src[i];
i = i + 1;
case 3:
dest[i] = src[i];
i = i + 1;
case 2:
dest[i] = src[i];
i = i + 1;
case 1:
dest[i] = src[i];
i = i + 1;
};
}
}
// main code
int main()
{
int count = 20;
bool dest[count], src[count];
int i;
for (i=0; i< count; i++)
//rand() generate a series of random numbers and assign to source
src[i] = rand()%2;
copyBoolArray(src, dest, count);
for (i=0; i< count; i++)
//print result
printf("src=%d\tdesc=%d\n", src[i], dest[i]);
}
Ouput :
src=1 desc=1
src=0 desc=0
src=1 desc=1
src=1 desc=1
src=1 desc=1
src=1 desc=1
src=0 desc=0
src=0 desc=0
src=1 desc=1
src=1 desc=1
src=0 desc=0
src=1 desc=1
src=0 desc=0
src=1 desc=1
src=1 desc=1
src=0 desc=0
src=0 desc=0
src=0 desc=0
src=0 desc=0
src=0 desc=0
Explanation
When a user enters a loop in this program, a condition is verified and a switch case is executed.It checks for the case label before proceeding to the next assignment statemen. as the the while loop is contained inside the switch expression, execution goes to the bottom of the loop, where it returns to the top. The switch is no longer re-evaluated. The loop then proceeds to copy data from the source to the destination, and the result gets andand result gets printed.
