日付 - Swift Betaのパフォーマンス:配列の並べ替え




perl 配列 日付 ソート (6)

私はSwift Betaでアルゴリズムを実装していて、パフォーマンスが非常に悪いことに気付きました。 深く掘り下げた後、ボトルネックの1つは配列を並べ替えるだけの単純なものであることに気付きました。 関連する部分はここにあります:

let n = 1000000
var x =  [Int](repeating: 0, count: n)
for i in 0..<n {
    x[i] = random()
}
// start clock here
let y = sort(x)
// stop clock here

C ++では、私のコンピュータで同様の操作が0.06秒かかる。

Pythonでは0.6秒しかかかりません(整数のリストの場合はトリックなし、ちょうどy = sorted(x))。

Swiftでは、次のコマンドでコンパイルすると6秒かかる:

xcrun swift -O3 -sdk `xcrun --show-sdk-path --sdk macosx`

そして、次のコマンドでコンパイルすると88秒もかかる。

xcrun swift -O0 -sdk `xcrun --show-sdk-path --sdk macosx`

"Release"と "Debug"ビルドのXcodeのタイミングは似ています。

ここで何が間違っていますか? 私はC ++と比較してパフォーマンスの低下を理解することができましたが、純粋なPythonと比較して10倍の速度低下はありません。

編集: mweathersは、 -O3-Ofast変更すると、このコードがC ++バージョンとほぼ同じ速度で実行されることに気付きました! しかし、 -Ofastは言語のセマンティクスを-Ofast変更します。私のテストでは、整数オーバーフローと配列インデックスのオーバーフローのチェックを無効にしました 。 たとえば、 -Ofastすると、次のSwiftコードがクラッシュすることなく静かに実行されます(そして、いくつかのガベージが印刷されます)。

let n = 10000000
print(n*n*n*n*n)
let x =  [Int](repeating: 10, count: n)
print(x[n])

ですから、 -Ofastは私たちが望むものではありません。 スウィフトの全体のポイントは、安全ネットが設置されていることです。 もちろん、セーフティネットは性能にある程度の影響を与えますが、プログラムを100倍遅くするべきではありません。 Javaはすでに配列境界をチェックしており、典型的なケースでは減速は2よりずっと小さい要素であることを忘れないでください。そして、ClangとGCC -ftrapv 、(符号付きの)整数オーバーフローをチェックするための-ftrapvがあります。 。

したがって、疑問:セーフティネットを失うことなくスウィフトで合理的なパフォーマンスを得るにはどうすればよいでしょうか?

編集2:私はベンチマークをしました。

for i in 0..<n {
    x[i] = x[i] ^ 12345678
}

(ここでxor演算があるので、アセンブリコード内の関連するループをより簡単に見つけることができます。)チェックするのが簡単な操作を選択しようとしましたが、関連するチェックを必要としないという意味で「無害」整数オーバーフローまで)。

ここでも-O3-Ofast間には大きな違いがあり-Ofast 。 だから私はアセンブリコードを見ていた:

  • -Ofast私は私が期待するものをかなり得る。 関連する部分は、5つの機械語命令を含むループです。

  • -O3では私は想像以上のものを手に入れました。 内部ループは、88行のアセンブリコードにまたがっています。 私はすべてを理解しようとはしませんでしたが、最も疑わしい部分は "callq _swift_retain"の13回の呼び出しと "callq _swift_release"の13回の呼び出しです。 つまり、内側ループの26個のサブルーチン呼び出しです!

編集3:コメントで、Ferruccioは組み込み関数(ソートなど)に頼らないという意味で公平なベンチマークを求めました。 私は次のプログラムはかなり良い例だと思う:

let n = 10000
var x = [Int](repeating: 1, count: n)
for i in 0..<n {
    for j in 0..<n {
        x[i] = x[j]
    }
}

