Frage Schnelle Leistung: Sortierung von Arrays


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,06s auf meinem Computer.

In Python dauert es 0.6s (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 so viel wie 88s 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 sich das änderte -O3 zu -Ofast macht diesen Code fast so schnell wie die C ++ - Version! Jedoch, -Ofast verändert die Semantik der Sprache sehr - in meinen Tests deaktiviert die Überprüfung auf Integer-Überläufe und Array-Indexing-Überläufe. Zum Beispiel mit -Ofast Der folgende Swift-Code wird automatisch ohne Absturz ausgeführt (und gibt einen Müll aus):

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

Damit -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?


Bearbeiten 2: Ich habe ein bisschen 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 Assembler-Code leichter finden kann. Ich habe versucht, eine Operation auszuwählen, die leicht zu erkennen ist, aber auch "harmlos" in dem Sinne, dass sie keine Kontrollen erfordern sollte 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 bekomme ziemlich genau das, was ich erwarten würde. Der relevante Teil ist eine Schleife mit 5 Maschinensprachanweisungen.

  • Mit -O3 Ich bekomme etwas, das meine kühnste Vorstellungskraft übersteigt. 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 ist, 26 Unterroutine ruft in der inneren Schleife auf!


Bearbeiten 3: In Kommentaren fragte Ferruccio nach Benchmarks, die in dem Sinne fair seien, dass sie nicht auf eingebauten Funktionen (z. B. Sortieren) beruhten. 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 Bedenken haben, dass der Compiler die sinnlosen Schleifen vollständig optimieren könnte, können Sie ihn z. x[i] ^= x[j], und fügen Sie eine print-Anweisung hinzu, die ausgibt x[0]. Das ändert nichts; 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 sein viel langsamer als nicht optimiertes Swift. Mit Swift und Array-Indexierung scheint etwas ernsthaft gebrochen zu sein.


Edit 4: Diese Probleme (sowie einige andere Leistungsprobleme) scheinen 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 zu benutzen -Ofast (a.k.a. -Ounchecked); einfach -O produziert gleich guten Code.


829
2018-06-07 23:53


Ursprung


Antworten:


tl; dr Swift ist nun so schnell wie C mit diesem Benchmark und verwendet den Standard-Release-Optimierungslevel [-O].

Hier ist ein In-Place-Quicksort in Swift:

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 werden im selben Programm wie geschrieben 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 konvertiert die absoluten Zeiten in Sekunden:

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 Optimierungsstufen des Compilers:

[-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 [-Auf eins] zum n = 10_000:

Swift:            0.895296452
C:                0.001223848

Hier ist Swifts eingebautes sort () für n = 10_000:

Swift_builtin:    0.77865783

Hier ist [-O] zum n = 10_000:

Swift:            0.045478346
C:                0.000784666
Swift_builtin:    0.032513488

Wie Sie sehen können, verbesserte sich die Leistung von Swift um den Faktor 20.

Nach mweathers 'AntwortEinstellung [-Ofast] macht den wirklichen Unterschied, der sich in diesen Zeiten ergibt 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 [-Auf eins] zum n = 1_000_000:

Swift:            142.659763258
C:                0.162065333
Swift_sort:       114.095478272

Swift ohne Optimierungen war in diesem Entwicklungsstadium fast 1000-mal langsamer als C. Auf der anderen Seite, wenn beide Compiler auf [-Ofast] gesetzt sind, ist Swift tatsächlich mindestens genauso gut, wenn nicht etwas besser als C.

Es wurde darauf hingewiesen, dass [-Ofast] die Semantik der Sprache ändert, wodurch sie potenziell unsicher wird. Das sagt Apple in den Xcode 5.0-Versionshinweisen:

Eine neue Optimierungsstufe -Ofast, die in LLVM verfügbar ist, ermöglicht aggressive Optimierungen. -Entspannt einige konservative Einschränkungen, vor allem für Fließkommaoperationen, die für die meisten Codes sicher sind. Es kann signifikante Hochleistungs-Gewinne vom Compiler ergeben.

Sie alle befürworten es. Ob das weise ist oder nicht, konnte ich nicht sagen, aber nach dem, was ich sagen kann, scheint es vernünftig genug [-Ofast] in einer Version zu verwenden, wenn Sie keine hochpräzise Fließkomma-Arithmetik durchführen und keine Integer oder Array-Überläufe sind in Ihrem Programm möglich. Wenn Sie eine hohe Leistung benötigen und Überlaufprüfungen / genaue Arithmetik 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 so aus, als ob Swifts eingebaute Sortierung sich ziemlich stark verändert hat.

Letzter UPDATE:

[-Auf eins]:

Swift:   0.678056695
C:       0.000973914

[-O]:

Swift:   0.001158492
C:       0.001192406

[-Ounchecked]:

Swift:   0.000827764
C:       0.001078914

404
2018-06-08 01:36



TL; DR: Ja, die einzige Swift-Implementierung ist langsam, jetzt sofort. 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 ob sie eine Reihe von Optimierungen für das Entfernen von behalten und Freigaben benötigen, die in implementiert werden könnten Clang (für Objective-C), aber sie haben sie noch nicht portiert. 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:

Time profiling on -O3 Time profiling on -Ofast

Wie von vielen anderen gesagt wurde, -Ofast ist 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 einen Haufen swift_retain und swift_release nennt das ehrlich gesagt nicht so, als sollten sie für dieses Beispiel da sein. 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 verlangt, was bedeutet, dass viele der ausgegebenen Checks nutzlos sind. Es weiß auch, dass die ganze Zahl niemals über 10k liegen wird, also überprüft der Überlauf kann optimiert sein (nicht wegen -Ofast Seltsamkeit, aber wegen der Semantik der Sprache (nichts anderes ändert, dass var noch darauf zugreifen kann, und das Hinzufügen von bis zu 10k ist sicher für den Typ Int).

Der Compiler ist jedoch möglicherweise nicht in der Lage, das Array oder die Array-Elemente zu entpacken, da sie an sie übergeben werden sort(), das ist eine externe Funktion und muss die erwarteten Argumente erhalten. Dies wird uns dazu bringen müssen, die Int Werte indirekt, was es etwas langsamer machen würde. Dies könnte sich ändern, wenn die sort() generische Funktion (nicht in der Multi-Methode Weg) war für den Compiler verfügbar und wurde inline.

Dies ist eine sehr neue (öffentliche) Sprache, und sie geht durch, was ich vermute, sind viele Änderungen, da es Leute gibt, die (schwer) mit der Swift-Sprache um Feedback gebeten haben und alle sagen, dass die Sprache nicht fertig ist und werden 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 KakaoObjective-C oder die Swift-Laufzeiten. Ich könnte auch einige Dinge annehmen, die ich nicht geschrieben habe.


100
2018-06-09 06:30



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 kompiliere -Ounchecked.

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 sehe auch einen Unterschied zwischen -O und -Ounchecked zum ersten Mal.

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 nochmals und hält gleichzeitig 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 dieses Schreibens ist Swifts Sortierung schnell, aber noch nicht so schnell wie die von C ++ beim Kompilieren -Omit den oben genannten Compilern und Bibliotheken. Mit -Ouncheckedscheint es in Swift 4.0.2 und Apple LLVM 9.0.0 so schnell wie C ++ zu sein.


42
2017-10-26 21:47



Von The Swift Programming Language:

Die Standardbibliothek der Sort Function Swift bietet eine Funktion namens   sort, die ein Array von Werten eines bekannten Typs sortiert, basierend auf dem   Ausgabe einer Sortiersperre, die Sie bereitstellen. Sobald es abgeschlossen ist   Sortiervorgang, die Sortierfunktion gibt ein neues Array derselben zurück   Typ und Größe wie der alte, mit seinen Elementen in der richtigen sortiert   Auftrag.

Das sort Funktion 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 ...


29
2018-06-08 00:29



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

enter image description here


15
2018-06-11 16:56



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 leicht 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 unsicheren, pufferbasierten Swift-Arrays, dass die Verwendung von unsicheren Speicherpuffern nicht wirklich die Mühe wert zu sein scheint, was 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 an überprüfen 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 noch schneller ist.


8
2018-02-26 01:31



Das Hauptproblem, das von anderen erwähnt, aber nicht genug genannt wird, ist das -O3 macht in Swift gar nichts (und hat es auch nie), also ist es, wenn es damit kompiliert wird, effektiv nicht optimiert (-Onone).

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

-Onone // Debug - slow
-O     // Optimised
-O -whole-module-optimization //Optimised across files

Die Optimierung ganzer Module hat eine langsamere Kompilierung, kann aber über Dateien innerhalb des Moduls, d. H. Innerhalb jedes Frameworks und innerhalb des tatsächlichen Anwendungscodes, aber nicht zwischen ihnen, optimieren. Sie sollten dies für alles Leistungskritische verwenden)

Sie können Sicherheitschecks auch für noch mehr Geschwindigkeit deaktivieren, wobei jedoch alle Assertionen und Vorbedingungen nicht nur deaktiviert, sondern auf der Grundlage ihrer Richtigkeit optimiert werden. Wenn Sie jemals eine Assertion treffen, bedeutet dies, dass Sie ein unbestimmtes Verhalten haben. Verwenden Sie es mit äußerster Vorsicht und nur dann, wenn Sie feststellen, dass sich der Geschwindigkeitsschub für Sie lohnt (durch Testen). Wenn Sie es für einen bestimmten Code nützlich finden, empfehle ich, diesen Code in ein separates Framework zu trennen und nur die Sicherheitschecks für dieses Modul zu deaktivieren.


5
2018-04-13 10:58



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) 

Das 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


4
2017-12-06 11:12