c# - 我测量运行时间的方法有缺陷吗？

Question

对不起，它很长，但我只是在分析这个时解释我的思路。问题在最后。

我了解测量代码运行时间的内容。它运行多次以获得平均运行时间，以解释每次运行的差异，并获得更好地利用缓存的时间。

为了测量某人的运行时间，我想出了 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 pseudocodestart timer;loop N times:    run testing code (directly or via function);stop timer;report results;

This was good in my mind since with the numbers, I have the total running time and can easily work out the average running time and would have good cache locality.

But one set of values that I thought were important to have were minimum and maximum iteration running time. This could not be calculated using the above form. So when I wrote my testing code, I wrote them in this form:

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

This is good because I could then find the minimum, maximum as well as average times, the numbers I was interested in. Until now I realized that this could potentially skew results since the cache could potentially be affected since the loop wasn't very tight giving me less than optimal results.

---

The way I wrote the test code (using LINQ) added additional overheads which I knew about but ignored since I was just measuring the running code, not the overheads. Here was my first version:

// 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();
}

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

有一次，我强制线程在循环内让步，以确保在方便的某个时间点给它机会(如果测试代码受 CPU 限制并且根本没有阻塞)。我不太担心正在运行的进程可能会更糟地更改缓存，因为无论如何我都会单独运行这些测试。但是，我得出的结论是，对于这种特殊情况，没有必要。尽管如果证明总体上是有益的，我可能会将其纳入最终的最终版本。也许作为某些代码的替代算法。

现在我的问题:

我做了一些正确的选择吗？有些不对？

我在思考过程中是否对目标做出了错误的假设？

最小或最大运行时间是否真的是有用的信息，还是一个失败的原因？

如果是这样，一般哪种方法会更好？循环运行的时间(方法1)？或者只运行有问题的代码的时间(方法 2)？

我的混合方法一般可以使用吗？

我应该屈服(出于最后一段中解释的原因)还是对时代的伤害比必要的要大？

有没有我没有提到的更优选的方法来做到这一点？

为了清楚起见，我是 不是 寻找一个通用的、随处使用的、准确的计时器。我只是想知道一种算法，当我想要一个快速实现、相当准确的计时器来测量代码时，我应该使用一种算法，当库或其他 3rd 方工具不可用时。

如果没有异议，我倾向于以这种形式编写所有测试代码:

// 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 绑定(bind)测试用例的时间？
如果进程受 CPU 限制，操作系统调度程序将降低此任务的优先级，可能会由于 CPU 时间不足而增加次数。如果它不受 CPU 限制，我将省略屈服。

根据这里的答案，我将使用最终实现编写我的测试函数，而没有针对一般情况的个别时间。如果我想要其他统计数据，我会将其重新引入测试函数并应用此处提到的其他内容。

Answer 1

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

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 中的 Stopwatch 并注意到 Start() 和 Stop() 相当便宜(考虑到所涉及的数学，调用 Elapsed* 属性可能更昂贵。)

确保 Stopwatch 的 IsHighResolution 属性为 true。如果它是假的，秒表使用 DateTime.UtcNow，我相信它只每 15-16 毫秒更新一次。

1. 获得每个单独迭代的运行时间通常是一件好事吗？

通常不需要测量每个单独迭代的运行时间，但它 是 有助于找出不同迭代之间的性能差异。为此，您可以计算最小值/最大值(或 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 个输出。

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

3. 循环中的强制 Thread.Yield() 会帮助还是损害 CPU 绑定(bind)测试用例的计时？

我不知道。它可能会清除处理器缓存(L1、L2、TLB)，这不仅会降低整体基准测试速度，还会降低测量速度。您的结果将更加“人为”，不能很好地反射(reflect)您在现实世界中得到的结果。也许更好的方法是避免在执行基准测试的同时运行其他任务。