Exécution rapide : tri des tableaux

Question

J'ai été la mise en œuvre d'un algorithme rapide et remarqué que la performance a été très mauvaise. Après pour aller plus loin, j'ai réalisé que l'un des goulots d'étranglement a été quelque chose d'aussi simple que le tri des tableaux. La partie pertinente est ici:

let n = 1000000
let x = Int[](count: n, repeatedValue: 0)
for i in 0..n {
    x[i] = random()
}
// start clock here
let y = sort(x)
// stop clock here

En C++, une opération similaire prend 0.06 s sur mon ordinateur.

En Python, il prend 0,6 s (pas de trucs, juste y = sorted(x) pour une liste d'entiers).

En Swift, il prend 6 s si je compile avec la commande suivante:

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

Et il faut autant que 88 s si je compile avec la commande suivante:

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

Les périodes de temps dans Xcode avec "Libération" et "Debug" versions sont similaires.

Quel est le problème ici? J'ai pu comprendre certaines pertes de performances en comparaison avec le C++, mais pas 10 fois de ralentissement en comparaison avec pur Python.

---

Edit: mweathers remarqué qu'en changeant -O3 de -Ofast rend ce code exécuté presque aussi rapide que la version C++! Toutefois, -Ofast la sémantique de la langue beaucoup dans mes tests, il a désactivé les chèques pour les débordements d'entiers et le tableau d'indexation des débordements. Par exemple, avec -Ofast la suite Swift code s'exécute en mode silencieux sans s'écraser (et imprime des ordures):

let n = 10000000
println(n*n*n*n*n)
let x = Int[](count: n, repeatedValue: 10)
println(x[n])

Donc, -Ofast n'est pas ce que nous voulons; le point de l'ensemble de Swift est que nous avons les filets de sécurité en place. Bien sûr, les filets de sécurité qui ont une incidence sur les performances, mais ils ne devraient pas faire les programmes 100 fois plus lent. Rappelez-vous que Java est déjà vérifie les limites du tableau, et dans les cas typiques, le ralentissement de l'activité par un facteur inférieur à 2. Et dans le Bruit et la GCC que nous avons eu, -ftrapv pour le contrôle (signé) des débordements d'entiers, et il n'est pas lent, soit.

D'où la question: comment pouvons-nous obtenir un rendement raisonnables dans Swift sans perdre les filets de sécurité?

---

Edit 2: j'ai fait un peu plus d'analyse comparative, très simples boucles le long de la lignes de

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

(Ici, l'opération xor est là juste pour que je puisse plus facilement s'y retrouver boucle dans le code assembleur. J'ai essayé de chercher une opération qui est facile à repérer, mais aussi "inoffensif" dans le sens où il ne devrait pas exiger des vérifications liées à des débordements d'entiers.)

Encore une fois, il y avait une énorme différence dans les performances entre -O3 et -Ofast. J'ai donc eu un coup d'oeil à l'assemblée de code:

• Avec -Ofast - je obtenir à peu près ce que je m'attends. La partie pertinente est une boucle avec 5 instructions en langage machine.

• Avec -O3 - je obtenir quelque chose qui était au-delà de mon imagination la plus folle. La boucle interne s'étend sur 88 lignes de code assembleur. Je n'ai pas essayer de tout comprendre, mais la plupart des suspects pièces sont 13 invocations de "callq _swift_retain" et l'autre de 13 invocations de "callq _swift_release". C'est, 26 sous-routine appels dans l'intérieur de la boucle!

---

Edit 3: Dans les commentaires, Ferruccio demandé pour les points de référence qui sont juste dans le sens où ils ne reposent pas sur des fonctions intégrées (par exemple, tri). Je pense que le programme suivant est un assez bon exemple:

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

Il n'est pas de l'arithmétique, de sorte que nous n'avons pas besoin de s'inquiéter au sujet des débordements d'entiers. La seule chose que nous faisons est juste beaucoup de références de tableau. Et les résultats sont ici-Swift -O3 perd par un facteur de près de 500 en comparaison avec d'-Ofast:

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

(Si vous craignez que le compilateur peut optimiser l'inutile boucles entièrement, vous pouvez modifier, par exemple, x[i] ^= x[j], et ajouter une instruction d'impression que les sorties x[0]. Cela ne change rien; les horaires sont très similaires.)

Et oui, ici, le Python de la mise en œuvre a été un stupide pur Python de mise en œuvre avec une liste d'entiers et des boucles for imbriquées. Il devrait être beaucoup plus lent que unoptimised Swift. Quelque chose semble être brisé avec Swift et tableau d'indexation.

---

Edit 4: Ces questions (ainsi que certains autres problèmes de performances) semble avoir été corrigé dans Xcode 6 beta 5.

Pour le tri, j'ai maintenant le minutage suivant:

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

Pour les boucles imbriquées:

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

Il semble qu'il n'y a aucune raison de plus pour utiliser le dangereux -Ofast (un.k.un. -Ounchecked); plaine de l' -O produit également du bon code.

Answer 1

tl;dr Swift est maintenant aussi vite que C par ce repère à l'aide de la version par défaut de l'optimisation du niveau de [-O].

Ici est un lieu de quicksort dans 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)
}

