Swift Beta-Leistung: Sortierung von Arrays

Question

Ich implementierte einen Algorithmus in Swift Beta und bemerkte, dass die Leistung sehr schlecht war. Nach genauerer Analyse stellte ich fest, dass einer der Engpässe etwas so Einfaches wie das Sortieren von Arrays war. Der relevante Teil ist hier:

let n = 1000000
var x = [Int](repeating: 0, count: n)
for i in 0..

In C++ dauert eine ähnliche Operation **0,06s** auf meinem Computer.

In Python dauert es **0,6s** (keine Tricks, einfach y = sorted(x) für eine Liste ganzer Zahlen).

In Swift dauert es **6s**, wenn ich es mit folgendem Befehl kompiliere:

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

Und es dauert sogar **88s**, wenn ich es mit folgendem Befehl kompiliere:

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

Die Zeiten in Xcode mit "Release" und "Debug" Builds sind ähnlich.

Was stimmt hier nicht? Ich könnte einen Leistungsverlust im Vergleich zu C++ verstehen, aber keine zehnfache Verlangsamung im Vergleich zu reinem Python.

------

**Bearbeiten:** weather bemerkte, dass die Änderung von `-O3` zu `-Ofast` macht, dass dieser Code fast so schnell läuft wie die C++-Version! Allerdings ändert `-Ofast` die Semantik der Sprache stark - in meinem Test hat es **die Überprüfungen für Integerüberläufe und Arrayindexüberläufe deaktiviert**. Zum Beispiel führt der folgende Swift-Code mit `-Ofast` ohne Absturz aus und gibt Müll aus:

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

Also `-Ofast` ist nicht das, was wir wollen; der Sinn von Swift ist, dass wir die Sicherheitsnetze haben. Natürlich haben die Sicherheitsnetze Auswirkungen auf die Leistung, aber sie sollten die Programme nicht 100-mal langsamer machen. Denken Sie daran, dass Java bereits auf Arraygrenzen prüft, und in typischen Fällen ist die Verlangsamung um einen Faktor viel weniger als 2. Und bei Clang und GCC haben wir `-ftrapv` zur Überprüfung (signed) ganzzahliger Überläufe, und das ist auch nicht so langsam.

Also die Frage: Wie können wir vernünftige Leistung in Swift erzielen, ohne die Sicherheitsnetze zu verlieren?

------

**Bearbeiten 2:** In Kommentaren bat Ferruccio um Benchmarks, die fair sind in dem Sinne, dass sie nicht auf integrierten Funktionen beruhen (z.B. sort). Ich denke, das folgende Programm ist ein ziemlich gutes Beispiel:

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

``

Es gibt keine Arithmetik, also müssen wir uns keine Gedanken über Ganzzahlüberläufe machen. Das Einzige, was wir tun, sind einfach viele Array-Referenzen. Und die Ergebnisse sind hier - Swift -O3 verliert fast um den Faktor 500 im Vergleich zu -Ofast:

*   C++ -O3: **0,05 s**
*   C++ -O0: 0,4 s
*   Java: **0,2 s**
*   Python mit PyPy: 0,5 s
*   Python: **12 s**
*   Swift -Ofast: 0,05 s
*   Swift -O3: **23 s**
*   Swift -O0: 443 s

(Wenn Sie befürchten, dass der Compiler die sinnlosen Schleifen vollständig optimieren könnte, können Sie es z.B. in `x[i] ^= x[j]` ändern und eine Ausgabeanweisung hinzufügen, die `x[0]` ausgibt. Das ändert nichts; die Zeitmessungen werden sehr ähnlich sein.)

Und ja, hier war die Python-Implementierung eine dumme reine Python-Implementierung mit einer Liste von Ganzzahlen und verschachtelten for-Schleifen. Sie sollte **viel** langsamer sein als nicht optimiertes Swift. Hier scheint etwas ernsthaft mit Swift und der Arrayindizierung kaputt zu sein.

------

**Bearbeiten 4:** Diese Probleme (sowie einige andere Leistungsprobleme) scheinen in Xcode 6 Beta 5 behoben worden zu sein.

Beim Sortieren habe ich jetzt folgende Zeitmessungen:

*   clang++ -O3: 0,06 s
*   swiftc -Ofast: 0,1 s
*   swiftc -O: 0,1 s
*   swiftc: 4 s

Für verschachtelte Schleifen:

*   clang++ -O3: 0,06 s
*   swiftc -Ofast: 0,3 s
*   swiftc -O: 0,4 s
*   swiftc: 540 s

Es scheint keinen Grund mehr zu geben, das unsichere `-Ofast` (auch bekannt als `-Ounchecked`) zu verwenden; einfach `-O` erzeugt gleichwertigen Code.

