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

Leistung von Swift-Arrays neu betrachtet:

Ich habe meinen eigenen Benchmark geschrieben, der Swift mit C/Objective-C vergleicht. Mein Benchmark berechnet Primzahlen. Er verwendet das Array der bisherigen Primzahlen, um nach Primfaktoren in jedem neuen Kandidaten zu suchen, sodass er ziemlich schnell ist. Allerdings liest er TONNEN von Arrays und schreibt weniger in Arrays.

Ursprünglich habe ich diesen Benchmark gegen Swift 1.2 gemacht. Ich habe mich entschieden, das Projekt zu aktualisieren und es gegen Swift 2.0 laufen zu lassen.

Das Projekt ermöglicht es Ihnen, zwischen der Verwendung von normalen Swift-Arrays und der Verwendung von Swift unsicheren Speicherpuffern mit Array-Semantik zu wählen.

Für C/Objective-C können Sie entweder wählen, NSArrays zu verwenden oder C malloc'ed Arrays.

Die Testergebnisse scheinen ziemlich ähnlich zu sein mit der schnellsten, kleinsten Code-Optimierung ([-0s]) oder der schnellsten, aggressiven ([-0fast]) Optimierung.

Die Leistung von Swift 2.0 ist immer noch schrecklich, wenn die Code-Optimierung ausgeschaltet ist, während die Leistung von C/Objective-C nur moderat langsamer ist.

Der springende Punkt ist, dass C malloc-basierte Array-Berechnungen die schnellsten sind, mit einem bescheidenen Vorsprung.

Swift mit unsicheren Puffern dauert etwa 1,19X - 1,20X länger als C malloc'ed Arrays bei Verwendung der schnellsten, kleinsten Codeoptimierung. Der Unterschied scheint etwas geringer zu sein bei schneller, aggressiver Optimierung (Swift dauert eher 1,18x bis 1,16x länger als C).

Wenn Sie normale Swift-Arrays verwenden, ist der Unterschied zu C leicht größer. (Swift dauert ungefähr 1,22 bis 1,23 länger.)

Normale Swift-Arrays sind DRAMATISCH schneller als in Swift 1.2/Xcode 6. Ihre Leistung liegt so nah an Swift unsicheren Puffer-basierten Arrays, dass sich die Verwendung von unsicheren Speicherpuffern nicht wirklich mehr lohnt, was groß ist.

Übrigens, die Leistung von Objective-C NSArray stinkt. Wenn Sie die nativen Containerobjekte in beiden Sprachen verwenden möchten, ist Swift DRAMATISCH schneller.

Sie können mein Projekt auf Github unter SwiftPerformanceBenchmark überprüfen.

Es hat eine einfache Benutzeroberfläche, die das Sammeln von Statistiken ziemlich einfach macht.

Es ist interessant, dass Sortieren in Swift anscheinend jetzt etwas schneller ist als in C, aber dass dieser Primzahlenalgorithmus immer noch schneller in Swift ist.

Answer 2

Das Hauptproblem, das von anderen erwähnt wird, aber nicht genug betont wird, ist, dass -O3 in Swift überhaupt nichts bewirkt (und auch nie hat), sodass es effektiv nicht optimiert ist (-Onone).

Die Optionsnamen haben sich im Laufe der Zeit geändert, daher haben einige andere Antworten veraltete Flags für die Build-Optionen. Die korrekten aktuellen Optionen (Swift 2.2) sind:

-Onone // Debug - langsam
-O     // Optimiert
-O -whole-module-optimization // Optmiert über Dateien hinweg

Die Optimierung des gesamten Moduls dauert beim Kompilieren länger, kann aber über Dateien innerhalb des Moduls optimieren, d.h. innerhalb jedes Frameworks und innerhalb des eigentlichen Anwendungscode, jedoch nicht zwischen ihnen. Sie sollten dies für alles verwenden, was leistungskritisch ist.

Sie können auch Sicherheitsprüfungen deaktivieren, um noch mehr Geschwindigkeit zu erhalten, aber alle Aussagen und Vorbedingungen werden nicht nur deaktiviert, sondern optimiert, unter der Annahme, dass sie korrekt sind. Wenn Sie jemals auf eine Aussage stoßen, bedeutet dies, dass Sie sich in ein undefiniertes Verhalten begeben haben. Verwenden Sie dies mit äußerster Vorsicht und nur, wenn Sie feststellen, dass der Geschwindigkeitsschub für Sie lohnenswert ist (durch Testen). Wenn Sie feststellen, dass es für einige Codes wertvoll ist, empfehle ich, diesen Code in ein separates Framework zu trennen und nur die Sicherheitsüberprüfungen für dieses Modul zu deaktivieren.

Answer 3

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) 

Dies ist mein Blog über Quick Sort- Github Beispiel Quick-Sort

Sie können sich Lomutos Partitionsalgorithmus in Partitioning the List ansehen. Geschrieben in Swift.

Answer 4

Swift 4.1 führt einen neuen -Osize Optimierungsmodus ein.

In Swift 4.1 unterstützt der Compiler nun einen neuen Optimierungsmodus, der dedizierte Optimierungen ermöglicht, um die Codegröße zu reduzieren.

Der Swift-Compiler verfügt über leistungsstarke Optimierungen. Beim Kompilieren mit -O versucht der Compiler, den Code so zu transformieren, dass er mit maximaler Leistung ausgeführt wird. Diese Verbesserung der Laufzeitleistung kann jedoch manchmal mit einem Tradeoff von erhöhter Codegröße einhergehen. Mit dem neuen -Osize-Optimierungsmodus hat der Benutzer die Möglichkeit, für minimale Codegröße anstelle von maximaler Geschwindigkeit zu kompilieren.

Um den Optimierungsmodus für die Größe auf der Befehlszeile zu aktivieren, verwenden Sie -Osize anstelle von -O.

Weitere Informationen : https://swift.org/blog/osize/