Performances rapides: sorting des tableaux

Je mettais en œuvre un algorithme dans Swift et j’ai remarqué que les performances étaient très faibles. Après avoir creusé plus profondément, j’ai réalisé que l’un des goulots d’étranglement était quelque chose d’aussi simple que le sorting des tableaux. La partie pertinente est ici:

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 

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

En Python, il faut 0,6s (pas de trucs, juste y = sortinger (x) pour une liste d’entiers).

En Swift, il faut 6s si je le comstack avec la commande suivante:

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

Et cela prend jusqu’à 88 si je le comstack avec la commande suivante:

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

Les synchronisations dans Xcode avec les versions “Release” et “Debug” sont similaires.

Qu’est-ce qui ne va pas ici? Je pouvais comprendre certaines pertes de performances par rapport à C ++, mais pas un ralentissement de 10 fois par rapport à Python pur.


Edit: mweathers a remarqué que changer -O3 en -Ofast rend ce code presque aussi rapide que la version C ++! Cependant, -Ofast modifie -Ofast la sémantique du langage – lors de mes tests, il a désactivé les contrôles pour les débordements d’entiers et les débordements d’indexation des tableaux . Par exemple, avec -Ofast le code Swift suivant s’exécute en mode silencieux sans se bloquer (et -Ofast des -Ofast ):

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

Donc -Ofast n’est pas ce que nous voulons; Le but de Swift est que nous ayons les filets de sécurité en place. Bien entendu, les filets de sécurité ont un impact sur les performances, mais ils ne devraient pas ralentir les programmes. Rappelez-vous que Java vérifie déjà les limites des tableaux, et dans les cas typiques, le ralentissement est d’un facteur bien inférieur à 2. Et dans Clang et GCC, nous avons -ftrapv pour vérifier les dépassements d’entiers (signés), .

D’où la question: comment obtenir une performance raisonnable dans Swift sans perdre les filets de sécurité?


Edit 2: J’ai fait un peu plus de benchmarking, avec des boucles très simples comme

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

(Ici, l’opération xor est là pour que je puisse trouver plus facilement la boucle pertinente dans le code d’assemblage. J’ai essayé de choisir une opération facile à repérer mais aussi «inoffensive» en ce sens qu’elle ne nécessite aucune vérification. à des dépassements d’entier.)

Encore une fois, il y avait une énorme différence dans la performance entre -O3 et -Ofast . J’ai donc regardé le code de l’assemblage:

  • Avec -Ofast je reçois à peu près ce à quoi je m’attendais. La partie pertinente est une boucle avec 5 instructions en langage machine.

  • Avec -O3 je reçois quelque chose qui dépasse mon imagination la plus folle. La boucle interne couvre 88 lignes de code d’assemblage. Je n’ai pas essayé de tout comprendre, mais les parties les plus suspectes sont 13 invocations de “callq _swift_retain” et 13 autres invocations de “callq _swift_release”. C’est-à-dire 26 appels de sous-programmes dans la boucle interne !


Edit 3: Dans les commentaires, Ferruccio a demandé des tests de performances corrects dans le sens où ils ne reposent pas sur des fonctions intégrées (par exemple, le sorting). Je pense que le programme suivant est un assez bon exemple:

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

Il n’y a pas d’arithmétique, nous n’avons donc pas à nous soucier 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 là – Swift -O3 perd près de 500 facteurs par rapport à -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 optimise entièrement les boucles sans intérêt, vous pouvez le modifier, par exemple, en x[i] ^= x[j] et append une instruction print qui génère x[0] . Cela ne change rien ; les timings seront très similaires.)

Et oui, ici l’implémentation de Python était une implémentation Python pure et stupide avec une liste d’ints et de nids pour les boucles. Il devrait être beaucoup plus lent que Swift non optimisé. Quelque chose semble être sérieusement cassé avec Swift et l’indexation de tableau.


Edit 4: Ces problèmes (ainsi que d’autres problèmes de performances) semblent avoir été corrigés dans Xcode 6 beta 5.

Pour le sorting, j’ai maintenant les délais suivants:

  • clang ++ -O3: 0.06 s
  • swiftc -Ofast: 0.1 s
  • swiftc -O: 0.1 s
  • swiftc: 4 s

Pour les boucles nestedes:

  • clang ++ -O3: 0.06 s
  • swiftc -Ofast: 0.3 s
  • swiftc -O: 0.4 s
  • swiftc: 540 s

