如果陈述被认为是有益的
概括
形式的陈述if (a > max) max = a
是确定一组数字的最大值的最快方法。然而,循环基础设施本身占用了大部分 CPU 时间,因此这种优化最终是有问题的。
细节
luisperezphd 的答案很有趣,因为它提供了数字,但是我认为该方法存在缺陷:编译器很可能会将比较移出循环,因此答案不会测量它想要测量的内容。这解释了控制回路和测量回路之间可忽略的时间差。
为了避免这种循环优化,我向空控制循环以及所有测量循环添加了一个依赖于循环变量的操作。我模拟了在数字列表中查找最大值的常见用例,并使用了三个数据集:
- 最佳情况:第一个数字是最大值,之后的所有数字都较小
- 最坏的情况:每个数字都比前一个大,所以每次迭代的最大值都会改变
- 平均情况:一组随机数
请参阅下面的代码。
结果让我相当吃惊。在我的 Core i5 2520M 笔记本电脑上,我得到了以下 10 亿次迭代(在所有情况下,空控件大约需要 2.6 秒):
max = Math.Max(max, a)
: 2.0 秒最佳情况 / 1.3 秒最坏情况 / 2.0 秒平均情况
max = Math.Max(a, max)
:1.6 秒最佳情况/2.0 秒最坏情况/1.5 秒平均情况
max = max > a ? max : a
:1.2 秒最佳情况/1.2 秒最坏情况/1.2 秒平均情况
if (a > max) max = a
:0.2 秒最佳情况 / 0.9 秒最坏情况 / 0.3 秒平均情况
因此,尽管 CPU 流水线很长,并且对分支造成了惩罚,但好的旧if
语句显然是所有模拟数据集的赢家;在最好的情况下,它比 快 10 倍Math.Max
,在最坏的情况下仍然快 30% 以上。
另一个令人惊讶的是,论点的顺序很Math.Max
重要。这可能是因为 CPU 分支预测逻辑在两种情况下的工作方式不同,并且根据参数的顺序或多或少地错误预测分支。
但是,大部分 CPU 时间都花在了循环基础设施上,因此最终这种优化充其量是值得怀疑的。它在整体执行时间上提供了可衡量但轻微的减少。
由 luisperezphd 更新
我无法将其作为评论,将其写在这里而不是作为我的答案的一部分更有意义,以便它在上下文中。
你的理论是有道理的,但我无法重现结果。首先由于某种原因使用您的代码,我的控制循环比包含工作的循环花费的时间更长。
出于这个原因,我在这里制作了相对于最低时间而不是控制循环的数字。结果中的秒数是比最快时间花费的时间。例如,在紧接下方的结果中,最快时间是 Math.Max(a, max) 最佳情况,因此每个其他结果都表示它们花费了多长时间。
以下是我得到的结果:
max = Math.Max(max, a)
:0.012 秒最佳情况/0.007 秒最坏情况/0.028 秒平均情况
max = Math.Max(a, max)
:0.000 最佳情况 / 0.021 最坏情况 / 0.019 秒平均情况
max = max > a ? max : a
:0.022 秒最佳情况 / 0.02 秒最坏情况 / 0.01 秒平均情况
if (a > max) max = a
:0.015 秒最佳情况/0.024 秒最坏情况/0.019 秒平均情况
我第二次运行它时得到:
max = Math.Max(max, a
):0.024 秒最佳情况/0.010 秒最坏情况/0.009 秒平均情况
max = Math.Max(a, max)
:0.001 秒最佳情况/0.000 秒最坏情况/0.018 秒平均情况
max = max > a ? max : a
:0.011 秒最佳情况 / 0.005 秒最坏情况 / 0.018 秒平均情况
if (a > max) max = a
:0.000 秒最佳情况/0.005 秒最坏情况/0.039 秒平均情况
这些测试中有足够的量,任何异常都应该被消除。然而,尽管如此,结果却大不相同。也许数组的大内存分配与它有关。或者可能差异是如此之小,以至于当时计算机上发生的任何其他事情都是变化的真正原因。
请注意,在上面的结果中以 0.000 表示的最快时间约为 8 秒。因此,如果您考虑最长的运行时间是 8.039,那么时间变化大约是 0.5% (0.5%) - 也就是太小了。
电脑
该代码在 Windows 8.1、i7 4810MQ 2.8Ghz 上运行并在 .NET 4.0 中编译。
代码修改
我稍微修改了你的代码,以上面显示的格式输出结果。我还添加了额外的代码以在开始考虑运行程序集时 .NET 可能需要的任何额外加载时间后等待 1 秒。
此外,我两次运行所有测试以说明任何 CPU 优化。最后,我将 for 更改int
为i
a unit
,这样我就可以运行循环 40 亿次而不是 10 亿次,以获得更长的时间跨度。
这可能有点矫枉过正,但一切都是为了尽可能确保测试不受任何这些因素的影响。
您可以在以下位置找到代码: http: //pastebin.com/84qi2cbD
代码
using System;
using System.Diagnostics;
namespace ProfileMathMax
{
class Program
{
static double controlTotalSeconds;
const int InnerLoopCount = 100000;
const int OuterLoopCount = 1000000000 / InnerLoopCount;
static int[] values = new int[InnerLoopCount];
static int total = 0;
static void ProfileBase()
{
Stopwatch stopwatch = new Stopwatch();
stopwatch.Start();
int maxValue;
for (int j = 0; j < OuterLoopCount; j++)
{
maxValue = 0;
for (int i = 0; i < InnerLoopCount; i++)
{
// baseline
total += values[i];
}
}
stopwatch.Stop();
controlTotalSeconds = stopwatch.Elapsed.TotalSeconds;
Console.WriteLine("Control - Empty Loop - " + controlTotalSeconds + " seconds");
}
static void ProfileMathMax()
{
int maxValue;
Stopwatch stopwatch = new Stopwatch();
stopwatch.Start();
for (int j = 0; j < OuterLoopCount; j++)
{
maxValue = 0;
for (int i = 0; i < InnerLoopCount; i++)
{
maxValue = Math.Max(values[i], maxValue);
total += values[i];
}
}
stopwatch.Stop();
Console.WriteLine("Math.Max(a, max) - " + stopwatch.Elapsed.TotalSeconds + " seconds");
Console.WriteLine("Relative: " + (stopwatch.Elapsed.TotalSeconds - controlTotalSeconds) + " seconds");
}
static void ProfileMathMaxReverse()
{
int maxValue;
Stopwatch stopwatch = new Stopwatch();
stopwatch.Start();
for (int j = 0; j < OuterLoopCount; j++)
{
maxValue = 0;
for (int i = 0; i < InnerLoopCount; i++)
{
maxValue = Math.Max(maxValue, values[i]);
total += values[i];
}
}
stopwatch.Stop();
Console.WriteLine("Math.Max(max, a) - " + stopwatch.Elapsed.TotalSeconds + " seconds");
Console.WriteLine("Relative: " + (stopwatch.Elapsed.TotalSeconds - controlTotalSeconds) + " seconds");
}
static void ProfileInline()
{
int maxValue = 0;
Stopwatch stopwatch = new Stopwatch();
stopwatch.Start();
for (int j = 0; j < OuterLoopCount; j++)
{
maxValue = 0;
for (int i = 0; i < InnerLoopCount; i++)
{
maxValue = maxValue > values[i] ? values[i] : maxValue;
total += values[i];
}
}
stopwatch.Stop();
Console.WriteLine("max = max > a ? a : max: " + stopwatch.Elapsed.TotalSeconds + " seconds");
Console.WriteLine("Relative: " + (stopwatch.Elapsed.TotalSeconds - controlTotalSeconds) + " seconds");
}
static void ProfileIf()
{
int maxValue = 0;
Stopwatch stopwatch = new Stopwatch();
stopwatch.Start();
for (int j = 0; j < OuterLoopCount; j++)
{
maxValue = 0;
for (int i = 0; i < InnerLoopCount; i++)
{
if (values[i] > maxValue)
maxValue = values[i];
total += values[i];
}
}
stopwatch.Stop();
Console.WriteLine("if (a > max) max = a: " + stopwatch.Elapsed.TotalSeconds + " seconds");
Console.WriteLine("Relative: " + (stopwatch.Elapsed.TotalSeconds - controlTotalSeconds) + " seconds");
}
static void Main(string[] args)
{
Random rnd = new Random();
for (int i = 0; i < InnerLoopCount; i++)
{
//values[i] = i; // worst case: every new number biggest than the previous
//values[i] = i == 0 ? 1 : 0; // best case: first number is the maximum
values[i] = rnd.Next(int.MaxValue); // average case: random numbers
}
ProfileBase();
Console.WriteLine();
ProfileMathMax();
Console.WriteLine();
ProfileMathMaxReverse();
Console.WriteLine();
ProfileInline();
Console.WriteLine();
ProfileIf();
Console.ReadLine();
}
}
}