Swiftパフォーマンス：map（）とreduce（）vs forループ

Question

私はSwiftにパフォーマンスクリティカルなコードを書いています。私が考えることのできるすべての最適化を実装し、Instrumentsのアプリケーションをプロファイリングした後、Floatの配列に対してCPUサイクルの大部分がmap()とreduce()の演算を実行するのに費やされることに気付きました。ですから、私はmapとreduceのすべてのインスタンスを古き良きのforループに置き換えました。と私の驚きに... forループははるかに、はるかに速かった！

これに少し戸惑って、私はいくつかのラフなベンチマークを行うことにしました。

// Populate array with 1,000,000,000 random numbers 
var array = [Float](count: 1_000_000_000, repeatedValue: 0) 
for i in 0..<array.count { 
    array[i] = Float(random()) 
} 
let start = NSDate() 
// Construct a new array, with each element from the original multiplied by 5 
let output = array.map({ (element) -> Float in 
    return element * 5 
}) 
// Log the elapsed time 
let elapsed = NSDate().timeIntervalSinceDate(start) 
print(elapsed) 

と同等forループの実装：20.1秒：mapため

var output = [Float]() 
for element in array { 
    output.append(element * 5) 
} 

の平均実行時間つのテストでは、私はそうのようないくつかの簡単な計算を実行した後にfloatの配列を返しmapました。 forループの平均実行時間：11.2秒結果は、浮動小数点数の代わりに整数を使用して同様でした。

Swiftのreduceのパフォーマンスをテストするために同様のベンチマークを作成しました。今回、reduceとforループは、1つの大きな配列の要素を合計するとほぼ同じ性能を達成しました。しかし、ときに、このようなIループテストを10万回：対

// Populate array with 1,000,000 random numbers 
var array = [Float](count: 1_000_000, repeatedValue: 0) 
for i in 0..<array.count { 
    array[i] = Float(random()) 
} 
let start = NSDate() 
// Perform operation 100,000 times 
for _ in 0..<100_000 { 
    let sum = array.reduce(0, combine: {$0 + $1}) 
} 
// Log the elapsed time 
let elapsed = NSDate().timeIntervalSinceDate(start) 
print(elapsed) 

：forループは（明らかに）0.000003秒かかりながら

for _ in 0..<100_000 { 
    var sum: Float = 0 
    for element in array { 
     sum += element 
    } 
} 

reduce方法は29秒かかります。

もちろん、私はコンパイラの最適化の結果として最後のテストを無視する準備はできていますが、コンパイラがループとSwiftの組み込みの配列メソッドに対して異なる方法で最適化する方法についていくつかの洞察を与えるかもしれません。すべてのテストは、2.5 GHz i7 MacBook Proで-O最適化を使用して実行されたことに注意してください。結果は配列サイズと反復回数によって異なりますが、forループは他の方法よりも常に1.5倍以上、時には10倍以上パフォーマンスが優れています。

ここで私はスウィフトのパフォーマンスについて少し難解です。そのような操作を実行するための単純なアプローチよりも組み込みのArrayメソッドが高速であるべきではありませんか？おそらく私よりも低レベルの知識を持つ誰かが、その状況を明らかにすることができます。

Answer 1

組み込みの配列メソッドは、このような操作を行うための単純なアプローチよりも高速ではいけませんか？おそらく私よりも低レベルの知識を持つ誰かが、その状況を明らかにすることができます。

私はちょうど質問のこの部分を（必ずしも必要ではない）概念レベル（Swiftのオプティマイザの本質をほとんど理解していない状態）から取り除こうとしています。 Swiftのオプティマイザの本質を深く根づかれた知識よりも、コンパイラ設計とコンピュータアーキテクチャのバックグラウンドからより多くのものが得られています。入力としてmapとreduce受諾機能などの機能を備えたオーバーヘッド

を呼び出す

、それはそれを一つの方法を置くことをオプティマイザに大きなひずみを配置します。このようなケースでは、非常に積極的な最適化には至っていないのですが、具体的にはmapの実装と提供したクロージャの間を常に行き来し、同様にこれらの異なるコードの枝を介してデータを送信します、典型的には）。