Il semble qu’il n’y ait plus de raison d’utiliser le dangereux -Ofast (aka -Ounchecked ); plain -O produit un code aussi bon.

tl; dr Swift est maintenant aussi rapide que C par ce benchmark en utilisant le niveau d’optimisation par défaut [-O].

Voici un quicksort sur place 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 chose 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); } 

Les deux travaillent:

 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 que celui é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(); 

Cela convertit les temps absolus en 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 un résumé des niveaux d'optimisation du compilateur:

 [-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 [-Onone] pour n = 10_000 :

 Swift: 0.895296452 C: 0.001223848 

Voici le sorting de Swift () pour n = 10_000 :

 Swift_builtin: 0.77865783 

Voici [-O] pour n = 10_000 :

 Swift: 0.045478346 C: 0.000784666 Swift_builtin: 0.032513488 

Comme vous pouvez le constater, les performances de Swift ont été multipliées par 20.

Selon la réponse de mweathers , le réglage de [-Ofast] fait la vraie différence, ce qui se traduit par 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 comparaison, ceci est avec [-Onone] pour n = 1_000_000 :

 Swift: 142.659763258 C: 0.162065333 Swift_sort: 114.095478272 

Ainsi, Swift, sans optimisation, était presque 1000 fois plus lent que C dans ce benchmark, à ce stade de son développement. En revanche, avec les deux compilateurs définis sur [-Ofast], Swift a en fait au moins aussi bien fonctionné, sinon un peu mieux que C.

Il a été souligné que [-Ofast] change la sémantique du langage, le rendant potentiellement dangereux. Voici ce que Apple déclare dans les notes de version de Xcode 5.0:

Un nouveau niveau d'optimisation -Ofast, disponible dans LLVM, permet des optimisations agressives. -Ofast assouplit certaines ressortingctions conservasortingces, principalement pour les opérations en virgule flottante, qui sont sûres pour la plupart des codes. Il peut générer des gains significatifs de haute performance du compilateur.

Ils le préconisent tous. Que ce soit sage ou pas je ne pourrais pas dire, mais de ce que je peux dire, il semble assez raisonnable d'utiliser [-Ofast] dans une version si vous ne faites pas d'arithmétique à virgule flottante de haute précision et que vous êtes sûr les débordements de tableaux sont possibles dans votre programme. Si vous avez besoin de contrôles de performance et de débordement / arithmétique précise, choisissez une autre langue pour le moment.

MISE À JOUR BETA 3:

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 le sorting intégré de Swift ait considérablement changé.

MISE À JOUR FINALE:

[-Onone] :

 Swift: 0.678056695 C: 0.000973914 

[-O] :

 Swift: 0.001158492 C: 0.001192406 

[-Ounchecked] :

 Swift: 0.000827764 C: 0.001078914 

TL; DR : Oui, la seule implémentation du langage Swift est lente, pour le moment . Si vous avez besoin de code rapide, numérique (et d’autres types de code, probablement), il vous suffit d’en choisir un autre. À l’avenir, vous devriez réévaluer votre choix. Cela peut être suffisant pour la plupart des codes d’application écrits à un niveau supérieur.

D’après ce que je vois dans SIL et LLVM IR, il semble qu’ils aient besoin d’optimisations pour supprimer les retenues et les versions, qui pourraient être implémentées dans Clang (pour Objective-C), mais elles ne les ont pas encore scopes. C’est la théorie avec laquelle je vais (pour l’instant… je dois encore confirmer que Clang fait quelque chose à ce sujet), puisqu’un profileur exécuté sur le dernier test de cette question donne ce résultat «joli»:

Profilage du temps sur -O3Profilage du temps sur -Ofast

Comme cela a été dit par beaucoup d’autres, -Ofast est totalement dangereux et change la sémantique du langage. Pour moi, c’est à l’étape «Si vous allez l’utiliser, utilisez simplement une autre langue». Je réévaluerai ce choix plus tard, s’il change.

-O3 nous swift_retain un tas d’ swift_retain et swift_release qui, honnêtement, ne semblent pas devoir être là pour cet exemple. L’optimiseur aurait dû s’en écarter (pour la plupart) de l’AFAICT, car il connaît la plupart des informations sur la masortingce, et sait qu’il y fait référence (au moins).

Il ne devrait pas émettre plus de retenues quand il ne s’agit même pas d’appeler des fonctions susceptibles de libérer les objects. Je ne pense pas qu’un constructeur de tableaux puisse retourner un tableau plus petit que ce qui a été demandé, ce qui signifie que beaucoup de contrôles émis sont inutiles. Il sait aussi que le nombre entier ne sera jamais supérieur à 10k, donc les vérifications de débordement peuvent être optimisées (pas à cause de la bizarrerie -Ofast , mais à cause de la sémantique du langage (rien d’autre ne change ce var ni à 10k est sans danger pour le type Int ).

Le compilateur ne sera peut-être pas en mesure de déballer le tableau ou les éléments du tableau, car ils sont passés à sort() , qui est une fonction externe et doit obtenir les arguments attendus. Cela nous obligera à utiliser les valeurs d’ Int indirectement, ce qui le rendrait un peu plus lent. Cela pourrait changer si la fonction générique sort() (pas dans la méthode multi-méthode) était disponible pour le compilateur et mise en ligne.

C’est un langage très nouveau (publiquement), et il passe par beaucoup de changements, car il y a des personnes (fortement) impliquées dans le langage Swift qui demandent des commentaires et qui disent que la langue n’est pas finie et changement.

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

PS: Je ne suis pas un expert d’Objective-C ni de toutes les installations de Cocoa , d’Objective-C ou des environnements d’exécution de Swift. Je pourrais aussi prendre certaines choses que je n’ai pas écrites.

J’ai décidé de jeter un oeil à ça pour le plaisir, et voici les horaires que je reçois:

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

Rapide

 // Swift 4.0 code import Foundation func doTest() -> Void { let arraySize = 10000000 var randomNumbers = [UInt32]() for _ in 0.. 

Résultats:

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 

Cela semble être la même performance si je comstack avec -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 

Il semble y avoir eu une régression des performances de Swift 2.0 à Swift 3.0, et je constate également une différence entre -O et -Ounchecked pour la première fois.

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 améliore encore la performance, tout en maintenant un écart entre -O et -Ounchecked . -O -whole-module-optimization n'a pas semblé faire la différence.

C ++

 #include  #include  #include  #include  #include  using namespace std; using namespace std::chrono; int main(int argc, const char * argv[]) { const auto arraySize = 10000000; vector 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>(end - start).count() < < "\n"; return 0; } 

Résultats:

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 

Verdict

Au moment de l'écriture, le sorting de Swift est rapide, mais pas encore aussi rapide que le sorting de C ++ lorsqu'il est compilé avec -O , avec les compilateurs et bibliothèques ci-dessus. Avec -Ounchecked , il semble être aussi rapide que C ++ dans Swift 4.0.2 et Apple LLVM 9.0.0.

Du The Swift Programming Language :

La fonction de sorting La bibliothèque standard de Swift fournit une fonction appelée sort, qui sortinge un tableau de valeurs d’un type connu, basé sur la sortie d’une fermeture de sorting que vous fournissez. Une fois le processus de sorting terminé, la fonction de sorting renvoie un nouveau tableau du même type et de la même taille que l’ancien, avec ses éléments dans l’ordre de sorting correct.

La fonction de sort a deux déclarations.

La déclaration par défaut qui vous permet de spécifier une clôture de comparaison:

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

Et une deuxième déclaration qui ne prend qu’un seul paramètre (le tableau) et est “codée en dur pour utiliser le comparateur moins que”.

 func sort(array: T[]) -> T[] Example: sort( _arrayToSort_ ) { $0 > $1 } 

J’ai testé une version modifiée de votre code dans un terrain de jeu avec la fermeture ajoutée afin de pouvoir surveiller la fonction un peu plus étroitement et j’ai constaté qu’avec n défini sur 1000, la fermeture était appelée 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 } 

Ce n’est pas une fonction efficace, je vous recommande d’utiliser une meilleure implémentation de la fonction de sorting.

MODIFIER:

J’ai jeté un coup d’oeil à la page de Wikipédia Quicksort et j’ai écrit une implémentation de Swift pour cela. Voici le programme complet que j’ai utilisé (dans une cour de récréation)

 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 } 

