Szybka wydajność beta: sortowanie tablic

Wdrażałem algorytm w Swift Beta i zauważyłem, że wydajność była bardzo słaba. Po głębszym kopaniu zdałem sobie sprawę, że jednym z wąskich gardeł było coś tak prostego, jak sortowanie tablic. Odpowiednia część znajduje się tutaj:

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

W C ++ podobna operacja zajmuje 0,06 s na moim komputerze.

W Pythonie zajmuje 0,6 s (bez lew, tylko y = sorted (x) dla listy liczb całkowitych).

W Swift zajmuje 6s, jeśli skompiluję go za pomocą następującego polecenia:

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

A kompilacja za pomocą następującego polecenia zajmuje aż 88 sekund :

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

Czasy w Xcode z kompilacjami „Release” vs. „Debug” są podobne.

Co tu jest nie tak? Mogłem zrozumieć pewną utratę wydajności w porównaniu z C ++, ale nie 10-krotne spowolnienie w porównaniu z czystym Pythonem.

Edycja: pogoda zauważyła, że ​​zmiana -O3na -Ofastten powoduje, że ten kod działa prawie tak szybko, jak wersja C ++! Jednak bardzo -Ofastzmienia semantykę języka - w moich testach wyłączyłem sprawdzanie przepełnień liczb całkowitych i przepełnienia indeksowania tablic . Na przykład -Ofastnastępujący kod Swift działa w trybie cichym bez awarii (i drukuje śmieci):

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

Więc -Ofastnie tego chcemy; chodzi o to, że mamy siatki bezpieczeństwa. Oczywiście siatki bezpieczeństwa mają pewien wpływ na wydajność, ale nie powinny powodować, że programy będą 100 razy wolniejsze. Pamiętaj, że Java już sprawdza granice tablic, a w typowych przypadkach spowolnienie jest znacznie mniejsze niż 2. A w Clang i GCC mamy -ftrapvdo sprawdzania (podpisanych) przepełnień liczb całkowitych, i to nie jest tak powolne.

Stąd pytanie: w jaki sposób możemy uzyskać rozsądną wydajność w Swift bez utraty sieci bezpieczeństwa?

Edycja 2: Zrobiłem trochę więcej testów porównawczych, z bardzo prostymi pętlami wzdłuż linii

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

(Tutaj jest operacja xor, aby łatwiej znaleźć odpowiednią pętlę w kodzie asemblera. Próbowałem wybrać operację, która jest łatwa do wykrycia, ale także „nieszkodliwa” w tym sensie, że nie powinna wymagać żadnych kontroli związanych z do przelewów liczb całkowitych).

Ponownie, była ogromna różnica w wydajności pomiędzy -O3i -Ofast. Spojrzałem więc na kod asemblera:

• Z -Ofasttym dostaję prawie to, czego bym się spodziewał. Odpowiednia część to pętla z 5 instrukcjami języka maszynowego.

• Z -O3I dostać coś, co było poza moim najdzikszych fantazji. Pętla wewnętrzna obejmuje 88 linii kodu asemblera. Nie próbowałem tego wszystkiego zrozumieć, ale najbardziej podejrzane są 13 wywołań „callq _swift_retain” i kolejne 13 wywołań „callq _swift_release”. To znaczy, 26 wywołań podprogramów w wewnętrznej pętli !

Edycja 3: W komentarzach Ferruccio poprosił o testy porównawcze, które są uczciwe w tym sensie, że nie polegają na wbudowanych funkcjach (np. Sortowanie). Myślę, że następujący program jest dość dobrym przykładem:

let n = 10000
var x = [Int](repeating: 1, count: n)
for i in 0..<n {
    for j in 0..<n {
        x[i] = x[j]
    }
}

Nie ma arytmetyki, więc nie musimy się martwić o przepełnienie liczb całkowitych. Jedyne, co robimy, to po prostu wiele odniesień do tablicy. A wyniki są tutaj - Swift -O3 traci prawie 500 razy w porównaniu z opcją -Ofast:

