Swift Beta performance: ordenando matrices

sorting xcode6

Question

Estaba implementando un algoritmo en Swift Beta y noté que el rendimiento era muy pobre. Después de profundizar, me di cuenta de que uno de los cuellos de botella era algo tan simple como ordenar matrices. La parte relevante está aquí:

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 ++, una operación similar toma 0.06s en mi computadora.

En Python, se necesitan 0.6 s (sin trucos, solo y = ordenados (x) para obtener una lista de enteros).

En Swift toma 6s si lo compilo con el siguiente comando:

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

Y toma tanto como 88 si lo compilo con el siguiente comando:

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

Los tiempos en Xcode con las compilaciones "Release" vs. "Debug" son similares.

¿Que esta mal aquí? Pude entender algunas pérdidas de rendimiento en comparación con C ++, pero no una ralentización de 10 veces en comparación con Python puro.

Edit: mweathers notó que cambiar -Ofast a -Ofast hace que este código se ejecute casi tan rápido como la versión C ++. Sin embargo, -Ofast cambia mucho la semántica del lenguaje: en mis pruebas, deshabilitó las comprobaciones de desbordamientos de enteros y desbordamientos de indexación de matrices . Por ejemplo, con -Ofast el siguiente código Swift se ejecuta silenciosamente sin fallar (e imprime algo de basura):

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

Así que -Ofast no es lo que queremos; El punto central de Swift es que tenemos las redes de seguridad en su lugar. Por supuesto, las redes de seguridad tienen algún impacto en el rendimiento, pero no deberían hacer que los programas sean 100 veces más lentos. Recuerde que Java ya verifica los límites de la matriz, y en casos típicos, la desaceleración es un factor mucho menor que 2. Y en Clang y GCC tenemos -ftrapv para verificar los desbordamientos de enteros (con firma), y tampoco es tan lento .

De ahí la pregunta: ¿cómo podemos obtener un rendimiento razonable en Swift sin perder las redes de seguridad?

Edit 2: Hice algunos más puntos de referencia, con bucles muy simples a lo largo de las líneas de

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

(Aquí está la operación xor para poder encontrar más fácilmente el bucle relevante en el código del ensamblaje. Intenté elegir una operación que sea fácil de detectar pero también "inocua" en el sentido de que no debería requerir ninguna verificación relacionada a los desbordamientos de enteros.)

Nuevamente, hubo una gran diferencia en el rendimiento entre -Ofast y -Ofast . Así que eché un vistazo al código de montaje:

• Con -Ofast obtengo casi lo que esperaría. La parte relevante es un bucle con 5 instrucciones de lenguaje de máquina.

• Con -O3 obtengo algo que estaba más allá de mi imaginación más salvaje. El bucle interno abarca 88 líneas de código de ensamblaje. No intenté entenderlo todo, pero las partes más sospechosas son 13 invocaciones de "callq _swift_retain" y otras 13 invocaciones de "callq _swift_release". Es decir, 26 llamadas de subrutinas en el bucle interno !

Edición 3: En los comentarios, Ferruccio solicitó puntos de referencia que son justos en el sentido de que no se basan en funciones integradas (por ejemplo, clasificación). Creo que el siguiente programa es un buen ejemplo:

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

No hay aritmética, por lo que no debemos preocuparnos por los desbordamientos de enteros. Lo único que hacemos es simplemente un montón de referencias de matriz. Y los resultados están aquí: Swift -O3 pierde casi 500 en comparación con -Fast:

• C ++ -O3: 0,05 s
• C ++ -O0: 0,4 s
• Java: 0.2 s
• Python con PyPy: 0.5 s
• Python: 12 s
• Rápido -Rápido: 0.05 s
• Swift -O3: 23 s
• Swift -O0: 443 s

