Compare Algorithms Performance

Have you ever wondered if a given C# algorithm/code fragment is faster than another that does the same job? If the answer is yes, then continue reading this article as it will give you a facility to easily test both code fragments and determine the faster one. To compare the performance of 2 code fragments we need to execute them one by one and measure the time each of them has worked. Many developers use the DateTime.Now property for this purpose, but it has one major flaw - it is not very accurate. The most precise method to measure elapsed time in the .NET framework is the Stopwatch class.

To measure the execution time of a given code fragment using a stopwatch we can use the following piece of code:

Stopwatch s = Stopwatch.StartNew();
// Tested code here
s.Stop();

Unfortunately, there's a lot of activity going on under the hood of the OS, which is very likely to mess up our time measurements. In order to improve the accuracy of the measured times we should execute the tests multiple times and remove the lowest and the greatest times from the final results. This approach will exclude most of the external factors that may influence our code's execution time and will serve us well in most cases. To make this easy we will create an abstract class that can be used for testing whether a given code fragment is faster than another one. All you have to do is to create a class that inherits from the presented performance test class and implements the Method1 and Method2 methods (put there the code fragments you want to test). Then you can use your performance test class like this:

PerformanceTest test = new CustomTest();
string results = test.Execute();

Console.WriteLine("\n==============================");
Console.WriteLine(results);
Console.WriteLine("==============================\n");

Here's the C# source code of the performance test class implementation:

public abstract class PerformanceTest
{
    public PerformanceTest(string name1, string name2)
    {
        m_Name1 = name1;
        m_Name2 = name2;
    }

    public string Name1
    {
        get
        {
            return m_Name1;
        }
    }
    public string Name2
    {
        get
        {
            return m_Name2;
        }
    }
    /// <summary>
    /// The number of times to execute the test methods.
    /// By default set to 100.
    /// </summary>
    public virtual int TestRuns
    {
        get
        {
            return 100;
        }
    }

    public string Execute()
    {
        Stopwatch s1, s2;
        long[] times1 = new long[TestRuns];
        long[] times2 = new long[TestRuns];

        for (int i = 0; i < TestRuns; i++)
        {
            // Execute the tests in alternating order to make sure there
            // will be no optimizations for the first or the second test
            if (i % 2 == 0)
            {
                s1 = Stopwatch.StartNew();
                Method1();
                s1.Stop();

                s2 = Stopwatch.StartNew();
                Method2();
                s2.Stop();
            }
            else
            {
                s2 = Stopwatch.StartNew();
                Method2();
                s2.Stop();

                s1 = Stopwatch.StartNew();
                Method1();
                s1.Stop();
            }

            times1[i] = s1.ElapsedMilliseconds;
            times2[i] = s2.ElapsedMilliseconds;
        }

        // Sort the elapsed times for all test runs
        Array.Sort(times1);
        Array.Sort(times2);

        // Calculate the total times discarding
        // the 5% min and 5% max test times
        long time1 = 0, time2 = 0;
        int discardCount = (int)Math.Round(TestRuns * 0.05);
        int count = TestRuns - discardCount;
        for (int i = discardCount; i < count; i++)
        {
            time1 += times1[i];
            time2 += times2[i];
        }

        return FormatResults(time1, time2);
    }
        
    /// <summary>
    /// This method can be called in loops. As it is virtual
    /// it won't be inlined and optimized by the compiler.
    /// </summary>
    protected virtual void DoNothing()
    {
    }

    private string FormatResults(long time1, long time2)
    {
        // Add the times to the string
        int nameLength = Math.Max(m_Name1.Length, m_Name2.Length);
        int timeLength = Math.Max(time1.ToString().Length,
            time2.ToString().Length);

        string result = String.Format("{0," + nameLength + "} = {1," +
            timeLength + "} ms\n{2," + nameLength + "} = {3," +
            timeLength +  "} ms\n------------------------------\n",
            m_Name1, time1, m_Name2, time2);

        // Determine who's faster
        if (time1 != time2)
        {
            result += String.Format("{0} is {1:P} faster",
                time1 < time2 ? m_Name1 : m_Name2,
                (double)Math.Max(time1, time2) / Math.Min(time1, time2) - 1);
        }
        else
        {
            result += "The times are equal";
        }

        return result;
    }

    public abstract void Method1();
    public abstract void Method2();

    private string m_Name1;
    private string m_Name2;
}

See also:

• Cross-Platform C# Development
• Colorize C# Code For Blog or Website
• The Most Useful Visual Studio Keyboard Shortcuts