Put the Most-likely If-checks in the Front

If you know the possibility (roughly is ok) of the condition checks, you can sort them in descending order, which improves the cache (pre fetching, decreases the chances of condition mis-predict/increase cache hit).

Example 1 – Binary Search

Binary Search is a generally-used technique to search for specific items in a sorted list of elements. Every iteration, the current guess is compared to the middle element of the list to search, if it is smaller or bigger, narrow the range by its half. Therefore, on average, it is less-likely to happen for one-time guess, we therefore put the ‘equal’ check at the end.

1
2
3
4
5
6
7
8
9
10
11

while (left <= right) {
  mid = (left + right) / 2;
  if (num < arr[mid]) {      
    right = mid - 1;   
  }    
  else if (num > arr[mid]) {
     left = mid + 1;
  } else {
     return mid;
  }
}

while (left <= right) {
  mid = (left + right) / 2;
  if (num < arr[mid]) {      
    right = mid - 1;   
  }    
  else if (num > arr[mid]) {
     left = mid + 1;
  } else {
     return mid;
  }
}

Example 2 – Switch Case

Most programming languages (especially C-like languages, C/C++, Java etc) provide switch-case statements, which are in fact equivalent as the multiple -if checks. Therefore, we can put the condition-checks of the highest probability first. As discussed, some compilers (like Intel C++) may optimise switch into a look-up table (and then using kinda goto jumps), in this case, optimising this does not make much difference.. But still, stick to this style because you don’t know what the code will be optimised by the compiler. Don’t rely much on the compiler as not all of them will translate multiple-ifs to look up tables.

1
2
3
4
5
6
7
8
9
10

switch (num) {
  case 100: {
    // the num is most-likely to be 100;
    break;
  }
  case 90: {
    break;
  }
//  case ... 
}

switch (num) {
  case 100: {
    // the num is most-likely to be 100;
    break;
  }
  case 90: {
    break;
  }
//  case ... 
}

Example 3 – Fast Integer Log10

A 32-bit unsigned integer can hold values From 0 to 4,294,967,295 which is . Therefore, the possible values for are from 0 to 9, the is undefined. .

Assume the distribution of the input integers is equally the same (each integer has the same probability), the answer for is most likely to happen because all numbers bigger than 1,000,000,000 ()  yield a value 9 after log. The second largest group is the numbers between 100,000,000 () to 1,000,000,000 () and so on.

Thus (also from here and here) it is easy to cook up this special integer log10 implementation (following C#)

1
2
3
4
5
6
7

static uint log10(uint v)
{
    return (v >= 1000000000u) ? 9 : (v >= 100000000u) ? 8 : 
        (v >= 10000000u) ? 7 : (v >= 1000000u) ? 6 : 
        (v >= 100000u) ? 5 : (v >= 10000u) ? 4 :
        (v >= 1000u) ? 3 : (v >= 100u) ? 2 : (v >= 10u) ? 1u : 0u; 
}

static uint log10(uint v)
{
    return (v >= 1000000000u) ? 9 : (v >= 100000000u) ? 8 : 
        (v >= 10000000u) ? 7 : (v >= 1000000u) ? 6 : 
        (v >= 100000u) ? 5 : (v >= 10000u) ? 4 :
        (v >= 1000u) ? 3 : (v >= 100u) ? 2 : (v >= 10u) ? 1u : 0u; 
}

Again, we have to point out that the above code depends on the distribution of the inputs. The performance may vary a lot in different cases. For example, for most inputs smaller than e.g. 100, the above code will have lots of mis-predict conditions that will actually be even slower than the (int)log10(n).  The above code works great only if most inputs are correctly predicted (within 1, 2, or 3 if conditions). Use it wisely.

–EOF (Coding For Speed) —