• C ++ -O3: 0,05 s
• C ++ -O0: 0,4 s
• Java: 0,2 s
• Python z PyPy: 0,5 s
• Python: 12 s
• Szybki - szybki: 0,05 s
• Swift -O3: 23 s
• Swift -O0: 443 s

(Jeśli obawiasz się, że kompilator może całkowicie zoptymalizować niepotrzebne pętle, możesz go zmienić na np. x[i] ^= x[j]I dodać instrukcję print, która wypisuje wynik x[0]. To niczego nie zmienia; czasy będą bardzo podobne.)

I tak, tutaj implementacja Pythona była głupią czystą implementacją Pythona z listą liczb int i zagnieżdżoną dla pętli. Powinien być znacznie wolniejszy niż niezoptymalizowany Swift. Wydaje się, że coś jest poważnie zepsute w Swift i indeksowaniu tablic.

Edycja 4: Te problemy (podobnie jak niektóre inne problemy z wydajnością) zostały prawdopodobnie rozwiązane w Xcode 6 beta 5.

Do sortowania mam teraz następujące czasy:

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

W przypadku zagnieżdżonych pętli:

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

Wydaje się, że nie ma już powodu, aby używać tego niebezpiecznego -Ofast(aka -Ounchecked); zwykły -Otworzy równie dobry kod.

tl; dr Swift 1.0 jest teraz tak szybki jak C według tego testu porównawczego przy użyciu domyślnego poziomu optymalizacji wersji [-O].

Oto szybki Quick -ort w 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)
}

I to samo w 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);
}

Oba działają:

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]

Oba są wywoływane w tym samym programie, co napisane.

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

Konwertuje to czasy bezwzględne na sekundy:

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

Oto podsumowanie poziomów optymalizacji kompilatora:

