performance - Prestazioni di Swift Beta:ordinamento di array




sorting xcode6 compiler-optimization (8)

Da The Swift Programming Language :

La libreria standard di Sort Function Swift fornisce una funzione chiamata sort, che ordina una matrice di valori di un tipo noto, in base all'output di una chiusura di ordinamento fornita dall'utente. Una volta completato il processo di ordinamento, la funzione di ordinamento restituisce una nuova matrice dello stesso tipo e dimensione di quella precedente, con i suoi elementi nell'ordine ordinato corretto.

La funzione di sort ha due dichiarazioni.

La dichiarazione predefinita che consente di specificare una chiusura di confronto:

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

E una seconda dichiarazione che prende solo un singolo parametro (la matrice) ed è "hardcoded per usare il comparatore minore di".

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

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

Ho provato una versione modificata del tuo codice in un parco giochi con la chiusura aggiunta in modo da poter controllare la funzione un po 'più da vicino, e ho trovato che con n impostato su 1000, la chiusura veniva chiamata circa 11.000 volte.

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

Non è una funzione efficiente, vorrei raccomandare una migliore implementazione della funzione di ordinamento.

MODIFICARE:

Ho dato un'occhiata alla pagina di wikipedia Quicksort e ho scritto un'implementazione Swift per questo. Ecco il programma completo che ho usato (in un parco giochi)

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
}

Usando questo con n = 1000, l'ho trovato

  1. quickSort () è stato chiamato circa 650 volte,
  2. sono stati fatti circa 6000 swap,
  3. e ci sono circa 10.000 confronti

Sembra che il metodo di ordinamento incorporato sia (o sia vicino) all'ordinamento rapido ed è molto lento ...

Stavo implementando un algoritmo in Swift Beta e ho notato che la performance era molto scarsa. Dopo aver scavato più a fondo, mi sono reso conto che uno dei colli di bottiglia era qualcosa di semplice come l'ordinamento degli array. La parte rilevante è qui:

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 ++, un'operazione simile richiede 0.06 sul mio computer.

In Python ci vogliono 0,6 secondi (senza trucchi, solo y = ordinati (x) per un elenco di numeri interi).

In Swift ci vogliono 6 se lo compilo con il seguente comando:

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

E ci vogliono ben 88 se lo compilo con il seguente comando:

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

I tempi in Xcode con build "Release" vs "Debug" sono simili.

Cosa c'è di sbagliato qui? Potrei capire alcune perdite di prestazioni rispetto al C ++, ma non un rallentamento di 10 volte rispetto al Python puro.