(Si le preocupa que el compilador pueda optimizar los bucles sin sentido por completo, puede cambiarlo a, por ejemplo, x[i] ^= x[j] , y agregar una declaración de impresión que genere x[0] . Esto no cambia nada Los tiempos serán muy similares.

Y sí, aquí la implementación de Python fue una implementación pura y estúpida de Python con una lista de ints y anidados para bucles. Debería ser mucho más lento que el Swift no optimizado. Algo parece estar seriamente roto con Swift y la indexación de matrices.

Edición 4: Estos problemas (así como algunos otros problemas de rendimiento) parecen haberse solucionado en Xcode 6 beta 5.

Para ordenar, ahora tengo los siguientes horarios:

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

Para bucles anidados:

• clang ++ -O3: 0.06 s
• swiftc - rápido: 0,3 s
• swiftc -O: 0,4 s
• swiftc: 540 s

Parece que ya no hay razón para usar el inseguro -Ofast (también -Ounchecked como -Ounchecked ); plain -O produce un código igualmente bueno.

Answer 1

A partir de Xcode 7 puede activar la Fast, Whole Module Optimization . Esto debería aumentar su rendimiento de inmediato.

Answer 2

Decidí echarle un vistazo a esto por diversión, y aquí están los horarios que recibo:

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

Rápido

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

Resultados:

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

Parece ser el mismo rendimiento si 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

Parece que ha habido una regresión de rendimiento de Swift 2.0 a Swift 3.0, y también estoy viendo una diferencia entre -O y -Ounchecked por primera vez.

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 mejora el rendimiento nuevamente, mientras mantiene una brecha entre -O y -Ounchecked . -O -whole-module-optimization no parece hacer una diferencia.

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

Resultados:

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

Veredicto

En el momento de escribir este artículo, el tipo de Swift es rápido, pero aún no es tan rápido como el de C ++ cuando se compila con -O , con los compiladores y bibliotecas anteriores. Con -Ounchecked , parece ser tan rápido como C ++ en Swift 4.0.2 y Apple LLVM 9.0.0.

Answer 3

Del The Swift Programming Language :

La biblioteca estándar de la función de clasificación de Swift proporciona una función llamada clasificación, que ordena una matriz de valores de un tipo conocido, en función de la salida de un cierre de clasificación que usted proporciona. Una vez que completa el proceso de clasificación, la función de clasificación devuelve una nueva matriz del mismo tipo y tamaño que la anterior, con sus elementos en el orden correcto.

La función de sort tiene dos declaraciones.

La declaración por defecto que le permite especificar un cierre de comparación:

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

Y una segunda declaración que solo toma un solo parámetro (la matriz) y está "programada para usar el comparador menos que".

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

Probé una versión modificada de su código en un patio de recreo con el cierre agregado para poder monitorear la función un poco más de cerca, y descubrí que con n establecido en 1000, el cierre se llamaba unas 11,000 veces.

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

No es una función eficiente, recomendaría usar una mejor implementación de la función de clasificación.

EDITAR:

Eché un vistazo a la página de wikipedia Quicksort y escribí una implementación Swift para ella. Aquí está el programa completo que usé (en un patio de recreo)

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 esto con n = 1000, encontré que

1. QuickSort () fue llamado alrededor de 650 veces,
2. se hicieron unos 6000 swaps,
3. y hay alrededor de 10.000 comparaciones

Parece que el método de clasificación incorporado es (o está cerca de) una clasificación rápida, y es realmente lento ...

Answer 4

El problema principal que mencionan los demás, pero que no se menciona lo suficiente, es que -O3 no hace nada en Swift (y nunca lo ha hecho), por lo que cuando se compila con él no está optimizado ( -Onone ).

Los nombres de las opciones han cambiado con el tiempo, por lo que algunas otras respuestas tienen marcas obsoletas para las opciones de compilación. Las opciones actuales correctas (Swift 2.2) son:

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

La optimización de todo el módulo tiene una compilación más lenta, pero se puede optimizar a través de archivos dentro del módulo, es decir, dentro de cada marco y dentro del código de la aplicación real, pero no entre ellos. Debes usar esto para cualquier cosa que sea crítica para el rendimiento)

También puede deshabilitar las comprobaciones de seguridad para obtener aún más velocidad, pero con todas las afirmaciones y condiciones previas, no solo se deshabilitan, sino que se optimizan sobre la base de que son correctas. Si alguna vez llegas a una afirmación, esto significa que estás en un comportamiento indefinido. Úselo con extrema precaución y solo si determina que el aumento de velocidad vale la pena para usted (mediante pruebas). Si lo encuentra valioso para algún código, recomiendo separar ese código en un marco separado y deshabilitar solo las comprobaciones de seguridad para ese módulo.

Answer 5

Se revisó el rendimiento de Swift Array:

