Ich habe einen Algorithmus in Swift Beta implementiert und festgestellt, dass die Leistung sehr schlecht war. Nachdem ich tiefer gegraben hatte, stellte ich fest, 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 ein ähnlicher Vorgang auf meinem Computer 0,06 Sekunden .
In Python dauert es 0,6 Sekunden (keine Tricks, nur y = sortiert (x) für eine Liste von ganzen Zahlen).
In Swift dauert es 6s, wenn ich es mit dem folgenden Befehl kompiliere:
xcrun swift -O3 -sdk `xcrun --show-sdk-path --sdk macosx`
Und es dauert bis zu 88 Sekunden, 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 konnte einen gewissen Leistungsverlust im Vergleich zu C ++ verstehen, aber keine 10-fache Verlangsamung im Vergleich zu reinem Python.
Bearbeiten: Wetter bemerkte, dass das Ändern -O3
in -Ofast
diesen Code fast so schnell laufen lässt wie die C ++ - Version! Allerdings -Ofast
ändert sich die Semantik der Sprache viel - in meinen Tests, es die Kontrollen für Integer - Überläufe und Array - Indizierung Überlauf deaktiviert . Mit -Ofast
dem folgenden Swift-Code wird beispielsweise lautlos und ohne Absturz ausgeführt (und es wird etwas Müll ausgedruckt):
let n = 10000000
print(n*n*n*n*n)
let x = [Int](repeating: 10, count: n)
print(x[n])
Also -Ofast
ist es nicht das, was wir wollen; Der springende Punkt bei Swift ist, dass wir die Sicherheitsnetze installiert 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 die Verlangsamung um einen Faktor von weniger als 2 beträgt. In Clang und GCC müssen wir -ftrapv
(signierte) Ganzzahlüberläufe überprüfen, 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 noch mehr Benchmarking durchgeführt, mit sehr einfachen Schleifen nach dem Vorbild von
for i in 0..<n {
x[i] = x[i] ^ 12345678
}
(Hier ist die xor-Operation nur vorhanden, damit ich die relevante Schleife im Assembler-Code leichter finden kann. Ich habe versucht, eine Operation auszuwählen, die leicht zu erkennen, aber auch "harmlos" ist, da keine Überprüfungen erforderlich sind zu ganzzahligen Überläufen.)
Auch hier gab es einen großen Unterschied in der Leistung zwischen -O3
und -Ofast
. Also habe ich mir den Assembler-Code angesehen:
Mit
-Ofast
bekomme ich so ziemlich das, was ich erwarten würde. Der relevante Teil ist eine Schleife mit 5 Anweisungen in Maschinensprache.Mit
-O3
bekomme ich etwas, das jenseits meiner wildesten Vorstellungskraft lag. Die innere Schleife umfasst 88 Zeilen Assembler-Code. 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 !
Bearbeiten 3: In Kommentaren fragte Ferruccio nach Benchmarks, die in dem Sinne fair sind, dass sie nicht auf eingebauten Funktionen beruhen (z. B. Sortieren). 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]
}
}
Es gibt keine Arithmetik, daher müssen wir uns keine Gedanken über ganzzahlige Überläufe machen. Das einzige, was wir tun, sind nur viele Array-Referenzen. Und die Ergebnisse sind da - Swift -O3 verliert im Vergleich zu -Ofast um einen Faktor von fast 500:
- C ++ -O3: 0,05 s
- C ++ -O0: 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 optimiert, können Sie sie in z. B. ändern x[i] ^= x[j]
und eine print-Anweisung hinzufügen x[0]
, die ausgegeben wird. Dies ändert nichts; die Timings sind sehr ähnlich.)
Und ja, hier war die Python-Implementierung eine blöde reine Python-Implementierung mit einer Liste von Ints und verschachtelten for-Schleifen. Es sollte viel langsamer sein als nicht optimierter Swift. Bei der Swift- und Array-Indizierung scheint etwas ernsthaft kaputt zu sein.
Bearbeiten 4: Diese Probleme (sowie einige andere Leistungsprobleme) scheinen in Xcode 6 Beta 5 behoben worden zu sein.
Zum Sortieren habe ich jetzt folgende Timings:
- clang ++ -O3: 0,06 s
- schnell-schnell: 0,1 s
- swiftc -O: 0,1 s
- schnell: 4 s
Für verschachtelte Schleifen:
- clang ++ -O3: 0,06 s
- schnell-schnell: 0,3 s
- swiftc -O: 0,4 s
- schnell: 540 s
Es scheint, dass es keinen Grund mehr gibt, das unsichere -Ofast
(aka -Ounchecked
) zu verwenden; plain -O
erzeugt gleich guten Code.
quelle
xcrun --sdk macosx swift -O3
. Es ist kürzer.Antworten:
tl; dr Swift 1.0 ist nach diesem Benchmark mit der Standardoptimierungsstufe [-O] jetzt so schnell wie C.
Hier ist eine In-Place-Quicksortierung in Swift Beta:
Und das gleiche in C:
Beide arbeiten:
Beide werden im selben Programm wie geschrieben aufgerufen.
Dies konvertiert die absoluten Zeiten in Sekunden:
Hier ist eine Zusammenfassung der Optimierungsstufen des Compilers:
Zeit in Sekunden mit [-Onone] für n = 10_000 :
Hier ist Swifts eingebaute sort () für n = 10_000 :
Hier ist [-O] für n = 10_000 :
Wie Sie sehen können, hat sich die Leistung von Swift um den Faktor 20 verbessert.
Wie pro mweathers' Antwort , Einstellung [-Ofast] macht den wirklichen Unterschied, in diesen Zeiten resultierende für n = 10_000 :
Und für n = 1_000_000 :
Zum Vergleich ist dies mit [-Onone] für n = 1_000_000 :
Daher war Swift ohne Optimierungen in diesem Benchmark zu diesem Zeitpunkt seiner Entwicklung fast 1000-mal langsamer als C. Auf der anderen Seite lief Swift mit beiden auf [-Ofast] eingestellten Compilern mindestens genauso gut, wenn nicht sogar etwas besser als C.
Es wurde darauf hingewiesen, dass [-Ofast] die Semantik der Sprache ändert und sie möglicherweise unsicher macht. Dies gibt Apple in den Versionshinweisen zu Xcode 5.0 an:
Sie alle befürworten es fast. Ob das klug ist oder nicht, kann ich nicht sagen, aber soweit ich das beurteilen kann, erscheint es vernünftig genug, [-Ofast] in einer Version zu verwenden, wenn Sie keine hochpräzise Gleitkomma-Arithmetik ausführen und sicher sind, keine Ganzzahl oder Array-Überläufe sind in Ihrem Programm möglich. Wenn Sie Hochleistungs- und Überlaufprüfungen / präzise Arithmetik benötigen, wählen Sie vorerst eine andere Sprache.
BETA 3 UPDATE:
n = 10_000 mit [-O] :
Swift ist im Allgemeinen etwas schneller und es sieht so aus, als ob sich die integrierte Sortierung von Swift erheblich geändert hat.
ENDGÜLTIGES UPDATE:
[-Onone] :
[-O] :
[-Ungeprüft] :
quelle
TL; DR : Ja, die einzige Swift Sprache Implementierung ist langsam, gerade jetzt . Wenn Sie schnellen, numerischen Code (und vermutlich auch andere Codetypen) benötigen, wählen Sie einfach einen anderen. In Zukunft sollten Sie Ihre Wahl neu bewerten. Es könnte jedoch für die meisten Anwendungscodes gut genug sein, die auf einer höheren Ebene geschrieben sind.
Nach dem, was ich in SIL und LLVM IR sehe, scheinen sie eine Reihe von Optimierungen zum Entfernen von Aufbewahrungen und Releases zu benötigen, die möglicherweise in Clang (für Objective-C) implementiert sind , aber noch nicht portiert wurden. Das ist die Theorie, mit der ich gehe (vorerst… ich muss noch bestätigen, dass Clang etwas dagegen unternimmt), da ein Profiler, der den letzten Testfall dieser Frage ausführt, dieses „hübsche“ Ergebnis liefert:
Wie von vielen anderen gesagt,
-Ofast
ist völlig unsicher und ändert die Sprachsemantik. Für mich ist es in der Phase "Wenn Sie das verwenden wollen, verwenden Sie einfach eine andere Sprache". Ich werde diese Auswahl später neu bewerten, wenn sie sich ändert.-O3
holt uns ein paarswift_retain
undswift_release
nennt das ehrlich gesagt nicht so, als ob sie für dieses Beispiel da sein sollten. Der Optimierer sollte (die meisten) AFAICT eliminiert haben, da er die meisten Informationen über das Array kennt und weiß, dass es (zumindest) einen starken Bezug dazu hat.Es sollte keine weiteren Retains ausgeben, wenn nicht einmal Funktionen aufgerufen werden, die die Objekte freigeben könnten. Ich glaube nicht, dass ein Array-Konstruktor ein Array zurückgeben kann, das kleiner ist als gewünscht, was bedeutet, dass viele ausgegebene Prüfungen nutzlos sind. Er weiß auch , dass die ganze Zahl wird nie über 10k sein, so dass die Überlaufprüfungen können (nicht wegen optimiert werden
-Ofast
Seltsamkeit, sondern wegen der Semantik der Sprache (nichts anderes , dass var verändert sich noch darauf zugreifen können, und das Hinzufügen von bis zu 10k ist sicher für den TypInt
).Der Compiler kann das Array oder die Array-Elemente möglicherweise nicht entpacken, da sie an übergeben werden. Dies
sort()
ist eine externe Funktion und muss die erwarteten Argumente abrufen. Dadurch müssen wir dieInt
Werte indirekt verwenden, wodurch es etwas langsamer wird. Dies könnte sich ändern, wenn diesort()
generische Funktion (nicht auf Multi-Methoden-Weise) dem Compiler zur Verfügung stand und inline wurde.Dies ist eine sehr neue (öffentliche) Sprache, und ich gehe davon aus, dass sich viele Änderungen ergeben, da (stark) Leute, die mit der Swift-Sprache zu tun haben, um Feedback bitten und alle sagen, dass die Sprache noch nicht fertig ist und wird Veränderung.
Verwendeter Code:
PS: Ich bin kein Experte für Objective-C oder alle Einrichtungen von Cocoa , Objective-C oder den Swift-Laufzeiten. Ich könnte auch einige Dinge annehmen, die ich nicht geschrieben habe.
quelle
-Ofast
"total unsicher"? Angenommen, Sie wissen, wie Sie Ihren Code testen und Überläufe ausschließen.-Ofast
ändert auch die Sprachsemantik, aber ich kann keine Dokumente dafür finanzieren. Wie können Sie sicher sein, dass Sie wissen, was es tut?Int[]
" machen, da dies von der Ebene abhängt, die der Compiler einbinden kann, und er sollte in der Lage sein, die engen Schleifen mit / nach einer gewissen Anleitung einzubinden.Ich habe beschlossen, mir das zum Spaß anzuschauen, und hier sind die Zeiten, die ich bekomme:
Schnell
Ergebnisse:
Swift 1.1
Swift 1.2
Swift 2.0
Es scheint die gleiche Leistung zu sein, wenn ich mit kompiliere
-Ounchecked
.Swift 3.0
Es scheint eine Leistungsregression von Swift 2.0 auf Swift 3.0 gegeben zu haben, und ich sehe auch einen Unterschied zwischen
-O
und-Ounchecked
zum ersten Mal.Swift 4.0
Swift 4 verbessert die Leistung erneut und behält gleichzeitig eine Lücke zwischen
-O
und bei-Ounchecked
.-O -whole-module-optimization
schien keinen Unterschied zu machen.C ++
Ergebnisse:
Apple Clang 6.0
Apple Clang 6.1.0
Apple Clang 7.0.0
Apple Clang 8.0.0
Apple Clang 9.0.0
Urteil
Zum Zeitpunkt dieses Schreibens ist Swifts Sortierung schnell, aber noch nicht so schnell wie die Sortierung von C ++, wenn sie
-O
mit den oben genannten Compilern und Bibliotheken kompiliert wird . Mit-Ounchecked
scheint es so schnell wie C ++ in Swift 4.0.2 und Apple LLVM 9.0.0 zu sein.quelle
Von
The Swift Programming Language
:Die
sort
Funktion hat zwei Deklarationen.Die Standarddeklaration, mit der Sie einen Vergleichsabschluss angeben können:
Und eine zweite Deklaration, die nur einen einzigen Parameter (das Array) akzeptiert und "fest codiert ist, um den Komparator kleiner als zu verwenden".
Ich habe eine modifizierte Version Ihres Codes auf einem Spielplatz mit dem hinzugefügten Verschluss getestet, damit ich die Funktion etwas genauer überwachen kann, und festgestellt, dass der Verschluss bei n auf 1000 ungefähr 11.000 Mal aufgerufen wurde.
Es ist keine effiziente Funktion, und ich würde empfehlen, eine bessere Implementierung der Sortierfunktion zu verwenden.
BEARBEITEN:
Ich habe mir die Wikipedia-Seite von Quicksort angesehen und eine Swift-Implementierung dafür geschrieben. Hier ist das vollständige Programm, das ich verwendet habe (auf einem Spielplatz)
Als ich dies mit n = 1000 verwendete, fand ich das
Es scheint, dass die eingebaute Sortiermethode eine schnelle Sortierung ist (oder nahe daran liegt) und sehr langsam ist ...
quelle
2*n*log(n)
. Das sind 13815 Vergleiche zum Sortieren von n = 1000 Elementen. Wenn die Vergleichsfunktion also ungefähr 11000 Mal aufgerufen wird, scheint dies nicht so schlecht zu sein.log(n)
für algorithmische Komplexität bezieht sich herkömmlicherweise auf log base-2. Der Grund dafür, dass die Basis nicht angegeben wird, besteht darin, dass das Basisänderungsgesetz für Logarithmen nur einen konstanten Multiplikator einführt, der für die Zwecke der O-Notation verworfen wird.C(n) = 2n ln n ≈ 1.39n log₂ n
. Für n = 1000 ergibt dies C (n) = 13815, und es ist keine "Big-O-Notation".Ab Xcode 7 können Sie einschalten
Fast, Whole Module Optimization
. Dies sollte Ihre Leistung sofort steigern.quelle
Die Leistung von Swift Array wurde überarbeitet:
Ich habe meinen eigenen Benchmark geschrieben, der Swift mit C / Objective-C vergleicht. Mein Benchmark berechnet Primzahlen. Es verwendet das Array vorheriger Primzahlen, um in jedem neuen Kandidaten nach Primfaktoren zu suchen, daher ist es ziemlich schnell. Es werden jedoch Tonnen von Arrays gelesen und weniger in Arrays geschrieben.
Ich habe diesen Benchmark ursprünglich gegen Swift 1.2 durchgeführt. Ich habe beschlossen, das Projekt zu aktualisieren und es gegen Swift 2.0 auszuführen.
Im Projekt können Sie zwischen der Verwendung normaler schneller Arrays und der Verwendung unsicherer Swift-Speicherpuffer mithilfe der Array-Semantik wählen.
Für C / Objective-C können Sie entweder NSArrays oder C malloc'ed Arrays verwenden.
Die Testergebnisse scheinen mit der schnellsten, kleinsten Codeoptimierung ([-0s]) oder der schnellsten, aggressiven ([-0fast]) Optimierung ziemlich ähnlich zu sein.
Die Leistung von Swift 2.0 ist bei deaktivierter Codeoptimierung immer noch schrecklich, während die Leistung von C / Objective-C nur mäßig langsamer ist.
Das Fazit ist, dass C malloc'd Array-basierte Berechnungen mit bescheidenem Abstand am schnellsten sind
Swift mit unsicheren Puffern dauert etwa 1,19X - 1,20X länger als C malloc-Arrays, wenn die schnellste und kleinste Codeoptimierung verwendet wird. Bei schneller, aggressiver Optimierung scheint der Unterschied etwas geringer zu sein (Swift dauert eher 1,18x bis 1,16x länger als C.
Wenn Sie normale Swift-Arrays verwenden, ist der Unterschied zu C etwas größer. (Swift dauert ~ 1,22 bis 1,23 länger.)
Normale Swift-Arrays sind
DRAMATICALLY
schneller als in Swift 1.2 / Xcode 6. Ihre Leistung kommt Swift-Arrays auf der Basis unsicherer Puffer so nahe, dass die Verwendung unsicherer Speicherpuffer die Mühe nicht mehr wert zu sein scheint, was sehr groß ist.Übrigens stinkt die Leistung von Objective-C NSArray. Wenn Sie die nativen Containerobjekte in beiden Sprachen verwenden möchten , ist Swift DRAMATISCH schneller.
Sie können mein Projekt auf Github bei SwiftPerformanceBenchmark überprüfen
Es hat eine einfache Benutzeroberfläche, die das Sammeln von Statistiken ziemlich einfach macht.
Es ist interessant, dass das Sortieren in Swift jetzt etwas schneller zu sein scheint als in C, aber dass dieser Primzahlalgorithmus in Swift immer noch schneller ist.
quelle
Das Hauptproblem, das von anderen erwähnt, aber nicht genug angesprochen wird, ist, dass
-O3
es in Swift überhaupt nichts tut (und es nie getan hat). Wenn es damit kompiliert wird, ist es effektiv nicht optimiert (-Onone
).Optionsnamen haben sich im Laufe der Zeit geändert, sodass einige andere Antworten veraltete Flags für die Build-Optionen haben. Richtige aktuelle Optionen (Swift 2.2) sind:
Die gesamte Moduloptimierung hat eine langsamere Kompilierung, kann jedoch über Dateien innerhalb des Moduls hinweg optimiert werden, dh innerhalb jedes Frameworks und innerhalb des tatsächlichen Anwendungscodes, jedoch nicht zwischen diesen. Sie sollten dies für alles verwenden, was leistungskritisch ist.
Sie können Sicherheitsüberprüfungen auch für noch mehr Geschwindigkeit deaktivieren, wobei jedoch alle Aussagen und Voraussetzungen nicht nur deaktiviert, sondern auf der Grundlage ihrer Richtigkeit optimiert werden. Wenn Sie jemals eine Behauptung treffen, bedeutet dies, dass Sie sich in undefiniertem Verhalten befinden. Verwenden Sie es mit äußerster Vorsicht und nur, wenn Sie feststellen, dass sich die Geschwindigkeitssteigerung für Sie lohnt (durch Testen). Wenn Sie es für einen Code wertvoll finden, empfehle ich, diesen Code in ein separates Framework zu unterteilen und nur die Sicherheitsüberprüfungen für dieses Modul zu deaktivieren.
quelle
Dies ist mein Blog über Quick Sort- Github-Beispiel Quick-Sort
Sie können sich den Partitionierungsalgorithmus von Lomuto unter Partitionieren der Liste ansehen. Geschrieben in Swift.
quelle
Swift 4.1 führt den neuen
-Osize
Optimierungsmodus ein.Lesen Sie weiter: https://swift.org/blog/osize/
quelle