抱歉,这篇文章很长,但我只是在分析这个问题时解释一下我的思路。问题在最后。
我了解测量代码运行时间的原理。它运行多次以获得平均运行时间,以考虑每次运行的差异,并获得更好地利用缓存的时间。
为了测量某人的跑步时间,我想出了this https://stackoverflow.com/questions/3992363/sum-of-products-of-two-arrays-dotproduct/3992840#3992840代码经过多次修改。
最后,我得到了这段代码,它产生了我想要捕获的结果,而没有给出误导性的数字:
// 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,而是得到了现在位于顶部的代码。这种混合动力以最小的开销获得了我认为重要的时间。 (启动和停止计时器只是查询高分辨率计时器)此外,发生的任何上下文切换对我来说都不重要,因为无论如何它都是正常执行的一部分。
在某一时刻,我强制线程在循环内让步,以确保它在某个方便的时间有机会(如果测试代码受 CPU 限制并且根本不会阻塞)。我不太关心正在运行的进程可能会使缓存变得更糟,因为无论如何我都会单独运行这些测试。然而,我得出的结论是,对于这种特殊情况,没有必要这样做。不过,如果它总体上证明是有益的,我可能会将其合并到最终版本中。也许作为某些代码的替代算法。
现在我的问题是:
- 我做出了一些正确的选择吗?有些是错误的吗?
- 我在思考过程中是否对目标做出了错误的假设?
- 最小或最大运行时间真的是有用的信息还是一个失败的原因?
- 如果是这样,一般来说哪种方法更好?时间循环运行(方法1)?或者只运行相关代码的时间(方法 2)?
- 我的混合方法一般可以使用吗?
-
Should我屈服了(出于上一段中解释的原因),或者这对时代的伤害是否比必要的更大?
- 有没有我没有提到的更优选的方法?
只是为了清楚起见,我not正在寻找一款通用、随处使用、准确的计时器。我只是想知道当我想要一个快速实现、相当准确的计时器来测量代码(当库或其他第三方工具不可用时)时应该使用的算法。
如果没有异议,我倾向于以这种形式编写所有测试代码:
// 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
}
对于赏金,我希望上述所有问题都能得到解答。我希望能得到一个很好的解释,说明我影响这里代码的想法是否合理(以及可能关于如何改进它的想法,如果不是最理想的),或者如果我的观点是错误的,请解释为什么它是错误的和/或不必要的,如果适用,提供更好的选择。
总结重要的问题和我对所做决定的想法:
-
获取每个单独迭代的运行时间通常是一件好事吗?
通过每次迭代的时间,我可以计算其他统计信息,例如最小和最大运行时间以及标准差。所以我可以看看是否有诸如缓存或其他未知因素之类的因素可能会扭曲结果。这导致了我的“混合”版本。
-
在实际计时开始之前进行一个小循环也很好吗?
从我的回复到萨姆·萨弗隆的 https://stackoverflow.com/questions/4001610/is-my-method-of-measuring-running-time-flawed/4102936#4102936在循环中思考,这是为了增加不断访问的内存被缓存的可能性。这样,我仅测量所有内容都被缓存时的时间,而不是某些内存访问未缓存的情况。
-
是否会被迫
Thread.Yield()
循环内对 CPU 限制测试用例的计时有帮助还是有害?
如果进程受 CPU 限制,操作系统调度程序将降低该任务的优先级,从而可能会由于 CPU 时间不足而增加时间。如果它不受CPU限制,我会省略屈服。
根据这里的答案,我将使用最终实现来编写我的测试函数,而不需要针对一般情况的单独计时。如果我想要其他统计数据,我会将其重新引入到测试函数中,并应用此处提到的其他内容。