[-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.

Czas w sekundach z [-Onone] dla n = 10_000 :

Swift:            0.895296452
C:                0.001223848

Oto wbudowane sortowanie Swift () dla n = 10_000 :

Swift_builtin:    0.77865783

Oto [-O] dla n = 10_000 :

Swift:            0.045478346
C:                0.000784666
Swift_builtin:    0.032513488

Jak widać, wydajność Swift poprawiła się 20-krotnie.

Zgodnie z odpowiedzią mweathers , ustawienie [-Ofast] robi prawdziwą różnicę, czego rezultatem są czasy dla n = 10_000 :

Swift:            0.000706745
C:                0.000742374
Swift_builtin:    0.000603576

A dla n = 1_000_000 :

Swift:            0.107111846
C:                0.114957179
Swift_sort:       0.092688548

Dla porównania jest to z [-Onone] dla n = 1_000_000 :

Swift:            142.659763258
C:                0.162065333
Swift_sort:       114.095478272

Zatem Swift bez optymalizacji był prawie 1000 razy wolniejszy niż C w tym teście, na tym etapie jego rozwoju. Z drugiej strony przy obu kompilatorach ustawionych na [-Ofast] Swift faktycznie działał co najmniej równie dobrze, jeśli nie nieco lepiej niż C.

Zwrócono uwagę, że [-Ofast] zmienia semantykę języka, czyniąc go potencjalnie niebezpiecznym. Tak stwierdza Apple w uwagach do wydania Xcode 5.0:

Nowy poziom optymalizacji -Ofast, dostępny w LLVM, umożliwia agresywną optymalizację. -Ofast rozluźnia niektóre konserwatywne ograniczenia, głównie dla operacji zmiennoprzecinkowych, które są bezpieczne dla większości kodów. Może przynieść znaczące wygrane z kompilatora.

Wszyscy raczej to popierają. Bez względu na to, czy jest to mądre, czy nie, nie mogę powiedzieć, ale z tego, co mogę powiedzieć, wydaje się rozsądne użycie [-Ofast] w wydaniu, jeśli nie wykonujesz precyzyjnej arytmetyki zmiennoprzecinkowej i nie masz pewności, że liczba całkowita lub przepełnienia tablicy są możliwe w twoim programie. Jeśli potrzebujesz wysokiej wydajności i kontroli przepełnienia / precyzyjnej arytmetyki, wybierz na razie inny język.

AKTUALIZACJA BETA 3:

n = 10_000 przy [-O] :

Swift:            0.019697268
C:                0.000718064
Swift_sort:       0.002094721

Ogólnie rzecz biorąc, Swift jest nieco szybszy i wygląda na to, że wbudowane sortowanie Swift zmieniło się dość znacząco.

AKTUALIZACJA KOŃCOWA:

[-Onone] :

Swift:   0.678056695
C:       0.000973914

[-O] :

Swift:   0.001158492
C:       0.001192406

[-Oznaczone] :

Swift:   0.000827764
C:       0.001078914

TL; DR : Tak, jedyne wdrożenie języka Swift jest teraz powolne . Jeśli potrzebujesz szybkiego, numerycznego (i prawdopodobnie innego rodzaju kodu), po prostu wybierz inny. W przyszłości powinieneś ponownie ocenić swój wybór. Jednak może być wystarczający dla większości kodu aplikacji napisanego na wyższym poziomie.

Z tego, co widzę w SIL i LLVM IR, wygląda na to, że potrzebują szeregu optymalizacji do usuwania zachowań i wydań, które mogą być zaimplementowane w Clang (dla Objective-C), ale jeszcze ich nie przeniesiono. Z tą teorią popieram (na razie… muszę jeszcze potwierdzić, że Clang coś z tym robi), ponieważ profiler uruchomiony na ostatnim przypadku testowym tego pytania daje ten „ładny” wynik:

Jak zostało powiedziane przez wielu innych, -Ofastjest całkowicie niebezpieczny i zmienia semantykę języka. Dla mnie jest to etap „Jeśli zamierzasz tego użyć, po prostu użyj innego języka”. Ponownie ocenię ten wybór, jeśli się zmieni.

-O3daje nam garść swift_retaini swift_releasenazywa to, szczerze mówiąc, nie wygląda na to, że powinni być przy tym przykładzie. Optymalizator powinien unikać (większość) AFAICT, ponieważ zna większość informacji o tablicy i wie, że ma (przynajmniej) silne odniesienie do niej.

Nie powinien emitować więcej zachowań, nawet jeśli nie wywołuje funkcji, które mogłyby zwolnić obiekty. Nie sądzę, aby konstruktor tablic mógł zwrócić tablicę, która jest mniejsza niż ta, o którą prosiliśmy, co oznacza, że ​​wiele wysłanych kontroli jest bezużytecznych. Wie również, że liczba całkowita nigdy nie będzie większa niż 10k, więc kontrole przepełnienia można zoptymalizować (nie z powodu -Ofastdziwności, ale z powodu semantyki języka (nic innego się nie zmienia, ani nie można uzyskać do niej dostępu, i sumowanie do 10k jest bezpieczny dla tego typu Int).

Kompilator może jednak nie być w stanie rozpakować tablicy lub elementów tablicy, ponieważ są one przekazywane do sort(), która jest funkcją zewnętrzną i musi uzyskać oczekiwane argumenty. Spowoduje to, że będziemy musieli korzystać z Intwartości pośrednio, co sprawi, że będzie trochę wolniej. Mogłoby to ulec zmianie, gdyby sort()funkcja ogólna (nie w trybie wielu metod) była dostępna dla kompilatora i została wstawiona.

To jest bardzo nowy (publicznie) język i przechodzi przez to, co, jak zakładam, wiele zmian, ponieważ ludzie (mocno) zaangażowani w język Swift proszą o opinie i wszyscy mówią, że język nie jest ukończony i będzie zmiana.

Zastosowany kod:

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: Nie jestem ekspertem od Objective-C, ani wszystkich udogodnień z Cocoa , Objective-C, ani Swift. Mogę również zakładać pewne rzeczy, których nie napisałem.

Postanowiłem przyjrzeć się temu dla zabawy, a oto czasy, które otrzymuję:

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

Szybki

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

Wyniki:

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

Wydaje mi się, że jest to ta sama wydajność, jeśli się kompiluję -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

Wydaje się, że nastąpiła regresja wydajności od Swift 2.0 do Swift 3.0, a także widzę różnicę między -Oi -Ouncheckedpo raz pierwszy.

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 ponownie poprawia wydajność, zachowując lukę między -Oi -Ounchecked.-O -whole-module-optimizationnie wydaje się mieć znaczenia.

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

Wyniki:

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

Werdykt

W chwili pisania tego tekstu sortowanie Swift jest szybkie, ale jeszcze nie tak szybkie jak sortowanie w C ++ po kompilacji z -Opowyższymi kompilatorami i bibliotekami. Dzięki -Ouncheckedwydaje się być tak szybki jak C ++ w Swift 4.0.2 i Apple LLVM 9.0.0.

Od The Swift Programming Language:

Standardowa biblioteka funkcji sortowania Swift udostępnia funkcję o nazwie sort, która sortuje tablicę wartości znanego typu na podstawie danych wyjściowych dostarczonego zamknięcia sortowania. Po zakończeniu procesu sortowania funkcja sortowania zwraca nową tablicę tego samego typu i wielkości, co stara, z elementami w prawidłowej kolejności sortowania.

sortFunkcja ma dwa oświadczenia.

Domyślna deklaracja, która pozwala określić zamknięcie porównania:

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

I druga deklaracja, która bierze tylko jeden parametr (tablicę) i jest „zakodowana na stałe, aby użyć komparatora mniejszego niż”.

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

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

Przetestowałem zmodyfikowaną wersję twojego kodu na placu zabaw z dodanym zamknięciem, dzięki czemu mogłem nieco dokładniej monitorować tę funkcję, i odkryłem, że przy n ustawionym na 1000 zamknięcie było wywoływane około 11 000 razy.

let n = 1000
let x = Int[](count: n, repeatedValue: 0)
for i in 0..n {
    x[i] = random()
}
let y = sort(x) { $0 > $1 }

To nie jest wydajna funkcja, polecam użycie lepszej implementacji funkcji sortowania.

EDYTOWAĆ:

Przejrzałem stronę wikipedii Quicksort i napisałem dla niej implementację Swift. Oto pełny program, z którego korzystałem (na placu zabaw)

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
}

Używając tego przy n = 1000, znalazłem to

1. quickSort () został wywołany około 650 razy,
2. dokonano około 6000 zamian,
3. i jest około 10 000 porównań

Wygląda na to, że wbudowana metoda sortowania jest (lub jest bliska) szybkim sortowaniem i jest naprawdę powolna ...

Od Xcode 7 możesz włączyć Fast, Whole Module Optimization. Powinno to natychmiast zwiększyć wydajność.

Ponownie sprawdzono wydajność funkcji Swift Array:

Napisałem własny test porównawczy Swift z C / Objective-C. Mój test porównawczy oblicza liczby pierwsze. Wykorzystuje tablicę poprzednich liczb pierwszych do wyszukiwania czynników pierwszych u każdego nowego kandydata, więc jest dość szybki. Jednak robi TONY odczytu tablicy i mniej zapisu do tablic.

Pierwotnie zrobiłem ten test porównawczy przeciwko Swift 1.2. Postanowiłem zaktualizować projekt i uruchomić go przeciwko Swift 2.0.

Projekt pozwala wybierać między użyciem zwykłych szybkich tablic a użyciem szybkich niebezpiecznych buforów pamięci przy użyciu semantyki macierzy.

W przypadku C / Objective-C możesz wybrać użycie NSArrays lub C malloc'ed.

Wyniki testu wydają się dość podobne z najszybszą, najmniejszą optymalizacją kodu ([-0s]) lub najszybszą, agresywną ([-0fast]) optymalizacją.

Wydajność Swift 2.0 jest nadal okropna przy wyłączonej optymalizacji kodu, podczas gdy wydajność C / Objective-C jest tylko umiarkowanie wolniejsza.

Najważniejsze jest to, że obliczenia oparte na tablicy C malloc'd są najszybsze, ze skromnym marginesem

Swift z niebezpiecznymi buforami zajmuje około 1,19X - 1,20X dłużej niż tablice C malloc'd przy użyciu najszybszej, najmniejszej optymalizacji kodu. różnica wydaje się nieco mniejsza w przypadku szybkiej, agresywnej optymalizacji (Swift zajmuje o 1,18x do 1,16x więcej niż C.

Jeśli używasz zwykłych tablic Swift, różnica z C jest nieco większa. (Swift zajmuje ~ 1,22 do 1,23 dłużej.)

Zwykłe tablice Swift są DRAMATICALLY szybsze niż w Swift 1.2 / Xcode 6. Ich wydajność jest tak bliska, jak w przypadku tablic Swift opartych na buforach niebezpiecznych, że używanie niebezpiecznych buforów pamięci nie wydaje się już warte większych kłopotów, co jest duże.

BTW, wydajność NSArray Objective-C śmierdzi. Jeśli zamierzasz używać natywnych obiektów kontenerowych w obu językach, Swift jest DRAMATYCZNIE szybszy.

Możesz sprawdzić mój projekt na github na SwiftPerformanceBenchmark

Ma prosty interfejs użytkownika, który sprawia, że ​​zbieranie statystyk jest bardzo łatwe.

Interesujące jest to, że sortowanie w Swift wydaje się nieco szybsze niż w C, ale ten algorytm liczb pierwszych jest jeszcze szybszy w Swift.

Głównym problemem, o którym wspominają inni, ale nie są wystarczająco wzywani, jest to, że -O3w Swift nic nie robi (i nigdy nie ma), więc po skompilowaniu jest efektywnie niezoptymalizowany ( -Onone).

Nazwy opcji zmieniają się z czasem, więc niektóre inne odpowiedzi mają przestarzałe flagi dla opcji kompilacji. Prawidłowe bieżące opcje (Swift 2.2) to:

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

Optymalizacja całego modułu ma wolniejszą kompilację, ale może optymalizować pliki w module, tj. W ramach każdej struktury i w obrębie rzeczywistego kodu aplikacji, ale nie między nimi. Powinieneś używać tego do wszystkiego, co ma kluczowe znaczenie dla wydajności)

