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

Question

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

我已经了解了测量代码运行时间的方法.它运行多次以获得平均运行时间来计算每次运行的差异,并获得更好地利用缓存的时间.

为了测量某人的运行时间,我在多次修改后想出了这段代码.

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

// 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;

这很好,因为我可以找到最小,最大和平均时间,我感兴趣的数字.直到现在我才意识到这可能会导致结果偏差,因为缓存可能会受到影响,因为循环不是很紧给我不太理想的结果.

---

我编写测试代码的方式(使用LINQ)增加了我知道但忽略的额外开销,因为我只是测量运行代码,而不是开销.这是我的第一个版本:

// 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,最后得到了我现在在顶部的代码.这种混合动力获得了我认为最重要的开销时间AFAIK.(启动和停止计时器只是查询高分辨率计时器)同样,任何上下文切换对我来说都不重要,因为它仍然是正常执行的一部分.

有一次,我强制线程在循环内产生,以确保在方便的时间某个时刻给它机会(如果测试代码是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
}

---

对于赏金,我希望能够回答上述所有问题.我希望得到一个很好的解释,我的思想是否能够很好地证明这里的代码(如果不是最理想的话,可能会考虑如何改进它),或者如果我错了一点,解释为什么它是错误的和/或不必要的,如果适用,提供更好的选择.

总结重要问题和我对决策的看法:

1. 获得每个迭代的运行时间通常是一件好事吗？
   通过每次迭代的时间,我可以计算其他统计信息,如最小和最大运行时间以及标准偏差.所以我可以看看是否存在缓存或其他未知因素可能会导致结果偏差.这导致了我的"混合"版本.
2. 在实际计时开始之前还有一小圈的运行吗？
   根据我对Sam Saffron关于循环的想法的回应,这是为了增加缓存不断访问的内存的可能性.这样我只测量所有内容被缓存的时间,而不是某些没有缓存内存访问的情况.
3. Thread.Yield()在循环中强制是否会帮助或损害CPU绑定测试用例的时间？
   如果进程受CPU限制,则由于CPU上的时间不足,OS调度程序会降低此任务的优先级,从而可能增加时间.如果它不受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中的秒表并注意到Start()和Stop()相当便宜(考虑到所涉及的数学,调用Elapsed*属性可能更贵).

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

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

它通常没有必要来衡量每一个人迭代的运行时间,但它是性能不同迭代之间的差异程度有用的找出来.为此,您可以计算最小值/最大值(或k个异常值)和标准差.只有"中位数"统计信息要求您记录每次迭代.

如果您发现标准差很大,那么您可能有理由记录每次迭代,以便探究时间不断变化的原因.

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

对于我自己,我写了一个用于收集最小值,最大值,平均值和标准差的小类,可以用于基准测试或其他统计:

// 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绑定测试用例的时间？

我不确定.它可以清除处理器缓存(L1,L2,TLB),这不仅会降低整体基准速度,还会降低测量速度.你的结果将更加"人为",而不是反映你在现实世界中会得到什么.也许更好的方法是避免在与基准测试同时运行其他任务.