473,734 Members | 2,567 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

Loop unrolling question. Does this make sense?

Hello,

I have sort of a newbie question. I'm trying to optimize a loop by
breaking it into two
passes.

Example:

for(i = 0; i < max; i++)
{
do this
and this
}

(The value of max is not known)

I want to change it to this:

for(i = 0; i < max /2; i++)
{
do this
and this
}
for(i = max /2; i < max; i++)
{
do this
and this
}
Does this make sense and will I get anything out of it?


Jul 19 '05 #1
5 5522
"John Edwards" <sa***@caselear ning.com> wrote...
I have sort of a newbie question. I'm trying to optimize a loop by
breaking it into two
passes.

Example:

for(i = 0; i < max; i++)
{
do this
and this
}

(The value of max is not known)

I want to change it to this:

for(i = 0; i < max /2; i++)
{
do this
and this
}
for(i = max /2; i < max; i++)
{
do this
and this
}
Does this make sense and will I get anything out of it?


No, you will not. You might be able to get something out of

if (max & 1)
{
do this
and this
}
for (i = 0; i < max/2; ++i)
{
do this
and this
do this
and this
}

Of course, if 'do this and this' uses 'i' somehow, it may not
be worth unrolling, since any arithmetic will chew up any time
you save by unrolling.

Victor
Jul 19 '05 #2
On Sun, 06 Jul 2003 20:06:24 GMT, John Edwards <sa***@caselear ning.com> wrote:
Hello,

I have sort of a newbie question. I'm trying to optimize a loop by
breaking it into two
passes.

Example:

for(i = 0; i < max; i++)
{
do this
and this
}

(The value of max is not known)

I want to change it to this:

for(i = 0; i < max /2; i++)
{
do this
and this
}
for(i = max /2; i < max; i++)
{
do this
and this
}
Does this make sense and will I get anything out of it?


Not really and it will run slower.

Loop unrolling looks like:

for(i=0;i<max;i +=2)
{
do this
and this
do this
and this
}

If i is more than just a loop counter, then the i+=2 might change to ++i
with a ++i inside the loop body as well.

Of course this will do awful things for an odd length max, and two instances
of the loop body isn't going to achieve much (especially when the check for
odd max overhead is added).

Don't even think of unrolling a loop until the loop has been shown to
actually be contributing to unsatisfactory performance. And then benchmark
before and after, since you can slow things down (by a lot if the code of
the body (and loop overhead) now doesn't fit in cache on architectures
which have such things - which I suspect is almost all architectures in
which you would be trading code space for code speed in that direction).

--
Sam Holden

Jul 19 '05 #3
"John Edwards" <sa***@caselear ning.com> wrote...
So what you're saying is that unless they are using 'i', it may not be worth it?
No, I said exactly the opposite.

'Do this & that' is actually doing writes for vector graphics.

"Victor Bazarov" <v.********@att Abi.com> wrote in message
news:vg******** ****@corp.super news.com...
"John Edwards" <sa***@caselear ning.com> wrote...
I have sort of a newbie question. I'm trying to optimize a loop by
breaking it into two
passes.

Example:

for(i = 0; i < max; i++)
{
do this
and this
}

(The value of max is not known)

I want to change it to this:

for(i = 0; i < max /2; i++)
{
do this
and this
}
for(i = max /2; i < max; i++)
{
do this
and this
}
Does this make sense and will I get anything out of it?


No, you will not. You might be able to get something out of

if (max & 1)
{
do this
and this
}
for (i = 0; i < max/2; ++i)
{
do this
and this
do this
and this
}

Of course, if 'do this and this' uses 'i' somehow, it may not
be worth unrolling, since any arithmetic will chew up any time
you save by unrolling.

Victor


Jul 19 '05 #4
John Edwards wrote:
Hello,

I have sort of a newbie question. I'm trying to optimize a loop by
breaking it into two
passes.

Example:

for(i = 0; i < max; i++)
{
do this
and this
}

(The value of max is not known)

I want to change it to this:

for(i = 0; i < max /2; i++)
{
do this
and this
}
for(i = max /2; i < max; i++)
{
do this
and this
}
Does this make sense and will I get anything out of it?


Unfortunately, you seem not to have a real understanding of what loop
unrolling is. May I refer you to the following link?

