Optimising "conditional" while loop
Author Message
Optimising "conditional" while loop

Hi all,

Below is a rather common general optimization problem, but I think
there might be more sophisticated methods to deal with it other than
those which I know of. All suggestions are welcome!

Problem:
--------
i)  There is a while loop which will be iterated many times ("hot
spot") and needs to be optimised.
ii)  The executing code within the while loop differs, depending on a
boolean condition.
iii) 3 possible (and common?) solutions are presented below, but each
has its own drawbacks:
1) superflous comparison statements
2) duplicate code

Possible solutions:
------------------
METHOD 1:
if(artist)
{
while(alive)
{
Sleep();
Wakeup();
BreakFast();
{
... A chunk of artist code ...
}
}

Quote:
}

else
{
while(alive)
{
Sleep();
Wakeup();
BreakFast();
{
... A chunk of non-artist code ...
}
}

Quote:
}

METHOD 2:
while(alive)
{
Sleep();
Wakeup();
BreakFast();
if(artist)
{
{
... A chunk of artist code ...
}
}
else
{
{
... A chunk of non-artist code ...
}
}

Quote:
}

METHOD 3:
// DoWork is a pointer to a function
// DoArt() = {  ... A chunk of artist code ...  };
// DoRatRace() = {  ... A chunk of non-artist code ...  };

if(artist)
{
DoWork = &DoArt;

Quote:
}

else
{
DoWork = &DoRatRace;

Quote:
}

while(alive)
{
Sleep();
Wakeup();
BreakFast();
DoWork();

Quote:
}

Comparison of the above approaches:
----------------------------------
Method 1:
GOOD: No IF statement within while loop

Method 2:
GOOD: No duplicate code

Method 3:
GOOD: No duplicate code

Questions:
----------
A) Is there a method to achieve the common objective of the above
pseudo-code, and satisfies all 3 criteria below?:
1) Does not involve code duplication
2) Incurrs zero/minimal function call overhead

B) In method 3, is it possible to modify DoWork() during runtime (this
will be a Windows app), so that this particular section of the
executing code within the loop just needs to be changed once? While
"compromise" is a keyword in engineering solutions, I think B) might
offer a solution which removes all 3 defiencies of the eariler
approaches. Is it possible to implement, if (even if?) the code is to
run on Windows?

peace
mangotree
--

Mon, 21 Mar 2005 08:13:50 GMT
Optimising "conditional" while loop
Quote:

> Hi all,

> Below is a rather common general optimization problem, but I think
> there might be more sophisticated methods to deal with it other than
> those which I know of. All suggestions are welcome!

Your code to be optimized looks like this:

while (alive) {
Sleep();
Wakeup();
Breakfast();
if (artist) { .... }
else {....}

Quote:
}

You are assuming that the compiler will test the "if" condition each
time through the loop.  A smart compiler won't, especially if you can
ensure that the compiler can determine that artist's value won't change
(which means don't pass a pointer to artist out of the function, and/or
possibly declare it const).  Such an optimization is called hoisting.
The only way to be sure is to examine your compiler's output.

Also, I notice that you are cross posting this to comp.lang.c++.  You
can use templates in C++-land to optimize this sort of thing.

-Peter

[...]

Mon, 21 Mar 2005 10:09:19 GMT
Optimising "conditional" while loop

Quote:
> Hi all,

> Below is a rather common general optimization problem, but I think
> there might be more sophisticated methods to deal with it other than
> those which I know of. All suggestions are welcome!

> Problem:
> --------
> i)  There is a while loop which will be iterated many times ("hot
> spot") and needs to be optimised.
> ii)  The executing code within the while loop differs, depending on a
> boolean condition.
> iii) 3 possible (and common?) solutions are presented below, but each
> has its own drawbacks:
>    1) superflous comparison statements
>    2) duplicate code

> Possible solutions:
> ------------------
> METHOD 1:
> if(artist)
> {
>  while(alive)
>  {
>   Sleep();
>   Wakeup();
>   BreakFast();
>   {
>    ... A chunk of artist code ...
>   }
>  }
> }
> else
> {
>  while(alive)
>  {
>   Sleep();
>   Wakeup();
>   BreakFast();
>   {
>    ... A chunk of non-artist code ...
>   }
>  }
> }

> METHOD 2:
> while(alive)
> {
>  Sleep();
>  Wakeup();
>  BreakFast();
>  if(artist)
>  {
>   {
>    ... A chunk of artist code ...
>   }
>  }
>  else
>  {
>   {
>    ... A chunk of non-artist code ...
>   }
>  }
> }