Escribí mi propio punto de referencia comparando Swift con C / Objective-C. Mi punto de referencia calcula los números primos. Utiliza la matriz de números primos anteriores para buscar factores primos en cada nuevo candidato, por lo que es bastante rápido. Sin embargo, hace TONELADAS de lectura de matrices, y menos escritura en matrices.

Originalmente hice este punto de referencia contra Swift 1.2. Decidí actualizar el proyecto y ejecutarlo contra Swift 2.0.

El proyecto le permite seleccionar entre usar matrices swift normales y usar buffers de memoria inseguros Swift usando semántica de matrices.

Para C / Objective-C, puede optar por usar NSArrays o C malloc''ed arrays.

Los resultados de las pruebas parecen ser bastante similares con la optimización más rápida y pequeña del código ([-0s]) o la optimización más rápida y agresiva ([-0fast]).

El rendimiento de Swift 2.0 sigue siendo horrible con la optimización de código desactivada, mientras que el rendimiento de C / Objective-C es solo moderadamente más lento.

La conclusión es que los cálculos basados ​​en matrices de C malloc''d son los más rápidos, por un margen modesto

Swift con búferes inseguros toma alrededor de 1.19X - 1.20X más que las matrices C malloc''d cuando se usa la optimización de código más rápida y pequeña. la diferencia parece ligeramente menor con la optimización rápida y agresiva (Swift toma más como 1.18x a 1.16x más que C.

Si utiliza matrices Swift regulares, la diferencia con C es ligeramente mayor. (Swift toma ~ 1.22 a 1.23 más.)

Los arreglos Swift regulares son DRAMATICALLY más rápidos de lo que eran en Swift 1.2 / Xcode 6. Su rendimiento es tan cercano a los arreglos basados ​​en búfer inseguro Swift que el uso de búferes de memoria inseguros ya no parece valer la pena, lo cual es grande.

Por cierto, el rendimiento Objective-C NSArray apesta. Si va a utilizar los objetos contenedores nativos en ambos idiomas, Swift es DRAMÁTICAMENTE más rápido.

Puedes ver mi proyecto en github en SwiftPerformanceBenchmark

Tiene una interfaz de usuario simple que hace que la recopilación de estadísticas sea bastante fácil.

Es interesante que la clasificación parece ser un poco más rápida en Swift que en C ahora, pero que este algoritmo de número primo es aún más rápido en Swift.

Answer 6

tl; dr Swift 1.0 ahora es tan rápido como C por este punto de referencia utilizando el nivel de optimización de la versión predeterminada [-O].

Aquí hay un quicksort in situ en 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)
}

Y lo mismo 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);
}

Ambos trabajan:

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]

Ambos se llaman en el mismo programa como está escrito.

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

Esto convierte los tiempos absolutos en segundos:

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

Aquí hay un resumen de los niveles de optimización del compilador:

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

Tiempo en segundos con [-Onone] para n = 10_000 :

Swift: 0.895296452
C: 0.001223848

Aquí está la ordenación () incorporada de Swift para n = 10_000 :

Swift_builtin: 0.77865783

Aquí está [-O] para n = 10_000 :

Swift: 0.045478346
C: 0.000784666
Swift_builtin: 0.032513488

Como puede ver, el rendimiento de Swift mejoró en un factor de 20.

De acuerdo con la respuesta de mweathers , el ajuste [-Fast] hace la diferencia real, lo que resulta en estos tiempos para n = 10_000 :

Swift: 0.000706745
C: 0.000742374
Swift_builtin: 0.000603576

Y para n = 1_000_000 :

Swift: 0.107111846
C: 0.114957179
Swift_sort: 0.092688548

Para comparar, esto es con [-Onone] para n = 1_000_000 :

Swift: 142.659763258
C: 0.162065333
Swift_sort: 114.095478272

Por lo tanto, Swift sin optimizaciones fue casi 1000x más lento que C en este punto de referencia, en esta etapa de su desarrollo. Por otro lado, con ambos compiladores configurados en [-Ovático] Swift en realidad funcionó al menos tan bien como un poco mejor que C.

Se ha señalado que [-Fast] cambia la semántica del idioma, lo que lo hace potencialmente inseguro. Esto es lo que Apple dice en las notas de lanzamiento de Xcode 5.0:

Un nuevo nivel de optimización: Rápido, disponible en LLVM, permite optimizaciones agresivas. -Rápido relaja algunas restricciones conservadoras, principalmente para operaciones de punto flotante, que son seguras para la mayoría de los códigos. Puede producir importantes ganancias de alto rendimiento del compilador.

Todos lo abogan. Ya sea que sea inteligente o no, no podría decirlo, pero por lo que puedo decir, parece lo suficientemente razonable para usar [-Fast] en una versión si no está haciendo aritmética de punto flotante de alta precisión y está seguro de que no hay un entero o Los desbordamientos de matriz son posibles en su programa. Si necesita un alto rendimiento y verificaciones de desbordamiento / aritmética precisa, elija otro idioma por ahora.

ACTUALIZACIÓN BETA 3:

n = 10_000 con [-O] :

Swift: 0.019697268
C: 0.000718064
Swift_sort: 0.002094721

En general, Swift es un poco más rápido y parece que la clasificación incorporada de Swift ha cambiado bastante significativamente.

ACTUALIZACIÓN FINAL:

[-Ninguno] :

Swift: 0.678056695
C: 0.000973914

[-O] :

Swift: 0.001158492
C: 0.001192406

[-Activado] :

Swift: 0.000827764
C: 0.001078914

Answer 7

TL; DR : Sí, la única implementación del lenguaje Swift es lenta, en este momento . Si necesita un código rápido, numérico (y otros tipos de código, presumiblemente), simplemente vaya con otro. En el futuro, debe volver a evaluar su elección. Sin embargo, podría ser lo suficientemente bueno para la mayoría de los códigos de aplicación que están escritos en un nivel superior.

Por lo que veo en SIL y LLVM IR, parece que necesitan un montón de optimizaciones para eliminar retenciones y liberaciones, que podrían implementarse en Clang (para Objective-C), pero aún no las han portado. Esa es la teoría con la que voy (por ahora ... todavía necesito confirmar que Clang hace algo al respecto), ya que un análisis de perfil en el último caso de prueba de esta pregunta produce este resultado "bonito":

Como han dicho muchos otros, -Ofast es totalmente inseguro y cambia la semántica del lenguaje. Para mí, es en la etapa "Si vas a usar eso, solo usa otro idioma". Volveré a evaluar esa elección más tarde, si cambia.

-O3 nos da un montón de llamadas swift_retain y swift_release que, honestamente, no parece que deban estar ahí para este ejemplo. El optimizador debería haberlos eliminado (la mayoría de ellos) como AFAICT, ya que conoce la mayor parte de la información sobre la matriz, y sabe que tiene (al menos) una fuerte referencia a ella.

No debería emitir más retenciones cuando ni siquiera está llamando a funciones que podrían liberar los objetos. No creo que un constructor de arreglos pueda devolver un arreglo que sea más pequeño de lo que se solicitó, lo que significa que muchas de las verificaciones que se emitieron son inútiles. También sabe que el número entero nunca estará por encima de 10k, por lo que las comprobaciones de desbordamiento se pueden optimizar (no por la rareza -Ofast , sino por la semántica del lenguaje (nada más cambia esa var ni puede acceder a ella, y se suma) a 10k es seguro para el tipo Int ).

Sin embargo, es posible que el compilador no pueda desempaquetar la matriz o los elementos de la matriz, ya que pasan a sort() , que es una función externa y tiene que obtener los argumentos que espera. Esto hará que tengamos que usar los valores de Int indirectamente, lo que lo haría ir un poco más lento. Esto podría cambiar si la función genérica sort() (no de forma multimétodo) estuviera disponible para el compilador y se integrara.

Este es un lenguaje muy nuevo (públicamente), y está pasando por lo que supongo que hay muchos cambios, ya que hay personas (muy) involucradas con el lenguaje Swift que solicitan comentarios y todos dicen que el idioma no está terminado y cambio.

Código utilizado:

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

PD: No soy un experto en Objective-C ni en todas las instalaciones de Cocoa , Objective-C o Swift. También podría estar asumiendo algunas cosas que no escribí.

Answer 8

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)

Este es mi blog sobre Quick Sort - muestra de Github Quick-Sort

Puedes echar un vistazo al algoritmo de partición de Lomuto en Particionando la lista. Escrito en Swift