开发者

Math.Max vs inline if - what are the differences?

开发者 https://www.devze.com 2023-02-20 11:10 出处:网络
I was working on a project today, and found myself using Math.Max in several places and inline if statements in other places.So, I was wondering if anybody knew which is \"better\"... or rather, what

I was working on a project today, and found myself using Math.Max in several places and inline if statements in other places. So, I was wondering if anybody knew which is "better"... or rather, what the real differences are.

For example, in the following,开发者_如何学Go c1 = c2:

Random rand = new Random();
int a = rand.next(0,10000);
int b = rand.next(0,10000);

int c1 = Math.Max(a, b);
int c2 = a>b ? a : b;

I'm asking specifically about C#, but I suppose the answer could be different in different languages, though I'm not sure which ones have similar concepts.


One of the major differences I would notice right away would be for readability sake, as far as I know for implementation/performance sake, they would be nearly equivalent.

Math.Max(a,b) is very simple to understand, regardless of previous coding knowledge.

a>b ? a : b would require the user to have some knowledge of the ternary operator, at least.

"When in doubt - go for readability"


I thought it would be fun to throw in some numbers into this discussion so I wrote some code to profile it. As expected they are almost identical for all practical purposes.

The code does a billion loops (yep 1 billion). Subtracting the overhead of the loop you get:

  • Math.Max() took .0044 seconds to run 1 billion times
  • The inline if took .0055 seconds to run 1 billion times

I subtracted the overhead which I calculated by running an empty loop 1 billion times, the overhead was 1.2 seconds.

I ran this on a laptop, 64-bit Windows 7, 1.3 Ghz Intel Core i5 (U470). The code was compiled in release mode and ran without a debugger attached.

Here's the code:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;

namespace TestMathMax {
    class Program {
        static int Main(string[] args) {
            var num1 = 10;
            var num2 = 100;
            var maxValue = 0;
            var LoopCount = 1000000000;
            double controlTotalSeconds;
            { 
                var stopwatch = new Stopwatch();
                stopwatch.Start();
                for (var i = 0; i < LoopCount; i++) {
                    // do nothing
                }
                stopwatch.Stop();
                controlTotalSeconds = stopwatch.Elapsed.TotalSeconds;
                Console.WriteLine("Control - Empty Loop - " + controlTotalSeconds + " seconds");
            }
            Console.WriteLine();
            {
                var stopwatch = new Stopwatch();
                stopwatch.Start();
                for (int i = 0; i < LoopCount; i++) {
                    maxValue = Math.Max(num1, num2);
                }
                stopwatch.Stop();
                Console.WriteLine("Math.Max() - " + stopwatch.Elapsed.TotalSeconds + " seconds");
                Console.WriteLine("Relative: " + (stopwatch.Elapsed.TotalSeconds - controlTotalSeconds) + " seconds");
            }
            Console.WriteLine();
            {
                var stopwatch = new Stopwatch();
                stopwatch.Start();
                for (int i = 0; i < LoopCount; i++) {
                    maxValue = num1 > num2 ? num1 : num2;
                }
                stopwatch.Stop();
                Console.WriteLine("Inline Max: " + stopwatch.Elapsed.TotalSeconds + " seconds");
                Console.WriteLine("Relative: " + (stopwatch.Elapsed.TotalSeconds - controlTotalSeconds) + " seconds");
            }

            Console.ReadLine();

            return maxValue;
        }
    }
}

UPDATED Results 2/7/2015

On a Windows 8.1, Surface 3 Pro, i7 4650U 2.3Ghz Ran as a console application in release mode without the debugger attached.

  • Math.Max() - 0.3194749 seconds
  • Inline Max: 0.3465041 seconds


if statement considered beneficial

Summary

a statement of the form if (a > max) max = a is the fastest way to determine the maximum of a set of numbers. However the loop infrastructure itself takes most of the CPU time, so this optimization is questionable in the end.

Details

The answer by luisperezphd is interesting because it provides numbers, however I believe the method is flawed: the compiler will most likely move the comparison out of the loop, so the answer doesn't measure what it wants to measure. This explains the negligible timing difference between control loop and measurement loops.

To avoid this loop optimization, I added an operation that depends on the loop variable, to the empty control loop as well as to all measurement loops. I simulate the common use case of finding the maximum in a list of numbers, and used three data sets:

  • best case: the first number is the maximum, all numbers after it are smaller
  • worst case: every number is bigger than the previous, so the max changes each iteration
  • average case: a set of random numbers

See below for the code.

The result was rather surprising to me. On my Core i5 2520M laptop I got the following for 1 billion iterations (the empty control took about 2.6 sec in all cases):

  • max = Math.Max(max, a): 2.0 sec best case / 1.3 sec worst case / 2.0 sec average case
  • max = Math.Max(a, max): 1.6 sec best case / 2.0 sec worst case / 1.5 sec average case
  • max = max > a ? max : a: 1.2 sec best case / 1.2 sec worst case / 1.2 sec average case
  • if (a > max) max = a: 0.2 sec best case / 0.9 sec worst case / 0.3 sec average case