算術演算がないので、整数のオーバーフローを心配する必要はありません。 私たちが行う唯一のことは、配列の参照がたくさんあることです。 そして結果はここにあります - スウィフト-O3は-Ofastに比べて約500倍のファクターで失われます:

  • C ++ -O3: 0.05秒
  • C ++ -O0:0.4秒
  • Java: 0.2秒
  • PythonでのPython:0.5秒
  • Python: 12秒
  • スウィフト高速:0.05秒
  • スウィフト-O3: 23秒
  • スウィフト-O0:443秒

(コンパイラが無意味なループを完全に最適化するのであれば、 x[i] ^= x[j]x[0]を出力するprint文を追加することができます。タイミングは非常に似ています。)

そして、はい、ここのPythonの実装はintのリストと入れ子になったforループを持つ愚かな純粋なPythonの実装でした。 最適化されていないSwiftよりもはるかに遅くなるはずです。 Swiftや配列のインデックス作成では、何かが真剣に壊れているようです。

編集4:これらの問題(他のパフォーマンスの問題と同様)は、Xcode 6 beta 5で修正されているようです。

並べ替えのために、私は今、次のタイミングを持っています:

  • clang ++ -O3:0.06秒
  • swiftc高速:0.1秒
  • スイフト-O:0.1秒
  • スイフト:4秒

ネストされたループの場合:

  • clang ++ -O3:0.06秒
  • swiftc高速:0.3秒
  • swiftc -O:0.4秒
  • swiftc:540秒

安全でないものを使用する理由はもうないと思われます。 -Ofast-Ounchecked ); プレーン-Oは同じように良いコードを生成します。


Swiftアレイの性能再考:

SwiftとC / Objective-Cを比較した私自身のベンチマークを書いた。 私のベンチマークは素数を計算します。 以前の素数の配列を使用して、新しい候補のそれぞれに素因数を求めるので、かなり高速です。 しかし、それは配列の読み込みのトーンを行い、配列への書き込みは少なくなります。

私はもともとSwift 1.2に対してこのベンチマークを行った。 私はプロジェクトを更新し、それをSwift 2.0に対して実行することに決めました。

このプロジェクトでは、通常のswift配列を使用するか、配列セマンティクスを使用してSwiftの安全でないメモリバッファを使用するかを選択できます。

C / Objective-Cでは、NSArraysまたはC mallocの配列を使用することができます。

テスト結果は、最速で最小のコード最適化([-0s])または最速で積極的([-fast])最適化とかなり類似しているようです。

C / Objective-Cのパフォーマンスはやや遅くなるのに対し、Swift 2.0のパフォーマンスは、コード最適化をオフにしてもひどいです。

要点は、Cのmallocの配列ベースの計算が最も速い、わずかなマージンであることです

