swift - subrange - Schnelle Leistung: Sortierung von Arrays




swift reduce (6)

Ich implementierte einen Algorithmus in Swift und bemerkte, dass die Leistung sehr schlecht war. Nachdem ich tiefer gegraben hatte, wurde mir klar, dass einer der Engpässe so einfach war wie das Sortieren von Arrays. Der relevante Teil ist hier:

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

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

In Python dauert es 0,6 s (keine Tricks, nur y = sortiert (x) für eine Liste von ganzen Zahlen).

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

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

Und es dauert bis zu 88 s, wenn ich es mit dem folgenden Befehl kompiliere:

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

Timings in Xcode mit "Release" vs. "Debug" Builds sind ähnlich.

Was ist hier falsch? Ich könnte einen Leistungsverlust im Vergleich zu C ++ verstehen, aber keine 10-fache Verlangsamung im Vergleich zu reinem Python.

Bearbeiten: mweathers bemerkte, dass das Ändern von -O3 zu -Ofast diesen Code fast so schnell -Ofast lässt wie die C ++ - Version! -Ofast ändert jedoch die Semantik der Sprache sehr. In meinen Tests hat es die Überprüfungen auf Integer-Überläufe und Array- -Ofast deaktiviert . Zum Beispiel, mit -Ofast der folgende Swift-Code -Ofast ohne Absturz ausgeführt (und druckt etwas 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 was wir wollen; Der Hauptpunkt von Swift ist, dass wir die Sicherheitsnetze haben. Natürlich haben die Sicherheitsnetze einen gewissen Einfluss auf die Leistung, aber sie sollten die Programme nicht 100 Mal langsamer machen. Denken Sie daran, dass Java bereits nach Array-Grenzen sucht, und in typischen Fällen ist die Verlangsamung um einen Faktor viel kleiner als 2. Und in Clang und GCC haben wir -ftrapv zum Überprüfen (signierter) Integer-Überläufe, und es ist auch nicht so langsam .

Daher die Frage: Wie können wir in Swift eine angemessene Leistung erzielen, ohne die Sicherheitsnetze zu verlieren?

Edit 2: Ich habe etwas mehr Benchmarking gemacht, mit sehr einfachen Loops nach

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

(Hier ist die xor-Operation nur vorhanden, damit ich die entsprechende Schleife im Assemblercode leichter finden kann. Ich habe versucht, eine Operation auszuwählen, die leicht zu erkennen ist, aber auch "harmlos" in dem Sinne, dass keine weiteren Prüfungen erforderlich sein sollten zu Integerüberläufen.)

Auch hier gab es einen großen Unterschied in der Leistung zwischen -O3 und -Ofast . Also habe ich mir den Assembler-Code angeschaut:

  • Mit -Ofast ich so ziemlich das, was ich erwarten würde. Der relevante Teil ist eine Schleife mit 5 Maschinensprachanweisungen.

  • Mit -O3 ich etwas, das jenseits meiner wildesten Vorstellungskraft liegt. Die innere Schleife umfasst 88 Linien des Assemblercodes. Ich habe nicht versucht, alles zu verstehen, aber die verdächtigsten Teile sind 13 Aufrufe von "Callq _swift_retain" und weitere 13 Aufrufe von "Callq _swift_release". Das heißt, 26 Unterprogrammaufrufe in der inneren Schleife !

Edit 3: In Kommentaren fragte Ferruccio nach Benchmarks, die in dem Sinne fair sind, dass sie nicht auf eingebauten Funktionen beruhen (zB 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..<n {
    for j in 0..<n {
        x[i] = x[j]
    }
}

Da es keine Arithmetik gibt, müssen wir uns keine Gedanken über Integer-Überläufe machen. Das einzige, was wir tun, sind nur viele Array-Referenzen. Und die Ergebnisse sind hier - Swift -O3 verliert im Vergleich zu -Ofast fast um den Faktor 500:

  • C ++ -O3: 0,05 s
  • C ++ -O 0: 0,4 s
  • Java: 0,2 s
  • Python mit PyPy: 0.5 s
  • Python: 12 s
  • Schnell-Schnell: 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 ihn zB zu x[i] ^= x[j] ändern und eine print-Anweisung hinzufügen, die x[0] ausgibt, was nichts ändert Die Zeiten werden sehr ähnlich sein.)

Und ja, hier war die Python-Implementierung eine dumme reine Python-Implementierung mit einer Liste von Ints und verschachtelten For-Schleifen. Es sollte viel langsamer als unoptimierte Swift sein. Mit Swift und Array Indexing scheint etwas ernsthaft gebrochen zu sein.

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

Zum Sortieren habe ich jetzt folgende Zeiten:

  • Klang ++ -O3: 0,06 s
  • swiftc -Ofast: 0,1 s
  • swiftc -O: 0,1 s
  • swiftc: 4 s

Für verschachtelte Schleifen:

  • Klang ++ -O3: 0,06 s
  • swiftc -Ofast: 0,3 s
  • swiftc -O: 0,4 s
  • swiftc: 540 s

Es scheint, dass es keinen Grund mehr gibt, das unsichere -Ofast (aka -Ounchecked ) zu verwenden; plain -O produziert gleich guten Code.


Ab Xcode 7 können Sie Fast, Whole Module Optimization einschalten. Dies sollte Ihre Leistung sofort steigern.


Aus The Swift Programming Language :

Die Sort Function Swift-Standardbibliothek stellt eine Funktion namens sort bereit, die ein Array von Werten eines bekannten Typs basierend auf der Ausgabe eines von Ihnen bereitgestellten Sortierabschlusses sortiert. Sobald der Sortiervorgang abgeschlossen ist, gibt die Sortierfunktion ein neues Array des gleichen Typs und der gleichen Größe wie das alte Array mit seinen Elementen in der richtigen sortierten Reihenfolge zurück.

Die sort hat zwei Deklarationen.

Die Standarddeklaration, mit der Sie einen Vergleichsabschluss angeben können:

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

Und eine zweite Deklaration, die nur einen einzigen Parameter (das Array) annimmt und "hartkodiert ist, um den Kleiner-als-Komparator zu verwenden".

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

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

Ich habe eine modifizierte Version Ihres Codes auf einem Spielplatz mit dem hinzugefügten Verschluss getestet, so dass ich die Funktion etwas genauer überwachen konnte, und ich fand, dass mit n auf 1000 der Verschluss ungefähr 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 ist keine effiziente Funktion, ich würde empfehlen, eine bessere Sortierfunktion zu verwenden.

BEARBEITEN:

Ich habe mir die Quicksort-Wikipedia-Seite angeschaut und eine Swift-Implementierung dafür geschrieben. Hier ist das volle Programm, das ich benutzt habe (auf einem Spielplatz)

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
}