En utilisant cela avec n = 1000, j'ai trouvé que

  1. quickSort () a été appelé environ 650 fois,
  2. environ 6000 échanges ont été effectués,
  3. et il y a environ 10 000 comparaisons

Il semble que la méthode de sorting intégrée soit (ou est proche de) un sorting rapide et qu'elle soit vraiment lente ...

A partir de Xcode 7, vous pouvez activer Fast, Whole Module Optimization . Cela devrait augmenter vos performances immédiatement.

entrer la description de l'image ici

Performance de Swift Array revisitée:

J’ai écrit ma propre comparaison en comparant Swift à C / Objective-C. Mon benchmark calcule les nombres premiers. Il utilise le tableau des nombres premiers précédents pour rechercher les facteurs premiers dans chaque nouveau candidat. Il est donc assez rapide. Cependant, il fait des tonnes de lecture de tableau, et moins d’écriture dans les tableaux.

J’ai initialement réalisé ce benchmark contre Swift 1.2. J’ai décidé de mettre à jour le projet et de l’exécuter avec Swift 2.0.

Le projet vous permet de choisir entre utiliser des tableaux swift normaux et utiliser des tampons de mémoire Swift peu sûrs en utilisant la sémantique des tableaux.

Pour C / Objective-C, vous pouvez choisir d’utiliser les baies NSArrays ou C malloc.

