代码之家 › 专栏 › 技术社区 › Jeff Mercado

我测量运行时间的方法有缺陷吗?

benchmarking c#

Jeff Mercado · 技术社区 · 14 年前

我了解如何度量代码的运行时间。它可以多次运行,以获得平均运行时间来解释每次运行的差异,并获得更好地利用缓存的时间。

this 多次修订后的代码。

最后,我得到了这个代码,它产生了我想要捕获的结果,而没有给出误导性的数字:

// implementation C
static void Test<T>(string testName, Func<T> test, int iterations = 1000000)
{
    Console.WriteLine(testName);
    Console.WriteLine("Iterations: {0}", iterations);
    var results = Enumerable.Repeat(0, iterations).Select(i => new System.Diagnostics.Stopwatch()).ToList();
    var timer = System.Diagnostics.Stopwatch.StartNew();
    for (int i = 0; i < results.Count; i++)
    {
        results[i].Start();
        test();
        results[i].Stop();
    }
    timer.Stop();
    Console.WriteLine("Time(ms): {0,3}/{1,10}/{2,8} ({3,10})", results.Min(t => t.ElapsedMilliseconds), results.Average(t => t.ElapsedMilliseconds), results.Max(t => t.ElapsedMilliseconds), timer.ElapsedMilliseconds);
    Console.WriteLine("Ticks:    {0,3}/{1,10}/{2,8} ({3,10})", results.Min(t => t.ElapsedTicks), results.Average(t => t.ElapsedTicks), results.Max(t => t.ElapsedTicks), timer.ElapsedTicks);
    Console.WriteLine();
}

在我看到的所有度量运行时间的代码中,它们通常采用以下形式:

// approach 1 pseudocode
start timer;
loop N times:
    run testing code (directly or via function);
stop timer;
report results;

但我认为有一组重要的值是最小和最大的迭代运行时间。无法使用上述表单计算此值。因此,当我编写测试代码时,我用以下形式编写它们:

// approach 2 pseudocode
loop N times:
    start timer;
    run testing code (directly or via function);
    stop timer;
    store results;
report results;

这很好,因为我可以找到我感兴趣的最小、最大和平均次数。直到现在,我才意识到这可能会扭曲结果,因为缓存可能会受到影响,因为循环不是很紧,给我的结果不太理想。

// implementation A
static void Test<T>(string testName, Func<T> test, int iterations = 1000000)
{
    Console.WriteLine(testName);
    var results = Enumerable.Repeat(0, iterations).Select(i =>
    {
        var timer = System.Diagnostics.Stopwatch.StartNew();
        test();
        timer.Stop();
        return timer;
    }).ToList();
    Console.WriteLine("Time(ms): {0,3}/{1,10}/{2,8}", results.Min(t => t.ElapsedMilliseconds), results.Average(t => t.ElapsedMilliseconds), results.Max(t => t.ElapsedMilliseconds));
    Console.WriteLine("Ticks:    {0,3}/{1,10}/{2,8}", results.Min(t => t.ElapsedTicks), results.Average(t => t.ElapsedTicks), results.Max(t => t.ElapsedTicks));
    Console.WriteLine();
}

在这里,我认为这很好,因为我只测量运行测试函数所需的时间。与LINQ相关联的开销不包括在运行时间中。为了减少在循环中创建计时器对象的开销,我进行了修改。

// implementation B
static void Test<T>(string testName, Func<T> test, int iterations = 1000000)
{
    Console.WriteLine(testName);
    Console.WriteLine("Iterations: {0}", iterations);
    var results = Enumerable.Repeat(0, iterations).Select(i => new System.Diagnostics.Stopwatch()).ToList();
    results.ForEach(t =>
    {
        t.Start();
        test();
        t.Stop();
    });
    Console.WriteLine("Time(ms): {0,3}/{1,10}/{2,8} ({3,10})", results.Min(t => t.ElapsedMilliseconds), results.Average(t => t.ElapsedMilliseconds), results.Max(t => t.ElapsedMilliseconds), results.Sum(t => t.ElapsedMilliseconds));
    Console.WriteLine("Ticks:    {0,3}/{1,10}/{2,8} ({3,10})", results.Min(t => t.ElapsedTicks), results.Average(t => t.ElapsedTicks), results.Max(t => t.ElapsedTicks), results.Sum(t => t.ElapsedTicks));
    Console.WriteLine();
}