Możesz także wyłączyć kontrole bezpieczeństwa, aby uzyskać jeszcze większą prędkość, ale wszystkie twierdzenia i warunki wstępne są nie tylko wyłączone, ale zoptymalizowane na podstawie ich poprawności. Jeśli kiedykolwiek trafisz na stwierdzenie, oznacza to, że jesteś w nieokreślonym zachowaniu. Używaj z dużą ostrożnością i tylko wtedy, gdy stwierdzisz, że przyspieszenie jest dla Ciebie opłacalne (przez testowanie). Jeśli uznasz, że jest on cenny dla jakiegoś kodu, zalecam rozdzielenie tego kodu na osobną strukturę i wyłączenie kontroli bezpieczeństwa tylko dla tego modułu.

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) 

To jest mój blog o szybkim sortowaniu - przykładowy szybki sort Githuba

Możesz przyjrzeć się algorytmowi partycjonowania Lomuto w Partycjonowaniu listy. Napisane w Swift.

Swift 4.1 wprowadza nowy -Osizetryb optymalizacji.

W Swift 4.1 kompilator obsługuje teraz nowy tryb optymalizacji, który umożliwia dedykowane optymalizacje w celu zmniejszenia rozmiaru kodu.

Kompilator Swift jest wyposażony w zaawansowane optymalizacje. Podczas kompilacji z opcją -O kompilator próbuje przekształcić kod, aby działał z maksymalną wydajnością. Jednak ta poprawa wydajności środowiska wykonawczego może czasem wynikać z kompromisu zwiększonego rozmiaru kodu. Dzięki nowemu trybowi optymalizacji -Osize użytkownik ma możliwość kompilacji dla minimalnego rozmiaru kodu, a nie dla maksymalnej prędkości.

Aby włączyć tryb optymalizacji rozmiaru w wierszu poleceń, użyj -Osize zamiast -O.

Dalsza lektura: https://swift.org/blog/osize/