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

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

-O3はswift_retainとswift_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のパーティショニングアルゴリズムをご覧ください。 スウィフトで書かれた