算法性能

Question

我正在测试计算机上不同参数的算法.我注意到每个参数的性能波动.

假设我第一次运行20 ms,第二次运行5 ms,第三次运行4 ms:但算法应该在这3次运行相同.

我正在使用stopwatchC#库来计算时间,有没有更好的方法来衡量性能而不受这些波动的影响？

Answer 1

欢迎来到基准测试的世界.

代码在4ms内完成,您将无法获得仅运行一次的准确测量.页面错误,静态初始化程序,JIT,CPU缓存,分支预测变量和上下文切换都会影响运行时间,在这个小的测试中,任何一个都可以轻松地产生巨大的差异.循环运行,直到秒表测量超过1或2秒,然后除以它运行的次数.

此外,您应该在开始之前运行一次或两次代码,Stopwatch以确保代码在CPU的缓存中被JIT和热.

这是我在想要一个穷人基准而不是分析时使用的代码.它比我上面描述的更多 - 比如从基准测试中删除秒表的开销,然后向下钻取,直到它确信它找到了最小的执行时间.

runCount =它应检查下一个最小执行时间的次数.

subRunCount =如果您传入的Action已经运行循环,或者运行多个项目等,并且您想测量每个项目花费的时间,请将计数放在此处.

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

首次运行需要更多时间，因为在执行时，即时 (JIT) 编译器会将 MSIL 转换为本机代码（请参阅托管执行过程）。

要消除首次运行问题，您可以使用：

• Ngen.exe（本机图像生成器）；

本机映像生成器 (Ngen.exe) 是一种可提高托管应用程序性能的工具。Ngen.exe 创建本机映像，这些映像是包含已编译的特定于处理器的机器代码的文件，并将它们安装到本地计算机上的本机映像缓存中。运行时可以使用缓存中的本机映像，而不是使用即时 (JIT) 编译器来编译原始程序集。

• 或者运行多次迭代并跳过第一次运行的结果（但您需要确保它遍历所有分支以对其进行编译）。

要分析代码而不包含StopWatch在其中，可以使用Visual Studio 中包含的性​​能分析器中的检测分析。

Visual Studio 的检测分析方法记录分析应用程序中函数调用、行和指令的详细计时信息：

您还可以分析“热路径”并比较来自多个不同运行的报告。