这改善了总体时间,但造成了一个小问题。我通过添加每个迭代的时间来添加报告中的总运行时间,但给出了误导性的数字,因为时间很短,并没有反映实际的运行时间(通常要长得多)。我现在需要测量整个循环的时间,所以我离开了LINQ,最终得到了现在位于顶部的代码。这种混合动力车以最少的开销获得了我认为重要的时间。(启动和停止计时器只是查询高分辨率计时器)同时,发生的任何上下文切换对我来说都不重要,因为这是正常执行的一部分。

有一次,我强迫线程在循环中屈服,以确保在某个方便的时候给它机会(如果测试代码是CPU绑定的,并且根本不阻塞)。我不太担心正在运行的进程可能会使缓存变得更糟,因为无论如何,我都会单独运行这些测试。然而,我得出的结论是,对于这一特殊情况,没有必要这样做。不过,如果总的来说是有益的,我可能会把它合并到最终版本中。或许可以作为某些代码的替代算法。

现在我的问题是:

我做了正确的选择吗?一些错误的?
最短或最长运行时间真的是有用的信息吗?还是它是一个丢失的原因?
如果是的话,一般来说哪种方法更好?循环中运行的时间(方法1)?或者只运行问题代码的时间(方法2)?
我的混合方法可以普遍使用吗?
我屈服了(因为上一段解释的原因),还是这对时代的危害比必要的更大?
有没有我没有提到的更可取的方法?

只是说清楚,我不寻找一个通用的,使用任何地方,准确的计时器。我只想知道一个算法,我应该使用时,我想要一个快速实现,合理准确的计时器,以衡量代码库或其他第三方工具不可用。

如果没有人反对,我倾向于用这种形式编写我的所有测试代码:

// final implementation
static void Test<T>(string testName, Func<T> test, int iterations = 1000000)
{
    // print header
    var results = Enumerable.Repeat(0, iterations).Select(i => new System.Diagnostics.Stopwatch()).ToList();
    for (int i = 0; i < 100; i++) // warm up the cache
    {
        test();
    }
    var timer = System.Diagnostics.Stopwatch.StartNew(); // time whole process
    for (int i = 0; i < results.Count; i++)
    {
        results[i].Start(); // time individual process
        test();
        results[i].Stop();
    }
    timer.Stop();
    // report results
}

总结重要问题和我对所做决定的看法:

获得每个迭代的运行时间通常是件好事吗?
通过每次迭代的次数,我可以计算额外的统计信息,比如最小和最大运行时间以及标准差。所以我可以看看是否有因素,如缓存或其他未知因素可能会扭曲结果。这导致了我的“混合”版本。
在实际计时开始前有一个小循环运行是否也很好?
从我的反应到 Sam Saffron's 考虑到循环,这是为了增加不断访问的内存被缓存的可能性。这样,我只测量缓存所有内容的时间,而不是一些不缓存内存访问的情况。
Thread.Yield() 在循环内帮助或损害CPU绑定测试用例的计时?
如果进程受CPU限制,则OS调度程序将降低此任务的优先级,这可能会由于CPU时间不足而增加时间。如果它不受CPU限制,我将忽略这个结果。

基于这里的答案,我将使用最终实现编写测试函数,而不必为一般情况单独计时。如果我想有其他的统计数据,我会把它重新引入到测试函数中,并应用这里提到的其他东西。

8 回复 | 直到 7 年前

Qwertie 14 年前

我的第一个想法是一个简单的循环

for (int i = 0; i < x; i++)
{
    timer.Start();
    test();
    timer.Stop();
}

相比之下有点傻:

timer.Start();
for (int i = 0; i < x; i++)
    test();
timer.Stop();

原因是(1)这种“for”循环的开销非常小,以至于即使test()只需要一微秒,也几乎不值得担心,(2)timer.Start()和timer.Stop()都有自己的开销,这可能比for循环更影响结果。也就是说,我在Reflector中浏览了一下秒表,发现Start()和Stop()相当便宜(考虑到所涉及的数学问题,调用Elapsed*属性可能更贵)

确保秒表的IsHighResolution属性为true。如果为false,则秒表使用DateTime.UtcNow,我认为它仅每15-16毫秒更新一次。

一。获得每个迭代的运行时间通常是件好事吗?

通常不需要测量每个单独迭代的运行时,但是是有助于了解不同迭代之间的性能变化。为此,可以计算最小值/最大值(或k个异常值)和标准偏差。只有“中值”统计需要记录每次迭代。

