0

I give the following example to illustrate my question:

 bool bSign;
 // bSign will be set depending on some criteria, which is omitted here.
 // b[][][] is a float array, which is initialized in the program  
 for(int i=0; i<1000; i++)
     for(int j=0; j<10000; j++)
         for(int k=0; k<10000; k++)
             if(bSign)
                 a[i][j][k] = (b[i][j][k]>500);
             else
                 a[i][j][k] = (b[i][j][k]<500);

In the above codes, I have to rely on bSign to design the kind of operator (> or <) I should use to set the output variable a. However, I found it costly as it is done within a long for loop. Any ideas on how I can escape that?

Ohad Eytan
  • 8,114
  • 1
  • 22
  • 31
feelfree
  • 11,175
  • 20
  • 96
  • 167
  • I don't see how operator overloading is supposed to get rid of the branch. – Baum mit Augen Aug 12 '16 at 09:10
  • 1) you can not change the language. Overloading the operator for int is simple impossible. 2) the value of bSign is only known during run time. How should operator overloading work, because this takes place during compile time. – Klaus Aug 12 '16 at 09:11
  • @CinCout: `a` is, presumably, a `bool[1000][10000][10000]`. – Lightness Races in Orbit Aug 12 '16 at 09:11
  • `b` is a `float` array, not `a`. My bad. – CinCout Aug 12 '16 at 09:12
  • If bsign is set before the loop then branch prediction may save you anyway. However you could assign a function pointer before the loop, with that pointer either pointing at a less than function or a greater than. – James Elderfield Aug 12 '16 at 09:18
  • Have you determined that the test actually is costly, for instance by comparing to a loop that always does `a[i][j][k] = (b[i][j][k]>500);`? I would expect the CPU to be able to predict that branch pretty well. – molbdnilo Aug 12 '16 at 09:22
  • 1
    A decent optimising compiler will notice that bSign is a loop invariant and remove it from the innermost loop. – gnasher729 Aug 12 '16 at 09:24
  • 1
    And I'd love a machine where this code actually runs, with at least 500 Gigabyte of memory. On my home computer, if I added a bigger hard drive, this would take forever to run because of loading / writing virtual memory from / to disk. – gnasher729 Aug 12 '16 at 09:24

6 Answers6

3

Your compiler should be able to optimise this out if it knows bSign won't change during the loop. Making it const would help.

If for some reason that's not happening, you could move the if (bSign) out to surround the entire set of nested loops. (Basically, doing manually what you're hoping the compiler will do for you.)

Beyond that, you're relying on branch prediction (whose success will depend on the nature of your data).

Operator overloading, though, has absolutely nothing to do with it.

Really, though, this kind of iteration is just not going to be efficient. Can't you find a better algorithm?

Lightness Races in Orbit
  • 378,754
  • 76
  • 643
  • 1,055
  • Just thought the same thing, if the values in this huge matrix matrix can change during runtime, I belive it would be better to store the boolean during change, and not "all at once" – Najzero Aug 12 '16 at 09:20
1

As many people said, it is better to move if statement out of loops (if it is possible). To prevent code duplication, you can use function pointers, but it may be worse if there will be real calls. Calls cost more than simple if. If compiler can inline them, it will be ok.

You also can use templates metaprogramming (simple template algorithm in this case) on this manner:

 template<typename ComparatorT>
 void doTheWork(float ***a, const float ***b, ComparatorT comparator)
 {
     for(int i=0; i<1000; i++)
         for(int j=0; j<10000; j++)
             for(int k=0; k<10000; k++)
                 a[i][j][k] = comparator(b[i][j][k], 500);
 }

 ...
 // Usage.
 bool bSign;
 ...
 if (bSign) {
     doTheWork(a, b, std::greater<float>());
 } else {
     doTheWork(a, b, std::larger<float>());
 }

Compiler can inline comparator's calls (it is much easier than with function pointers) and it will work almost like you wrote two different loops. The comparator object can be really created, but usually it is not significant. One disadvantage is that it often produces hard-to-read code.

ilotXXI
  • 1,075
  • 7
  • 9
0

Can you just move the check out of the loop?

if (bSign)
    for(int i=0; i<1000; i++)
        for(int j=0; j<10000; j++)
            for(int k=0; k<10000; k++)
                a[i][j][k] = (b[i][j][k]>500);
else
    for(int i=0; i<1000; i++)
        for(int j=0; j<10000; j++)
            for(int k=0; k<10000; k++)
                a[i][j][k] = (b[i][j][k]<500);
Wiki Wang
  • 668
  • 6
  • 23
0

I think that you can't get rid of such ifs in your program. But you can help processor to run your program faster. Consider sorting b array (or copy & sort if you can't change b). This should help to predict branches by processor. Of course make some benchmarks to be sure that won't be worse than your current code.

stryku
  • 722
  • 5
  • 12
0

I'm not sure if this is any faster (you'd have to do a perfomance check) but you could avoid all the if statements using a function pointer.

int comparisonValue = 500;
auto greater = [comparisonValue](float val) {
    return val > comparisonValue;
};
auto lesser = [comparisonValue](float val) {
    return val < comparisonValue;
};

bool bSign;
// bSign will be set depending on some criteria, which is omitted here.
// b[][][] is a float array, which is initialized in the program  
decltype(greater)* funcPtr;

if(bSign) {
    funcPtr = &greater;
} else {
    funcPtr = &lesser;
}


for(int i=0; i<1000; i++)
    for(int j=0; j<10000; j++)
        for(int k=0; k<10000; k++)
            a[i][j][k] = (*funcPtr)(b[i][j][k]);
James Elderfield
  • 2,389
  • 1
  • 34
  • 39
0

Why don't you use it like that?;

  a[i][j][k] = (bSign == (b[i][j][k] > 500)) && (b[i][j][k] != 500);
Yusuf R. Karagöz
  • 589
  • 8
  • 22