Ich habe das mit n = 1000 gefunden

  1. quickSort () wurde ca. 650 mal aufgerufen,
  2. etwa 6000 Swaps wurden gemacht,
  3. und es gibt ungefähr 10.000 Vergleiche

Es scheint, dass die eingebaute Sortiermethode (oder ist nahe) schnelle Sortierung ist, und ist wirklich langsam ...


Ich habe beschlossen, das zum Spaß zu betrachten, und hier sind die Zeitpunkte, die ich bekomme:

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

Schnell

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

Ergebnisse:

Schnell 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

Schnell 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

Schnell 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

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

Schnelles 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

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

Schnell 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 verbessert die Performance erneut, während eine Lücke zwischen -O und -Ounchecked . -O -whole-module-optimization schien keinen Unterschied zu machen.

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

Ergebnisse:

Apple Clang 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

Urteil

Zum Zeitpunkt dieser Arbeit ist Swifts Sortierung schnell, aber noch nicht so schnell wie die von C ++ bei der Kompilierung mit -O mit den oben genannten Compilern und Bibliotheken. Mit " -Ounchecked scheint es in Swift 4.0.2 und Apple LLVM 9.0.0 so schnell wie C ++ zu sein.


Swift Array-Leistung überarbeitet:

Ich habe einen eigenen Benchmark geschrieben, der Swift mit C / Objective-C vergleicht. Meine Benchmark berechnet Primzahlen. Es verwendet das Array der vorherigen Primzahlen, um nach Primfaktoren in jedem neuen Kandidaten zu suchen, also ist es ziemlich schnell. Es führt jedoch TONS Array-Lesen und weniger Schreiben in Arrays.

Ich habe diesen Benchmark ursprünglich gegen Swift 1.2 gemacht. Ich beschloss, das Projekt zu aktualisieren und es gegen Swift 2.0 laufen zu lassen.

Im Projekt können Sie zwischen der Verwendung von normalen Swift-Arrays und Swift-unsicheren Speicherpuffern mit Array-Semantik wählen.

Für C / Objective-C können Sie entweder NSArrays oder C Malloc'ed-Arrays verwenden.

Die Testergebnisse scheinen sich mit der schnellsten, kleinsten Code-Optimierung ([-0s]) oder der schnellsten, aggressiven ([-0fast]) Optimierung zu vergleichen.

Swift 2.0-Leistung ist immer noch schrecklich mit Code-Optimierung ausgeschaltet, während C / Objective-C-Leistung nur geringfügig langsamer ist.

Das Fazit lautet, dass C-Array-basierte Berechnungen am schnellsten sind, mit einem bescheidenen Vorsprung

