Loop Un Rolling
root
purposes.
But the code has to target a variety of plat forms.
So I can't use compiler specific directives to force an un rolling.
My question is what is a good way to HINT to a compiler by the very
structure of the code that a loop should be un rolled in such a way that
many compilers will understand this hint.
Thanks.
/root
--
Learn more or lose your rights!
http://www.guncontrolkills.com/
http://www.gunbanobama.com/
Learn more or lose your rights!
Ben Pfaff
> Hi I have a loop in C/C++ that I want to be un rolled for efficiency
> purposes.
>
> But the code has to target a variety of plat forms.
>
> So I can't use compiler specific directives to force an un rolling.
>
> My question is what is a good way to HINT to a compiler by the very
> structure of the code that a loop should be un rolled in such a way that
> many compilers will understand this hint.
Why don't you just unroll the loop yourself, by e.g. repeating
code or using a macro?
--
Ben Pfaff
http://benpfaff.org
root
This would not be acceptable to me as it would make the code too messy to
be readable.
The loop may have thousands of iterations.
/root
--
Learn more or lose your rights!
http://www.guncontrolkills.com/
http://www.gunbanobama.com/
Learn more or lose your rights!
Sam
> Hi I have a loop in C/C++ that I want to be un rolled for efficiency
> purposes.
>
> But the code has to target a variety of plat forms.
>
> So I can't use compiler specific directives to force an un rolling.
>
> My question is what is a good way to HINT to a compiler by the very
> structure of the code that a loop should be un rolled in such a way that
> many compilers will understand this hint.
By reading the compiler's documentation, which hopefully explains what you
need to do, if it's possible at all.
There is no universal magical incantation one can utter, and have every C++
compiler in the world unroll your loops, upon demand. This is a
compiler-specific subject.
Ben Pfaff
root <ro...@localhost.localdomain> writes:
> Ben Pfaff writes:
>> root <ro...@localhost.localdomain> writes:
>>
>>> Hi I have a loop in C/C++ that I want to be un rolled for efficiency
>>> purposes.
>>>
>>> But the code has to target a variety of plat forms.
>>>
>>> So I can't use compiler specific directives to force an un rolling.
>>>
>>> My question is what is a good way to HINT to a compiler by the very
>>> structure of the code that a loop should be un rolled in such a way
>>> that many compilers will understand this hint.
>>
>> Why don't you just unroll the loop yourself, by e.g. repeating code or
>> using a macro?
>
> be readable.
>
> The loop may have thousands of iterations.
I really doubt that unrolling a loop thousands of times will have
performance benefits.
Paavo Helde
> Hi I have a loop in C/C++ that I want to be un rolled for efficiency
> purposes.
>
> But the code has to target a variety of plat forms.
>
> So I can't use compiler specific directives to force an un rolling.
>
> My question is what is a good way to HINT to a compiler by the very
> structure of the code that a loop should be un rolled in such a way that
> many compilers will understand this hint.
Duff's device?
hth
Paavo
Daniel Pitts
> Hi I have a loop in C/C++ that I want to be un rolled for efficiency
> purposes.
>
> But the code has to target a variety of plat forms.
>
> So I can't use compiler specific directives to force an un rolling.
>
> My question is what is a good way to HINT to a compiler by the very
> structure of the code that a loop should be un rolled in such a way that
> many compilers will understand this hint.
Forcing unrolling (or any "optimization") is likely to cause inefficient
binaries. Smaller caches, and other situations, can negate any
performance gained from unrolled loops. It is better to let the
compiler decide whether to unroll or not.
Alf P. Steinbach
> Hi I have a loop in C/C++
There is no such hybrid language (wrong).
So from the outset, you're saying that you don't know what you're talking about.
This is also indicated by cross-posting to [comp.lang.c] and [comp.lang.c++]
(wrong), and by not posting any of the relevant code (wrong).
> that I want to be un rolled for efficiency
> purposes.
>
> But the code has to target a variety of plat forms.
>
> So I can't use compiler specific directives to force an un rolling.
>
> My question is what is a good way to HINT to a compiler
Telepathy may be even better. Just think very very hard what you want compiler
to do. Sometimes appears to work! :-)
However, in C++ you can use the Boost preprocessor macros to help repeat code.
Check out Duff's device for the code you'd want the macros to generate. Since
the preprocessor is largely the same in C and C++ there is a possibility but no
guarantee that you can also use those macros in C.
However, unrolling a loop at the source code level may have the opposite effect
of what you want.
> by the very
> structure of the code that a loop should be un rolled in such a way that
> many compilers will understand this hint.
Most inefficiency is of the algorithmic kind.
That's where you get most return on your optimization effort.
Cheers & hth.,
- Alf
Moi
> Ben
>
> This would not be acceptable to me as it would make the code too messy
> to be readable.
>
> The loop may have thousands of iterations.
Yes. if it had only one iteration, it would not be a loop.
For examples of macroization, you could look at GNU's libc
string function implementation.
You can easily conclude from that that it will take a lot
of time (probably 10-100 hours per LOC)
IMHO the rules of thumb for (loop-)optimization:
1) avoid "fat" loops. Don't do too much in one loop.
2) avoid (conditional) jumps
3) try to deal with register- or cache- line aligned chunks
of data as much as possible.
BTW: show us the loop.
HTH,
AvK
bartc
"root" <ro...@localhost.localdomain> wrote in message
news:he20cl$538$1...@aioe.org...
> Ben
>
> This would not be acceptable to me as it would make the code too messy to
> be readable.
>
> The loop may have thousands of iterations.
You don't need to unroll the loop completely. If the loop executes 1000
times, then unrolling one iteration means the loop only needs to execute 500
times:
for (i=0; i<1000; ++i) {
<yourcode>
}
for (i=0; i<500; ++i) {
<yourcode>
<yourcode>
}
Or are you saying the body of the loop is complex? In that case loop
overheads may not be significant.
--
Bartc
White Wolf
Maybe. Most probably not. He did not say *anything* about what the
loop does. Duff's device is not loop unrolling, and Duff's devices is a
very specific idiom applicable in a very specific case: copying a lot of
bytes to hardware that can only efficiently copy words, while using a
compiler does doesn't do Duff's device on its own as an optimization
(gcc does, AFAIK).
To the OP:
1.) Follow Michael Jackson's rules of optimization
2.) Chances are high that the most stupid compiler optimizer is still
better at loop unrolling than you will ever be. Not because you are
stupid, but because those guys writing the compilers have 25 years of
head start on you.
3.) So to reword rule #1 and #2 from the Jackson rules: Don't sweat it.
BR, WW
Hamiral
> But the code has to target a variety of plat forms.
It's nearly impossible to unroll a loop efficiently for a variety of
platforms, because they can have a lot of differences regarding cache etc.
The best optimization IMHO would be to trust your compiler and to have
an efficient algorithm.
Ham
root
Perhaps you are confused about what loop un rolling does.
The efficiency is because of avoided jumps. It is the size of the loop
body not the number of iter ations that determine if loop un rolling is
beneficial.
In this case the loop body is very short.
Also if the number of iterations is a compile time constant but defined
in a complicated way then your method will not work.
/root
--
Learn more or lose your rights!
http://www.guncontrolkills.com/
http://www.gunbanobama.com/
Learn more or lose your rights!
Ben Pfaff writes:
Keith Thompson
[...]
> 2.) Chances are high that the most stupid compiler optimizer is still
> better at loop unrolling than you will ever be. Not because you are
> stupid, but because those guys writing the compilers have 25 years of
> head start on you.
And because the compiler can do a tremendous amount of analysis
*every time* you compile your code, and can redo all the same
analysis from scratch when you change a single line and recompile.
--
Keith Thompson (The_Other_Keith) ks...@mib.org <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
Richard Harter
<ro...@localhost.localdomain> wrote:
>Hi I have a loop in C/C++ that I want to be un rolled for efficiency
>purposes.
>
>But the code has to target a variety of plat forms.
>
>So I can't use compiler specific directives to force an un rolling.
>
>My question is what is a good way to HINT to a compiler by the very
>structure of the code that a loop should be un rolled in such a way that
>many compilers will understand this hint.
>
>Thanks.
>
>/root
Unless your compiler is really klutzy it is best to let the
compiler do the loop unrolling. I gather that you understand
that.
In my experience the best thing to do is to simplify your loop
logic so that the termination condition is crystal clear and the
number of cycles is fixed. Remember that the only thing you save
by unrolling the loop is the time spent on the loop logic.
Basically, if you can't convert the loop into a simple countdown
loop then there isn't any point in worrying about unrolling.
Richard Harter, c...@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Infinity is one of those things that keep philosophers busy when they
could be more profitably spending their time weeding their garden.
Seebs
> Perhaps you are confused about what loop un rolling does.
This seems exceedingly unlikely.
> The efficiency is because of avoided jumps. It is the size of the loop
> body not the number of iter ations that determine if loop un rolling is
> beneficial.
Both are factors.
In practice, most modern compilers are better at loop unrolling than
most people.
-s
--
Copyright 2009, all wrongs reversed. Peter Seebach / usenet...@seebs.net
http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
Willem
) Perhaps you are confused about what loop un rolling does.
There is no reason to try to be patronizing.
) The efficiency is because of avoided jumps. It is the size of the loop
) body not the number of iter ations that determine if loop un rolling is
) beneficial.
The *in*efficiency is because of caching issues. Jumps are almost free on
any reasonably modern CPU, as opposed to having to read new instructions
from memory all the time.
What platform are you targeting where you believe loop unrolling will be
beneficial ?
SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
Seebs
> The *in*efficiency is because of caching issues. Jumps are almost free on
> any reasonably modern CPU, as opposed to having to read new instructions
> from memory all the time.
For an obvious counterexample, some non-OOO chips pay a HUGE penalty for
jumps. Especially unpredicted or mispredicted jumps. I seem to recall that,
on the Cell SPEs, the cost of reading instructions (if you hint them suitably)
is fairly low, the cost of a predicted branch is several instructions'
worth of time, and the cost of an unpredicted branch is more than twenty
instructions' worth. So, on that particular chip, jumps are also extremely
expensive -- comparable in cost to the cost of needing to request data.
(Unless you need to obtain it from main memory -- the SPEs primarily work
with a local store which is essentially Fast Enough, and no distinct
"cache".)
Both caching and jumps are significant issues. If you unroll a loop hugely,
you can suffer from caching -- you have too much code and it's not sticking
in the cache. If you don't unroll it much at all, the branch can be pretty
expensive.
Look at the recent example someone gave of tweaking a PRNG by replacing
a conditional operation with calculating both sides and multiplying them
by truth values -- it dramatically improved performance, to such an extent
that it was a very measurable improvement in the performance of the whole
thing.
Ben Pfaff
> The efficiency is because of avoided jumps. It is the size of the loop
> body not the number of iter ations that determine if loop un rolling is
> beneficial.
>
> In this case the loop body is very short.
Unrolling the loop thousands of times, regardless of its length,
is unlikely to be beneficial. Even if it is only a single
instruction, thousands of copies of that instruction will
probably not fit in your CPU cache or, if they do, then they will
evict other instructions from it, which will cause a high cost
for other code and possibly cause it to be a net loss.
> Also if the number of iterations is a compile time constant but defined
> in a complicated way then your method will not work.
Then you need a switch statement. See Duff's Device (in an
obsolete form of C, from Wikipedia):
send(to, from, count)
register short *to, *from;
register count;
{
register 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);
}
}
--
char a[]="\n .CJacehknorstu";int putchar(int);int main(void){unsigned long b[]
={0x67dffdff,0x9aa9aa6a,0xa77ffda9,0x7da6aa6a,0xa67f6aaa,0xaa9aa9f6,0x11f6},*p
=b,i=24;for(;p+=!*p;*p/=4)switch(0[p]&3)case 0:{return 0;for(p--;i--;i--)case+
2:{i++;if(i)break;else default:continue;if(0)case 1:putchar(a[i&15]);break;}}}
Willem
) Look at the recent example someone gave of tweaking a PRNG by replacing
) a conditional operation with calculating both sides and multiplying them
) by truth values -- it dramatically improved performance, to such an extent
) that it was a very measurable improvement in the performance of the whole
) thing.
That was because the branches were essentially unpredictable.
The branch in this loop is effectively 99.9% predictable.
So we're basically only looking at the cost of predicted branches.
However, if the OP is worried about chips where predicted branches cost
more than memory access, *and* memory is cheap (otherwise massively
unrolling would be a non-issue) I would be interested to know.
PS: I think most compilers are smart enough to unroll a loop until it
*just* fits into the cache. Although that would be a very minor speedup,
and it might even be that more of the speedup comes from potential parallel
execution of instructions than from dropping the branches.
Scott Fluhrer
"Willem" <wil...@stack.nl> wrote in message
news:slrnhgb6am....@turtle.stack.nl...
>
> PS: I think most compilers are smart enough to unroll a loop until it
> *just* fits into the cache.
So that when that loop executes, all the other code is flushed from the
cache? I'm sorry, but that would be rude. I would hope that the compiler
would be smart enough not to microoptimize one particular loop at the
expense of overall program performance.
--
poncho
White Wolf
> White Wolf <wo...@freemail.hu> writes:
> [...]
>> 2.) Chances are high that the most stupid compiler optimizer is still
>> better at loop unrolling than you will ever be. Not because you are
>> stupid, but because those guys writing the compilers have 25 years of
>> head start on you.
> [...]
>
> And because the compiler can do a tremendous amount of analysis
> *every time* you compile your code, and can redo all the same
> analysis from scratch when you change a single line and recompile.
Yep. :-) The good old assembler versus C debate. :-)
BR, WW
Walter Banks
Paavo Helde wrote:
> Duff's device?
There might be a general case for Duff's device that
could eliminate a lot of conditional checking.
The power of Duff's device is to do a a single
check in such a way that periodic checks are needed
less frequently.
The core of Duff's algorithm might even be able
to be implemented in macro's with some reasonable
assumptions and produce significant execution
improvements.
Regards,
Walter Banks
root
That's good advice, thanks.
I always try to give the compiler hints for optimization ie by using
register variables. It can make all the difference in a tight inner loop.
/root
--
Learn more or lose your rights!
http://www.guncontrolkills.com/
http://www.gunbanobama.com/
Learn more or lose your rights!
Keith Thompson
> I always try to give the compiler hints for optimization ie by using
> register variables. It can make all the difference in a tight inner loop.
Please don't top-post. See:
http://www.caliburn.nl/topposting.html
http://www.cpax.org.uk/prg/writings/topposting.php
The common wisdom these days is that the compiler can usually do
a better job of register allocation than you can, and that the
"register" keyword isn't likely to help much; in fact, it may
hinder optimization.
If you're finding that the "register" keyword actually improves
performance measurably, perhaps the common wisdom is sometimes wrong.
(You're telling your compiler to use its maximum optimization level,
right?)
Noob
> Remember that the only thing you save by unrolling the loop is the
> time spent on the loop logic.
This statement is not universally true.
Interleaving several iterations may "hide" some latency.
Consider e.g a naive memcpy:
for (i=0; i < N; ++i)
{
temp = src[i];
dst[i] = temp; /* STALL WAITING FOR src[i] */
}
Unroll the loop 4 times.
for (i=0; i < N; i += 4)
{
temp0 = src[i+0];
temp1 = src[i+1];
temp2 = src[i+2];
temp3 = src[i+3];
dst[i+0] = temp0;
dst[i+1] = temp1;
dst[i+2] = temp2;
dst[i+3] = temp3;
}
Depending on the size of the Icache, the latency of memory loads, etc,
the unrolled version may perform much better.
At this point, comp.arch would be more appropriate.
To the original poster, Wikipedia is a good reference.
http://en.wikipedia.org/wiki/Loop_unwinding
http://en.wikipedia.org/wiki/Software_pipelining
Andy Champ
<snip>
> Depending on the size of the Icache, the latency of memory loads, etc,
> the unrolled version may perform much better.
>
I'd never write a memcpy, because I assume that the compiler / RTL
writer has optimised that basic function for the specific architecture.
On Intel, for example, you use REP MOVS...
> At this point, comp.arch would be more appropriate.
>
I'll shut up then!
Andy