Swift Beta performance: Sortieren von arrays

Ich war die Implementierung eines Algorithmus in Swift Beta und bemerkte, dass die performance war sehr schlecht. Nach dem Graben tiefer erkannte ich, dass einer der Engpässe war etwas so einfach 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++, ein ähnlicher Vorgang dauert 0.06 s auf meinem computer.

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

Swift dauert es 6s wenn ich es kompilieren mit folgendem Befehl:

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

Und es dauert so viel wie 88s wenn ich es kompilieren mit folgendem Befehl:

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

Timings in Xcode mit "Release" statt "Debug" baut ähnlich sind.

Was ist hier falsch? Ich könnte verstehen, dass einige performance-Verlust im Vergleich mit C++, aber nicht für eine 10-fache Verlangsamung im Vergleich zu reinem Python.

Edit: Wetter aufgefallen, dass eine änderung -O3 zu -Ofast macht dieser code laufen fast so schnell wie die C++ - version! Allerdings -Ofast ändert sich die Semantik der Sprache sehr viel — in meinen Tests, es deaktiviert die Prüfungen für integer-überläufe und array indexing overflows. Zum Beispiel, mit -Ofast den folgenden Swift-code automatisch ausgeführt wird, ohne abzustürzen (und druckt einige Müll):

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

So -Ofast ist nicht das, was wir wollen; der ganze Punkt von Swift ist, dass wir die Sicherheit der Netze statt. Natürlich, die Sicherheit der Netze haben einige Auswirkungen auf die Leistung, aber Sie sollten nicht die Programme, die 100-mal langsamer. Denken Sie daran, dass Java bereits Prüfungen für die array-Grenzen, und in typischen Fällen die Verlangsamung um einen Faktor viel weniger als 2. Und in Clang und GCC haben wir -ftrapv für die Prüfung (signed) integer-overflows, und es ist nicht so, dass langsam, entweder.

Daher die Frage: wie können wir vernünftige Leistung im Swift-ohne die Sicherheit der Netze?

Edit 2: hab ich etwas mehr benchmarking, mit sehr einfachen Schleifen entlang der Linien von

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

(Hier die xor-operation ist es einfach so, dass ich leichter finden Sie die entsprechenden Schleife in Assembler-code. Ich habe versucht zu Holen ein Vorgang, der leicht zu erkennen ist, sondern auch "harmlos" in dem Sinne, dass es sollte nicht verlangen, für alle Prüfungen im Zusammenhang zu integer-overflows.)

Wieder, es war ein großer Unterschied in der Leistung zwischen -O3 und -Ofast. Also ich hatte einen Blick auf den assembly-code:

Mit -Ofast ich bekomme ziemlich viel, was ich erwarten würde. Der relevante Teil ist eine Schleife mit 5 Maschinenbefehle.
Mit -O3 ich etwas bekommen, das war jenseits meiner wildesten Phantasie. Die innere Schleife überspannt 88 Zeilen Assembler-code. Ich habe nicht versucht, alles zu verstehen, aber die meisten verdächtigen Teile sind 13 Aufrufe von "callq _swift_retain" und weitere 13 Aufrufe von "callq _swift_release". Das ist, 26 Unterprogramm-Aufrufe in der inneren Schleife!

Edit 3: In den Kommentaren, Ferruccio gebeten, für benchmarks, die sind fair in dem Sinne, dass Sie nicht verlassen sich auf built-in Funktionen (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]
    }
}

Gibt es keine arithmetische, so brauchen wir nicht zu befürchten, integer-overflows. Das einzige, was wir tun, ist einfach nur eine Menge von array-Referenzen. Und die Ergebnisse sind hier—Swift -O3 verliert durch einen Faktor von fast 500 im Vergleich mit -Ofast:

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

(Wenn Sie besorgt sind, dass der compiler kann optimieren-aus der sinnlos-Schleifen vollständig, können Sie es ändern, um z.B. x[i] ^= x[j], und fügen Sie eine print-Anweisung, Ausgänge x[0]. Dies ändert nichts an; die Zeiten werden sich sehr ähnlich sein.)

Und ja, hier ist die Python-Implementierung war eine dumme, Reine Python-Implementierung mit einer Liste von ints und verschachtelte for-Schleifen. Es sollte viel langsamer als die nicht optimierte Swift. Irgendwas scheint ernst zu werden gebrochen, mit Swift und array-Indizierung.

Edit 4: Diese Probleme (wie auch einige andere performance-Probleme) scheint fest in der Xcode 6 beta 5.

Zum Sortieren, ich habe jetzt folgende timings:

clang++ -O3: 0.06 s
swiftc -Ofast: 0,1 s
swiftc -O: 0.1 s
swiftc: 4 s