Et la même en 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);
}

À la fois le travail:

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]

Les deux sont appelés dans le même programme qu'à l'écrit.

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

Cette fonction convertit l'absolu fois de secondes:

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

Voici, en résumé, le compilateur optimazation niveaux:

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

Temps (en secondes) avec [Individualisé] pour n=10_000:

Swift:            0.895296452
C:                0.001223848

Voici Swift builtin sort() pour n=10_000:

Swift_builtin:    0.77865783

Ici est [-O] pour n=10_000:

Swift:            0.045478346
C:                0.000784666
Swift_builtin:    0.032513488

Comme vous pouvez le voir, de Swift, de l'amélioration du rendement d'un facteur 20.

Comme par mweathers réponse, paramètre [-Ofast] fait la véritable différence, résultant en ces temps pour n=10_000:

Swift:            0.000706745
C:                0.000742374
Swift_builtin:    0.000603576

Et pour n=1_000_000:

Swift:            0.107111846
C:                0.114957179
Swift_sort:       0.092688548

Pour la comparaison, c'est avec [Individualisé] pour n=1_000_000:

Swift:            142.659763258
C:                0.162065333
Swift_sort:       114.095478272

Tellement rapide avec aucun des optimisations était presque 1000x plus lent que C dans ce repère, à ce stade de son développement. D'autre part, avec les deux compilateurs définie sur [-Ofast] Swift effectivement accompli au moins aussi bien si ce n'est légèrement mieux que C.

Il a été souligné que [-Ofast] la sémantique de la langue, ce qui en fait potentiellement dangereux. C'est ce que Apple états dans Xcode 5.0 notes de version:

Un nouveau niveau d'optimisation -Ofast, disponible dans LLVM, permet des optimisations agressives. -Ofast détend de certains conservateurs, les restrictions, surtout pour les opérations à virgule flottante, qui sont sans danger pour la plupart de code. Il peut apporter d'importants haute performance gagne du compilateur.

Ils ont tous, mais l'avocat. Si c'est judicieux ou pas, je ne pouvais pas le dire, mais de ce que je peux dire, il semble assez raisonnable d'utiliser [-Ofast] dans un communiqué de presse si vous ne faites pas de haute précision en arithmétique à virgule flottante et que vous en êtes sûr pas de nombre entier ou un tableau des débordements sont possibles dans votre programme. Si vous avez besoin de haute performance et de dépassement de contrôles / précis d'arithmétique, puis choisir une autre langue pour le moment.

LA BETA 3 DE MISE À JOUR:

n=10_000 avec [-O]:

Swift:            0.019697268
C:                0.000718064
Swift_sort:       0.002094721

Swift en général est un peu plus rapide et il semble que Swift intégré de sorte a bien changé de manière significative.

DERNIÈRE MISE À JOUR:

[Individualisé]:

Swift:   0.678056695
C:       0.000973914

[-O]:

Swift:   0.001158492
C:       0.001192406

[-Ounchecked]:

Swift:   0.000827764
C:       0.001078914

Answer 2

