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?

Solution 1

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);

Solution 2

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 [phone], 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();
    }
}

Solution 3

For what it's worth, absolute value of a 32-bit signed, 2's complement format int is usually implemented like this:

abs(x) = (x^(x>>31))-(x>>31)

Solution 4

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

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

Solution 5

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!

View more solutions

Comments

[Anthony Pegram]

This will be subtly different than Math.Abs. See: int.MinValue.

[LukeH]

It works, but it doesn't prove that the Abs call is inlined.

[Anthony Pegram]

Those meddling minimum values!

[manojlds]

@Anthony Pegram - noted. I was trying for the Java implementation of Abs :)

[manojlds]

checked(-X) - nice. didn't think of that.

[Voo]

I'd be extremely surprised if the .NET JIT wouldn't inline such Math Methods - at least the Hotspot JVM should do it and I think they'd be at least somewhat similar in that regard.

[Voo]

Ah I doubt that. It's definitely not implemented that way in Java and since in .NET the abs() class throws an exception for -2^31, that trick also won't work.

[Jon Skeet]

@Voo: Yes, I'd expect so too. I never like to make definite claims about such things without checking them though :)

[Adam Smith]

You're certainly correct that .NET wouldn't implement it this way without any range or error checking, nor would any robust math library. But as with many library calls, if you know you don't need the range checking, you can possibly write something the executes faster.

[Boppity Bop]

your answer is the really correct one - how to write fast abs function. and it is the last one. I was looking for this one day and got lots of boll0cks from 'masters' or local univers aka hans passant and little jon... meritocrasy seems dont work either.

[user1703401]

Patented by another master of the universe: patentgenius.com/patent/6073150.html

[Leo]

(x + (x >> 31)) ^ (x >> 31) works just as well and is not patented (even though the patent is probably not valid in court). Check the comments on this page: graphics.stanford.edu/~seander/bithacks.html#IntegerAbs

[Anders Gustafsson]

On my computer the first expression above is 8 times faster than Math.Abs when I loop over all integer values in the range [Int32.MinValue + 1, Int32.MaxValue - 1]. When I apply checked on -x, the speedup for the complete loop (negative and positive values) reduces to only 4 times faster. It of course dependent on how general the replacement Abs function need to be, but given that checked adds quite a lot of overhead for securing consistent handling of Int32.MinValue only, it is probably worthwhile to discard checked in most scenarios.

[Jon Skeet]

@AndersGustafsson: It depends - would you rather have fast but dangerous code which can silently give you an unexpected value, or slightly slower but safer code? How often is Math.Abs really a bottleneck anyway?

[Anders Gustafsson]

@JonSkeet I appreciated your answer to this question very much, and in for example a general purpose library I definitely agree that safety is better than optimal speed. On the other hand, in a more isolated scenario where you are quite sure that you will never encounter values close to Int32.MinValue, leaving out checked could obviously buy you a little time. But of course you are right, Math.Abs is seldom a bottleneck. I just thought it was interesting to share that the ?= expression could be so much faster than the built-in Math.Abs method.

[RMalke]

In my machine (.Net 4.5 - Release) Math.Abs is slightly faster

[Special Sauce]

upvote for actually performing the benchmark and providing relevant benchmark environment details

[MonsterMMORPG]

i just tested and results are like below .net 4.5.2 32 bit : 5224 3759 3782

[MonsterMMORPG]

at x64 : 5764 4191 4026

[MonsterMMORPG]

just tested. checked and and non checked equal. they are faster than math.abs

[Chaitanya Gadkari]

my results are also similar to MonsterMMORPG,

[joe]

Ryzen 3800X, dotnet core 3.1: 855, 1407, 950.

[Guiorgy]

Windows, Ryzen 3600 .Net Core 3.1 x64: 861, 961, 972; x86: 858, 962, 969; .Net 5 x64: 963, 1438, 959; x86: 958, 957, 1436; .Net Framework 4.8 x64: 2155, 967, 967; x86: 2154, 959, 959; The results are an average of 5 runs. Conclusion: Just use the Math.Abs function, unless you are on .Net Framework, in which case, use either of the others (I'll be using 2nd option)