3

I am trying to understand better what causes a branch prediction to be calculated, and what does not.

Say for example I have an array which contains 1's and 0's. I want to loop through this array, and if it reads a 0 do something, but if it reads 1 do something else.

Using JavaScript it would look like this:

var array = [0, 1, 1, 1, 0, 0, 0];

for(i=0; i < array.length; i++){
    if(array[i] == 0){
        // Do The 0 Instruction

    }else{
        // Do The 1 Instruction

    }
}

I know that this will cause branch predictions to be made because the program won't know what steps it needs to take until it has read the data from the array.

However what if I pre-processed the array to combine the number of consecutive 1's or 0's into a single number. So for example the array would change to this:

var array = [0, 1, 1, 1, 0, 0, 0];
var condensedArray = [1, 3, 3];

Now instead of using if statements to branch my instructions, I can use loops like this:

var condensedArray = [1, 3, 3];

for(i=0; i < condensedArray.length; i+=2){

  for(j=0; j < condensedArray[i]; j++)
    //Do The 0 Instruction

  for(j=0; j < condensedArray[i+1]; j++)
    //Do The 1 Instruction

}

Does this still cause branch predictions to be calculated and missed? And if so is it at least more efficient that using an if statement to test every index of the original array?

Edit: In the comments I was asked how would I know if the array starts with a 0 or a 1? I left that out for simplicity and don't want to edit the code above to make it any longer, but I would have a single if statement at the start of the program that says if the array begins with 0 or 1. Then that single branch would put the loops in the correct order.

YAHsaves
  • 1,697
  • 12
  • 33
  • In first for Loop how do you it will be always 0 case lets consider this array [1,0,0,1,1] it will fail and second issue is that when i become 2 second for loop will throw exception ArrayindexOutOfException. – DHARMENDRA SINGH Jun 21 '18 at 03:32
  • @DHARMENDRASINGH I left that out of the question for simplicity but basically I would have a single if statement at the start of the program that says if the array starts with 0 or 1, then that single branch would put the following loops in order. Sorry I'll edit my answer to reflect this. – YAHsaves Jun 21 '18 at 03:34
  • 1
    I don't see the benefit of optimizing like this. Adding more branches will not improve performance. Sorting the data will definitely help, and that's basically what you're trying to do in the second example. However, sorting takes time so unless you're going to reuse the data then there's no point. – ffhighwind Jun 21 '18 at 03:42
  • @ffhighwind the sorting would be done before the client runs the program. This is a question of which array to give the client. And how does it add more branches? That's what I'm trying to figure out. – YAHsaves Jun 21 '18 at 03:45

1 Answers1

0

Benchmarking may tell if the CPU does branch prediction on such a code. As you create two loops whose exit conditions are fairly easy to predict, the CPU might be able to do branch prediction there.

Nowhere man
  • 5,007
  • 3
  • 28
  • 44