TL;DR: Oui, la seule Swift de la langue mise en œuvre est lente, à droite maintenant. Si vous avez besoin rapide, numérique (et d'autres types de code, sans doute) du code, il suffit d'aller avec un autre. Dans l'avenir, vous devez réévaluer votre choix. Il pourrait être assez bon pour la plupart des applications de code est écrit à un niveau plus élevé, cependant.

À partir de ce que je vois dans SIL et IR LLVM, il semble comme ils ont besoin d'un tas d'optimisations pour le retrait de conserve et restitue, qui pourrait être mise en œuvre dans Clang (Objective-C), mais ils n'ont pas porté encore. C'est la théorie, je vais avec (pour l'instant... j'ai encore besoin de confirmer que Clang fait quelque chose à ce sujet), depuis un profileur de fonctionner sur le dernier test de cette question, les rendements de cette "jolie" résultat:

Comme cela a été dit par beaucoup d'autres, -Ofast est totalement dangereux et change la langue de la sémantique. Pour moi, c'est à la "Si vous allez l'utiliser, il suffit d'utiliser une autre langue". Je vais re-évaluer ce choix plus tard, si elle change.

-O3 nous permet d'obtenir un tas d' swift_retain et swift_release des appels qui, honnêtement, ne me regardez pas comme ils devraient être là pour cet exemple. L'optimiseur doit avoir élidés (la plupart de) AFAICT, car il sait que la plupart des informations sur le tableau, et il sait qu'il a (au moins) une référence forte.

Il ne devrait pas émettre plus de conserve quand il n'est même pas à appeler des fonctions qui pourraient libérer les objets. Je ne pense pas qu'un constructeur array peut retourner un tableau qui est plus petit que ce qui était demandé, ce qui signifie que beaucoup de vérifications qui ont été émises sont inutiles. Il sait aussi que l'entier ne sera jamais au-dessus de 10k, de sorte que le dépassement de contrôles peut être optimisé (pas à cause de l' -Ofast "bizarre", mais à cause de la sémantique de la langue (rien d'autre est en train de changer que la var ne peut y accéder, et en ajoutant jusqu'à 10k est sans danger pour le type d' Int).

Le compilateur pourrait ne pas être en mesure de unbox le tableau ou le tableau des éléments, bien que, depuis qu'ils sont passé à l' sort(), ce qui est une fonction externe et dispose pour obtenir les arguments qu'il attend. Cela va nous faire utiliser l' Int valeurs indirectement, ce qui serait aller un peu plus lent. Cela pourrait changer si l' sort() de la fonction générique (pas dans le multi-way méthode) était disponible pour le compilateur et a obtenu inline.

C'est un très nouveau (publiquement) de la langue, et il va par ce que je suppose que beaucoup de changements, car il y a des gens (très) impliqués avec la Swift de la langue pour obtenir des commentaires et ils disent tous la langue n'est pas fini et va changer.

Code utilisé:

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: je ne suis pas un expert sur Objective-C, ni de toutes les installations de Cocoa, Objective-C, ou la Swift runtimes. Je pourrais aussi être en supposant que certaines choses que je n'ai pas écrit.

Answer 3

J'ai décidé de prendre un coup d'oeil à cela pour le plaisir, et voici les horaires que j'obtiens:

Swift: 1.02s
C++:   0.67s

Swift

import Foundation

func doTest() -> Void {
    let arraySize = 10000000
    var randomNumbers = [UInt32]()

    for i in 0..<arraySize {
        randomNumbers.append(arc4random_uniform(UInt32(arraySize)))
    }

    let start = NSDate()
    sort(&randomNumbers)
    let end = NSDate()

    println(randomNumbers[0])
    println("Elapsed time: \(end.timeIntervalSinceDate(start))")
}

doTest()

Résultats:

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

Il semble être le même rendement que si je compile avec -Ounchecked.

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

Résultats:

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

Verdict

Au moment d'écrire ces lignes, Swift est un peu rapide, mais pas encore aussi rapide que du C++de tri, avec les compilateurs et bibliothèques. Depuis Swift est encore jeune, il est concevable que cette lacune sera fermé dans l'avenir.

Answer 4

La modification de la Swift Compilateur - Niveau d'Optimisation dans Xcode pour le plus Rapide, Non' a accéléré ce jusqu'à être comparables avec C++.

Edit:

-Ofast

Mépris des normes strictes de conformité. -Ofast permet à tous -O3 optimisations. Il permet également aux optimisations qui ne sont pas valables pour tous les programmes compatibles. Il tourne sur -ffast-math et le Fortran-à-fno-protéger-parens et -fstack-tableaux.

-ffast-math: Cette option n'est pas activée par toute option-O outre -Ofast, car il peut entraîner une mauvaise sortie pour les programmes qui dépendent d'une application stricte de la norme IEEE ou les règles de l'ISO/spécifications pour les fonctions mathématiques. Il peut, cependant, le rendement plus rapide de code pour les programmes qui ne nécessitent pas les garanties du présent cahier des charges.

Answer 5

D' The Swift Programming Language:

La Fonction de Tri de Swift, la bibliothèque standard fournit une fonction appelée trier, qui trie un tableau de valeurs d'un type connu, basé sur la sortie de tri de fermeture que vous fournissez. Une fois terminé, l' le processus de tri, le tri de la fonction renvoie un nouveau tableau de la même le type et la taille que l'ancien, avec ses éléments dans le bon triés ordre.

L' sort fonction a deux déclarations.

Le défaut de déclaration qui vous permet de spécifier une comparaison de fermeture:

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

Et une deuxième déclaration qui ne font qu'un seul paramètre (le tableau) et est "codé en dur pour utiliser le moins de point de comparaison."

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

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

J'ai testé une version modifiée de votre code dans une aire de jeux avec la fermeture ajouté sur afin que je puisse contrôler la fonction d'un peu plus près, et j'ai trouvé que, avec n fixé à 1000, la fermeture a été appelé à environ 11 000 fois.

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

Il n'est pas un fonctionnement efficace, je vous conseille d'utiliser un meilleur tri fonction de mise en œuvre.

EDIT:

J'ai pris un coup d'oeil à la Quicksort page de wikipédia et a écrit une mise en œuvre rapide. Voici le programme complet j'ai utilisé (dans une aire de jeux)

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
}

L'utilisation de ce avec n=1000, j'ai trouvé que

1. quickSort() m'a appelé environ 650 fois,
2. environ 6000 swaps ont été faites,
3. et il y a environ 10 000 comparaisons

Il semble que le haut-méthode de tri est (ou à proximité) tri rapide, et il est vraiment lent...