衡量並驗證你的績效假設
這個例子是用 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 倍。
驗證步驟涉及逆向工程可執行檔案幫助我們解釋為什麼我們做了或沒有得到我們期望的效能。此外，驗證可以幫助我們預測在執行適當測量時太難的情況下的效能。
很難預測效能總是測量，總是驗證你的效能假設。