この種の分岐/呼び出しのオーバーヘッドは、特にSwiftの閉鎖の柔軟性（不可能ではないが概念的には難しい）を考慮すると、オプティマイザが排除することは非常に困難です。 C++オプティマイザは関数オブジェクトの呼び出しをインライン化できますが、コンパイラが渡す関数オブジェクトのタイプごとにmapの新しい命令セットを効果的に生成する必要がある場合は、コード生成に使用される関数テンプレートを示すプログラマの）。

あなたのハンド・ロール・ループがより高速に実行できることを見いだすことは、驚くべきことではありません。オプティマイザに大きな負担をかけることはありません。私は、ベンダーがループを並列化するようなことをすることができるため、これらの高次関数はより高速になるはずであると述べている人もいますが、ループを効果的に並列化するためには、オプティマイザは、ネストされた関数呼び出しを手作業のループと同じくらい安くなるまでインライン化することができます。さもなければ、あなたが渡す関数/クロージャの実装は、map/reduceのような関数に対して効果的に不透明になるでしょう：それらは呼び出すことができ、そうするオーバーヘッドを支払うだけで、副作用の性質について何も仮定することができないので、そうすることでスレッドの安全性。

もちろん、これはすべて概念的です。スウィフトは将来的にこれらのケースを最適化することができるかもしれませんし、既にこれを行うこともできます（-Ofastを参照してください）。安全のためのコスト）。しかし、オプティマイザには、この種の機能をハンド・ロール・ループで使用することに重い負担がかかります。最初のベンチマークで見た時差は、この付加的な呼び出しのオーバーヘッドで期待します。最適な方法はアセンブリを見て、さまざまな最適化フラグを試すことです。このような関数の使用を阻止することはありません

標準機能

。彼らは意図をより簡潔に表現し、生産性を高めることができます。そして、それらに頼ることで、Swiftの将来のバージョンであなたのコードベースがより速くなることができます。しかし、必ずしも常に高速になるとは限りません。あなたがしたいことをより直接的に表現するより高いレベルのライブラリ関数がより速くなると考えるのは良い一般的なルールですが、信頼性の面で間違いを犯す方がはるかに優れているので、ここでは不確かなものではありません。 2番目のベンチマークについては

人工ベンチマーク

、それはほぼ確実にユーザ出力に影響を与える副作用を持たないコードを離れて最適化コンパイラの結果です。人工的なベンチマークは、無関係な副作用（ユーザーの出力に本質的に影響を与えない副作用）を排除するためにオプティマイザが行うことの結果として誤解を招く傾向があります。ベンチマークを実際にスキップするだけのオプティマイザの結果ではないので、ベンチマークを構築するときには注意が必要です。少なくとも、計算から集められた最終結果を出力するテストが必要です。

Answer 2

私はあなたの最初のテスト（map()対ループの中でappend()）について多くのことを言うことはできません あなたの結果を確認することができます。アペンドループを使用すると、アレイの作成後

output.reserveCapacity(array.count) 

を追加し、さらに高速 場合になります。アップルはここにあるものを改善できると思われます。 あなたはバグレポートを提出するかもしれません。計算結果は全く使用されないので

for _ in 0..<100_000 { 
    var sum: Float = 0 
    for element in array { 
     sum += element 
    } 
} 

コンパイラで

は（おそらく）ループ全体 を除去します。 同様の最適化が

for _ in 0..<100_000 { 
    let sum = array.reduce(0, combine: {$0 + $1}) 
} 

では発生しませんが、閉鎖してreduce()を呼び出すと、任意の副作用を持っているか、いない場合、それはより困難かを決定するだろう、なぜ私は推測することができます。

テストコードは、両方の変異体は私のテストでは約10秒かかり、その後と印刷合計

do { 
    var total = Float(0.0) 
    let start = NSDate() 
    for _ in 0..<100_000 { 
     total += array.reduce(0, combine: {$0 + $1}) 
    } 
    let elapsed = NSDate().timeIntervalSinceDate(start) 
    print("sum with reduce:", elapsed) 
    print(total) 
} 

do { 
    var total = Float(0.0) 
    let start = NSDate() 
    for _ in 0..<100_000 { 
     var sum = Float(0.0) 
     for element in array { 
      sum += element 
     } 
     total += sum 
    } 
    let elapsed = NSDate().timeIntervalSinceDate(start) 
    print("sum with loop:", elapsed) 
    print(total) 
} 

を計算するために若干変更された場合。