cmicro-optimizationsigned-integer

Fast sign of integer in C


There is a sign function in C:

int sign(int x)
{
    if(x > 0) return 1;
    if(x < 0) return -1;
    return 0;
}

Unfortunately, comparison cost is very high, so I need to modify function in order reduce the number of comparisons.

I tried the following:

int sign(int x)
{
    int result;
    result = (-1)*(((unsigned int)x)>>31);

    if (x > 0) return 1;

    return result;
}

In this case I get only one comparison.

Is there any way to avoid comparisons at all?

EDIT possible duplicate does not give an answer for a question as all answers are C++, uses comparison (that I supposed to avoid) or does not return -1, +1, 0.


Solution

  • First of all, integer comparison is very cheap. It's branching that can be expensive (due to the risk of branch mispredictions).

    I have benchmarked your function on a Sandy Bridge box using gcc 4.7.2, and it takes about 1.2ns per call.

    The following is about 25% faster, at about 0.9ns per call:

    int sign(int x) {
        return (x > 0) - (x < 0);
    }
    

    The machine code for the above is completely branchless:

    _sign:
        xorl    %eax, %eax
        testl   %edi, %edi
        setg    %al
        shrl    $31, %edi
        subl    %edi, %eax
        ret
    

    Two things are worth pointing out:

    1. The base level of performance is very high.
    2. Eliminating branching does improve performance here, but not dramatically.