如果您发现标准差很大,那么您可能有理由记录每个迭代,以便探索时间为什么不断变化。

有些人编写了一些小框架来帮助您进行性能基准测试。例如, CodeTimers . 如果您正在测试的对象非常微小和简单,以至于基准库的开销很重要,请考虑在基准库调用的lambda中的for循环中运行该操作。如果操作太小以至于for循环的开销很重要(例如,测量乘法的速度),那么使用手动循环展开。但是,如果使用循环展开,请记住,大多数实际应用程序不使用手动循环展开,因此您的基准测试结果可能会夸大实际性能。

// A lightweight class to help you compute the minimum, maximum, average
// and standard deviation of a set of values. Call Clear(), then Add(each
// value); you can compute the average and standard deviation at any time by 
// calling Avg() and StdDeviation().
class Statistic
{
    public double Min;
    public double Max;
    public double Count;
    public double SumTotal;
    public double SumOfSquares;

    public void Clear()
    {
        SumOfSquares = Min = Max = Count = SumTotal = 0;
    }
    public void Add(double nextValue)
    {
        Debug.Assert(!double.IsNaN(nextValue));
        if (Count > 0)
        {
            if (Min > nextValue)
                Min = nextValue;
            if (Max < nextValue)
                Max = nextValue;
            SumTotal += nextValue;
            SumOfSquares += nextValue * nextValue;
            Count++;
        }
        else
        {
            Min = Max = SumTotal = nextValue;
            SumOfSquares = nextValue * nextValue;
            Count = 1;
        }
    }
    public double Avg()
    {
        return SumTotal / Count;
    }
    public double Variance()
    {
        return (SumOfSquares * Count - SumTotal * SumTotal) / (Count * (Count - 1));
    }
    public double StdDeviation()
    {
        return Math.Sqrt(Variance());
    }
    public Statistic Clone()
    {
        return (Statistic)MemberwiseClone();
    }
};

2。在实际计时开始前有一个小循环运行是否也很好?

您测量哪些迭代取决于您最关心的是启动时间、稳态时间还是总运行时间。一般来说,将一次或多次运行单独记录为“启动”运行可能很有用。您可以期望第一次迭代(有时不止一次)运行得更慢。作为一个极端的例子,我的 GoInterfaces 库始终需要140毫秒来产生第一个输出,然后在大约15毫秒内再输出9个。

根据基准测试的内容,您可能会发现,如果在重新启动后立即运行基准测试,则第一次迭代(或前几次迭代)将运行得非常缓慢。然后,如果您再次运行基准测试,第一次迭代将更快。

三。循环中的强制Thread.Yield()是否有助于或损害CPU绑定测试用例的计时?

Richard Flamsholt 14 年前

不管函数计时的机制是什么(这里的答案似乎很好),有一个非常简单的技巧可以消除基准代码本身的开销,即循环、计时器读数和方法调用的开销:

Func<T> 首先,即。

void EmptyFunc<T>() {}

这将为您提供一个计时开销的基线,您可以从实际基准函数的后一个度量中减去该基线。

当然,您必须重新安排一点基准代码。理想情况下,您需要使用为了对空函数和实际的基准函数进行基准测试,我建议您将计时循环移到另一个函数中,或者至少保持这两个循环 完全地 一模一样。总结

对空函数进行基准测试
对实际测试函数进行基准测试
从这些测试结果中减去平均开销
你完了

通过这样做,实际的计时机制突然变得不那么重要了。

Rich Turner 14 年前

我认为您的第一个代码示例似乎是最好的方法。

您的第一个代码示例是小的、干净的和简单的,并且在测试循环期间不使用任何主要的抽象,这可能会带来隐藏的开销。

使用Stopwatch类是一件好事,因为它简化了通常需要编写以获得高分辨率计时的代码。

您可以考虑的一件事是提供一个选项,在进入计时循环以预热测试例程可能执行的任何缓存、缓冲区、连接、句柄、套接字、线程池线程等之前,对测试进行较少次数的迭代。

哦。

Community Navdeep Singh 7 年前

我倾向于同意@ Sam Saffron 关于每次迭代使用一个秒表而不是一个秒表。在您的示例中,默认情况下执行1000000次迭代。我不知道制作一块秒表的成本是多少,但你要制作一百万块。可以想象,这本身可能会影响你的测试结果。我对您的“最终实现”进行了一些修改,允许在不创建1000000个秒表的情况下测量每个迭代。当然,由于我正在保存每次迭代的结果,所以我正在分配1000000个long,但是乍一看,这似乎比分配那么多秒表的总体影响要小。我还没有将我的版本与你的版本进行比较,看我的版本是否会产生不同的结果。

