Fast integer ABS function

Question

int X = a-b;
int d = Math.Abs(X);

I am pretty sure that .NET doesn't do inlining. So, will I do if(), or is there some other less-known trick?

Answer 1

I did some performance tests, to find out whether you can actually save time using something besides the standard Math.Abs.

The results after executing all of these 2000000000 times (with i from -1000000000 to +1000000000, so without overflows):

Math.Abs(i)                    5839 ms     Factor 1
i > 0 ? i : -i                 6395 ms     Factor 1.09
(i + (i >> 31)) ^ (i >> 31)    5053 ms     Factor 0.86

(These numbers vary a bit for different runs)

Basically you can get a very slight improvement over Math.Abs, but nothing spectacular.

With the bit hack you can shave of a little of the time required for Math.Abs, but readability suffers severely.
With the simple branch you can actually be slower. Overall not worth it in my opinion.

All tests where run on a 32 bit OS, Net 4.0, VS 2010, Release mode, no debugger attached.

Here is the actual code:

class Program
{
    public static int x; // public static field. 
                         // this way the JITer will not assume that it is  
                         // never used and optimize the wholeloop away
    static void Main()
    {
        // warm up
        for (int i = -1000000000; i < 1000000000; i++)
        {
            x = Math.Abs(i);
        }

        // start measuring
        Stopwatch watch = Stopwatch.StartNew();
        for (int i = -1000000000; i < 1000000000; i++)
        {
            x = Math.Abs(i);
        }
        Console.WriteLine(watch.ElapsedMilliseconds);

        // warm up
        for (int i = -1000000000; i < 1000000000; i++)
        {
            x = i > 0 ? i : -i;
        }

        // start measuring
        watch = Stopwatch.StartNew();
        for (int i = -1000000000; i < 1000000000; i++)
        {
            x = i > 0 ? i : -i;
        }
        Console.WriteLine(watch.ElapsedMilliseconds);

        // warm up
        for (int i = -1000000000; i < 1000000000; i++)
        {
            x = (i + (i >> 31)) ^ (i >> 31);
        }

        // start measuring
        watch = Stopwatch.StartNew();
        for (int i = -1000000000; i < 1000000000; i++)
        {
            x = (i + (i >> 31)) ^ (i >> 31);
        }
        Console.WriteLine(watch.ElapsedMilliseconds);


        Console.ReadLine();
    }
}

Answer 2

The JIT performs inlining in some circumstances. I don't know whether it inlines Math.Abs or not... but have you verified that this is actually a performance problem for you? Don't micro-optimize until you know that you need to, and then measure the performance gain from something like:

int d = X > 0 ? X : -X;

to verify that it's really worth it.

As noted by Anthony, the above won't (normally) work for int.MinValue, as -int.MinValue == int.MinValue, whereas Math.Abs will throw an OverflowException. You can force this in the straight C# as well using checked arithmetic:

int d = X > 0 ? X : checked(-X);

Answer 3

I just see if it is less than zero and multiply by -1

int d = (X < 0) ? (-X) : X;

Answer 4

See http://graphics.stanford.edu/~seander/bithacks.html#IntegerAbs for how to compute absolute value without branching.

Whilst .Net supports inlining, I doubt that Math.Abs() would be considered a candidate for inlining by the compiler. Here's the implementation of the int overload, courtesy of Reflector.

public static int Abs(int value)
{
  if (value >= 0)
    {
      return value;
    }
  return AbsHelper(value);
}

private static int AbsHelper(int value)
{
  if (value == -2147483648)
  {
    throw new OverflowException(Environment.GetResourceString("Overflow_NegateTwosCompNum"));
  }
  return -value;
}

The overloads for other integral types are similar. The float and double overloads are external calls whilst the decimal overload uses its own implementation, which constructs a new instance. Ouch!