最速で最小のコード最適化を使用する場合、安全でないバッファを使用するSwiftは、C mallocの配列より約1.19X〜1.20X長くなります。 速い、積極的な最適化(SwiftはCより1.16倍長く1.18倍かかる

通常のSwift配列を使用すると、Cとの差はわずかに大きくなります。 (スイフトは〜1.22〜1.23時間かかる)

通常のSwiftアレイは、Swift 1.2 / Xcode 6よりもはるかに高速です。その性能は、安全ではないメモリバッファを使用するSwiftの安全でないバッファベースの配列にはほど遠く、これ以上問題にはならないようです。

ところで、Objective-C NSArrayのパフォーマンスが悪くなります。 両方の言語でネイティブコンテナオブジェクトを使用する場合、Swiftは劇的に高速です。

あなたはSwiftPerformanceBenchmarkでgithubで私のプロジェクトをチェックアウトすることができます

統計情報を簡単に収集できるシンプルなUIを備えています。

SwiftではソートがCよりもやや速いように見えるのは興味深いですが、この素数アルゴリズムはSwiftでもまだまだ高速です。


Xcode 7 Fast, Whole Module Optimization有効にすることができます。 これにより、すぐにパフォーマンスが向上します。


The Swift Programming Language

Sort関数Swiftの標準ライブラリにはsortと呼ばれる関数が用意されています。この関数は、提供するソートクロージャの出力に基づいて、既知の型の値の配列をソートします。 並べ替え処理が完了すると、sort関数は古い要素と同じ型とサイズの新しい配列を返します。要素の配列は正しいソート順になります。

sort関数には2つの宣言があります。

比較クロージャを指定できるデフォルトの宣言:

func sort<T>(array: T[], pred: (T, T) -> Bool) -> T[]

また、単一のパラメータ(配列)しか取らず、「より小さいコンパレータを使用するためにハードコードされた」2番目の宣言です。

func sort<T : Comparable>(array: T[]) -> T[]

Example:
sort( _arrayToSort_ ) { $0 > $1 }

私は、クロージャーが追加された状態で遊び場にコードの修正版をテストしたので、関数を少し詳しく監視することができました.nを1000に設定すると、クロージャーは約11,000回呼び出されました。

let n = 1000
let x = Int[](count: n, repeatedValue: 0)
for i in 0..n {
    x[i] = random()
}
let y = sort(x) { $0 > $1 }

それは効率的な関数ではありません、私はより良いソート関数の実装を使用することをお勧めします。

編集:

私はQuicksort wikipediaのページを見て、Swiftの実装を書いた。 私が(遊び場で)使った完全なプログラムはここにあります

import Foundation

func quickSort(inout array: Int[], begin: Int, end: Int) {
    if (begin < end) {
        let p = partition(&array, begin, end)
        quickSort(&array, begin, p - 1)
        quickSort(&array, p + 1, end)
    }
}

func partition(inout array: Int[], left: Int, right: Int) -> Int {
    let numElements = right - left + 1
    let pivotIndex = left + numElements / 2
    let pivotValue = array[pivotIndex]
    swap(&array[pivotIndex], &array[right])
    var storeIndex = left
    for i in left..right {
        let a = 1 // <- Used to see how many comparisons are made
        if array[i] <= pivotValue {
            swap(&array[i], &array[storeIndex])
            storeIndex++
        }
    }
    swap(&array[storeIndex], &array[right]) // Move pivot to its final place
    return storeIndex
}

let n = 1000
var x = Int[](count: n, repeatedValue: 0)
for i in 0..n {
    x[i] = Int(arc4random())
}

quickSort(&x, 0, x.count - 1) // <- Does the sorting

for i in 0..n {
    x[i] // <- Used by the playground to display the results
}

これをn = 1000で使用すると、私は

  1. quickSort()は約650回呼び出され、
  2. 約6000回のスワップが行われ、
  3. 約10,000の比較があります

それは、組み込みのソートメソッドは、(または近くにある)クイックソートと思われ、本当に遅いです...


TL; DR :はい、スウィフト言語の実装は現在のところ遅いです。 速く、数字の(そして他の種類のコード、おそらく)コードが必要な場合は、別のコードと一緒に行ってください。 将来、あなたの選択を再評価する必要があります。 それは、しかし、より高いレベルで書かれているほとんどのアプリケーションコードのために十分かもしれません。

私がSILとLLVM IRで見てきたことから、 Clang (Objective-C用)に実装されているかもしれない保持とリリースを取り除くための最適化が必要だと思われますが、まだ移植していません。 これは私が行っている理論です(今のところ、Clangが何かしていることを確認する必要があります)。この質問の最後のテストケースでプロファイラを実行すると、この "かなり"結果が得られます。

-Ofastは完全に安全ではなく、言語の意味を変えます。 私にとっては、「それを使うならば、別の言語を使う」段階にあります。 私は後でそれが変更された場合、その選択肢を再評価します。

-O3swift_retainswift_release束を私たちに与えてくれ-O3 。正直なところ、この例ではそうは見えません。 オプティマイザは配列に関する情報の大部分を知っており、(少なくとも)その配列への強い参照があることを知っているため、オプティマイザはAFAICTを省略しました(ほとんど)。

オブジェクトを解放する可能性のある関数を呼び出していなくても、より多くの保持を行うべきではありません。 私は、配列コンストラクターが、求められたものよりも小さい配列を返すことはできないと考えています。つまり、排出された多くのチェックが役に立たないということです。 また、整数が決して10kを超えることはないことを知っているので、オーバーフローチェック最適化することできます( -Ofastではなく、言語のセマンティクスのために) -Ofast変更したり、 〜10kはInt型にとって安全です)。

