|
|
|
|
|
by vitus
717 days ago
|
|
There are some other good explanations in the other comments, but I suspect you might want a balance between more detail and the deluge of information in the wikipedia page for loop unrolling. You might first write something like memcpy as: void memcpy(char* from, char* to, int n) {
if (n == 0) return;
do {
*from++ = *to++;
} while (n-- > 0);
}
(Yes, this is oversimplified, and also you'd probably have size_t instead of int as the type for n, but it's simplified for explanatory purposes.)Consider that the loop boils down to something like: loop:
*from++ = *to++;
if (n-- > 0) goto loop;
Each iteration of the loop corresponds to a single memory write and a single check of the loop condition (branches are generally expensive). If you unuroll your loop once, you might write something: int iterations = n / 2;
if (n % 2 == 1) {
*from++ = *to++;
n--;
}
do {
*from++ = *to++;
*from++ = *to++;
} while (iterations-- > 0);
This gets you two memory writes for a single check of the loop condition! That said, since you're advancing by two bytes each time, you need to handle the case where you have an odd number of overall bytes to copy.You can pretty easily show that this code is equivalent to: int iterations = n / 2;
if (n % 2 == 1) {
goto one;
}
do {
*from++ = *to++;
one:
*from++ = *to++;
} while (iterations-- > 0);
which in turn is not that far from Duff's device with 2x-loop unrolling: int iterations = n / 2;
switch (n % 2) {
case 0: do { *from++ = *to++;
case 1: *from++ = *to++;
} while (iterations-- > 0);
}
(The core observation here is that ifs, switches, whiles, and other conditional constructs are all conditional jumps under the hood.) |
|