« Previous entry | Next entry » Browse > Snippets
Skip to comments (6)
D-loop - optimizing loops containing conditional branches
Posted by Erik on Jan 07 2006 @ 12:07 :: 2619 unique visits
first a little about conditional branches
When a processor encounters a conditional test, it tries to guess its outcome and execute the rest of the instructions accordingly. All this is done before actually knowing the results of the test. This mechanism is called branch prediction. It enables the processor to execute the program as if there were no tests, and this eliminates any pipeline stall that might occur when the processor waits for the result of a test. But the processor can guess wrong, in which case it has to undo every instruction executed after the test. To achieve this, the processor removes all the instructions and intermediate results from its pipeline and jumps back to the test before resuming the execution. This process is very expensive because modern processors have lots of stages in their pipelines (AMD Athlon 64 has 12 stages, Intel Pentium 4 Northwood 20 and the Intel Pentium 4 Prescott 31)
D-loop
Double Loop or D-Loop is a technique to reduces the average number of conditional branches inside a loop.
A simple example function which counts the numer of occurences of a character in a string:
CODE: C
int charcount(char *str, char ch) {
int c = 0;
while (*str != 0) {
if (*str == ch) {
c++;
}
str++;
}
return c;
}
int c = 0;
while (*str != 0) {
if (*str == ch) {
c++;
}
str++;
}
return c;
}
For each character in the string it's doing two conditional tests. The first test is executed to know whether the end of the string has been reached. The second test is performed within the loop to check whether the current character has to be count. The 0 character indicates the end of the string and is unlikely to be encountered during most iterations. This is where the D-loop pattern improves the loop.
A D-loop optimized version of the above function.
CODE: C
int charcount(char *str, char ch) {
char mask[256];
int c = 0;
memset(mask, 0, 256);
mask[(unsigned char)ch] = 1;
mask[0] = 1;
while (*str != 0) {
while (mask[(unsigned char)*str] == 0) {
str++;
}
if (*str == 0) {
break;
} else {
c++;
}
str++;
}
return c;
}
char mask[256];
int c = 0;
memset(mask, 0, 256);
mask[(unsigned char)ch] = 1;
mask[0] = 1;
while (*str != 0) {
while (mask[(unsigned char)*str] == 0) {
str++;
}
if (*str == 0) {
break;
} else {
c++;
}
str++;
}
return c;
}
As you can see, the single loop from the previous implementation has been split
in two parts. A global loop and an inner loop. The global loop checks whether the end of the string was reached, either at the beginning of the function, or when the inner loop has stopped. The inner loop runs through the string, discarding most of the characters, and stops whenever a character may be important. In this case, either the character is ch or the 0 character. The idea is that most characters will be skipped in the inner loop using only one conditional test.
Note that for small string the D-loop will be slower because of the memset. D-loop will also be slower if the number of occurrences of ch in the string increases.
6 comments posted so far
Add your own »
2. On Jan 12 2006 @ 20:43 another_guest wrote:
Far Better method is remove unnecessary branchs.CODE: C
int charcount(unsigned char *str, unsigned char ch) {
int mask[256];
memset(mask, 0, sizeof(int)*256);
while (*str!=0){ mask[*str++]++; }
return mask[ch];
}
int mask[256];
memset(mask, 0, sizeof(int)*256);
while (*str!=0){ mask[*str++]++; }
return mask[ch];
}
3. On Jan 12 2006 @ 22:05 Erik wrote:
cool, yes for charcount that's even faster :D4. On May 31 2006 @ 14:26 guest wrote:
Hi,the best thing to do is to read the PDF that describe the d-loop pattern technique.
The article describing that technique.
http://www.onversity.net/cgi-bin/progarti/art_aff.cgi?Eudo=bgteob&P=a0404
Direct link to the pdf
http://www.onversity.com/load/d-loop.pdf
Le count_char function is just an easy and fast way to the 'how to use d-loop'. In that pdf you will find an important part explaining the math behind D-loop. With that math you would be able to use D-loop pattern in more cases.
Best regards : Maquiné Jean-François
5. On Jul 14 2009 @ 07:32 guest wrote:
AVI to DVD Converter,AVI to DVD Creator,iPhone Ringtone Maker for Mac,AVI Converter OS X,VOB Converter OS X,AVCHD Video Converter,FLV Converter,PowerPoint Converter,AVCHD Converter,Blue-Ray ripper,Rip Blue Ray,FLV to MOV Mac,VOB to DVD,HD Video Converter,iPod Playlist Transfer6. On Jan 05 2010 @ 14:28 uggbaileybutton wrote:
bailey button uggs-ugg boots cheap
ugg boots uk
ugg classic
1. On Jan 07 2006 @ 15:30 guest wrote:
That's really fascinating!