Swift mit unsicheren Puffern dauert etwa 1.19X - 1.20X länger als C malloc'd Arrays bei der Verwendung der schnellsten, kleinsten Code-Optimierung. der Unterschied scheint bei der schnellen, aggressiven Optimierung etwas geringer zu sein (Swift benötigt mehr 1,18x bis 1,16x länger als C.

Wenn Sie reguläre Swift-Arrays verwenden, ist der Unterschied zu C etwas größer. (Schnell dauert ~ 1.22 bis 1.23 länger.)

Reguläre Swift-Arrays sind DRAMATICALLY schneller als in Swift 1.2 / Xcode 6. Ihre Leistung ist so nah an Swift-unsicheren pufferbasierten Arrays, dass die Verwendung von unsicheren Speicherpuffern nicht wirklich den Aufwand wert ist, der groß ist.

BTW, Objective-C NSArray Leistung stinkt. Wenn Sie die systemeigenen Containerobjekte in beiden Sprachen verwenden möchten , ist Swift DRAMATISCH schneller.

Sie können mein Projekt auf Github bei SwiftPerformanceBenchmark

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

Es ist interessant, dass das Sortieren in Swift jetzt etwas schneller ist als in C, aber dass dieser Primzahl-Algorithmus in Swift immer noch schneller ist.


TL; DR : Ja, die einzige Swift-Implementierung ist langsam, gerade jetzt . Wenn Sie schnelle, numerische (und andere Arten von Code, vermutlich) Code benötigen, gehen Sie einfach mit einem anderen. In Zukunft sollten Sie Ihre Wahl neu bewerten. Für die meisten Anwendungscodes, die auf einer höheren Ebene geschrieben wurden, ist es jedoch möglicherweise ausreichend.

Von dem, was ich in SIL und LLVM IR sehe, scheint es, als bräuchten sie eine Reihe von Optimierungen zum Entfernen von Vorbehalten und Freigaben, die in Clang (für Objective-C) implementiert sein könnten, aber noch nicht portiert wurden. Das ist die Theorie, mit der ich gehe (für den Moment ... ich muss noch bestätigen, dass Clang etwas dagegen tut), da ein Profiler, der im letzten Testfall dieser Frage ausgeführt wurde, dieses "hübsche" Ergebnis liefert:

Wie von vielen anderen gesagt wurde, ist -Ofast völlig unsicher und ändert die Semantik der Sprache. Für mich ist es in der "Wenn Sie das verwenden, nur eine andere Sprache verwenden" Bühne. Ich werde diese Wahl später noch einmal überprüfen, wenn sie sich ändert.

-O3 bringt uns eine Reihe von swift_retain und swift_release Calls, die ehrlich gesagt nicht so aussehen, als ob sie für dieses Beispiel da wären. Der Optimierer sollte (meistens) die AFAICT-Klasse verlassen haben, da er die meisten Informationen über das Array kennt und weiß, dass er (zumindest) eine starke Referenz darauf hat.

Es sollte nicht mehr zurückhalten, wenn es nicht einmal Funktionen aufruft, die die Objekte freigeben könnten. Ich glaube nicht, dass ein Array-Konstruktor ein Array zurückgeben kann, das kleiner ist als gefordert, was bedeutet, dass viele der ausgegebenen Checks nutzlos sind. Es weiß auch, dass die Ganzzahl niemals über 10k liegen wird, so dass die Überlaufüberprüfungen optimiert werden können (nicht wegen -Ofast , sondern wegen der Semantik der Sprache (nichts anderes ändert diese -Ofast , noch kann sie darauf zugreifen und aufaddieren) bis 10k ist sicher für den Typ Int ).

Der Compiler ist möglicherweise nicht in der Lage, das Array oder die Array-Elemente zu entpacken, da sie an sort() , was eine externe Funktion ist und die erwarteten Argumente erhalten muss. Dies wird dazu führen, dass wir die Int Werte indirekt verwenden müssen, wodurch es etwas langsamer wird. Dies könnte sich ändern, wenn die generische sort() Funktion (nicht auf multimethische Weise) für den Compiler verfügbar und inline verfügbar wäre.

Dies ist eine sehr neue (öffentliche) Sprache, und sie geht durch, was ich vermute, sind viele Änderungen, da es Leute gibt, die (stark) mit der Swift-Sprache um Feedback gebeten werden und alle sagen, dass die Sprache nicht fertig ist und wird Veränderung.

Code verwendet:

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: Ich bin kein Experte für Objective-C und auch nicht für alle Einrichtungen von Cocoa , Objective-C oder den Swift-Laufzeiten. Ich könnte auch einige Dinge annehmen, die ich nicht geschrieben habe.


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 einen Blick auf Lomutos Partitionierungsalgorithmus werfen, indem Sie die Liste partitionieren. In Swift geschrieben







sorting