Geschachtelte Schleifen:

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

Es scheint, dass es keinen Grund mehr zu verwenden, die die unsichere -Ofast (ein.k.ein. -Ounchecked); Ebene -O produziert gleichermaßen guten code.

Hier ist ein weiteres "Swift 100 mal langsamer als C" - Frage: stackoverflow.com/questions/24102609/...
Und hier ist die Diskussion über apples marketing-material im Zusammenhang mit Swift eine gute Leistung in der Sortierung: programmers.stackexchange.com/q/242816/913
Es wäre noch interessant/informativ, um zu sehen, einen Vergleich zu einem sort-Funktion in Python implementiert. Python ist sorted() Funktion ist Teil seiner Laufzeit, die (glaube ich) ist in C geschrieben.
Siehe edit 3. (Es ist nicht eine Art Funktion, aber ich denke es zeigt sehr gut, welche Art von code schlecht in Swift im Vergleich mit allem anderen, einschließlich Python.)
Können Sie vergleichen Sie es mit Java auch?
Getan. (Übrigens, eine naive Java-compiler erzeugt langsameren code als eine naive Swift-compiler. In Java berechnen x[i] müssen Sie zunächst prüfen, ob x != null und dann x.length > i. In Swift können wir überspringen Sie die erste Prüfung. Dennoch, wie wir in den benchmarks, Java gewinnt Swift -O3 um einen Faktor von ca. 100.)
Haben Sie gesehen, die zum Teil aus der "the Swift Programming Language" iBook über for-Schleifen? Es sagt, dass "[i] ist eine Konstante, deren Wert automatisch zu Beginn jeder iteration der Schleife.". Vielleicht erklärt es als var i: Int vor der Schleife wird die Dinge ändern?
Hängt von der Plattform ab. Null-check nicht erforderlich, wenn die Plattform den virtuellen Speicher und verwendet nicht die niedrigen Speicher-Adressen als gültige Speicherbereiche (z.B. Windows und ich denke, anderen Betriebssysteme auch); die MMU behandelt die null-check in diesem Fall. Überhaupt nicht überraschend, dass eine Marke neue front-end für eine neue Sprache ist schlimmer als eine 6 Jahre alte, Reife, front-end. Ich vermute, Apple wird dieses Problem beheben, bevor Swift ist aus der beta.
Sie können kompilieren mit: xcrun --sdk macosx swift -O3. Es ist kürzer.
Dieser link zeigt einige andere grundlegende Operationen im Vergleich zu Objective-C.
Denken Sie daran, dass Java bereits Prüfungen für die array-Grenzen, gebunden Kontrollen sind sehr wahrscheinlich zu sein entfernt, weil, wenn der compiler beweisen kann, dass. Java sollte laufen, ziemlich viel wie C (wenn richtig aufgewärmt) in diesem einfachen Fall. Null-Prüfungen sind in der Regel nicht direkt ausgeführt, sondern gefangen von der hardware und der compiler beweisen kann, x[i] ist nicht null für sicher - hat der compiler die jenseits von dumm, um tatsächlich überprüfen Sie für x null.
was ist falsch mit der Verwendung von swift 's" Sicherheitsnetze " in Entwicklung-und speichern -Ofast für den release?
Sie brauchen das "Sicherheitsnetz" bei der Produktion als input variiert. Anders ist es, um Prozess-Werte zwischen 1-10 und multiplizieren Sie Sie im Vergleich zum multiplizieren von Werten im Bereich von 2^31. Zum Beispiel die berühmt-berüchtigten heartbleed-bug wurde verursacht durch einen Mangel an range-check.
sicher, aber wenn Sie sich der Risiken bewusst, dann sicherlich können Sie bereinigen Ihre Eingänge, wo notwendig, um zu garantieren, dass der überlauf nicht auftreten
nicht sagen, es ist ideal, aber wenn die Leistung ist die Priorität, dann die Risiken zumindest scheinen überschaubar
um es einfach auszudrücken, wir Leben nicht in einer perfekten Welt und versucht, zu tun, was Sie vorschlagen, in 1 M LoC-Projekte ist weit härter als man sich das vorstellt. Bugs tun "exis", "stack-overflow" (name der Website) war einer der häufigsten (und immer noch ist) und bevor die no-execute-bit verwendet, um die Ausführung von beliebigem code ermöglichen sehr oft. Java läuft mit voller Bandbreite prüft, ob alle die Zeit und es kommt wirklich nicht auf die Leistung auswirken, dass die Prüfungen und nicht, anmutig, ist eine große Leistung, für die Sprache. In den letzten Jahren gab es eine riesige Sicherheitslücke, durch Umgehung es über die Unsichere scheinbar gut getan-code.
Jeder weiß, dass jede iteration auf iOS oder OS X, die mehr als 10000 Iterationen durchgeführt werden sollte, die in C oder C++. Wo ist die überraschung? Ist das eine rhetorische Wendung in Frage?
Übrigens -Ofast deaktiviert auch die Prüfungen für unwrapping nils; kompilieren Sie und führen Sie dieses "erfolgreich": let s: Double? = nil; println(s!)
Mit Beta 5 es wurden beträchtliche Verbesserung in Swift ' s Geschwindigkeit-siehe diesem post von Jesse Squires für weitere Details.
Wird Sie auch dieses update für Swift 2.0, wie es behauptet, die weitere Leistung zu erhöhen. In meinen eigenen tests fand ich heraus, dass, es sei denn, Sie kompilieren mit -Ounchecked es ist 100000 langsamer, selbst für einfache loop-tests. Mit -Ounchecked es ist "nur" 50 mal langsamer. Immer noch weht es von Python aus dem Wasser, in beiden Fällen.
Die java-Zahl scheint hoch, so dass ich es selber getestet und bekam mal von 50-60ms, die zum ausführen der code für "=" und 60-80ms, wenn ich die "^=". Hast du den VM-Start Zeit in diesen zahlen, oder vielleicht haben Sie gemeint .02s? Java ist in der Regel so schnell wie C für diese Art von operation. Auch java läßt sich etwa .04(=) und .06(^=) wenn ich die Schleife wiederholt (so dass Java-Zeit, um es zu kompilieren in optimierter Maschinensprache). Die .04 können beinhalten test-breaking-Optimierungen obwohl.