So despite long CPU pipelines and the resulting penalties for branching, the good old if statement is the clear winner for all simulated data sets; in the best case it is 10 times faster than Math.Max, and in the worst case still more than 30% faster.

Another surprise is that the order of the arguments to Math.Max matters. Presumably this is because of CPU branch prediction logic working differently for the two cases, and mispredicting branches more or less depending on the order of arguments.

However, the majority of the CPU time is spent in the loop infrastructure, so in the end this optimization is questionable at best. It provides a measurable but minor reduction in overall execution time.

UPDATED by luisperezphd

I couldn't fit this as a comment and it made more sense to write it here instead of as part of my answer so that it was in context.

Your theory makes sense, but I was not able to reproduce the results. First for some reason using your code my control loop was taking longer than the loops containing work.

For that reason I made the numbers here relative to the lowest time instead of the control loop. The seconds in the results are how much longer it took than the fastest time. For example in the results immediately below the fastest time was for Math.Max(a, max) best case, so every other result represents how much longer they took than that.

Below are the results I got:

  • max = Math.Max(max, a): 0.012 sec best case / 0.007 sec worst case / 0.028 sec average case
  • max = Math.Max(a, max): 0.000 best case / 0.021 worst case / 0.019 sec average case
  • max = max > a ? max : a: 0.022 sec best case / 0.02 sec worst case / 0.01 sec average case
  • if (a > max) max = a: 0.015 sec best case / 0.024 sec worst case / 0.019 sec average case

The second time I ran it I got:

  • max = Math.Max(max, a): 0.024 sec best case / 0.010 sec worst case / 0.009 sec average case
  • max = Math.Max(a, max): 0.001 sec best case / 0.000 sec worst case / 0.018 sec average case
  • max = max > a ? max : a: 0.011 sec best case / 0.005 sec worst case / 0.018 sec average case
  • if (a > max) max = a: 0.000 sec best case / 0.005 sec worst case / 0.039 sec average case

There is enough volume in these tests that any anomalies should have been wiped out. Yet despite that the results are pretty different. Maybe the large memory allocation for the array has something to do with it. Or possibly the difference is so small that anything else happening on the computer at the time is the true cause of the variation.

Note the fastest time, represented in the results above by 0.000 is about 8 seconds. So if you consider that the longest run then was 8.039, the variation in time is about half a percent (0.5%) - aka too small to matter.

The computer

The code was ran on Windows 8.1, i7 4810MQ 2.8Ghz and compiled in .NET 4.0.

Code modifications

I modified your code a bit to output the results in the format shown above. I also added additional code to wait 1 second after starting to account for any additional loading time .NET might need when running the assembly.

Also I ran all the tests twice to account for any CPU optimizations. Finally I changed the int for i to a unit so I could run the loop 4 billion times instead of 1 billion to get a longer timespan.

That's probably all overkill, but it's all to make sure as much as possible that the tests are not affected by any of those factors.

You can find the code at: http://pastebin.com/84qi2cbD

Code

using System;
using System.Diagnostics;

namespace ProfileMathMax
{
  class Program
  {
    static double controlTotalSeconds;
    const int InnerLoopCount = 100000;
    const int OuterLoopCount = 1000000000 / InnerLoopCount;
    static int[] values = new int[InnerLoopCount];
    static int total = 0;

    static void ProfileBase()
    {
        Stopwatch stopwatch = new Stopwatch();
        stopwatch.Start();
        int maxValue;
        for (int j = 0; j < OuterLoopCount; j++)
        {
            maxValue = 0;
            for (int i = 0; i < InnerLoopCount; i++)
            {
                // baseline
                total += values[i];
            }
        }
        stopwatch.Stop();
        controlTotalSeconds = stopwatch.Elapsed.TotalSeconds;
        Console.WriteLine("Control - Empty Loop - " + controlTotalSeconds + " seconds");
    }

    static void ProfileMathMax()
    {
        int maxValue;
        Stopwatch stopwatch = new Stopwatch();
        stopwatch.Start();
        for (int j = 0; j < OuterLoopCount; j++)
        {
            maxValue = 0;
            for (int i = 0; i < InnerLoopCount; i++)
            {
                maxValue = Math.Max(values[i], maxValue);
                total += values[i];
            }
        }
        stopwatch.Stop();
        Console.WriteLine("Math.Max(a, max) - " + stopwatch.Elapsed.TotalSeconds + " seconds");
        Console.WriteLine("Relative: " + (stopwatch.Elapsed.TotalSeconds - controlTotalSeconds) + " seconds");
    }

    static void ProfileMathMaxReverse()
    {
        int maxValue;
        Stopwatch stopwatch = new Stopwatch();
        stopwatch.Start();
        for (int j = 0; j < OuterLoopCount; j++)
        {
            maxValue = 0;
            for (int i = 0; i < InnerLoopCount; i++)
            {
                maxValue = Math.Max(maxValue, values[i]);
                total += values[i];
            }
        }
        stopwatch.Stop();
        Console.WriteLine("Math.Max(max, a) - " + stopwatch.Elapsed.TotalSeconds + " seconds");
        Console.WriteLine("Relative: " + (stopwatch.Elapsed.TotalSeconds - controlTotalSeconds) + " seconds");
    }

