Optimization Headache - removing if's from Look Up Table

Question

I'm trying to optimize the following piece of code, which is a bottleneck in my application. What it does: It takes the double values value1 and value2 and tries to find the maximum including a correctional factor. If the difference between both values is greater than 5.0 (the LUT is scaled by factor 10), I can just take the max value of those two. If the difference is smaller than 5.0, I can use the correctional factor from the LUT.

Does anyone have an idea what could be a better style for this piece of code? I don't know where I'm losing time - is it the large number of ifs or the multiplication by 10?

double value1, value2;
// Lookup Table scaled by 10 for (ln(1+exp(-abs(x)))), which is almost 0 for x > 5 and symmetrical around 0. LUT[0] is x=0.0, LUT[40] is x=4.0.
const logValue LUT[50] = { ... }

if (value1 > value2)
{
    if (value1 - value2 >= 5.0)
    {
        return value1;
    }
    else
    {
        return value1 + LUT[(uint8)((value1 - value2) * 10)];
    }
}
else
{
    if (value2 - value1 >= 5.0)
    {
        return value2;
    }
    else
    {
        return value2 + LUT[(uint8)((value2 - value1) * 10)];
    }
}

Answer 1

It probably goes down both paths equally enough that you're causing a lot of pipe-lining problems for your processor.

Have you tried profiling?

I'd also suggest trying to use the standard library and see if that helps (for example if it's able to use and processor-specific instructions):

double diff = std::fabs(value1 - value2);
double maxv = std::max(value1, value2);
return (diff >= 5.0) ? maxv : maxv + LUT[(uint8)((diff) * 10)];

Answer 2

I'd probably have written the code a bit different to handle the value2<value1 case:

if (value2 < value1) std::swap(value1, value2);
assert(value1 <= value2); // Assertion corrected
int diff = int((value2 - value1) * 10.0);
if (diff >= 50) diff = 49; // Integer comparison iso floating point
return value2 + LUT[diff];

Answer 3

A couple of minutes of playing with Excel produces an approximation equation that looks like it might have the accuracy you need, so you can do away with the lookup table altogether. You still need one condition to make sure the parameters to the equation remain within the range that it was optimized for.

double diff = abs(value1 - value2);
double dmax = (value1 + value2 + diff) * 0.5; // same as (min+max+(max-min))/2
if (diff > 5.0)
    return dmax;
return dmax + 4.473865638/(2.611112371+diff) + 0.088190879*diff + -1.015046114;

P.S. I'm not guaranteeing this is faster, only that it's a different enough approach to be worth benchmarking.

P.P.S. It's possible to change the constraints to come up with slightly different constants, there are a lot of variations. Here's another set I did where the difference between your table and the formula will always be less than 0.008, also each value will be less than the one preceeding.

return dmax + 3.441318133/(2.296924445+diff) + 0.065529678*diff + -0.797081529;

Edit: I tested this code (second formula) with 100 passes against a million random numbers between 0 and 10, along with the original code from the question, MSalters currently accepted answer, and a brute force implementation max(value1,value2)+log(1.0+exp(-abs(value1-value2))). I tried it on a dual-core AMD Athlon and an Intel quad-core i7 and the results were roughly consistent. Here's a typical run:

• Original: 1.32 seconds.
• MSalters: 1.13 seconds.
• Mine: 0.67 seconds.
• Brute force: 4.50 seconds.

Processors have gotten unbelievably fast over the years, so fast now that they can do a couple of floating point multiplies and divides faster than they can look up a value in memory. Not only is this approach faster on a modern x86, it's also more accurate; the approximation errors in the equation are much less than the step errors caused by truncating the input for the lookup.

Naturally results can still vary based on your processor and compiler; benchmarking is still required for your own particular target.

Answer 4

I am going to assume when the function is called, you'll most likely get the part where you have to use the look up table, rather then the >=5.0 parts. In this case, it's better to guide the compiler towards this.

double maxval = value1;
double difference_scaled = (value1-value2)*10;
if (difference < 0)
{
    difference = -difference;
    maxval = value2;
}
if (difference < 50)
    return maxval+LUT[(int)difference_scaled];
else
    return maxval;

Try this and let me know if that improves your program's performance.

Answer 5

The only reason this code would be the bottleneck in your application is because you are calling it many many times. Are you sure you need to? Perhaps the algorithm higher up in the code can be changed to use the comparison less?

Answer 6

You are computing value1 - value2 quite a few times in your function. Just do it once.

That cast to a uint8_t may also be also problematic. A far as performance is concerned, the best integral type to use as a conversion from double to integer is an int, as is the best integral type to use an array index is an int.

max_value = value1;
diff = value1 - value2;
if (diff < 0.0) {
  max_value = value2;
  diff = -diff;
}

if (diff >= 5.0) {
  return max_value;
}
else {
  return max_value + LUT[(int)(diff * 10.0)];
}

Note that the above guarantees that the LUT index will be between 0 (inclusive) and 50 (exclusive). There's no need for a uint8_t here.

Edit
After some playing around with some variations, this is a fairly fast LUT-based approximation to log(exp(value1)+exp(value2)):

#include <stdint.h>

// intptr_t *happens* to be fastest on my machine. YMMV.
typedef intptr_t IndexType;

double log_sum_exp (double value1, double value2, double *LUT) {
  double diff = value1 - value2;
  if (diff < 0.0) {
    value1 = value2;
    diff = -diff;
  }   
  IndexType idx = diff * 10.0;
  if (idx < 50) {
    value1 += LUT[idx];
  }   
  return value1;
}   

The integral type IndexType is one of the keys to speeding things up. I tested with clang and g++, and both indicated that casting to an intptr_t (long on my computer) and using a intptr_t as an index into the LUT is faster than other integral types. It is considerably faster than some types. For example, unsigned long long and uint8_t are incredibly poor choices on my computer.

The type is not just a hint, at least with the compilers I used. Those compilers did exactly what the code told it to do with regard to the conversion from floating point type to integral type, regardless of the optimization level.

Another speed bump results from comparing the integral type to 50 as opposed to comparing the floating point type to 5.0.

One last speed bump: Not all compilers are created equal. On my computer (YMMV), g++ -O3 generates considerably slower code (25% slower with this problem!) than does clang -O3, which in turn generates code that is a bit slower than that generated by clang -O4.

I also played with a rational function approximation approach (similar to Mark Ransom's answer), but the above obviously does not use such an approach.

Answer 7

I've done some very quick tests but please profile the code yourself to verify the effect.

Changing the LUT[] to a static variable got me a 600% speed up (from 3.5s to 0.6s). Which is close to the absolute minimum of test I used (0.4s). See if that works and re-profile to determine if any further optimization is needed.

For reference, the I was simply timing the execution of this loop (100 million iterations of the inner loop) in VC++ 2010:

int Counter = 0;

for (double j = 0; j < 10; j += 0.001)
    {
        for (double i = 0; i < 10; i += 0.001)
        {
            ++Counter;
            Value1 += TestFunc1(i, j);
        }
    }