> METHOD 3:
> // DoWork is a pointer to a function
> // DoArt() = {  ... A chunk of artist code ...  };
> // DoRatRace() = {  ... A chunk of non-artist code ...  };

> if(artist)
> {
>  DoWork = &DoArt;
> }
> else
> {
>  DoWork = &DoRatRace;
> }

> while(alive)
> {
>  Sleep();
>  Wakeup();
>  BreakFast();
>  DoWork();
> }

> Comparison of the above approaches:
> ----------------------------------
> Method 1:
> GOOD: No IF statement within while loop

> Method 2:
> GOOD: No duplicate code

> Method 3:
> GOOD: No duplicate code

In my opinion, it's not just important to make efficient code, it's also
important to make maintainable code which has a good overall design.  I
think Method 1 is just ugly due to the duplicate code.

Method 2 is my personal pick.  It has the cleanest look and doesn't have
much overhead.  Yes, it has some overhead for the conditional checks, but
really these checks do not take that many instructions to complete.  I'm not
familiar with every processor's assembly code, but on the ones I have worked
with, this comparison would only take three instructions.  There would be
one instruction to move the data (the artist boolean) into a register (which
would only need to be done once outside of the loop) and then two
instructoins to check its value and to branch to a piece of code based on
the comparison.

Method 3 is a nice design...the code looks nice, but it does have overhead
for the function call, which is more significant than the comparison
overhead in Method 2.  But depending upon how much code is in the "chunk of
artist code" and "chunk of non-artist code", it might be better to have it
in a function.  For readability purposes, you shouldn't have too much code
stuffed into one function.  So it might make more sense to split it out into
separate functions.

Quote:
> Questions:
> ----------
> A) Is there a method to achieve the common objective of the above
> pseudo-code, and satisfies all 3 criteria below?:
>   1) Does not involve code duplication
>   2) Incurrs zero/minimal function call overhead
>   3) Incurrs zero/minimal comparison overhead

I think Method 2 does this, except for the comparison overhead, which I
really don't think is a big deal.

Quote:
> B) In method 3, is it possible to modify DoWork() during runtime (this
> will be a Windows app), so that this particular section of the
> executing code within the loop just needs to be changed once? While
> "compromise" is a keyword in engineering solutions, I think B) might
> offer a solution which removes all 3 defiencies of the eariler
> approaches. Is it possible to implement, if (even if?) the code is to
> run on Windows?

I'm really not sure what you're asking here.  Maybe somebody else can field
this one...

Dan

Mon, 21 Mar 2005 10:19:06 GMT
Optimising "conditional" while loop

Quote:

> A) Is there a method to achieve the common objective of the above
> pseudo-code, and satisfies all 3 criteria below?:
>   1) Does not involve code duplication
>   2) Incurrs zero/minimal function call overhead 3) Incurrs zero/minimal

This may be a very uncool solution, but using the preprocessor might help.
Just put the common part in a #define and your 1) problem is solved while
you can keep the code as in your first solution. I tend to avoid the
preprocessor whenever possible, but there are cases where it really works :)

Regards, Daniel
--

Wed, 23 Mar 2005 06:00:29 GMT
Optimising "conditional" while loop

Quote:

> Hi all,

> Below is a rather common general optimization problem, but I think
> there might be more sophisticated methods to deal with it other than
> those which I know of. All suggestions are welcome!

[SNIP]
1. If you want to be fast eliminate Sleep.
2. If you want to be really fast you'd also skip Wakeup and BreakFast.
[Sorry I could not resist ;-]

Now serious.
In general the execution time depends heavily on your processor (and the
For example, modern processors will execute code very fast as long as
your code and data resides in level 1 cache. A cache miss will be far
more expensive than a compare or a function call. Because you mention
your program has to run on Windows this (a modern CPU, e.g.
Pentium/Athlon/..) will be likely the case. Furthermore, time used by
Windows functions may be far more than that of your code.
Hence, I think it's best to write your code in a way that's best to
understand/maintain and not really worry about these (micro)performance
issues.

And if you really can't resist, some things you may think about:
- avoid code with unnecessary computational complexity, i.e. focus on efficient
- avoid excessive copying of medium/large data structures (the copying
consumes time by itself and it may kill your cache performance [assuming
a cache based CPU]).

PS: the above is not related to the C/C++, but to CPUs and possibly the
efficiency of the compiler being used.

Rob Windgassen
--

Wed, 23 Mar 2005 06:01:43 GMT
Optimising "conditional" while loop

Quote:

> Hi all,

> Below is a rather common general optimization problem, but I think
> there might be more sophisticated methods to deal with it other than
> those which I know of. All suggestions are welcome!

> Problem:
> --------
> i)  There is a while loop which will be iterated many times ("hot
> spot") and needs to be optimised.
> ii)  The executing code within the while loop differs, depending on a
> boolean condition.
> iii) 3 possible (and common?) solutions are presented below, but each
> has its own drawbacks:
>    1) superflous comparison statements
>    2) duplicate code