しかし、コンパイラは配列や配列要素をunboxすることができないかもしれません。なぜなら、外部関数であるsort()渡されているため、引数が必要です。 これにより、 Int値を間接的に使用する必要があります。これにより、少し遅くなります。 sort()ジェネリック関数(マルチメソッドではない)がコンパイラで利用可能で、インライン展開されている場合、これは変わる可能性があります。

これは非常に新しい(公開された)言語であり、Swift言語に関わる人々がフィードバックを求めており、言語が終わっていないと言いますので、私は多くの変更を行っていると考えています。変化する。

使用されるコード:

import Cocoa

let swift_start = NSDate.timeIntervalSinceReferenceDate();
let n: Int = 10000
let x = Int[](count: n, repeatedValue: 1)
for i in 0..n {
    for j in 0..n {
        let tmp: Int = x[j]
        x[i] = tmp
    }
}
let y: Int[] = sort(x)
let swift_stop = NSDate.timeIntervalSinceReferenceDate();

println("\(swift_stop - swift_start)s")

PS:私はObjective-Cの専門家でも、 Cocoa 、Objective-C、Swiftランタイムのすべての施設でもありません。 私も書いていないことをいくつか仮定しているかもしれません。


私はこれを楽しみのために見てみることにしました、そして、私が得るタイミングはここにあります:

Swift 4.0.2           :   0.83s (0.74s with `-Ounchecked`)
C++ (Apple LLVM 8.0.0):   0.74s

迅速

// Swift 4.0 code
import Foundation

func doTest() -> Void {
    let arraySize = 10000000
    var randomNumbers = [UInt32]()

    for _ in 0..<arraySize {
        randomNumbers.append(arc4random_uniform(UInt32(arraySize)))
    }

    let start = Date()
    randomNumbers.sort()
    let end = Date()

    print(randomNumbers[0])
    print("Elapsed time: \(end.timeIntervalSince(start))")
}

doTest()

結果:

Swift 1.1

xcrun swiftc --version
Swift version 1.1 (swift-600.0.54.20)
Target: x86_64-apple-darwin14.0.0

xcrun swiftc -O SwiftSort.swift
./SwiftSort     
Elapsed time: 1.02204304933548

スウィフト1.2

xcrun swiftc --version
Apple Swift version 1.2 (swiftlang-602.0.49.6 clang-602.0.49)
Target: x86_64-apple-darwin14.3.0

xcrun -sdk macosx swiftc -O SwiftSort.swift
./SwiftSort     
Elapsed time: 0.738763988018036

Swift 2.0

xcrun swiftc --version
Apple Swift version 2.0 (swiftlang-700.0.59 clang-700.0.72)
Target: x86_64-apple-darwin15.0.0

xcrun -sdk macosx swiftc -O SwiftSort.swift
./SwiftSort     
Elapsed time: 0.767306983470917

-Ouncheckedコンパイルすると同じパフォーマンスになるよう-Ounchecked

スウィフト3.0

xcrun swiftc --version
Apple Swift version 3.0 (swiftlang-800.0.46.2 clang-800.0.38)
Target: x86_64-apple-macosx10.9

xcrun -sdk macosx swiftc -O SwiftSort.swift
./SwiftSort     
Elapsed time: 0.939633965492249

xcrun -sdk macosx swiftc -Ounchecked SwiftSort.swift
./SwiftSort     
Elapsed time: 0.866258025169373

Swift 2.0からSwift 3.0へのパフォーマンスの回帰があるようですが、私は-O-Ounchecked違いも初めて見ています。

Swift 4.0

xcrun swiftc --version
Apple Swift version 4.0.2 (swiftlang-900.0.69.2 clang-900.0.38)
Target: x86_64-apple-macosx10.9

xcrun -sdk macosx swiftc -O SwiftSort.swift
./SwiftSort     
Elapsed time: 0.834299981594086

xcrun -sdk macosx swiftc -Ounchecked SwiftSort.swift
./SwiftSort     
Elapsed time: 0.742045998573303