InformationsquelleAutor Jukka Suomela | 2014-06-07

451

tl;dr Swift 1.0 ist jetzt so schnell wie C, die von diesem benchmark mit dem Standard-release Optimierung-Ebene [-O].

Hier ist ein in-place-quicksort im 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 das gleiche 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 arbeiten:
```
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 sind berufen, in das gleiche Programm geschrieben.
```
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();
```
Dieser wandelt das absolute 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 compiler-Optimierungs-Stufen:
```
[-Onone] no optimizations, the default for debug.
[-O]     perform optimizations, the default for release.
[-Ofast] perform optimizations and disable runtime overflow checks and runtime type checks.
```
Zeit in Sekunden mit [persönliches Gespräch] für n=10_000:
```
Swift:            0.895296452
C:                0.001223848
```
Hier ist Swift builtin sort() 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 Sie sehen können, Swift ' s performance verbessert durch einen Faktor von 20.

Als pro mweathers' Antwort, Einstellung [-Ofast] macht den echten Unterschied aus, der sich in diesen Zeiten für n=10_000:
```
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, das ist mit [persönliches Gespräch] für n=1_000_000:
```
Swift:            142.659763258
C:                0.162065333
Swift_sort:       114.095478272
```
So rasch ohne Optimierungen wurde fast 1000 mal langsamer als C in diesem Maßstab, in diesem Stadium in seiner Entwicklung. Auf der anderen Seite mit beiden Compilern auf [-Ofast] Swift tatsächlich durchgeführt, der mindestens genauso gut wenn nicht etwas besser als C.

Es wurde darauf hingewiesen, dass [-Ofast] ändert die Semantik der Sprache, so dass es möglicherweise unsicher ist. Dies ist, was Apple-Staaten, die in der Xcode 5.0 release Hinweise:

Eine neue Optimierungsstufe -Ofast, verfügbar in LLVM ermöglicht aggressive Optimierungen. -Ofast entspannt einige konservative Einschränkungen, vor allem für floating-point-Operationen, die sicher für die meisten code. Es kann Ausbeute bedeutende high-performance-Gewinne aus dem compiler.

Sie alle, aber befürworten es. Ob das klug ist oder nicht konnte ich nicht sagen, aber was ich sagen kann, scheint es vernünftig genug, um zu verwenden [-Ofast] in einer Freigabe, wenn man nicht tut high-precision-floating-point-Arithmetik, und Sie sind zuversichtlich, kein integer oder array-überläufe möglich sind, in Ihrem Programm. Wenn Sie brauchen high-performance - und overflow-checks /präzise arithmetische dann wählen Sie eine andere Sprache für jetzt.

BETA 3-UPDATE:

n=10_000 mit [-O]:
```
Swift:            0.019697268
C:                0.000718064
Swift_sort:       0.002094721
```
Swift im Allgemeinen ist ein bisschen schneller und es sieht aus wie Swift gebaut-in der Art geändert hat, ganz deutlich.

LETZTE AKTUALISIERUNG:

[Persönliches Gespräch]:
```
Swift:   0.678056695
C:       0.000973914
```
[-O]:
```
Swift:   0.001158492
C:       0.001192406
```
[-Ounchecked]:
```
Swift:   0.000827764
C:       0.001078914
```
- Mit -Strahlen, sil für die Ausgabe der Mittelstufe SIL-code zeigt, was beibehalten wird (argh, stack overflow macht dies unmöglich-format). Es ist ein interner buffer-Objekt in das Array. Das klingt auf jeden Fall wie ein optimizer-Fehler, die ARC-Optimierer sollte in der Lage sein, um die zu entfernen behält ohne -Ofast.
- werd Nur nicht damit einverstanden, dass müssen wir eine andere Sprache, wenn Sie benutzen möchten Ofast Optimierungen. Es sich ähnlich wie mit der Frage von Grenzen, Kontrollen und andere kleinere Probleme, wenn Sie wählen Sie eine andere Sprache wie C. Der swift ist cool, weil es genau das ist standardmäßig sicher und, Optional, schnell und unsicher, wenn nötig. Dies ermöglicht dem Programmierer, den code Debuggen, als auch, um sicherzustellen, dass alles in Ordnung ist, und kompilieren Sie mit Ofast. Die Möglichkeit der Verwendung von modernen standards, und noch die Kraft haben, von einer "unsicheren" Sprache wie C, ist sehr cool.
- es ist nicht angezeigt, ein problem, Erstens, weil C hat keine Typ-Prüfungen und ist kein problem. In der Tat, erzwingen die Entwickler verwenden eine check-version jede Aussage ist schlecht, die Entwickler brauchen, um die Kontrolle zu übernehmen. Und ja, dies ist eine BETA-Sprache, existiert einige bugs. Und Java und C# ist sehr, sehr langsamer als C, aber swift ist nicht, existiert einige Probleme, die jetzt mit dem -O3 aber angepasst werden, für sicher, dass ich den gleichen code über Objective-C-e funktioniert einwandfrei mit -O3, in swift kann, erzielt eine performance auf -O3 ähnlich -Ofast wie ObjC habe, so rasch ausgeführt wird, sehr eng an C.
- Über dem BOGEN: ich habe die multimedia-Anwendung schreiben, die auf Objective-C und verwenden Sie im Durchschnitt 350-threads zur gleichen Zeit, alle über ARC. Es ist ein sehr gutes feature, in der Tat, auf eine frühere version mit GC-ich habe nie mehr als 150 threads ohne einige Probleme. Das problem ist nicht die ARC, das problem ist, dass die aktuelle Implementierung der swift-compiler, der ObjC-version des ARC läuft wunderbar auf -Onone ohne legen Sie die retain/release innerhalb der einfach wie, die, doent Sinn machen, nachdem alle. Só kann dieser Fehler werden damit optimal schnell, denn auf ObjC dem compiler die richtige Arbeit.
- Sie glaube nicht, dass ein speedup von 800 x ist sehr verdächtig? Ihre benchmark ist wahrscheinlich ungültig. Vielleicht den gesamten code unter test gelöscht wurde, als eine Optimierung.
- wenn Ihr mir sagen könnt, wie es sein könnte ungültig bitte. ich habe immer gerne, um mehr zu erfahren
- Joseph, kann ich bestechen Sie mit einem kleinen bounty zum ausführen dieser benchmark mit der Swift-version, die im Bundle mit der Xcode 6 Beta 3?
- Ich habe eine quick-edit mit der beta 3 Zeiten. wenn ich die chance bekomme, werde ich wohl schauen es ein wenig tiefer. die änderung der integrierten Sortieren, ist faszinierend.
- b5 verbessern sollten diese einen Haufen, wie gut
- Finale update, Swift ist jetzt so schnell wie C von diesem benchmark mit standard-Optimierungen.
- Tipp: Sowohl der Swift-und C-Implementierungen von quicksort kann verbessert werden, wenn Ihre Parameter recurse auf die kleinste partition! (Statt recursing auf der linken partition ist immer die erste.) Quicksort implementiert mit einem einfachen pivot-Auswahl im schlimmsten Fall in O(n^2) Zeit, aber selbst in diesem schlimmsten Fall brauchen Sie nur O(log n) stack-Speicher von recursing auf der kleineren partition.
- Nicht, dass davon tail-call-Optimierung? Ich bezweifle Swift hat TCO durch den Einsatz von reference counting.
- Wie hast du das kompilieren von C (compiler und Einstellungen)?
- Es scheint der Vergleich der Ergebnisse hängt davon ab, WAS man mit arrays. Werfen Sie einen Blick auf meine Antwort.
- kann mich nicht erinnern, aber es war llvm und hätte default xcode Einstellungen abgesehen von der Optimierung, wie beide waren das gleiche Projekt.
- was ist der eigentliche Befehl Sie ausführen? xcrun -sdk -O macosx swiftc-Datei.swift funktioniert nicht für mich
- überprüfen Sie diese timings mit nachfolgenden Operationen mit array sortiert. Auch schreiben, array in Datei nach dem timing schauen könnte nicht funktionieren, weil die Letzte Stufe der Optimierung können tatsächlich überspringen Teil der Sortierung, Umsortierung es auf den Punkt letzten checkpoint. Wenn das array nicht verwendet? ganze Sortieren kann übersprungen werden, zusammen. Nicht sicher, über C, aber C++ und Swift\C# - Compiler neigen dazu, das zu tun.. das ist der Grund, warum aliasing-Verletzung-Effekt in C++ erscheint in der Regel nur in optimierten Programms.
InformationsquelleAutor Joseph Mark
107

