Branch-free implementation of f(x) := if x == 0 then 0 else (x * log(x))

Question

I have this C function:

double f(int x)
{
    if (x <= 0)
        return 0.0;
    else
        return x * log(x);
}

which I am calling in a tight loop, and would like to get rid of the branch to see if it improves performance.

I cannot use this:

double f(int x)
{
    return x * log(x);
}

because it returns NaN when x == 0 (which is true about 25% of the time.)

Is there another way to implement it so that it returns 0 when x == 0, but still get rid of the branch?

(I am less concerned about negative inputs, because these are errors, whereas zeros are not.)

Answer 1

First note that log(1) = 0. Then you can write the problem as x * log(y), where y = 1 if x <= 0, and otherwise equals x; if y = 1, then x doesn't matter, because log(y)=0.

Something like y = (x > 0)*x + (x <= 0) will do this, and then:

double f(int x) {
    return x * log((x > 0)*x + (x <= 0));
}

It just depends on whether log(1) and four integer ops are worse than a branch.

Answer 2

Compiler extensions can help here. In GCC, you would do this:

if(__builtin_expect(x > 0, 1)) {
    return x * log(x);
}
return 0.0;

GCC will then generate machine code that favors the x > 0 == 1 branch.

If you don't care about negative numbers, then you can treat x == 0 as an unlikely branch instead:

if(__builtin_expect(x == 0, 0)) {
    return 0.0;
}
return x * log(x);

If you're not on GCC, you should check the documentation of your compiler and see whether it provides an analogous feature.

Note that it's still not branch-free. It's just that the likely branch takes less time.

Answer 3

Any branch free code must contain a calculation of x * log(x) to cover the "normal" case.

So, before trying to come up with that branch-free code, measure the speed of x * log(x) alone. Unless it's significantly faster than the code you have, there's nothing significant to be gained here. And I suspect it won't be.