You can eliminate the boolean conditional check by maintaining
seperate containers (of poointers) for each possible state.  When the
state changes, remove/add a pointer to it in/from the appro.
list/arrays.
--

Thu, 24 Mar 2005 09:56:09 GMT
Optimising "conditional" while loop

Quote:
> Hi all,

> Below is a rather common general optimization problem, but I think
> there might be more sophisticated methods to deal with it other than
> those which I know of. All suggestions are welcome!

> Problem:
> --------
> i)  There is a while loop which will be iterated many times ("hot
> spot") and needs to be optimised.
> ii)  The executing code within the while loop differs, depending on a
> boolean condition.
> iii) 3 possible (and common?) solutions are presented below, but each
> has its own drawbacks:
>    1) superflous comparison statements
>    2) duplicate code

Since you are using functions for the common tasks without worrying about
specific tasks is not an excessive concern.

DoWork[0] = DoRatRace;
DoWork[1] = DoArt;

while(alive)
{
Sleep();
Wakeup();
BreakFast();
(DoWork[artist])();

Quote:
}

Now, I've only used pointers to functions once - and that was well over a
decade ago - and so I am really guessing at how you would invoke a
particular function from an array of pointers to functions based on how you
presented it here except I don't think you want the "&" that you had before
the function names since the names ARE pointers to the functions IIRC.
Hopefully the idea is clear and someone else can illustrate how you actually
do it.

As far as the tradeoffs and compromises go, the key to deciding which one is
"best" is completely tied up in what your measure of "best" needs to be.
Ease of implementation? Ease of maintainability? Size of program? Amount of
memory needed? Speed? Robustness? Not to mention lots of others.

Depending on the application, you might be willing to take substantial hits
in nearly all of the above in exchange for marginal improvements in one.
--

Fri, 25 Mar 2005 01:22:35 GMT
Optimising "conditional" while loop
Quote:

> Hi all,

> Below is a rather common general optimization problem, but I think
> there might be more sophisticated methods to deal with it other than
> those which I know of. All suggestions are welcome!

ship

Optimizations depend rather strong on the spezific combination of code/compiler/processor.
Therefore my suggestions are general:

1.) Profile your code. I'm rather sure the results surprise you.
2.) Look at the compiler's assembler code.
3.) Optimization: Don't do it.
For experts ony: Don't do it now.

--
Udo
--

Fri, 25 Mar 2005 09:09:52 GMT
Optimising "conditional" while loop
If you post more specific details you may get better pointers to
information.

Generally you can look into better data structures/algorithms, as the
previous poster suggested. There are lots of good books on sorting,
searching. Sometimes it can be as simple as not using strlen() or other time
linear functions.

If you are calling the OS in your loop you may look into changing the API,
for example use completion ports on win32.

If numerical computations are involed you can partially unroll the loop,
this eliminates some of tests.

You may be able to pre-compute some of the data used in the loop or you may
be able to postpone some of the calculations until after the loop is done.

In other limited cases you may be able to move to assembly language. Or
maybe you can just throw more hardware to the problem.

As I said before, better details about the problem will give you better
information.

Take care,

Marius Seritan

Quote:
> > Hi all,

> > Below is a rather common general optimization problem, but I think
> > there might be more sophisticated methods to deal with it other than
> > those which I know of. All suggestions are welcome!

> > Problem:
> > --------
> > i)  There is a while loop which will be iterated many times ("hot
> > spot") and needs to be optimised.
> > ii)  The executing code within the while loop differs, depending on a
> > boolean condition.
> > iii) 3 possible (and common?) solutions are presented below, but each
> > has its own drawbacks:
> >    1) superflous comparison statements
> >    2) duplicate code
> >    3) function call overhead

> You can eliminate the boolean conditional check by maintaining
> seperate containers (of poointers) for each possible state.  When the
> state changes, remove/add a pointer to it in/from the appro.
> list/arrays.
> --

--

Fri, 25 Mar 2005 09:09:49 GMT

 Page 1 of 1 [ 9 post ]

Relevant Pages