Algorithm performance [closed]

Question

I am testing an algorithm for different parameters on a computer. I notice the performance fluctuates for each parameters.

Say I run for the first time I got 20 ms, second times I got 5ms, third times I got 4ms: But the algorithm should work the same for these 3 times.

I am using stopwatch from C# library to count the time, is there a better way to measure the performance without subjecting to those fluctuations?

Answer 1

Welcome to the world of benchmarking.

With code that finishes in 4ms, you aren't going to be able to get an accurate measurement running it just once. Page faults, static initializers, JIT, CPU cache, branch predictors, and context switches all affect run time, and at that small of a test any one of them could easily create a huge variance. Run it in a loop until the stopwatch measures over 1 or 2 seconds, then divide by the amount of times it ran.

Also, you should run the code once or twice before you start the Stopwatch to ensure the code is JITed and hot in the CPU's cache.

Here's code I use when I want a poor-mans benchmark instead of profiling. It does a bit more than what I described above -- such as removing overhead of Stopwatch from the benchmark, and drilling down until it's confident it's found the smallest execution time.

runCount = the amount of times it should check for the next smallest execution time.

subRunCount = if the Action you pass in already runs a loop, or runs over multiple items etc. and you want to measure the amount of time spent per item, put the count here.

static double Benchmark(string name, int runCount, int subRunCount, Action action)
{
    Console.WriteLine("{0}: warming up...", name);

    // warm up.
    action();

    Console.WriteLine("{0}: finding ballpark speed...", name);

    // find an average amount of calls it fill up two seconds.

    Stopwatch sw = Stopwatch.StartNew();

    int count = 0;
    do
    {
        ++count;
        action();
    }
    while (sw.ElapsedTicks < (Stopwatch.Frequency * 2));

    sw.Stop();

    Console.WriteLine("{0}: ballpark speed is {1} runs/sec", name, MulMulDiv(count, subRunCount, Stopwatch.Frequency, sw.ElapsedTicks));

    // The benchmark will run the Action in a loop 'count' times.

    count = Math.Max(count / 2, 1);

    // Start the benchmark.

    Console.Write("{0}: benchmarking", name);
    Console.Out.Flush();

    long minticks = long.MaxValue;
    int runs = 0;

    while (runs < runCount)
    {
        sw.Restart();

        for (int i = 0; i < count; ++i)
        {
            action();
        }

        sw.Stop();

        long ticks = sw.ElapsedTicks;

        if (ticks < minticks)
        {
            // Found a new smallest execution time. Reset.

            minticks = ticks;
            runs = 0;

            Console.Write('+');
            Console.Out.Flush();
            continue;
        }
        else
        {
            ++runs;
            Console.Write('.');
            Console.Out.Flush();
        }
    }

    Console.WriteLine("done");
    Console.WriteLine("{0}: speed is {1} runs/sec", name, MulMulDiv(count, subRunCount, Stopwatch.Frequency, minticks));

    return (double)count * subRunCount * Stopwatch.Frequency / minticks;
}

static long MulMulDiv(long count, long subRunCount, long freq, long ticks)
{
    return (long)((BigInteger)count * subRunCount * freq / ticks);
}

Answer 2

First run takes more time, because at execution time a just-in-time (JIT) compiler translates the MSIL into native code (see Managed Execution Process).

To eliminate the first-run problem you can either use:

• Ngen.exe (Native Image Generator);

The Native Image Generator (Ngen.exe) is a tool that improves the performance of managed applications. Ngen.exe creates native images, which are files containing compiled processor-specific machine code, and installs them into the native image cache on the local computer. The runtime can use native images from the cache instead of using the just-in-time (JIT) compiler to compile the original assembly.

• or run multiple iterations with skipping the result for the first run (but you need to make sure that it went through all the branches to have them compiled).

To profile the code without including StopWatch in it, you can use the instrumentation profiling from the Performance Profiler included in Visual Studio.

The instrumentation profiling method of the Visual Studio records detailed timing information for the function calls, lines, and instructions in the profiled application:

You can also analyse "hot paths" and compare reports from multiple different runs.