`` ```

Answer 1

Tl;dr Swift 1.0 ist jetzt gemäß diesem Benchmark mit dem Standard-Veröffentlichungsoptimierungslevel [-O] so schnell wie C.

---

Hier ist ein Quicksort in 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)
}

Und dasselbe in 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);
}

Beide funktionieren:

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]

Beide werden im selben Programm wie oben aufgerufen.

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

Dies wandelt die absoluten Zeiten in Sekunden um:

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;
}

Hier ist eine Zusammenfassung der Optimierungsebenen des Compilers:

[-Onone] keine Optimierungen, Standard für Debug.
[-O]     führt Optimierungen durch, Standard für Veröffentlichung.
[-Ofast] führt Optimierungen durch und deaktiviert Laufzeitüberlaufprüfungen und Laufzeit-Typprüfungen.

Zeit in Sekunden mit [-Onone] für n=10_000:

Swift:            0.895296452
C:                0.001223848

Hier ist Swifts integrierte Sortierfunktion für n=10_000:

Swift_builtin:    0.77865783

Hier ist [-O] für n=10_000:

Swift:            0.045478346
C:                0.000784666
Swift_builtin:    0.032513488

Wie man sehen kann, hat sich die Leistung von Swift um den Faktor 20 verbessert.

Wie in mweathers' Antwort erwähnt, macht die Einstellung von [-Ofast] den eigentlichen Unterschied aus, was in diesen Zeiten für n=10_000 resultiert:

Swift:            0.000706745
C:                0.000742374
Swift_builtin:    0.000603576

Und für n=1_000_000:

Swift:            0.107111846
C:                0.114957179
Swift_sort:       0.092688548

Zum Vergleich, dies ist mit [-Onone] für n=1_000_000:

Swift:            142.659763258
C:                0.162065333
Swift_sort:       114.095478272

Also war Swift ohne Optimierungen in diesem Benchmark zu diesem Zeitpunkt seiner Entwicklung fast 1000-mal langsamer als C. Andererseits hat Swift mit beiden Compilern auf [-Ofast] eingestellt tatsächlich mindestens genauso gut, wenn nicht sogar leicht besser als C abgeschnitten.

Es wurde darauf hingewiesen, dass [-Ofast] die Semantik der Sprache ändert und möglicherweise unsicher macht. Dies ist das, was Apple in den Versionshinweisen für Xcode 5.0 feststellt:

Ein neues Optimierungsniveau -Ofast, verfügbar in LLVM, ermöglicht aggressive Optimierungen. -Ofast lockert einige konservative Beschränkungen, hauptsächlich für Gleitkommaoperationen, die für den Großteil des Codes sicher sind. Es kann signifikante Leistungsgewinne durch den Compiler erzielen.

Sie empfehlen es fast. Ob das klug ist oder nicht, kann ich nicht sagen, aber soweit ich sehen konnte, scheint es vernünftig zu sein, [-Ofast] in einer Veröffentlichung zu verwenden, wenn Sie keine hochpräzisen Gleitkommaoperationen benötigen und sich sicher sind, dass in Ihrem Programm keine Integerüberläufe oder Arrayüberläufe möglich sind. Wenn Sie hohe Leistung benötigen und Überlaufprüfungen/präzise Arithmetik erforderlich sind, wählen Sie vorerst eine andere Sprache.

UPDATE BETA 3:

n=10_000 mit [-O]:

Swift:            0.019697268
C:                0.000718064
Swift_sort:       0.002094721

Swift ist insgesamt etwas schneller und es scheint, als hätte sich die integrierte Sortierfunktion von Swift deutlich verändert.

ABSCHLIEßENDES UPDATE:

[-Onone]:

Swift:   0.678056695
C:       0.000973914

[-O]:

Swift:   0.001158492
C:       0.001192406

[-Ounchecked]:

Swift:   0.000827764
C:       0.001078914

Answer 2

TL;DR: Ja, die einzige Swift-Sprachimplementierung ist im Moment langsam. Wenn Sie schnellen, numerischen (und anderen Arten von) Code benötigen, wählen Sie einfach eine andere Sprache. In Zukunft sollten Sie Ihre Wahl neu bewerten. Es könnte jedoch gut genug für den Großteil des Anwendungscode sein, der auf einer höheren Ebene geschrieben wird.

Basierend auf dem, was ich in SIL und LLVM IR sehe, scheint es, als bräuchten sie eine Menge Optimierungen, um Retains und Releases zu entfernen, die in Clang (für Objective-C) implementiert sein könnten, aber noch nicht portiert wurden. Das ist die Theorie, mit der ich im Moment gehe (ich muss immer noch bestätigen, dass Clang etwas damit macht), da ein Profilerlauf auf dem letzten Testfall dieser Frage dieses "schöne" Ergebnis ergibt:

Wie von vielen anderen gesagt wurde, ist -Ofast völlig unsicher und ändert die Sprachsemantik. Für mich ist das bereits der Punkt, wo man sagen kann "Wenn du das verwenden willst, benutze einfach eine andere Sprache". Ich werde diese Wahl später neu bewerten, wenn sich etwas ändert.

-O3 liefert uns eine Menge swift_retain und swift_release Aufrufe, die ehrlich gesagt in diesem Beispiel nicht dort sein sollten. Der Optimierer sollte (die meisten) davon elidiert haben, da er die meisten Informationen über das Array kennt und weiß, dass es (mindestens) einen starken Verweis darauf hat.

Es sollte keine weiteren Retains erzeugen, wenn es nicht einmal Funktionen aufruft, die die Objekte freigeben könnten. Ich glaube nicht, dass ein Arraykonstruktor ein Array zurückgeben kann, das kleiner ist als angefordert, was bedeutet, dass viele der überflüssigen Prüfungen, die erzeugt wurden, nutzlos sind. Es weiß auch, dass die ganze Zahl nie über 10k sein wird, so dass die Überlaufprüfungen optimiert werden können (nicht wegen der Seltsamkeit von -Ofast, sondern wegen der Semantik der Sprache (nichts anderes ändert diese Variable oder kann darauf zugreifen, und das Hinzufügen bis 10k ist für den Typ Int sicher).

Der Compiler kann das Array oder die Arrayelemente jedoch nicht auspacken, da sie an sort() übergeben werden, was eine externe Funktion ist und die Argumente benötigt, die er erwartet. Dadurch müssen wir die Int-Werte indirekt verwenden, was den Ablauf etwas verlangsamen würde. Dies könnte sich ändern, wenn die generische Funktion sort() (nicht auf multi-methodische Weise) dem Compiler zur Verfügung stünde und inliniert würde.

Dies ist eine sehr neue (öffentliche) Sprache, die meiner Annahme nach viele Veränderungen durchmacht, da es Leute gibt (stark) die mit der Swift-Sprache involviert sind, die um Feedback bitten und alle sagen, dass die Sprache noch nicht fertig ist und sich ändern wird.

Verwendeter Code:

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

P.S.: Ich bin kein Experte für Objective-C oder all die Einrichtungen von Cocoa, Objective-C oder die Swift-Laufzeiten. Ich könnte auch einige Dinge annehmen, die ich nicht geschrieben habe.

Answer 3

Ich habe beschlossen, mir das aus Spaß anzusehen, und hier sind die Zeiten, die ich erhalte:

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

Swift

// Swift 4.0 Code
import Foundation

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

    for _ in 0..

``

Ergebnisse:

Swift 1.1

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

xcrun swiftc -O SwiftSort.swift
./SwiftSort     
Verstrichene Zeit: 1.02204304933548

Swift 1.2

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

xcrun -sdk macosx swiftc -O SwiftSort.swift
./SwiftSort     
Verstrichene Zeit: 0.738763988018036

Swift 2.0

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

xcrun -sdk macosx swiftc -O SwiftSort.swift
./SwiftSort     
Verstrichene Zeit: 0.767306983470917

Es scheint die gleiche Leistung zu sein, wenn ich mit -Ounchecked kompiliere.

Swift 3.0

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

xcrun -sdk macosx swiftc -O SwiftSort.swift
./SwiftSort     
Verstrichene Zeit: 0.939633965492249

xcrun -sdk macosx swiftc -Ounchecked SwiftSort.swift
./SwiftSort     
Verstrichene Zeit: 0.866258025169373

Es scheint eine Leistungsverschlechterung von Swift 2.0 auf Swift 3.0 gegeben zu haben, und ich sehe auch zum ersten Mal einen Unterschied zwischen -O und -Ounchecked.

Swift 4.0

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

xcrun -sdk macosx swiftc -O SwiftSort.swift
./SwiftSort     
Verstrichene Zeit: 0.834299981594086

xcrun -sdk macosx swiftc -Ounchecked SwiftSort.swift
./SwiftSort     
Verstrichene Zeit: 0.742045998573303

Swift 4 verbessert die Leistung erneut, während ein Unterschied zwischen -O und -Ounchecked bestehen bleibt. -O -whole-module-optimization scheint keinen Unterschied zu machen.

C++

#include 
#include 
#include 
#include 
#include 

using namespace std;
using namespace std::chrono;

int main(int argc, const char * argv[]) {
    const auto arraySize = 10000000;
    vector 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 << "Verstrichene Zeit: " << duration_cast>(end - start).count() << "\n";

    return 0;
}

Ergebnisse:

Apple Clang 6.0

clang++ --version
Apple LLVM Version 6.0 (clang-600.0.54) (basiert auf LLVM 3.5svn)
Ziel: x86_64-apple-darwin14.0.0
Thread-Modell: posix

clang++ -O3 -std=c++11 CppSort.cpp -o CppSort
./CppSort     
Verstrichene Zeit: 0.688969

Apple Clang 6.1.0

clang++ --version
Apple LLVM Version 6.1.0 (clang-602.0.49) (basiert auf LLVM 3.6.0svn)
Ziel: x86_64-apple-darwin14.3.0
Thread-Modell: posix

clang++ -O3 -std=c++11 CppSort.cpp -o CppSort
./CppSort     
Verstrichene Zeit: 0.670652

Apple Clang 7.0.0

clang++ --version
Apple LLVM Version 7.0.0 (clang-700.0.72)
Ziel: x86_64-apple-darwin15.0.0
Thread-Modell: posix

clang++ -O3 -std=c++11 CppSort.cpp -o CppSort
./CppSort     
Verstrichene Zeit: 0.690152

Apple Clang 8.0.0

clang++ --version
Apple LLVM Version 8.0.0 (clang-800.0.38)
Ziel: x86_64-apple-darwin15.6.0
Thread-Modell: posix

clang++ -O3 -std=c++11 CppSort.cpp -o CppSort
./CppSort     
Verstrichene Zeit: 0.68253

Apple Clang 9.0.0

clang++ --version
Apple LLVM Version 9.0.0 (clang-900.0.38)
Ziel: x86_64-apple-darwin16.7.0
Thread-Modell: posix

clang++ -O3 -std=c++11 CppSort.cpp -o CppSort
./CppSort     
Verstrichene Zeit: 0.736784

Fazit

Zum Zeitpunkt dieses Schreibens ist Swifts Sortierfunktion schnell, aber noch nicht so schnell wie die von C++, wenn sie mit -O kompiliert wird, mit den oben genannten Compilern und Bibliotheken. Mit -Ounchecked scheint es in Swift 4.0.2 und Apple LLVM 9.0.0 genauso schnell zu sein wie C++.

``

Answer 4

Von Die Swift-Programmiersprache :

Die Sort-Funktion Die Swift-Standardbibliothek bietet eine Funktion namens sort, die ein Array von Werten eines bekannten Typs basierend auf dem Ausgabewert eines von Ihnen bereitgestellten Sortierungsschließers sortiert. Nachdem der Sortiervorgang abgeschlossen ist, gibt die Sortierfunktion ein neues Array desselben Typs und derselben Größe wie das alte zurück, mit den Elementen in der richtigen sortierten Reihenfolge.

Die sort Funktion hat zwei Deklarationen.

Die Standarddeklaration, die es Ihnen ermöglicht, einen Vergleichsschließer anzugeben:

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

Und eine zweite Deklaration, die nur einen Parameter (das Array) annimmt und "fest codiert ist, um den weniger-als-Vergleicher zu verwenden".

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

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

Ich habe eine modifizierte Version Ihres Codes in einem Playground getestet, in dem der Schließung hinzugefügt wurde, damit ich die Funktion etwas genauer überwachen konnte, und ich habe festgestellt, dass mit n auf 1000 gesetzt, die Schließung etwa 11.000 Mal aufgerufen wurde.

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

Es handelt sich nicht um eine effiziente Funktion, und ich würde empfehlen, eine bessere Sortierfunktion zu verwenden.

BEARBEITEN:

Ich habe mir die Quicksort-Wikipedia-Seite angesehen und eine Swift-Implementierung dafür geschrieben. Hier ist das vollständige Programm, das ich verwendet habe (in einem Playground)

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 // <- Verwendet, um zu sehen, wie viele Vergleiche gemacht werden
        if array[i] <= pivotValue {
            swap(&array[i], &array[storeIndex])
            storeIndex++
        }
    }
    swap(&array[storeIndex], &array[right]) // Bewege Pivot an seinen endgültigen Platz
    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) // <- Führt die Sortierung durch

for i in 0..n {
    x[i] // <- Vom Playground verwendet, um die Ergebnisse anzuzeigen
}

Bei Verwendung davon mit n=1000, habe ich festgestellt, dass

1. quickSort() wurde etwa 650 Mal aufgerufen,
2. etwa 6000 Austausche wurden durchgeführt,
3. und ungefähr 10.000 Vergleiche gemacht wurden

Es scheint, dass die integrierte Sortiermethode (oder ist nah an) Quicksort ist und wirklich langsam ist...

Answer 5

Ab Xcode 7 können Sie Schnelle, gesamte Moduloptimierung aktivieren. Dies sollte Ihre Leistung sofort verbessern.