Les résultats du test semblent être assez similaires avec l’optimisation la plus rapide et la plus petite ([-0s]) ou l’optimisation la plus rapide ([-0fast]).

Les performances de Swift 2.0 sont toujours horribles avec l’optimisation du code désactivée, tandis que les performances de C / Objective-C ne sont que légèrement plus lentes.

L’essentiel est que les calculs basés sur les baies C malloc sont les plus rapides, avec une marge modeste

Swift avec des tampons dangereux prend environ 1,19 à 1,20 fois plus longtemps que les baies C malloc lors de l’utilisation de l’optimisation de code la plus rapide et la plus petite. la différence semble légèrement moins avec une optimisation rapide et agressive (Swift prend plus de 1,18 à 1,16 fois plus long que C.

Si vous utilisez des tableaux Swift réguliers, la différence avec C est légèrement supérieure. (Swift prend ~ 1,22 à 1,23 de plus.)

Les tableaux réguliers de Swift sont DRAMATICALLY plus rapides qu’ils ne l’étaient dans Swift 1.2 / Xcode 6. Leur performance est si proche de celle des baies Swift à base de tampons dangereux que l’utilisation de mémoires tampons non sécurisées ne semble plus la peine, ce qui est important.

BTW, les performances d’Objective-C NSArray piquent. Si vous envisagez d’utiliser les objects de conteneur natifs dans les deux langues, Swift est PLUS rapide.

Vous pouvez consulter mon projet sur github chez SwiftPerformanceBenchmark

Il a une interface utilisateur simple qui facilite la collecte de statistiques.

Il est intéressant de noter que le sorting semble être légèrement plus rapide dans Swift que dans C maintenant, mais que cet algorithme de nombres premiers est encore plus rapide dans Swift.

Le principal problème mentionné par d’autres mais pas suffisamment évoqué est que -O3 ne fait rien du tout dans Swift (et ne l’a jamais fait) et qu’il n’est donc pas optimisé ( -Onone ).

Les noms d’options ont changé au fil du temps, de sorte que d’autres réponses comportent des indicateurs obsolètes pour les options de génération. Les options actuelles correctes (Swift 2.2) sont:

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

Une optimisation complète du module a une compilation plus lente mais peut optimiser entre les fichiers du module, c’est-à-dire dans chaque cadre et dans le code de l’application réelle, mais pas entre eux. Vous devriez l’utiliser pour tout ce qui est essentiel à la performance)

Vous pouvez également désactiver les contrôles de sécurité pour encore plus de rapidité, mais avec toutes les assertions et conditions préalables non seulement désactivées, mais optimisées sur la base de leur exactitude. Si vous frappez une assertion, cela signifie que vous avez un comportement indéfini. Utilisez avec une extrême prudence et seulement si vous déterminez que l’augmentation de la vitesse est valable pour vous (par des tests). Si vous le trouvez utile pour du code, je vous recommande de séparer ce code dans un cadre distinct et de ne désactiver que les contrôles de sécurité pour ce module.

 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) 

Ceci est mon blog sur Quick Sort- Github exemple Quick-Sort

Vous pouvez jeter un coup d'oeil sur l'algorithme de partitionnement de Lomuto dans Partitionnement de la liste. Écrit en swift