static void Test2<T>(string testName, Func<T> test, int iterations = 1000000)
{
  long [] results = new long [iterations];

  // print header 
  for (int i = 0; i < 100; i++) // warm up the cache 
  {
    test();
  }

  var timer = System.Diagnostics.Stopwatch.StartNew(); // time whole process 

  long start;

  for (int i = 0; i < results.Length; i++)
  {
    start = Stopwatch.GetTimestamp();
    test();
    results[i] = Stopwatch.GetTimestamp() - start;
  }

  timer.Stop();

  double ticksPerMillisecond = Stopwatch.Frequency / 1000.0;

  Console.WriteLine("Time(ms): {0,3}/{1,10}/{2,8} ({3,10})", results.Min(t => t / ticksPerMillisecond), results.Average(t => t / ticksPerMillisecond), results.Max(t => t / ticksPerMillisecond), results.Sum(t => t / ticksPerMillisecond));
  Console.WriteLine("Ticks:    {0,3}/{1,10}/{2,8} ({3,10})", results.Min(), results.Average(), results.Max(), results.Sum());

  Console.WriteLine();
}

使用时间戳和频率来计算性能并不像直接使用秒表实例那么简单。但是,对每个迭代使用不同的秒表可能不如使用单个秒表来测量整个过程那么清楚。

我也同意热身循环。取决于你的测试正在做什么,可能有一些固定的启动成本,你不想影响整体结果。启动循环应该会消除这个问题。

由于保存整个值数组(或计时器)所需的存储成本,保持每个单独的计时结果会适得其反。对于更少的内存,但更多的处理时间,您可以简单地求和增量,计算最小值和最大值。这有可能会丢掉你的结果,但是如果你主要关心的是基于独立迭代测量生成的统计数据,那么你可以在时间增量检查之外进行最小和最大计算:

static void Test2<T>(string testName, Func<T> test, int iterations = 1000000)
{
  //long [] results = new long [iterations];
  long min = long.MaxValue;
  long max = long.MinValue;

  // print header 
  for (int i = 0; i < 100; i++) // warm up the cache 
  {
    test();
  }

  var timer = System.Diagnostics.Stopwatch.StartNew(); // time whole process 

  long start;
  long delta;
  long sum = 0;

  for (int i = 0; i < iterations; i++)
  {
    start = Stopwatch.GetTimestamp();
    test();
    delta = Stopwatch.GetTimestamp() - start;
    if (delta < min) min = delta;
    if (delta > max) max = delta;
    sum += delta;
  }

  timer.Stop();

  double ticksPerMillisecond = Stopwatch.Frequency / 1000.0;

  Console.WriteLine("Time(ms): {0,3}/{1,10}/{2,8} ({3,10})", min / ticksPerMillisecond, sum / ticksPerMillisecond / iterations, max / ticksPerMillisecond, sum);
  Console.WriteLine("Ticks:    {0,3}/{1,10}/{2,8} ({3,10})", min, sum / iterations, max, sum);

  Console.WriteLine();
}

看起来很老的学校没有林肯的手术,但它仍然能完成任务。

Quinn1000 14 年前

方法2中的逻辑对我来说更正确,但我只是一个CS学生。

我发现了一个你可能会感兴趣的链接: http://www.yoda.arachsys.com/csharp/benchmark.html

Pieter van Ginkel 14 年前

Community Navdeep Singh 7 年前

我有一个类似的 question here .

我更喜欢使用一个秒表的概念,特别是如果你是微型工作台。您的代码没有考虑可能影响性能的GC。

我认为在运行测试运行之前强制GC集合是非常重要的,而且我不确定100次预热运行的意义是什么。

Jon Hanna 14 年前

不过,要考虑的一件事是,CPU缓存未命中的影响是否真的是一件公平的事情?

一个基于数组或单链表的队列就是一个例子;当缓存线在两个调用之间没有被重新填充时,前者几乎总是有更高的性能,但是在调整大小操作上比后者更困难。因此,后者可以在现实世界中的情况下获胜(因为它们更容易以无锁的形式编写),即使它们几乎总是在快速迭代的计时测试中失败。

出于这个原因,还可以尝试一些迭代来强制刷新缓存。我不知道现在最好的办法是什么,所以如果我这样做的话,我可能会回来补充。