c - 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.)

score 13 · Accepted Answer

まず、 log(1) = 0であることに注意してください。次に、問題を x * log(y) として記述できます。ここで、x <= 0 の場合は y = 1、それ以外の場合は x に等しくなります。y = 1 の場合、log(y)=0 であるため、x は重要ではありません。

y = (x > 0)*x + (x <= 0) のようなものがこれを行います:

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

log(1) と 4 つの整数操作が分岐よりも悪いかどうかによって異なります。

score 11 · Accepted Answer

ここでは、コンパイラの拡張機能が役立ちます。GCC では、次のようにします。

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

その後、GCC はx > 0 == 1ブランチを優先するマシンコードを生成します。

負の数を気にしない場合は、x == 0代わりにありそうもない分岐として扱うことができます。

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

GCC を使用していない場合は、コンパイラのドキュメントをチェックして、類似の機能が提供されているかどうかを確認してください。

まだブランチフリーではないことに注意してください。可能性の高い分岐の方が時間がかからないというだけです。

score 7 · Accepted Answer

ブランチフリーコードにはx * log(x)、「通常の」ケースをカバーするためにの計算が含まれている必要があります。

したがって、分岐のないコードを考え出す前に、x * log(x)単独での速度を測定してください。あなたが持っているコードよりも大幅に高速でない限り、ここで得られるものは何もありません。そして、そうではないと思います。

3 に答える 3