TL;DR: ja, nur die Swift-Sprache die Umsetzung ist langsam, jetzt. Wenn Sie schnelle, numerische (und andere Arten von code, vermutlich) - code, gehen Sie einfach mit anderen. In der Zukunft sollte man dann überdenken Sie Ihre Wahl. Es könnte gut sein, genug für die meisten Anwendungs-code, der geschrieben wird, auf einer höheren Ebene, obwohl.

Von dem, was ich bin zu sehen in SIL-und LLVM-IR, wie es scheint, brauchen Sie eine Reihe von Optimierungen für die Beseitigung behält und Pressemitteilungen, die umgesetzt werden könnten, in Clang (für Objective-C), aber Sie haben nicht portiert, Sie noch nicht. Das ist die Theorie, ich Fahr mit (für jetzt... ich muss noch bestätigen, dass der Klang tut etwas dagegen), da ein profiler run auf die letzten test-bei dieser Frage ergibt dies ein "hübsches" Ergebnis:

Wie gesagt viele andere -Ofast ist Total unsicher und wechselt die Sprache Semantik. Für mich ist es die "Wenn du gehst zu verwenden, dass, nutzen Sie einfach eine andere Sprache" Bühne. Ich werde neu bewerten, dass die Wahl später, wenn es änderungen.

-O3 wird uns eine ganze Reihe von swift_retain und swift_release Anrufe, die, ehrlich gesagt, nicht so Aussehen wie Sie es sein sollte für dieses Beispiel. Die Optimierer haben sollte, erstellte die (meisten) Ihnen AFAICT, da es weiß, die meisten Informationen, die über das array, und weiß, dass es (mindestens) einen starken Bezug zur it.

