衡量并验证你的绩效假设
这个例子是用 F# 编写的，但这些想法适用于所有环境
优化性能时的第一条规则是不依赖于假设; 始终测量并验证你的假设。
由于我们不直接编写机器代码，因此很难预测编译器和 JIT 如何将程序转换为机器代码。这就是为什么我们需要测量执行时间以确保我们获得预期的性能改进并验证实际程序不包含任何隐藏的开销。
验证是一个非常简单的过程，涉及使用 ILSpy 等工具对可执行文件进行逆向工程。JIT：er 使验证变得复杂，因为看到实际的机器代码很棘手但可行。但是，通常检查 IL-code 会带来很大的收益。
更难的问题是衡量; 更难，因为设置可以衡量代码改进的现实情况很棘手。静止测量是非常宝贵的。
分析简单的 F#函数
让我们来看一些简单的 F# 函数，它们以各种不同的方式累积 1..n 中的所有整数。由于范围是一个简单的算术系列，因此可以直接计算结果，但为了本例的目的，我们迭代范围。
首先，我们定义一些有用的函数来测量函数的时间：
// now () returns current time in milliseconds since start
let now : unit -> int64 =
let sw = System.Diagnostics.Stopwatch ()
sw.Start ()
fun () -> sw.ElapsedMilliseconds
// time estimates the time 'action' repeated a number of times
let time repeat action : int64*'T =
let v = action () // Warm-up and compute value
let b = now ()
for i = 1 to repeat do
action () |> ignore
let e = now ()
e - b, v
time 反复运行一个动作，我们需要运行几百毫秒的测试来减少变化。
然后我们定义了一些函数，它们以不同的方式累积 1..n 中的所有整数。
// Accumulates all integers 1..n using 'List'
let accumulateUsingList n =
List.init (n + 1) id
|> List.sum
// Accumulates all integers 1..n using 'Seq'
let accumulateUsingSeq n =
Seq.init (n + 1) id
|> Seq.sum
// Accumulates all integers 1..n using 'for-expression'
let accumulateUsingFor n =
let mutable sum = 0
for i = 1 to n do
sum <- sum + i
sum
// Accumulates all integers 1..n using 'foreach-expression' over range
let accumulateUsingForEach n =
let mutable sum = 0
for i in 1..n do
sum <- sum + i
sum
// Accumulates all integers 1..n using 'foreach-expression' over list range
let accumulateUsingForEachOverList n =
let mutable sum = 0
for i in [1..n] do
sum <- sum + i
sum
// Accumulates every second integer 1..n using 'foreach-expression' over range
let accumulateUsingForEachStep2 n =
let mutable sum = 0
for i in 1..2..n do
sum <- sum + i
sum
// Accumulates all 64 bit integers 1..n using 'foreach-expression' over range
let accumulateUsingForEach64 n =
let mutable sum = 0L
for i in 1L..int64 n do
sum <- sum + i
sum |> int
// Accumulates all integers n..1 using 'for-expression' in reverse order
let accumulateUsingReverseFor n =
let mutable sum = 0
for i = n downto 1 do
sum <- sum + i
sum
// Accumulates all 64 integers n..1 using 'tail-recursion' in reverse order
let accumulateUsingReverseTailRecursion n =
let rec loop sum i =
if i > 0 then
loop (sum + i) (i - 1)
else
sum
loop 0 n
我们假设结果是相同的（除了使用 2 的增量的函数之一）但是性能有差异。为了测量这个，定义了以下功能：
let testRun (path : string) =
use testResult = new System.IO.StreamWriter (path)
let write (l : string) = testResult.WriteLine l
let writef fmt = FSharp.Core.Printf.kprintf write fmt
write "Name\tTotal\tOuter\tInner\tCC0\tCC1\tCC2\tTime\tResult"
// total is the total number of iterations being executed
let total = 10000000
// outers let us variate the relation between the inner and outer loop
// this is often useful when the algorithm allocates different amount of memory
// depending on the input size. This can affect cache locality
let outers = [| 1000; 10000; 100000 |]
for outer in outers do
let inner = total / outer
// multiplier is used to increase resolution of certain tests that are significantly
// faster than the slower ones
let testCases =
[|
// Name of test multiplier action
"List" , 1 , accumulateUsingList
"Seq" , 1 , accumulateUsingSeq
"for-expression" , 100 , accumulateUsingFor
"foreach-expression" , 100 , accumulateUsingForEach
"foreach-expression over List" , 1 , accumulateUsingForEachOverList
"foreach-expression increment of 2" , 1 , accumulateUsingForEachStep2
"foreach-expression over 64 bit" , 1 , accumulateUsingForEach64
"reverse for-expression" , 100 , accumulateUsingReverseFor
"reverse tail-recursion" , 100 , accumulateUsingReverseTailRecursion
|]
for name, multiplier, a in testCases do
System.GC.Collect (2, System.GCCollectionMode.Forced, true)
let cc g = System.GC.CollectionCount g
printfn "Accumulate using %s with outer=%d and inner=%d ..." name outer inner
// Collect collection counters before test run
let pcc0, pcc1, pcc2 = cc 0, cc 1, cc 2
let ms, result = time (outer*multiplier) (fun () -> a inner)
let ms = (float ms / float multiplier)
// Collect collection counters after test run
let acc0, acc1, acc2 = cc 0, cc 1, cc 2
let cc0, cc1, cc2 = acc0 - pcc0, acc1 - pcc1, acc1 - pcc1
printfn " ... took: %f ms, GC collection count %d,%d,%d and produced %A" ms cc0 cc1 cc2 result
writef "%s\t%d\t%d\t%d\t%d\t%d\t%d\t%f\t%d" name total outer inner cc0 cc1 cc2 ms result
在 .NET 4.5.2 x64 上运行时的测试结果：
我们看到了巨大的差异，一些结果出乎意料地糟糕。
让我们来看看坏情况：
名单
// Accumulates all integers 1..n using 'List'
let accumulateUsingList n =
List.init (n + 1) id
|> List.sum
这里发生的是一个包含所有整数的完整列表 1..n 是使用总和创建和减少的。这应该比在范围内迭代和累积更昂贵，它似乎比 for 循环慢约 42 倍。
此外，我们可以看到 GC 在测试运行期间运行了大约 100 倍，因为代码分配了大量对象。这也花费了 CPU。
SEQ
// Accumulates all integers 1..n using 'Seq'
let accumulateUsingSeq n =
Seq.init (n + 1) id
|> Seq.sum
Seq 版本没有分配一个完整的 List 所以有点令人惊讶的是这比 for 循环慢〜270 倍。此外，我们看到 GC 执行了 661x。
当每个项目的工作量非常小时（在这种情况下聚合两个整数），Seq 效率很低。
关键是不要永远不要使用 Seq。重点是测量。
（ manofstick 编辑： Seq.init 是这个严重性能问题的罪魁祸首。使用表达 { 0 .. n } 而不是 Seq.init (n+1) id 更有效。当这个 PR 合并和释放时，这将变得更有效。即使在释放之后，原始 Seq.init ... |> Seq.sum 仍然会很慢，但有点反直觉，Seq.init ... |> Seq.map id |> Seq.sum 会很快。这是为了保持与 Seq.inits 实现的向后兼容性，这不是最初计算 Current，而是将它们包含在 Lazy 对象中 - 尽管这也应该是由于这个 PR， 表现要好一点 。编辑注意：对不起这是一种漫无边际的笔记，但我不希望人们在改进即将来临时被推迟 Seq …… 当那个时代到来时，更新此页面上的图表会更好。 ）
foreach-expression over List
// Accumulates all integers 1..n using 'foreach-expression' over range
let accumulateUsingForEach n =
let mutable sum = 0
for i in 1..n do
sum <- sum + i
sum
// Accumulates all integers 1..n using 'foreach-expression' over list range
let accumulateUsingForEachOverList n =
let mutable sum = 0
for i in [1..n] do
sum <- sum + i
sum
这两个功能之间的差异非常微妙，但性能差异不大，约为 76 倍。为什么？让我们对坏代码进行逆向工程：
public static int accumulateUsingForEach(int n)
{
int sum = 0;
int i = 1;
if (n >= i)
{
do
{
sum += i;
i++;
}
while (i != n + 1);
}
return sum;
}
public static int accumulateUsingForEachOverList(int n)
{
int sum = 0;
FSharpList<int> fSharpList = SeqModule.ToList<int>(Operators.CreateSequence<int>(Operators.OperatorIntrinsics.RangeInt32(1, 1, n)));
for (FSharpList<int> tailOrNull = fSharpList.TailOrNull; tailOrNull != null; tailOrNull = fSharpList.TailOrNull)
{
int i = fSharpList.HeadOrDefault;
sum += i;
fSharpList = tailOrNull;
}
return sum;
}
accumulateUsingForEach 作为一个有效的 while 循环实现，但 for i in [1..n] 被转换为：
FSharpList<int> fSharpList =
SeqModule.ToList<int>(
Operators.CreateSequence<int>(
Operators.OperatorIntrinsics.RangeInt32(1, 1, n)));
这意味着首先我们在 1..n 上创建一个 Seq，然后最终调用 ToList。
昂贵。
foreach-expression 增量为 2
// Accumulates all integers 1..n using 'foreach-expression' over range
let accumulateUsingForEach n =
let mutable sum = 0
for i in 1..n do
sum <- sum + i
sum
// Accumulates every second integer 1..n using 'foreach-expression' over range
let accumulateUsingForEachStep2 n =
let mutable sum = 0
for i in 1..2..n do
sum <- sum + i
sum
这两个功能之间的差异再次微妙，但性能差异是残酷的：~25 倍
让我们再次运行 ILSpy：
public static int accumulateUsingForEachStep2(int n)
{
int sum = 0;
IEnumerable<int> enumerable = Operators.OperatorIntrinsics.RangeInt32(1, 2, n);
foreach (int i in enumerable)
{
sum += i;
}
return sum;
}
在 1..2..n 上创建了 Seq，然后我们使用枚举器迭代 Seq。
我们期待 F# 创建这样的东西：
public static int accumulateUsingForEachStep2(int n)
{
int sum = 0;
for (int i = 1; i < n; i += 2)
{
sum += i;
}
return sum;
}
但是，F# 编译器仅支持增加 1 的 int32 范围内的高效 for 循环。对于所有其他情况，它会回落到 Operators.OperatorIntrinsics.RangeInt32。这将解释下一个令人惊讶的结果
foreach-expression 超过 64 位
// Accumulates all 64 bit integers 1..n using 'foreach-expression' over range
let accumulateUsingForEach64 n =
let mutable sum = 0L
for i in 1L..int64 n do
sum <- sum + i
sum |> int
这比 for 循环慢约 47 倍，唯一的区别是我们迭代 64 位整数。ILSpy 向我们展示了原因：
public static int accumulateUsingForEach64(int n)
{
long sum = 0L;
IEnumerable<long> enumerable = Operators.OperatorIntrinsics.RangeInt64(1L, 1L, (long)n);
foreach (long i in enumerable)
{
sum += i;
}
return (int)sum;
}
F# 只支持 int32 号码的有效 for 循环，它必须使用 fallback Operators.OperatorIntrinsics.RangeInt64。
其他情况大致类似：
对于更大的测试运行，性能下降的原因是调用 action 的开销正在增长，因为我们在 tihuan 39 中的工作越来越少。
向 0 循环有时可以提供性能优势，因为它可能会节省 CPU 寄存器，但在这种情况下，CPU 有备用寄存器，所以它似乎没有什么区别。
结论
测量很重要，因为否则我们可能认为所有这些替代方案都是等效的，但有些替代方案比其他方案慢〜270 倍。
验证步骤涉及逆向工程可执行文件帮助我们解释为什么我们做了或没有得到我们期望的性能。此外，验证可以帮助我们预测在执行适当测量时太难的情况下的性能。
很难预测性能总是测量，总是验证你的性能假设。