CODEWITHSUNDEEP
c++cperformancecachingoptimization
Michael
Michael

Reputation: 2867

Optimizing by transforming "goto" to branch

I have the following code (This is partially pseudo code for demonstration):

void foo(...){

  //some code here
  do{
     min_item = _MAX_VALUE;
     //some code here also


    if (min_item == _MAX_VALUE)
       break;

    if (smaller_item_x == min_item){
FIRST_IS_SMALLER:
       global_queue[size++] = smaller_item_x;    
       if (next_item_x!=0){
            smaller_item_x= next_item_x;
            if (smaller_item_x > smaller_item_y)
               goto SECOND_IS_SMALLER;
       }
    }else{
SECOND_IS_SMALLER:
       global_queue[size++] = smaller_item_y;    
       if (next_item_y!=0){
            smaller_item_y= next_item_y;
            if (smaller_item_y > smaller_item_x)
               goto FIRST_IS_SMALLER;
       }
    }
  }while(true)

As far as i know goto is translated to jmp in assembler, i am interested to increase performance of this procedure by changing the second goto to something similar to branch (shorter command with short jump up), i may be missing something, and it could be trivial, so my apologies.

Upvotes: 1

Views: 197

Answers (2)

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726849

This is probably not an answer that you were looking for, but it does not fit in a comment, so I pasted it here.

This piece of code should be equivalent to yours, but it does not have gotos, and it does not introduce additional indirection. There is an additional check and a switch on branchId, but the compiler should be able to optimize it into a single access, and perhaps even put it in a register.

int branchId = smaller_item_x == min_item;
while (branchId >= 0) {
    switch (branchId) {
    case 0:
        global_queue[size++] = smaller_item_y;    
        if (next_item_y != 0) {
            branchId = (smaller_item_y=next_item_y) > smaller_item_x ? 1 : -1;
        }
        break;
    case 1:
        global_queue[size++] = smaller_item_x;    
        if (next_item_x != 0) {
            branchId = (smaller_item_x=next_item_x) > smaller_item_y ? 0 : -1;
        }
        break;
    }
}

Upvotes: 1

Ned Batchelder
Ned Batchelder

Reputation: 375804

It is very difficult to second-guess C compilers these days. They often compile to assembler that is tighter than people would have coded directly. They also don't offer controls to programmers that direct their optimizations to this degree.

If you want this level of control, you will probably have to write in assembler, and chances are good that your code will be slower than the C compiler's.

Upvotes: 7

Related Questions