Wydajność Swift Beta: sortowanie tablic

TL; DR: Tak, jedyna implementacja języka Swift jest powolna, w tej chwili. Jeśli potrzebujesz szybkiego, numerycznego (i innych rodzajów kodu, prawdopodobnie) kodu, po prostu wybierz inny. W przyszłości powinieneś ponownie ocenić swój wybór. Może to być jednak wystarczająco dobre dla większości kodu aplikacji, który jest napisany na wyższym poziomie.

Z tego, co widzę w SIL i LLVM IR, wygląda na to, że potrzebują kilku optymalizacji do usuwania zatrzymań i wydań, które mogą być zaimplementowano w Clang (dla Objective-C), ale jeszcze ich nie przeportowano. Z tą teorią się Zgadzam (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, -Ofast jest całkowicie niebezpieczne i zmienia semantykę języka. Dla mnie jest to etap "jeśli masz zamiar tego użyć, po prostu użyj innego języka". Ja oceń ten wybór później, jeśli się zmieni.

-O3 / align = "center" bgcolor = "# e0ffe0 " / cesarz chin / / align = center / Optymalizator powinien usunąć (większość) z nich AFAICT, ponieważ zna większość informacji o tablicy i wie, że ma (przynajmniej) silne odniesienie do niej.

Nie powinien emitować więcej zatrzymań, gdy nawet nie wywołuje funkcji, które mogłyby zwolnić obiekty. Nie sądzę, żeby konstruktor tablicy może zwrócić tablicę, która jest mniejsza niż ta, o którą poproszono, co oznacza, że wiele kontroli, które zostały wyemitowane, jest bezużytecznych. Wie również, że liczba całkowita nigdy nie będzie wyższa niż 10k, więc sprawdzanie przepełnienia Może być zoptymalizowane (nie ze względu na dziwność -Ofast, ale ze względu na semantykę języka(nic innego nie zmienia, że var nie może uzyskać do niego dostępu, a dodanie do 10K jest bezpieczne dla typu Int).

Kompilator może nie być w stanie rozpakować tablicy lub tablicy elementy, ponieważ są przekazywane do sort(), która jest zewnętrzną funkcją I musi uzyskać argumenty, których oczekuje. Spowoduje to, że będziemy musieli użyć wartości Int pośrednio, co sprawi, że będzie to działać nieco wolniej. Może się to zmienić, jeśli funkcja ogólna sort() (nie w sposób wielowątkowy) będzie dostępna dla kompilatora i zostanie zainlinowana.

Jest to bardzo nowy (publicznie) język i przechodzi przez to, co zakładam, że jest wiele zmian, ponieważ są ludzie (mocno) język Swift prosi o opinie i wszyscy mówią, że język nie jest skończony i się zmieni.

Użyty 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")

P. s: nie jestem ekspertem od Objective-C ani wszystkich urządzeń z Cocoa , Objective-C, czy Swift runtimes. Mogę też zakładać pewne rzeczy, których nie napisałem.

W tym samym czasie, w którym się pojawiłem, postanowiłem rzucić na to okiem dla zabawy, a oto momenty, które otrzymałem:

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

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 się być taka sama wydajność, jeśli kompiluję z -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

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 -O a -Ounchecked. -O -whole-module-optimization wydawało się, że nie robi różnicy.

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 momencie pisania tego tekstu, sortowanie Swifta jest szybkie, ale nie tak szybkie jak sortowanie C++, gdy jest skompilowane z -O, z powyższymi kompilatorami i bibliotekami. Z -Ounchecked, wydaje się być tak szybki jak C++ w Swift 4.0.2 i Apple LLVM 9.0.0.

Od The Swift Programming Language:

Funkcja sortowania Biblioteka Standardowa Swift udostępnia funkcję o nazwie sort, który sortuje tablicę wartości znanego typu, na podstawie wyjście zamknięcia sortowania, które dostarczasz. Po zakończeniu procesu sortowania, funkcja sort zwraca nową tablicę o tej samej typ i rozmiar jak stary, z jego elementami w poprawnym posortowaniu spokój.

Funkcja sort posiada dwie deklaracje.

Domyślna deklaracja, która pozwala określić zakończenie porównania:

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

I druga deklaracja, która przyjmuje tylko jeden parametr (tablicę) i jest " zakodowana na twardo, aby użyć komparatora less-than."

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

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

Przetestowałem zmodyfikowaną wersję Twojego kodu na placu zabaw z włączonym zamknięciem, aby móc dokładniej monitorować funkcję, i odkryłem, że z 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 }

Nie jest funkcją efektywną, a Polecam użycie lepszej implementacji funkcji sortowania.

EDIT:

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 z n=1000, stwierdziłem, że

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

Wygląda na to, że wbudowany sort metoda jest (lub jest blisko) szybkim sortowaniem i jest naprawdę powolna...

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

Swift array performance revisited:

Napisałem własny benchmark porównujący Swift z C / Objective - C. mój benchmark oblicza liczby pierwsze. Używa tablicy poprzednich liczb pierwszych, aby szukać czynników pierwszych w każdym nowym kandydacie, więc jest to dość szybkie. Jednak robi mnóstwo odczytu tablic i mniej zapisu do tablic.

Początkowo zrobiłem ten benchmark przeciwko Swift 1.2. Postanowiłem zaktualizować projekt i uruchomić go pod Swift 2.0.

Projekt pozwala Wybierz pomiędzy używaniem zwykłych tablic swift a używaniem bezpiecznych buforów pamięci Swift przy użyciu semantyki tablicy.

Dla C/Objective-C, możesz użyć tablic NSArrays lub C malloc ' ed.

Wyniki testów wydają się być bardzo podobne z najszybszą, najmniejszą optymalizacją kodu ([- 0s]) lub najszybszą, agresywną ([- 0fast]) optymalizacją.

Wydajność Swift 2.0 jest nadal okropna z wyłączoną optymalizacją kodu, podczas gdy wydajność C/Objective-C jest tylko umiarkowana wolniej.

Najważniejsze jest to, że obliczenia oparte na tablicy C malloc ' D są najszybsze, o skromny margines

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

Jeśli używasz zwykłych tablic Swift, różnica z C jest nieznacznie 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 tablicom opartym na bezpiecznych buforach Swift, że używanie niebezpiecznych buforów pamięci nie wydaje się już warte zachodu, co jest duże.

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

Możesz sprawdzić mój projekt na GitHubie pod adresem SwiftPerformanceBenchmark

Posiada prosty interfejs, który ułatwia zbieranie statystyk.

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

Głównym problemem, o którym wspominają inni, ale nie przywołanym wystarczająco, jest to, że -O3 nic nie robi w Swifcie (i nigdy nie robił), więc po skompilowaniu z tym jest efektywnie nieoptymalizowany (-Onone).

Nazwy opcji zmieniały się z czasem, więc niektóre inne odpowiedzi mają przestarzałe flagi dla opcji budowania. Poprawne 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 zoptymalizować pliki wewnątrz modułu, tj. w ramach każdego frameworka i w ramach rzeczywistego kodu aplikacji, ale nie między nimi. Powinieneś użyć tego do wszystkiego, co krytyczne dla wydajności)

Można również wyłączyć kontrole bezpieczeństwa dla jeszcze większej prędkości, ale ze wszystkimi twierdzeniami i warunkami wstępnymi nie tylko wyłączonymi, ale zoptymalizowanymi na podstawie ich poprawności. Jeśli kiedykolwiek trafisz na twierdzenie, oznacza to, że jesteś w nieokreślonym zachowaniu. Używaj ze szczególną ostrożnością i tylko wtedy, gdy stwierdzisz, że przyspieszenie prędkości jest dla Ciebie opłacalne (testując). Jeśli go znajdziesz cenny dla jakiegoś kodu polecam rozdzielenie tego kodu na osobny framework i wyłączenie tylko kontroli bezpieczeństwa 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) 

Możesz spojrzeć na algorytm partycjonowania Lomuto w partycjonowaniu listy. Napisane w Swift