Optimizing for branches

Order by frequency

Rearrange nested branches so that frequently taken branches are evaluated first, so that the number of branches taken dynamically is reduced. Thus, replace the sequences

	if( usually_true )
	  if( usually_false ) /* both branches generally evaluated */

      	if( usually_true &&
	    usually_false ) /* both branches generally evaluated */

	if( usually_false ||
	    usually_true ) /* both branches generally evaluated */

with the sequences

	if( usually_false ) /* usually don't fall through to second branch */
	  if( usually_true )

	if( usually_false &&
	    usually_true ) /* in false case, only one branch evaluated */

	if( usually_true ||
	    usually_false ) /* in true case, only one branch evaluated */

Group branches

Sometime a large number of conditionals have to be evaluated, but most of the time none of them are true. In that case, it is sometimes possible to replace them with a single test that checks to see if any of them are true, and then proceeds with the individual checks. A simple example is:

	if( err_code & ERR_1 ) {
	}
	/* ... */
	else if( err_code & ERR_N_1 ) {
	}
	else if( err_code & ERR_N ) {
	}
	else {
	/* no errors; common case! */
	}

	/* replace above code with more efficient */
	if( err_code & (ERR_1|...|ERR_N) ) {
	  if( err_code & ERR_1 ) {
	  }
	  /* ... */
	  else if( err_code & ERR_N_1 ) {
	  }
	  else {
	    assert( err_code & ERR_N );
	  }
	}
	else {
	  /* no errors; common case! */
	}

With this kind of a transform, in the common case only one branch is executed instead of the previous N.

Another example that sometimes arises is:

	if( x < 0 ) {
	}
	else if( x == 0 ) {
	}
	else {
	  /* common case! */
	}

	/* replace with more efficient */
	if( x <= 0 ) {
	  if( x < 0 ) {
	  }
	  else {
	    assert( x == 0 );
	  }
	}
	else {
	  /* common case */
	}

Equivalent sequences

It is sometimes possible to replace a branchy sequence with a straight-line sequence that has identical semantics. For instance:

	if( x > 0 ) {
	  z = 0;
	}


	/*  right arithmetic x by 31
	 * mask is 0 if x > 0, else all 1s 
	 */
	mask = (int)x >> 31;
	/* and z with 0s if x > 0, giving 0
	 * otherwise and with all 1s, giving z
	 */
	z= mask & z;

Unfortunately, this sequence uses behavior that is undefined by the standard:

• It relies on ints being 32 bits (fixable by using (sizeof(int)*CHAR_BITS)-1 instead of 31)
• It relies on right shifts of int being a sign-extending right

A lot of similar tricks that convert branches to sequences of instructions also rely on somewhat non-portable behavior. So, be careful.