Edit: mweathers ha notato che il passaggio da -O3 a -Ofast fa funzionare questo codice quasi alla stessa velocità della versione C ++! Tuttavia, -Ofast cambia la semantica della lingua molto - nel mio test, disabilita i controlli per overflow integer e overflow di indicizzazione degli array . Ad esempio, con -Ofast il seguente codice Swift gira in modo silenzioso senza -Ofast (e stampa un po 'di spazzatura):

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

Quindi, non è quello che vogliamo; l'intero punto di Swift è che abbiamo le reti di sicurezza sul posto. Ovviamente le reti di sicurezza hanno un impatto sulle prestazioni, ma non dovrebbero rendere i programmi 100 volte più lenti. Ricorda che Java controlla già i limiti dell'array, e nei casi tipici il rallentamento è di un fattore molto inferiore a 2. E in Clang e GCC abbiamo ottenuto -ftrapv per il controllo degli overflow integer (firmati), e non è così lento, .

Da qui la domanda: come possiamo ottenere una prestazione ragionevole in Swift senza perdere le reti di sicurezza?

Modifica 2: ho fatto un po 'più di benchmarking, con loop molto semplici sulla falsariga di

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

(Qui l'operazione xor è lì solo per poter trovare più facilmente il loop pertinente nel codice assembly. Ho provato a selezionare un'operazione facile da individuare ma anche "innocua" nel senso che non dovrebbe richiedere alcun controllo correlato to integer overflow.)

Ancora una volta, c'è stata un'enorme differenza nelle prestazioni tra -O3 e -Ofast . Quindi ho dato un'occhiata al codice assembly:

  • Con -Ofast ottengo più o meno quello che mi aspetterei. La parte rilevante è un loop con 5 istruzioni di linguaggio macchina.

  • Con -O3 ottengo qualcosa che andava oltre la mia più sfrenata immaginazione. Il ciclo interno si estende su 88 righe di codice assembly. Non ho cercato di capire tutto, ma le parti più sospette sono 13 invocazioni di "callq _swift_retain" e altre 13 chiamate di "callq _swift_release". Cioè, 26 chiamate di subroutine nel loop interno !

Modifica 3: nei commenti, Ferruccio ha chiesto dei benchmark che siano equi nel senso che non si basano su funzioni integrate (ad es. Sort). Penso che il seguente programma sia un buon esempio:

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

Non c'è aritmetica, quindi non dobbiamo preoccuparci di overflow integer. L'unica cosa che facciamo è solo un sacco di riferimenti di matrice. E i risultati sono qui: Swift -O3 perde per fattore quasi 500 in confronto a -Ottimo:

  • C ++ -O3: 0,05 s
  • C ++ -O0: 0,4 s
  • Java: 0,2 s
  • Python con PyPy: 0,5 s
  • Python: 12 s
  • Veloce: veloce: 0,05 s
  • Swift -O3: 23 s
  • Swift -O0: 443 s

(Se sei preoccupato che il compilatore possa ottimizzare completamente i loop senza punti, puoi cambiarlo ad esempio x[i] ^= x[j] e aggiungere un'istruzione print che restituisca x[0] . Questo non cambia nulla ; i tempi saranno molto simili).

E sì, qui l'implementazione di Python è stata una stupida implementazione di Python pura con un elenco di interi e cicli annidati. Dovrebbe essere molto più lento di Swift non ottimizzato. Qualcosa sembra essere seriamente rotto con Swift e l'indicizzazione degli array.

Modifica 4: questi problemi (così come altri problemi di prestazioni) sembrano essere stati risolti in Xcode 6 beta 5.

Per l'ordinamento, ora ho i seguenti tempi:

  • clang ++ -O3: 0,06 s
  • swiftc -Ottimo: 0,1 s
  • swiftc -O: 0,1 s
  • swiftc: 4 s

Per cicli annidati:

  • clang ++ -O3: 0,06 s
  • swiftc: veloce: 0.3 s
  • swiftc -O: 0.4 s
  • swiftc: 540 s

Sembra che non ci sia più alcun motivo per usare il non sicuro -Ofast (aka -Ounchecked ); plain -O produce codice altrettanto buono.


TL; DR : Sì, l'unica implementazione della lingua Swift è lenta, al momento . Se hai bisogno di codice veloce, numerico (e altri tipi di codice, presumibilmente), vai con un altro. In futuro, dovresti rivalutare la tua scelta. Potrebbe essere abbastanza buono per la maggior parte del codice applicativo che è scritto ad un livello più alto, però.

Da quello che sto vedendo in SIL e LLVM IR, sembra che abbiano bisogno di un sacco di ottimizzazioni per la rimozione di retain e release, che potrebbero essere implementati in Clang (per Objective-C), ma non li hanno ancora portati. Questa è la teoria con cui sto andando (per ora ... ho ancora bisogno di confermare che Clang fa qualcosa al riguardo), dal momento che un profiler eseguito sull'ultimo caso di test di questa domanda produce questo risultato "carino":

Come è stato detto da molti altri, -Ofast è assolutamente pericoloso e cambia la semantica della lingua". Per me, è nella fase "Se lo userai, usa solo un'altra lingua". Valuterò questa scelta più tardi, se cambierà.

-O3 ci fa un sacco di chiamate swift_retain e swift_release che, onestamente, non sembrano come dovrebbero essere lì per questo esempio. L'ottimizzatore dovrebbe averli elidati (la maggior parte) AFAICT, poiché conosce la maggior parte delle informazioni sull'array e sa di avere (almeno) un forte riferimento ad esso.

Non dovrebbe emettere più ritardi quando non chiama nemmeno funzioni che potrebbero rilasciare gli oggetti. Non penso che un costruttore di array possa restituire un array più piccolo di quello richiesto, il che significa che molti controlli emessi sono inutili. Sa anche che il numero intero non sarà mai superiore a 10k, quindi i controlli di overflow possono essere ottimizzati (non a causa di -Ofast strana -Ofast , ma a causa della semantica del linguaggio (nient'altro sta cambiando quel var né può accedervi e aggiungere a 10k è sicuro per il tipo Int ).

Il compilatore potrebbe non essere in grado di decomprimere l'array o gli elementi dell'array, dato che vengono passati a sort() , che è una funzione esterna e deve ottenere gli argomenti che si aspettano. Questo ci renderà necessario utilizzare i valori Int indirettamente, il che renderebbe un po 'più lento. Questo potrebbe cambiare se la funzione generica sort() (non nel modo multi-metodo) fosse disponibile per il compilatore e venisse sottolineata.

Questo è un linguaggio (pubblicamente) molto nuovo, e sta passando per quello che presumo sono molti cambiamenti, dal momento che ci sono persone (pesantemente) coinvolte nella lingua Swift che chiedono feedback e tutti dicono che la lingua non è finita e modificare.

Codice utilizzato:

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: Non sono un esperto di Objective-C, né tutte le strutture di Cocoa , Objective-C o dei runtime di Swift. Potrei anche assumere alcune cose che non ho scritto.


A partire da Xcode 7 è possibile attivare l' Fast, Whole Module Optimization . Questo dovrebbe aumentare la tua performance immediatamente.


Ho deciso di dare un'occhiata a questo per divertimento, e qui ci sono i tempi che ottengo:

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

veloce

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

risultati:

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

Sembra essere la stessa performance se compilo con -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

Sembra esserci stata una regressione delle prestazioni da Swift 2.0 a Swift 3.0, e vedo anche una differenza tra -O e -Ounchecked per la prima volta.

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 migliora di nuovo le prestazioni, mantenendo uno spazio tra -O e -Ounchecked . -O -whole-module-optimization non sembrava fare la differenza.

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

risultati:

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

Verdetto

Al momento della stesura di questo articolo, l'ordinamento di Swift è veloce, ma non ancora veloce come l'ordinamento di C ++ quando compilato con -O , con i compilatori e le librerie di cui sopra. Con -Ounchecked , sembra essere veloce come C ++ in Swift 4.0.2 e Apple LLVM 9.0.0.


Rendimento di Swift Array rivisitato:

Ho scritto il mio benchmark confrontando Swift con C / Objective-C. Il mio benchmark calcola i numeri primi. Usa la matrice dei precedenti numeri primi per cercare i fattori primi in ogni nuovo candidato, quindi è abbastanza veloce. Tuttavia, fa tonnellate di lettura di array e meno di scrittura su array.

Inizialmente ho fatto questo punto di riferimento contro Swift 1.2. Ho deciso di aggiornare il progetto ed eseguirlo contro Swift 2.0.

Il progetto ti consente di scegliere tra l'utilizzo di normali array swift e l'uso di buffer di memoria non sicuri Swift usando la semantica dell'array.

Per C / Objective-C, è possibile scegliere di utilizzare gli array NSArrays o C malloc'ed.

I risultati del test sembrano essere molto simili con l'ottimizzazione del codice più veloce, più piccola ([-0s]) o più rapida, aggressiva ([-0fast]).

Le prestazioni di Swift 2.0 sono ancora orribili con l'ottimizzazione del codice disattivata, mentre le prestazioni di C / Objective-C sono solo moderatamente più lente.

La linea di fondo è che i calcoli basati su array malloc C sono i più veloci, con un margine modesto

Swift con buffer non sicuri richiede circa 1.19X - 1.20X in più rispetto agli array malloc'd C quando si utilizza l'ottimizzazione del codice più rapida e più piccola. la differenza sembra leggermente inferiore con un'ottimizzazione rapida e aggressiva (Swift prende più come 1.18x a 1.16x più lungo di C.

Se si usano array Swift regolari, la differenza con C è leggermente maggiore. (Swift impiega ~ 1,22 a 1,23 in più.)

Gli array Swift regolari sono DRAMATICALLY più veloci di quanto non fossero in Swift 1.2 / Xcode 6. Le loro prestazioni sono così vicine agli array basati su buffer Swift non sicuri che l'utilizzo di buffer di memoria non sicuri non sembra davvero più un problema, che è grande.

A proposito, le prestazioni NSArray dell'Objective-C fa schifo. Se vuoi usare gli oggetti container nativi in ​​entrambe le lingue, Swift è DRAMATICAMENTE più veloce.

Puoi controllare il mio progetto su github su SwiftPerformanceBenchmark

Ha una semplice interfaccia utente che facilita la raccolta delle statistiche.

È interessante notare che l'ordinamento sembra essere leggermente più veloce in Swift che in C ora, ma che questo algoritmo di numero primo è ancora più veloce in Swift.


Il problema principale che viene menzionato da altri ma non chiamato abbastanza è che -O3 non fa nulla in Swift (e non ha mai) quindi quando compilato con esso è effettivamente non ottimizzato ( -Onone ).

I nomi delle opzioni sono cambiati nel tempo, quindi alcune altre risposte hanno contrassegni obsoleti per le opzioni di compilazione. Le opzioni correnti corrette (Swift 2.2) sono:

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

L'ottimizzazione di tutto il modulo ha una compilazione più lenta ma può essere ottimizzata su tutti i file all'interno del modulo, ad esempio all'interno di ogni framework e all'interno del codice effettivo dell'applicazione, ma non tra di essi. Si dovrebbe usare questo per qualsiasi performance critica

Puoi anche disabilitare i controlli di sicurezza per una velocità ancora maggiore, ma con tutte le asserzioni e le precondizioni non solo disabilitate ma ottimizzate sulla base della loro correttezza. Se hai mai raggiunto un'affermazione, significa che sei in comportamento indefinito. Usare con estrema cautela e solo se si determina che l'aumento di velocità è utile per te (testando). Se lo trovi utile per alcuni codici, ti consiglio di separare quel codice in un framework separato e di disabilitare solo i controlli di sicurezza per quel modulo.


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) 

Questo è il mio blog su Quick Sort- Github sample Quick-Sort

Puoi dare un'occhiata all'algoritmo di partizionamento di Lomuto in Partizionare la lista. Scritto in Swift


È dovuto all'utilizzo in virgola mobile denormalizzato. Come sbarazzarsi di entrambi e della penalità delle prestazioni? Dopo aver perlustrato Internet per modi di uccidere numeri denormali, sembra che non ci sia ancora un modo "migliore" per farlo. Ho trovato questi tre metodi che possono funzionare meglio in ambienti diversi:

  • Potrebbe non funzionare in alcuni ambienti GCC:

    // Requires #include <fenv.h>
    fesetenv(FE_DFL_DISABLE_SSE_DENORMS_ENV);
    
  • Potrebbe non funzionare in alcuni ambienti di Visual Studio: 1

    // Requires #include <xmmintrin.h>
    _mm_setcsr( _mm_getcsr() | (1<<15) | (1<<6) );
    // Does both FTZ and DAZ bits. You can also use just hex value 0x8040 to do both.
    // You might also want to use the underflow mask (1<<11)
    
  • Sembra funzionare sia in GCC che in Visual Studio:

    // Requires #include <xmmintrin.h>
    // Requires #include <pmmintrin.h>
    _MM_SET_FLUSH_ZERO_MODE(_MM_FLUSH_ZERO_ON);
    _MM_SET_DENORMALS_ZERO_MODE(_MM_DENORMALS_ZERO_ON);
    
  • Il compilatore Intel ha opzioni per disabilitare i denormali di default sulle moderne CPU Intel. Maggiori dettagli qui

  • Interruttori del compilatore. -ffast-math , -msse o -mfpmath=sse disabiliterà i denormals e renderà qualche altra cosa più veloce, ma sfortunatamente fa anche molte altre approssimazioni che potrebbero infrangere il tuo codice. Prova con attenzione! L'equivalente di fast-math per il compilatore di Visual Studio è /fp:fast ma non sono stato in grado di confermare se questo disabilita anche i denormali. 1







swift performance sorting xcode6 compiler-optimization