0

I'm looking for the fastest and most elegant way to perform a following action:


const bool condition1;

(...)

if (condition1)
{
  // add an expression to a loop below
}

while (condition2)
{
  (...)
  // expression to be executed if condition1 = true
}

I could of course check the condition on every iteration of the loop, but condition1 is constant so it wouldn't be the most efficient way.

Thanks in advance!

6
  • I would be surprised if on modern multi-Ghz CPU you will be able to tell any difference from any reasonable approach. As far as "elegant" goes, that's purely an opinion, and, unfortunately, opinion-based answers are not appropriate for Stackoverflow.com Feb 5, 2021 at 13:40
  • Your condition1 check is outside the loop.
    – MikeCAT
    Feb 5, 2021 at 13:41
  • @MikeCAT Yes, I think that is the point of the question....
    – Yunnosch
    Feb 5, 2021 at 13:41
  • 2
    Is condition1 value known at compilation time?
    – Damien
    Feb 5, 2021 at 13:43
  • 2
    Please clarfiy whether condition1 is really const as in your code (for that it lacks init...). It might be pseudo const, i.e. not really const but at least guaranteed not to change during the loop. The answers are interestingly different for those two cases. If you fundamentally change the question (e.g. asking about the interesting differences) the polite thing is to agree with authors of already existing answers, or create a new separate question.
    – Yunnosch
    Feb 5, 2021 at 13:45

3 Answers 3

3

Just put the branch in the loop like

while (condition2)
{
    if (condition1)
    {
      // run expression in the loop
    }
}

CPU's have a branch predictor and if your "branch" never branches because of a constant condition, then the predictor will figure that out and you'll never actually branch in your codes execution.

6
  • An optimizing compiler may also turn this inside and create two independent copies of the loop if it can determine that condition1 is invariant with respect to the loop, at least when told not to care about code size.
    – Johan
    Feb 5, 2021 at 13:45
  • I get it, won't there be some kind of a performance drop due to repeated checking of condition1, if we assume, for example, that the while loop in question executes up to 500k times?
    – user15039632
    Feb 5, 2021 at 13:47
  • @yuriko-ushikawa if the condition is const there is no need to check it more than once, and the compiler knows that Feb 5, 2021 at 13:48
  • @yuriko-ushikawa That's what the branch predictor is for. It'll figure out you don't actually branch, so it'll stop checking the condition. Feb 5, 2021 at 13:48
  • @largest_prime_is_463035818 I think that's exactly what I needed to know. Thanks a million!
    – user15039632
    Feb 5, 2021 at 13:58
2

Often you can rely on your compiler's optimizer to solve this problem for you. But not always.

So the first step is, write simple code, profile it, and see if your code is already fast enough; if the bottleneck is elsewhere, stop optimizing. Optimization effort is fungible; if can be spent on making the important code faster, and until you profile you don't know what is important.

Then use high-yield optimization techniques, like enabling vectorization, parallelizing, and using someone else's library. That can earn you 2, 30 or even 3000x speedups for really low effort. (We just swapped a manual bit of pixel fiddling with using a library with ~50 lines changed, and identical input/output went from 2 seconds to 50 ms, a 40x speedup. The pixel fiddling wasn't bad, it was just not good)

Eventually work down to what I am going to show you next; I would only go this far for stuff like per-frame per-pixel operations, code you want to run on the order of 50 million times per second or more.

auto loop=[&](auto condition1){
  while(condition2){
    // code
    if(condition1){
      // code
    }
  }
};
if(condition1){
  loop(std::integral_constsnt<bool,true>{});
} else {
  loop(std::integral_constsnt<bool,false>{});
}

what I just did was force the branch to be pre-calculated.

The trick here is that the auto condition1 variable is an integral constant, a stateless variable with a constexpr operstor bool. This gets every compiler to dead code eliminate the unreachable branch, sometimes even in debug mode.

We can then profile this against the raw version:

loop(condition1);

easily. (If you cannot profile the speed difference, you shouldn't be doing this.)

You can also use non type template parameters; a classic way to make per-pixel operation code clean and DRY and efficient is to hoist things like "is premultiplied" or "entirely opaque" to template parameter bools.

3
  • That's just for what I made advertising in my comment to eeroikas answer... :-) Feb 5, 2021 at 14:49
  • Thank for the tip, right after I finished with the basic functionality of my program, I'll have a go at profiling performance. The code is actually a raw renderer project without external 3D libraries, so performance is definetely going to be a major factor there.
    – user15039632
    Feb 5, 2021 at 15:43
  • @yiriko then if that condition isn't checked every pixel of every frame don't do anything like I suggest above. Feb 5, 2021 at 16:50
1

If you want to be sure that there is no branch in the code, you can use a template:

template<bool condition1>
void foo()
{
    while (condition2)
    {
        (...)
        if constexpr (condition1)
        {
          // run expression in the loop
        }
    }

}

// in the original function
if (condition1)
{
    foo<true>();
} else
{
    foo<false>();
}

Or, you can do this:

void loopBody()
{
    (...)
}


// in the original function
if (condition1)
{
    while (condition2)
    {
        loopBody();
        // expression to be executed if condition1 = true
    }
} else
{
    while (condition2)
    {
        loopBody();
    }
}

Also consider whether order of the expressions matter. If the order doesn't matter, then it may be simpler (and possibly more efficient) to have separate loops:

while (condition2)
{
    (...)
}

if (condition1)
{
    while (similar_condition)
    {
        // expression to be executed if condition1 = true
    }
}
4
  • I once had such an issue and solved it with a template to prevent the code duplication. Can be seen here: NoGLDemo: RenderContext::rasterize() (and how it is called: call of RenderContext::rasterize()) and the description of this: Optimization Attempts. Feb 5, 2021 at 14:36
  • @Scheff I'm not sure if it's exactly the same that you were suggesting, but I added a template example.
    – eerorika
    Feb 5, 2021 at 14:43
  • You got me right. ;-) (I gave my example because there were concerns whether such an optimization is justified. I'm really sure that in my case (with multiple conditions) it is.) Feb 5, 2021 at 14:44
  • @Scheff Ha! The code I'm working on is excatly a renderer without 3D libraries. The context of my question basically considers reading .obj files and rendering wireframes. I found out that the sizes (i.e., max. vertex coordinates) can vary greatly between different files available online so I'm implementing a kind of resizing function, which normalizes max. coordinates to 1 before drawing. Hence, condition1 in the snippet I posted is actually "check if the object is already normalized" and if not, then transform coordinates in the draw() loop.
    – user15039632
    Feb 5, 2021 at 15:37