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

Question

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`

Xcode の「リリース」ビルドと「デバッグ」ビルドのタイミングは似ています。

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

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

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

それは私-Ofastたちが望んでいることではありません。Swift の要点は、セーフティネットが整っていることです。もちろん、セーフティネットはパフォーマンスにある程度の影響を与えますが、プログラムを 100 倍遅くするべきではありません。Java はすでに配列の境界をチェックしていることを思い出してください。典型的なケースでは、速度低下は 2 倍未満です。また、Clang と GCC-ftrapvでは、(符号付き) 整数のオーバーフローをチェックしていますが、それほど遅くはありません。

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

編集2：次の行に沿った非常に単純なループで、さらにベンチマークを行いました

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

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

-O3ここでも、との間でパフォーマンスに大きな違いがありました-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]
    }
}

算術がないので、整数オーバーフローを心配する必要はありません。私たちがする唯一のことは、たくさんの配列参照です。そして結果はここにあります — Swift -O3 は -Ofast と比較してほぼ 500 倍負けます:

C++ -O3: 0.05 秒
C++ -O0: 0.4 秒
Java: 0.2 秒
Python と PyPy: 0.5 秒
Python: 12 秒
Swift -Ofast: 0.05 秒
スイフト -O3: 23 秒
スイフト -O0: 443 秒

(コンパイラが無意味なループを完全に最適化するのではないかと懸念している場合は、それを egx[i] ^= x[j]に変更し、を出力する print ステートメントを追加できますx[0]。これは何も変更しません。タイミングは非常に似ています。)

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

編集 4:これらの問題 (およびその他のパフォーマンスの問題) は、Xcode 6 ベータ 5 で修正されたようです。

並べ替えについては、次のタイミングがあります。

clang++ -O3: 0.06 秒
swiftc -Ofast: 0.1 秒
swiftc -O: 0.1 秒
スイフト：4秒

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

clang++ -O3: 0.06 秒
swiftc -Ofast: 0.3 秒
swiftc -O: 0.4 秒
スイフト：540秒

-Ofastunsafe (別名-Ounchecked)を使用する理由はもうないようです。plain-Oも同様に優れたコードを生成します。

score 475 · Accepted Answer

tl;dr デフォルトのリリース最適化レベル [-O] を使用したこのベンチマークでは、Swift 1.0 は現在 C と同じくらい高速です。

Swift Beta のインプレースクイックソートを次に示します。

func quicksort_swift(inout a:CInt[], start:Int, end:Int) {
    if (end - start < 2){
        return
    }
    var p = a[start + (end - start)/2]
    var l = start
    var r = end - 1
    while (l <= r){
        if (a[l] < p){
            l += 1
            continue
        }
        if (a[r] > p){
            r -= 1
            continue
        }
        var t = a[l]
        a[l] = a[r]
        a[r] = t
        l += 1
        r -= 1
    }
    quicksort_swift(&a, start, r + 1)
    quicksort_swift(&a, r + 1, end)
}

そしてCでも同じ：

void quicksort_c(int *a, int n) {
    if (n < 2)
        return;
    int p = a[n / 2];
    int *l = a;
    int *r = a + n - 1;
    while (l <= r) {
        if (*l < p) {
            l++;
            continue;
        }
        if (*r > p) {
            r--;
            continue;
        }
        int t = *l;
        *l++ = *r;
        *r-- = t;
    }
    quicksort_c(a, r - a + 1);
    quicksort_c(l, a + n - l);
}

どちらも機能します：

var a_swift:CInt[] = [0,5,2,8,1234,-1,2]
var a_c:CInt[] = [0,5,2,8,1234,-1,2]

quicksort_swift(&a_swift, 0, a_swift.count)
quicksort_c(&a_c, CInt(a_c.count))

// [-1, 0, 2, 2, 5, 8, 1234]
// [-1, 0, 2, 2, 5, 8, 1234]

両方とも、書かれているのと同じプログラムで呼び出されます。

var x_swift = CInt[](count: n, repeatedValue: 0)
var x_c = CInt[](count: n, repeatedValue: 0)
for var i = 0; i < n; ++i {
    x_swift[i] = CInt(random())
    x_c[i] = CInt(random())
}

let swift_start:UInt64 = mach_absolute_time();
quicksort_swift(&x_swift, 0, x_swift.count)
let swift_stop:UInt64 = mach_absolute_time();

let c_start:UInt64 = mach_absolute_time();
quicksort_c(&x_c, CInt(x_c.count))
let c_stop:UInt64 = mach_absolute_time();

これは絶対時間を秒に変換します。

static const uint64_t NANOS_PER_USEC = 1000ULL;
static const uint64_t NANOS_PER_MSEC = 1000ULL * NANOS_PER_USEC;
static const uint64_t NANOS_PER_SEC = 1000ULL * NANOS_PER_MSEC;

mach_timebase_info_data_t timebase_info;

uint64_t abs_to_nanos(uint64_t abs) {
    if ( timebase_info.denom == 0 ) {
        (void)mach_timebase_info(&timebase_info);
    }
    return abs * timebase_info.numer  / timebase_info.denom;
}

double abs_to_seconds(uint64_t abs) {
    return abs_to_nanos(abs) / (double)NANOS_PER_SEC;
}

コンパイラの最適化レベルの概要は次のとおりです。

[-Onone] no optimizations, the default for debug.
[-O]     perform optimizations, the default for release.
[-Ofast] perform optimizations and disable runtime overflow checks and runtime type checks.

n=10_000の[-Onone]での時間 (秒) :

Swift:            0.895296452
C:                0.001223848

n=10_000に対する Swift の組み込み sort() は次のとおりです。

Swift_builtin:    0.77865783

n=10_000の[-O]は次のとおりです。

Swift:            0.045478346
C:                0.000784666
Swift_builtin:    0.032513488

ご覧のとおり、Swift のパフォーマンスは 20 倍向上しました。

mweathers ' answerによると、 [-Ofast]を設定すると実際の違いが生じ、n=10_000の場合は次のようになります。

Swift:            0.000706745
C:                0.000742374
Swift_builtin:    0.000603576

n=1_000_000の場合:

Swift:            0.107111846
C:                0.114957179
Swift_sort:       0.092688548

比較のために、これはn=1_000_000の[-Onone]を使用しています:

Swift:            142.659763258
C:                0.162065333
Swift_sort:       114.095478272

そのため、最適化を行わない Swift は、開発のこの段階では、このベンチマークで C よりもほぼ 1000 倍遅くなりました。一方、両方のコンパイラが [-Ofast] に設定されている場合、Swift は実際には、C よりわずかに優れていないとしても、少なくとも同等のパフォーマンスを発揮しました。

[-Ofast] は言語のセマンティクスを変更し、潜在的に安全でなくなることが指摘されています。これは、Apple が Xcode 5.0 リリースノートで述べていることです。

LLVM で利用可能な新しい最適化レベル -Ofast により、積極的な最適化が可能になります。-Ofast は、ほとんどのコードで安全な、主に浮動小数点演算のいくつかの保守的な制限を緩和します。これにより、コンパイラーのパフォーマンスが大幅に向上します。

彼らは皆それを支持しています。それが賢明かどうかは私にはわかりませんが、高精度の浮動小数点演算を行っておらず、整数またはプログラムで配列オーバーフローが発生する可能性があります。高いパフォーマンスとオーバーフローチェック/正確な演算が必要な場合は、別の言語を選択してください。

ベータ 3 アップデート:

n=10_000で[-O] :

Swift:            0.019697268
C:                0.000718064
Swift_sort:       0.002094721

一般的に、Swift は少し高速であり、Swift の組み込みソートが大幅に変更されたようです。

最終更新:

[-オノネ] :

Swift:   0.678056695
C:       0.000973914

[-O] :

Swift:   0.001158492
C:       0.001192406

[-未チェック] :

Swift:   0.000827764
C:       0.001078914

score 114 · Accepted Answer

TL;DR : はい、現時点で Swift 言語の実装だけが遅いです。高速な数値 (およびおそらくその他の種類のコード) のコードが必要な場合は、別のコードを使用してください。将来的には、選択を再評価する必要があります。ただし、より高いレベルで記述されたほとんどのアプリケーションコードには十分かもしれません。

SIL と LLVM IR で見たものから、保持とリリースを削除するために一連の最適化が必要なようです。これはClang (Objective-C 用) で実装される可能性がありますが、まだ移植されていません。この質問の最後のテストケースでプロファイラーを実行すると、この「かなりの」結果が得られるため、それが私が行っている理論です（今のところ... Clangがそれについて何かを行うことを確認する必要があります）。

-O3 での時間プロファイリング -Ofast でのタイムプロファイリング

他の多くの人が言ったように、-Ofast完全に安全ではなく、言語のセマンティクスを変更します。私にとっては、「それを使うなら他の言語を使えばいい」という段階です。その選択が変更された場合は、後で再評価します。

-O3正直なところ、この例では存在しないように見える多数のswift_retainand呼び出しが得られます。swift_releaseオプティマイザは、配列に関するほとんどの情報を知っており、(少なくとも) それへの強い参照があることを知っているので、AFAICT で (ほとんどの) それらを除外する必要があります。

オブジェクトを解放する可能性のある関数を呼び出していない場合でも、これ以上保持を発行するべきではありません。配列コンストラクターが要求されたものよりも小さい配列を返すことはできないと思います。つまり、発行された多くのチェックは役に立たないということです。また、整数が 10k を超えることは決してないことも認識しているため、オーバーフローチェックを最適化でき-Ofastます (奇妙さのためではなく、言語のセマンティクスのためです (他にその var を変更したりアクセスしたりすることはなく、合計すると 10k になります)タイプに対して安全ですInt）。

ただし、コンパイラは配列または配列要素をボックス化解除できない場合があります。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 ランタイムのすべての機能の専門家でもありません。また、私が書いていないことを想定している可能性もあります。

score 58 · Accepted Answer

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

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()

結果：

スイフト 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

スイフト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。

スイフト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た。

スイフト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

-OSwift 4 は、との間のギャップを維持しながら、再びパフォーマンスを向上させ-Ouncheckedます。-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

アップルクラン 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++ と同じくらい高速に見えます。

score 34 · Accepted Answer

からThe Swift Programming Language:

並べ替え関数 Swift の標準ライブラリは、指定した並べ替えクロージャの出力に基づいて、既知の型の値の配列を並べ替える sort と呼ばれる関数を提供します。並べ替えプロセスが完了すると、並べ替え関数は、古い配列と同じ型とサイズの新しい配列を返し、その要素は正しい並べ替え順序で返されます。

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

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

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 ウィキペディアのページを見て、そのための 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 で使用すると、

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

組み込みのソート方法はクイックソートである（またはそれに近い）ようで、本当に遅いです...

score 18 · Accepted Answer

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

ここに画像の説明を入力

score 8 · Accepted Answer

他の人が言及しているが十分に呼び出されていない主な問題は-O3、Swift でまったく何もしない (そして決してない) ため、それを使用してコンパイルすると効果的に最適化されない ( -Onone) ことです。

オプション名は時間の経過とともに変更されたため、他の回答にはビルドオプションの古いフラグが含まれています。現在の正しいオプション (Swift 2.2) は次のとおりです。

-Onone // Debug - slow
-O     // Optimised
-O -whole-module-optimization //Optimised across files

モジュール全体の最適化はコンパイルに時間がかかりますが、モジュール内のファイル全体、つまり各フレームワーク内および実際のアプリケーションコード内で最適化できますが、それらの間では最適化できません。これは、パフォーマンスが重要な場合に使用する必要があります)

安全性チェックを無効にしてさらに高速化することもできますが、すべてのアサーションと前提条件を無効にするだけでなく、それらが正しいことに基づいて最適化します。アサーションにヒットしたことがある場合、これは未定義の動作をしていることを意味します。細心の注意を払って使用し、(テストによって) スピードブーストが価値があると判断した場合にのみ使用してください。一部のコードにとって価値があると思われる場合は、そのコードを別のフレームワークに分離し、そのモジュールの安全性チェックのみを無効にすることをお勧めします。

score 4 · Accepted Answer

Swift 4.1では、新しい-Osize最適化モードが導入されました。

Swift 4.1 では、コンパイラは新しい最適化モードをサポートするようになり、専用の最適化でコードサイズを削減できるようになりました。

Swift コンパイラには、強力な最適化が付属しています。-O を指定してコンパイルすると、コンパイラはコードを変換して、最大のパフォーマンスで実行できるようにします。ただし、このランタイムパフォーマンスの向上には、コードサイズの増加というトレードオフが伴う場合があります。新しい -Osize 最適化モードを使用すると、ユーザーは、最大速度ではなく最小コードサイズでコンパイルすることを選択できます。

コマンドラインでサイズ最適化モードを有効にするには、-O の代わりに -Osize を使用します。

さらに読む: https://swift.org/blog/osize/

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

9 に答える 9

迅速

C++

評決

Related

Reference