Swift 4は、 -O-Ounchecked間のギャップを維持しながら、パフォーマンスを再び向上させます。 -O -whole-module-optimization-O -whole-module-optimizationなかった。

C ++

#include <chrono>
#include <iostream>
#include <vector>
#include <cstdint>
#include <stdlib.h>

using namespace std;
using namespace std::chrono;

int main(int argc, const char * argv[]) {
    const auto arraySize = 10000000;
    vector<uint32_t> randomNumbers;

    for (int i = 0; i < arraySize; ++i) {
        randomNumbers.emplace_back(arc4random_uniform(arraySize));
    }

    const auto start = high_resolution_clock::now();
    sort(begin(randomNumbers), end(randomNumbers));
    const auto end = high_resolution_clock::now();

    cout << randomNumbers[0] << "\n";
    cout << "Elapsed time: " << duration_cast<duration<double>>(end - start).count() << "\n";

    return 0;
}

結果:

アップルクライン6.0

clang++ --version
Apple LLVM version 6.0 (clang-600.0.54) (based on LLVM 3.5svn)
Target: x86_64-apple-darwin14.0.0
Thread model: posix

clang++ -O3 -std=c++11 CppSort.cpp -o CppSort
./CppSort     
Elapsed time: 0.688969

Apple Clang 6.1.0

clang++ --version
Apple LLVM version 6.1.0 (clang-602.0.49) (based on LLVM 3.6.0svn)
Target: x86_64-apple-darwin14.3.0
Thread model: posix

clang++ -O3 -std=c++11 CppSort.cpp -o CppSort
./CppSort     
Elapsed time: 0.670652

Apple Clang 7.0.0

clang++ --version
Apple LLVM version 7.0.0 (clang-700.0.72)
Target: x86_64-apple-darwin15.0.0
Thread model: posix

clang++ -O3 -std=c++11 CppSort.cpp -o CppSort
./CppSort     
Elapsed time: 0.690152

Apple Clang 8.0.0

clang++ --version
Apple LLVM version 8.0.0 (clang-800.0.38)
Target: x86_64-apple-darwin15.6.0
Thread model: posix

clang++ -O3 -std=c++11 CppSort.cpp -o CppSort
./CppSort     
Elapsed time: 0.68253

Apple Clang 9.0.0

clang++ --version
Apple LLVM version 9.0.0 (clang-900.0.38)
Target: x86_64-apple-darwin16.7.0
Thread model: posix

clang++ -O3 -std=c++11 CppSort.cpp -o CppSort
./CppSort     
Elapsed time: 0.736784

評決

この記事の執筆時点では、Swiftのソートは高速ですが、上記のコンパイラとライブラリを使用して-Oでコンパイルした場合、C ++のように速くはありません。 -Ouncheckedでは、Swift 4.0.2とApple LLVM 9.0.0ではC ++ほど高速です。


func partition(inout list : [Int], low: Int, high : Int) -> Int {
    let pivot = list[high]
    var j = low
    var i = j - 1
    while j < high {
        if list[j] <= pivot{
            i += 1
            (list[i], list[j]) = (list[j], list[i])
        }
        j += 1
    }
    (list[i+1], list[high]) = (list[high], list[i+1])
    return i+1
}

func quikcSort(inout list : [Int] , low : Int , high : Int) {

    if low < high {
        let pIndex = partition(&list, low: low, high: high)
        quikcSort(&list, low: low, high: pIndex-1)
        quikcSort(&list, low: pIndex + 1, high: high)
    }
}

var list = [7,3,15,10,0,8,2,4]
quikcSort(&list, low: 0, high: list.count-1)

var list2 = [ 10, 0, 3, 9, 2, 14, 26, 27, 1, 5, 8, -1, 8 ]
quikcSort(&list2, low: 0, high: list2.count-1)

var list3 = [1,3,9,8,2,7,5]
quikcSort(&list3, low: 0, high: list3.count-1) 

これはクイックソート - Githubサンプルクイックソートについての私のブログです

「Partitioning the list」のLomutoのパーティショニングアルゴリズムをご覧ください。 スウィフトで書かれた







compiler-optimization