http://users.chariot.net.au/~matty/u...Unrolling.html

BTW -- your question is really not topical here (as, at its heart, it is
not a question about the C++ language).

Your compiler may have an optimization option to unroll loops (see your
documentation); in any event, micro-optimizations at the source code
level should only be performed if you have empirically determined (by,
e.g. profiling) that a particular piece of code is causing a bottleneck.

HTH,
--ag
--
Artie Gold -- Austin, Texas

----== Posted via Newsfeed.Com - Unlimited-Uncensored-Secure Usenet News==----
http://www.newsfeed.com The #1 Newsgroup Service in the World! >100,000 Newsgroups
---= 19 East/West-Coast Specialized Servers - Total Privacy via Encryption =---
Jul 19 '05 #5
John Edwards wrote:
Hello,

I have sort of a newbie question. I'm trying to optimize a loop by
breaking it into two
passes.

Example:

for(i = 0; i < max; i++)
{
do this
and this
}

(The value of max is not known)

I want to change it to this:

for(i = 0; i < max /2; i++)
{
do this
and this
}
for(i = max /2; i < max; i++)
{
do this
and this
}
Does this make sense and will I get anything out of it?


The standard technique of loop unrolling is to
repeat the statements inside the loop and adjusting
the counter; not to repeate the loops.

The goal is to divide the cost (overhead) of updating
and comparing the indices over the cost of the statements.
For example, repeating the inner block twice will reduce
the overhead cost by 1/2.

Be aware that the number of iterations must be evenly
divisible by the number of statement repetitions.

Guide to Optimization
---------------------
1. Don't. Get the program working correctly first.
2. Don't. Use a profiler and analyze the program execution.
The 80/20 rule states that 80% of the program's execution
occurs in 20% of the code.
3. Review function designs. A lot of execution gain can
be obtained at the design level. Remove unused functions,
operations, data and code. Simplify repetitive operations.
Don't process data unless required to do so (lazy processing).
4. Inline function calls for small sized functions. If the
content of the function is smaller or slightly larger than
the overhead of the function call, inline it.
5. Factor out constant expressions and statements from loops.
6. Review floating point operational costs. Some processors
choke on fp operations, some have no extra cost. If there
is a penalty (or additional cost) keep everything as integers
until the last moment.
7. Unroll loops, if you have the code space.
8. Replace function contents with assembly language. Write
the assembly language function to take advantage of any
special (helpful) processor features, such as pipelining
or caches.

--
Thomas Matthews

C++ newsgroup welcome message:
http://www.slack.net/~shiva/welcome.txt
C++ Faq: http://www.parashift.com/c++-faq-lite
C Faq: http://www.eskimo.com/~scs/c-faq/top.html
alt.comp.lang.l earn.c-c++ faq:
http://www.raos.demon.uk/acllc-c++/faq.html
Other sites:
http://www.josuttis.com -- C++ STL Library book

Jul 19 '05 #6

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

47
12264
by: Mountain Bikn' Guy | last post by:
Take some standard code such as shown below. It simply loops to add up a series of terms and it produces the correct result. // sum numbers with a loop public int DoSumLooping(int iterations) { int result = 0; for(int i = 1;i <=iterations;i++) { result += i;
22
2225
by: Jan Richter | last post by:
Hi there, the Code below shows DJBs own implementation of strlen (str_len): unsigned int str_len(char *s) { register char *t; t = s; for (;;) { if (!*t) return t - s; ++t;
16
3530
by: Claudio Grondi | last post by:
Sometimes it is known in advance, that the time spent in a loop will be in order of minutes or even hours, so it makes sense to optimize each element in the loop to make it run faster. One of instructions which can sure be optimized away is the check for the break condition, at least within the time where it is known that the loop will not reach it. Any idea how to write such a loop? e.g.
0
8946
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look ! Part I. Meaning of...
0
9449
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. Here is my compilation command: g++-12 -std=c++20 -Wnarrowing bit_field.cpp Here is the code in...
1
9236
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
0
8186
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own.... Now, this would greatly impact the work of software developers. The idea...
0
6031
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert into image. Globals.ThisAddIn.Application.ActiveDocument.Select();...
0
4809
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
1
3261
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
2
2724
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.
3
2180
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.