    static void ProfileInline()
    {
        int maxValue = 0;
        Stopwatch stopwatch = new Stopwatch();
        stopwatch.Start();
        for (int j = 0; j < OuterLoopCount; j++)
        {
            maxValue = 0;
            for (int i = 0; i < InnerLoopCount; i++)
            {
                maxValue = maxValue > values[i] ? values[i] : maxValue;
                total += values[i];
            }
        }
        stopwatch.Stop();
        Console.WriteLine("max = max > a ? a : max: " + stopwatch.Elapsed.TotalSeconds + " seconds");
        Console.WriteLine("Relative: " + (stopwatch.Elapsed.TotalSeconds - controlTotalSeconds) + " seconds");
    }

    static void ProfileIf()
    {
        int maxValue = 0;
        Stopwatch stopwatch = new Stopwatch();
        stopwatch.Start();
        for (int j = 0; j < OuterLoopCount; j++)
        {
            maxValue = 0;
            for (int i = 0; i < InnerLoopCount; i++)
            {
                if (values[i] > maxValue)
                    maxValue = values[i];
                total += values[i];
            }
        }
        stopwatch.Stop();
        Console.WriteLine("if (a > max) max = a: " + stopwatch.Elapsed.TotalSeconds + " seconds");
        Console.WriteLine("Relative: " + (stopwatch.Elapsed.TotalSeconds - controlTotalSeconds) + " seconds");
    }

    static void Main(string[] args)
    {
        Random rnd = new Random();
        for (int i = 0; i < InnerLoopCount; i++)
        {
            //values[i] = i;  // worst case: every new number biggest than the previous
            //values[i] = i == 0 ? 1 : 0;  // best case: first number is the maximum
            values[i] = rnd.Next(int.MaxValue);  // average case: random numbers
        }

        ProfileBase();
        Console.WriteLine();
        ProfileMathMax();
        Console.WriteLine();
        ProfileMathMaxReverse();
        Console.WriteLine();
        ProfileInline();
        Console.WriteLine();
        ProfileIf();
        Console.ReadLine();
    }
  }
}


I'd say it is quicker to understand what Math.Max is doing, and that should really be the only deciding factor here.

But as an indulgence, it's interesting to consider that Math.Max(a,b) evaluates the arguments once, whilst a > b ? a : b evaluates one of them twice. Not a problem with local variables, but for properties with side effects, the side effect may happen twice.


If the JITer chooses to inline the Math.Max function, the executable code will be identical to the if statement. If Math.Max isn't inlined, it will execute as a function call with call and return overhead not present in the if statement. So, the if statement will give identical performance to Math.Max() in the inlining case or the if statement may be a few clock cycles faster in the non-inlined case, but the difference won't be noticeable unless you are running tens of millions of comparisons.

Since the performance difference between the two is small enough to be negligible in most situations, I'd prefer the Math.Max(a,b) because it's easier to read.


Regarding performance, Modern CPUs have internal command pipeline such that every assembly command is executed in several internal steps. (e.g. fetching, interpretation, calculation, storage)

In most cases the CPU is smart enough to run these steps in parallel for sequential commands so the overall throughput is very high.

This is fine till there comes a branch (if, ?: etc.) . The branch may break the sequence and force the CPU to trash the pipeline. This costs a lot of clock cycles.

In theory, if the compiler is smart enough, the Math.Max can be implemented using a built it CPU command and the branching can be avoided.

In this case the Math.Max would actually be faster than the if - but it depends on the compiler..

In case of more complicated Max - like working on vectors, double []v; v.Max() the compiler can utilize highly optimized library code, that can be much faster than regular compiled code.

So it's best to go with Math.Max, but it is also recommended to check on your particular target system and compiler if it is important enough.


Math.Max(a,b)

is NOT equivalent to a > b ? a : b in all cases.

Math.Max returns the greater value of the two arguments, that is:

if (a == b) return a; // or b, doesn't matter since they're identical
else if (a > b && b < a) return a;
else if (b > a && a < b) return b;
else return undefined;

The undefined is mapped to double.NaN in case of the double overload of Math.Max for example.

a > b ? a : b

evaluates to a if a is greater than b, which does not necessarily mean that b is less than a.

A simple example that demonstrates that they are not equivalent:

var a = 0.0/0.0; // or double.NaN
var b = 1.0;
a > b ? a : b // evaluates to 1.0
Math.Max(a, b) // returns double.NaN


Take an operation; N must be >= 0

General solutions:

A) N = Math.Max(0, N)
B) if(N < 0){N = 0}

Sorting by speed:

Slow: Math.Max (A) < (B) if-then statement :Fast (3% more faster than solution 'A')

But my solution is 4% faster than solution 'B':

N *= Math.Sign(1 + Math.Sign(N));
0

精彩评论

暂无评论...
验证码 换一张
取 消