Sollte es nicht emittieren mehr behält, wenn es nicht sogar den Aufruf von Funktionen, die möglicherweise lassen Sie die Objekte. Ich glaube nicht, dass ein array-Konstruktor ein array zurückgeben, welches kleiner ist als das, was angesprochen wurde, was bedeutet, dass eine Menge von Tests, die emittiert wurden, sind nutzlos. Es weiß auch, dass die ganze Zahl wird nie über 10k, also der überlauf überprüft kann optimiert werden (nicht wegen -Ofast Verrücktheit, aber wegen der Semantik der Sprache (sonst ist nichts zu ändern, dass var noch darauf zugreifen können, und das hinzufügen von bis zu 10k ist sicher für die Art Int).

Der compiler möglicherweise nicht in der Lage sein, um unbox array oder array-Elemente, denn Sie sind immer übergeben sort(), die eine externe Funktion, und man muss die Argumente, die es erwartet. Dies macht uns zu verwenden haben Int Werte indirekt verwiesen wird, die es machen würde, gehen ein bisschen langsamer. Dies könnte sich ändern, wenn die sort() generische Funktion (nicht in der multi-Methode, Art und Weise) zur Verfügung Stand, um die compiler-und bekam inlined.

Dies ist eine sehr neue (öffentlich) Sprache, und es wird durch das, was ich davon ausgehen sind viele Veränderungen, seit es Menschen gibt (stark) beteiligt, mit der schnellen Sprache zu Fragen, für feedback, und Sie alle sagen, die Sprache ist noch nicht fertig und wird ändern.

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")
```
P. S: ich bin kein Experte auf Objective-C noch alle Einrichtungen, die von Kakao, Objective-C oder Swift-Laufzeiten. Ich kann auch vorausgesetzt werden, einige Dinge, die ich nicht geschrieben habe.
- Der compiler möglicherweise nicht in der Lage sein, um unbox array oder array-Elemente, denn Sie sind immer vergangen, sort(), die eine externe Funktion, und man muss die Argumente, die es erwartet. Das sollte keine Rolle spielen, um eine relativ gute compiler. Die Weitergabe der Metadaten (in der pointer - 64bits bieten Ihnen eine Vielzahl von levee) über die tatsächlichen Daten und verzweigen Sie in die aufgerufene Funktion.
- Was genau macht -Ofast "völlig unsicher"? Vorausgesetzt, Sie wissen, wie um den code zu testen und auszuschließen überläuft.
- Das ist tatsächlich davon eine Menge 🙂 Überprüfen des Codes und der Ausschluss overflows ist schwer zu tun. Aus meiner Erfahrung (ich Mach compiler arbeiten und überprüft haben, einige große codebase), und was ich ' ve hörte von Menschen, die compiler arbeiten auf großen Unternehmen, immer overflows und anderen undefinierten Verhalten richtig ist harter. Auch die Apple-Beratung (nur ein Beispiel) zur Festsetzung der UB ist falsch, manchmal (randomascii.wordpress.com/2014/04/17/... ). -Ofast ändert sich auch die Sprache-Semantik, aber ich kann nicht alle Fonds docs für Sie. Wie können Sie sicher sein, Sie wissen, was Sie tun?
- Es ist möglich, aber es kann nicht sinnvoll sein. Sie fügt hinzu, prüft jeden Zugriff auf ein Int[]. Es hängt davon ab, ob arrays von Int und ein paar andere primitive Typen (Sie haben höchstens 3 bits) verwendet werden, eine Menge (vor allem, wenn man tiefer auf C, wenn Sie müssen). Es wird auch einige bits, die Sie möglicherweise verwenden möchten, wenn, schließlich, die Sie hinzufügen möchten, nicht-ARC-GC. Es ist nicht skalierbar, um Generika mit mehr als einem argument, entweder. Da haben Sie alle die Typen, es wäre viel einfacher, sich zu spezialisieren, alle code berührte, Int[] (aber nicht Int?[]) zu verwenden inline Int. Aber dann muss man Obj-C-interop zu befürchten.
- non-ARC (also echte) GC wäre wirklich nützlich, aber Sie brauchen etwas, das nicht C kompatibel, wenn Sie wollen eine wirklich gleichzeitige, nicht-STW GC. Ich würde keine sorgen über 'jeder Zugriff auf Int[]", denn das hängt von der Ebene der compiler inline-und es sollte in der Lage sein zu inline die engen Schleifen mit/nach einige Hinweise.
InformationsquelleAutor filcab

Habe ich beschlossen, einen Blick auf das zum Spaß, und hier sind die timings, die ich bekomme:

Swift 4.0.2           :   0.83s (0.74s with `-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..<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:

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

Swift 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

Scheint es zu sein, die gleiche Leistung, wenn ich kompilieren mit -Ounchecked.

Swift 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

Scheint es eine performance regression von Swift 2.0 Swift 3.0, und ich bin auch zu sehen, einen Unterschied zwischen -O und -Ounchecked für die erste Zeit.

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 verbessert die Leistung wieder, wobei eine Lücke zwischen -O und -Ounchecked. -O -whole-module-optimization offenbar nicht um einen 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 Version 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

Als der Zeitpunkt des Schreibens dieses Artikels, Swift sort ist schnell, aber noch nicht so schnell wie C++'s Art bei der Kompilierung mit -O mit den oben genannten Compiler & Bibliotheken. Mit -Ounchecked erscheint es so schnell wie C++ in Swift 4.0.2 und Apple LLVM 9.0.0.

In Wirklichkeit sollten Sie nie nicht anrufen vector::reserve(), bevor Sie zehn Millionen Elementen.
Vielleicht! Nur die Sortierung ist zeitlich im moment.

InformationsquelleAutor Learn OpenGL ES

33

Vom The Swift Programming Language:

Die Funktion Sortieren Swift-standard-Bibliothek bietet eine Funktion namens
Art, die sortiert ein array von Werten von einer bekannten Art, auf der Grundlage der
Ausgabe eines Sortier-Schließung, die Sie bieten. Sobald es abgeschlossen ist die
Sortieren wird die Sortieren-Funktion liefert ein neues array mit der gleichen
Art und Größe wie der alte, mit seinen Elementen in der richtigen sortiert
um.

Den sort - Funktion hat zwei Erklärungen.

Die Standard-Erklärung, in der Sie angeben können, ein Vergleich Schließung:
```
func sort<T>(array: T[], pred: (T, T) -> Bool) -> T[]
```
Und eine zweite Erklärung, die nur einen einzigen parameter (das array) und ist "hardcoded zu verwenden, die weniger-als Komparator."
```
func sort<T : Comparable>(array: T[]) -> T[]

Example:
sort( _arrayToSort_ ) { $0 > $1 }
```
Getestet habe ich eine modifizierte version des Codes in einen Spielplatz mit der Schließung Hinzugefügt, so konnte ich monitor die Funktion ein wenig näher, und ich fand, dass mit n auf 1000 festgelegt, die Schließung aufgerufen wurde über 11.000 mal.
```
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 nicht eine effiziente Funktion, ein ich würde empfehlen, eine bessere Implementierung der Funktion.

EDIT:

Nahm ich einen Blick auf die Quicksort-wikipedia-Seite und schrieb eine schnelle Umsetzung für Sie. Hier ist das vollständige Programm, das ich verwendet (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
}
```
Mit diesem mit n=1000, fand ich, dass
1. quickSort() wurde aufgerufen, über 650 mal,
2. über 6000 swaps vorgenommen wurden,
3. und es gibt ungefähr 10.000 Vergleiche
Scheint es, dass die eingebauten sort-Methode ist (oder nahe zu) schnellen Sorte, und die ist wirklich langsam...
- Vielleicht bin ich völlig falsch, aber nach en.wikipedia.org/wiki/Quicksort, die Durchschnittliche Anzahl der Vergleiche in Quicksort ist 2*n*log(n). Das ist 13815 Vergleiche für das Sortieren von n = 1000 Elemente, so dass, wenn der Vergleich-Funktion wird aufgerufen über 11000 mal, die scheint nicht so schlecht.
- Auch Apple behauptet, dass ein "Komplexes Objekt "Sortieren" (was auch immer das ist) ist 3,9 mal schneller in Swift als in Python. Es sollte daher nicht notwendig, um eine "bessere Sortier-Funktion". - Aber Swift ist noch in der Entwicklung ...
- 2*n*log(n) für n=1000 Werke aus bis 6000. (es sei denn, log bezeichnet den natürlichen Logarithmus, aber ich bin es gewohnt, ln() wird verwendet für die). Ich update meine Antwort mit einigen neuen zu finden.
- Es nicht beziehen sich auf den natürlichen Logarithmus.
- log(n) für die Algorithmische Komplexität konventionell bezieht sich auf log-Basis-2. Der Grund für die nicht-Angabe der Basis ist, dass die change-of-base-Gesetz für Logarithmen stellt nur einen Konstanten Multiplikator, der verworfen wird, für die Zwecke von O-notation.
- HINWEIS: die Dokumentation entspricht nicht der Umsetzung. Sortieren sortiert und dann wieder, dass sehr array als Rückgabewert. Prüfen mit === oder ändern Sie einen Wert im zurückgegebenen array und überprüfen Sie das Ergebnis in das zurückgegebene array. Nicht wieder ein neues array, wie es sagt, es wird.
- Hinsichtlich der Diskussion über Natürliche Logarithmus vs base-2 Logarithmus: Die genaue Aussage aus der Wikipedia-Seite ist, dass die Durchschnittliche Anzahl der Vergleiche benötigt für n Elemente ist C(n) = 2n ln n ≈ 1.39n log₂ n. Für n = 1000 das gibt C(n) = 13815, und es ist nicht "big-O-notation".
InformationsquelleAutor David Skrundz
18

Als Xcode-7 können Sie aktivieren Fast, Whole Module Optimization. Dies sollte steigern Sie Ihre Leistung sofort.

InformationsquelleAutor Antoine
11

Swift-Array-Leistung revisited:

Schrieb ich meine eigene benchmark-Vergleich von Swift mit C/Objective-C. Mein benchmark berechnet Primzahlen. Es verwendet das array der vorherigen Primzahlen zu suchen, die wichtigsten Faktoren in jedem neuen Kandidaten, so dass es ganz schnell. Jedoch, es hat TONNEN von array Lesen und weniger schreiben-arrays.

Ich ursprünglich diesen benchmark gegen Swift 1.2. Ich beschlossen, aktualisieren Sie das Projekt und führen Sie es gegen Swift 2.0.

Dem Projekt können Sie wählen zwischen der Verwendung von normalen swift-arrays und mittels Swift-unsicher-Speicher-Puffer mit dem array-Semantik.

C/Objective-C, können Sie entweder entscheiden, zu verwenden NSArrays, oder C malloc ' ed arrays.

Die test-Ergebnisse scheinen ziemlich ähnlich wie mit den schnellsten, kleinsten code-Optimierung ([-0]) oder Schnellste, aggressiv ([-0fast]) - Optimierung.

Swift-2.0-Leistung ist immer noch schrecklich mit code-Optimierung ausgeschaltet, während C/Objective-C die Leistung ist nur mäßig langsamer.

Die Quintessenz ist, dass C malloc würd array-basierten Berechnungen sind die schnellsten, indem Sie eine bescheidene Marge

Swift mit unsicheren Puffer nimmt rund 1,19 X - 1.20 X länger als C malloc würd arrays bei der Verwendung Schnellste, kleinste code-Optimierung. der Unterschied scheint etwas weniger schnelle, aggressive Optimierung (Swift braucht mehr wie 1,18 x auf 1,16 x länger als C.

Wenn Sie regelmäßig Swift-arrays, der Unterschied zu C ist leicht größer. (Swift braucht ~1.22 1.23 länger.)

Regulären Swift-arrays sind DRAMATICALLY schneller als Sie waren im Swift 1.2/Xcode 6. Ihre Leistung ist so nah an Swift unsicher Puffer-basierten arrays, die mit unsicheren Speicher Puffer scheint nicht wirklich lohnt sich die Mühe nicht mehr, die ist groß.

BTW, Objective-C-NSArray Leistung stinkt. Wenn du gehst, um die nativen container-Objekte in beiden Sprachen, der Swift ist DRAMATISCH schneller.

Können Sie check out my Projekt auf github an SwiftPerformanceBenchmark

Es hat eine einfache Benutzeroberfläche, macht das sammeln stats ziemlich einfach.

Es ist interessant, dass die Sortierung scheint etwas schneller in Swift als in C nun aber, dass diese Primzahl-Algorithmus immer noch schneller in Swift.

InformationsquelleAutor Duncan C
8

Die wichtigste Frage, die erwähnt wird, von anderen aber nicht rief genug ist, dass -O3 tut überhaupt nichts in Swift (und auch nie hat), so dass bei der Kompilierung mit, dass es effektiv nicht-optimierte (-Onone).

Option Namen geändert haben im Laufe der Zeit so einige andere Antworten haben obsolete flags für den build-Optionen. Richtige aktuelle Optionen (Swift 2.2) sind:
```
-Onone //Debug - slow
-O     //Optimised
-O -whole-module-optimization //Optimised across files
```
Ganze Modul Optimierung langsamer kompilieren, aber optimieren kann zwischen Dateien innerhalb des Moduls, D. H. innerhalb der einzelnen Rahmen und innerhalb der eigentlichen Anwendungs-code, der aber nicht zwischen Ihnen. Sie sollten dies verwenden, für alles was performance kritisch)

Können Sie auch deaktivieren Sie Sicherheits-checks für noch mehr Geschwindigkeit, aber mit allen Behauptungen und Voraussetzungen, nicht nur Behinderte, sondern optimiert auf der Grundlage, dass Sie korrekt sind. Wenn Sie jemals getroffen, eine Behauptung dies bedeutet, dass Sie in ein Undefiniertes Verhalten. Verwenden Sie mit äußerster Vorsicht und nur, wenn Sie feststellen, dass die Geschwindigkeit zu steigern, lohnt sich für Sie (durch testen). Wenn Sie finden es wertvoll für den code empfehle ich die Trennung, die code in einem separaten Rahmen und nur das deaktivieren der Sicherheit-Prüfungen für das Modul.
- Diese Antwort ist nun veraltet. Als der Swift 4.1 das gesamte Modul Optimierung option ist eine separate boolescher Wert, der kombiniert werden kann mit anderen Einstellungen, und es ist nun -Os optimiert für die Größe. Ich kann zu aktualisieren, wenn ich Zeit habe, um zu überprüfen, die genaue option flags.
InformationsquelleAutor Joseph Lord

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 das Quick-Sort- Github-Beispiel Quick-Sort

Können Sie einen Blick über Lomuto ist Partitionierungs-Algorithmus in der Partitionierung der Liste. Geschrieben in Swift

InformationsquelleAutor Abo3atef

4

Swift 4.1 führt neue -Osize Optimierung-Modus.

Swift 4.1 der compiler unterstützt jetzt eine neue Optimierung-Modus
ermöglicht engagierten Optimierungen, um die Codegröße zu verringern.

Der Swift-compiler kommt mit leistungsstarken Optimierungen. Beim kompilieren
mit -O der compiler versucht, verwandeln Sie den code so, dass es ausgeführt wird
mit maximaler Leistung. Allerdings ist diese Verbesserung in der Laufzeit
kann die Leistung manchmal kommen Sie mit einem Kompromiss der erhöhte code-Größe.
Mit der neuen Osize Optimierung-Modus hat der Anwender die Wahl zu
kompilieren für die minimale code-Größe, nicht für maximale Geschwindigkeit.

Aktivieren Sie die Größe-Optimierung-Modus über die Befehlszeile verwenden -Osize
statt -O.

Weiter Lesen : https://swift.org/blog/osize/

InformationsquelleAutor casillas

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.