Rendimiento de Swift Beta: ordenación de matrices

Estaba implementando un algoritmo en Swift Beta y noté que el rendimiento era muy pobre. Después de profundizar más, me di cuenta de que uno de los cuellos de botella era algo tan simple como clasificar los arreglos. 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.6s (sin trucos, solo y = ordenado (x) para obtener una lista de enteros).

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

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

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

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

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

¿Que esta mal aquí? Podría entender alguna pérdida de rendimiento en comparación con C ++, pero no una desaceleración de 10 veces en comparación con Python puro.

Editar: el clima notó que cambiar -O3a -Ofasthace que este código se ejecute casi tan rápido como la versión C ++. Sin embargo, -Ofastcambia mucho la semántica del lenguaje: en mis pruebas, deshabilitó las comprobaciones de desbordamientos de enteros y desbordamientos de indexación de matriz . Por ejemplo, con -Ofastel 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])

Entonces -Ofastno es lo que queremos; El punto de Swift es que tenemos las redes de seguridad en su lugar. Por supuesto, las redes de seguridad tienen cierto 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 por un factor mucho menor que 2. Y en Clang y GCC tenemos -ftrapvpara verificar desbordamientos de enteros (firmados), y tampoco es tan lento.

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

Edición 2: hice más benchmarking, con bucles muy simples a lo largo de las líneas de

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

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

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

• Con -Ofastobtengo más o menos lo que esperaría. La parte relevante es un bucle con 5 instrucciones de lenguaje de máquina.

• Con -O3eso consigo 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 subrutina en el bucle interno !

Edición 3: En los comentarios, Ferruccio solicitó puntos de referencia que sean justos en el sentido de que no se basan en funciones integradas (por ejemplo, ordenar). 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 solo un montón de referencias de matriz. Y los resultados están aquí: Swift -O3 pierde en un factor casi 500 en comparación con -Ofast:

• 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 x[i] ^= x[j], por ejemplo , y agregar una declaración de impresión que salga x[0]. Esto no cambia nada; los tiempos serán muy similares).

Y sí, aquí la implementación de Python fue una implementación de Python pura y estúpida con una lista de entradas y anidados para bucles. Debería ser mucho más lento que 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 -Ofast: 0.1 s
• swiftc -O: 0.1 s
• swiftc: 4 s

Para bucles anidados:

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

Parece que ya no hay razón para usar el inseguro -Ofast(aka -Ounchecked); plain -Oproduce un código igualmente bueno.

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

Aquí hay un resumen rápido en el lugar 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 que el 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á el tipo incorporado () 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.

Según la respuesta de mweathers , establecer [-Ofast] hace la diferencia real, resultando 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

A modo de comparación, esto es con [-Onone] para n = 1_000_000 :

Swift:            142.659763258
C:                0.162065333
Swift_sort:       114.095478272

Entonces Swift sin optimizaciones fue casi 1000 veces más lento que C en este punto de referencia, en esta etapa de su desarrollo. Por otro lado, con ambos compiladores configurados en [-Ofast] Swift en realidad funcionó al menos tan bien, si no un poco mejor que C.

Se ha señalado que [-Ofast] cambia la semántica del lenguaje, haciéndolo potencialmente inseguro. Esto es lo que Apple afirma en las notas de lanzamiento de Xcode 5.0:

Un nuevo nivel de optimización -Ofast, disponible en LLVM, permite optimizaciones agresivas. -Ofast 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 menos lo defienden. Si eso es sabio o no, no podría decirlo, pero por lo que puedo decir, parece lo suficientemente razonable como para usar [-Ofast] 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 número entero o los desbordamientos de matriz son posibles en su programa. Si necesita un alto rendimiento y comprobaciones 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

Swift en general es un poco más rápido y parece que el tipo incorporado de Swift ha cambiado significativamente.

ACTUALIZACIÓN FINAL:

[-Uno] :

Swift:   0.678056695
C:       0.000973914

[-O] :

Swift:   0.001158492
C:       0.001192406

[-No comprobado] :

Swift:   0.000827764
C:       0.001078914

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 reevaluar su elección. Sin embargo, podría ser lo suficientemente bueno para la mayoría de los códigos de aplicaciones que se escriben en un nivel superior.

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

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

-O3nos da un montón de llamadas swift_retainy swift_release, sinceramente, no parece que deberían estar allí para este ejemplo. El optimizador debería haberlos eludido (la mayoría de ellos) 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 matrices pueda devolver una matriz que sea más pequeña de lo que se solicitó, lo que significa que muchas comprobaciones emitidas son inútiles. También sabe que el número entero nunca estará por encima de 10k, por lo que las comprobaciones de desbordamiento pueden optimizarse (no por -Ofastrareza, sino por la semántica del lenguaje (nada más está cambiando esa variable ni puede acceder a ella, y sumando hasta 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 se los pasa sort(), que es una función externa y tiene que obtener los argumentos que espera. Esto nos hará tener que usar los Intvalores indirectamente, lo que haría que fuera un poco más lento. Esto podría cambiar si la sort()función genérica (no en la forma de métodos múltiples) estuviera disponible para el compilador y se insertara.

Este es un lenguaje muy nuevo (públicamente), y está pasando por lo que supongo que son 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 lo hará. cambio.

Código usado:

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 los tiempos de ejecución Swift. También podría estar asumiendo algunas cosas que no escribí.

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

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 veo una diferencia entre -Oy -Ouncheckedpor 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 -Oy -Ounchecked. -O -whole-module-optimizationno parecía hacer la 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

Al momento de escribir esto, la clasificación de Swift es rápida, pero no tan rápida como la clasificación de C ++ cuando se compila -Ocon 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.

De The Swift Programming Language:

La biblioteca estándar de la función de clasificación Swift proporciona una función llamada clasificación, que clasifica 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 ordenado correcto.

La sortfunción tiene dos declaraciones.

La declaración predeterminada 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 único parámetro (la matriz) y está "codificado para usar el comparador menor 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 juegos con el cierre agregado para poder monitorear la función un poco más de cerca, y descubrí que con n configurado 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, y recomendaría usar una mejor implementación de la función de clasificación.

EDITAR:

Eché un vistazo a la página de Wikipedia de Quicksort y escribí una implementación Swift para ello. Aquí está el programa completo que utilicé (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. Se llamó a quickSort () unas 650 veces,
2. se hicieron unos 6000 swaps,
3. y hay alrededor de 10,000 comparaciones

Parece que el método de ordenamiento incorporado es (o está cerca) de ordenamiento rápido, y es realmente lento ...

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

Rendimiento de Swift Array revisitado:

Escribí mi propio punto de referencia comparando Swift con C / Objective-C. Mi punto de referencia calcula 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 matriz 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 memorias intermedias de memoria inseguras Swift usando semántica de matrices.

Para C / Objective-C, puede optar por usar matrices NSA o matrices mal asignadas en C.

Los resultados de la prueba parecen ser bastante similares con la optimización de código más pequeña y rápida ([-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 del 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 la matriz 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 tiempo que las matrices mal asignadas en C cuando se utiliza la optimización de código más rápida y más pequeña. la diferencia parece un poco menor con una optimización rápida y agresiva (Swift tarda más como 1.18x a 1.16x más que C.

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

Las matrices Swift regulares son DRAMATICALLYmás rápidas de lo que eran en Swift 1.2 / Xcode 6. Su rendimiento es tan cercano a las matrices basadas en el buffer inseguro de Swift que el uso de buffers de memoria inseguros ya no parece valer la pena, lo cual es grande.

Por cierto, el rendimiento de 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 recopilar 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.

El problema principal que otros mencionan pero que no se mencionan lo suficiente es que -O3no hace nada en Swift (y nunca lo ha hecho), por lo que, cuando se compila, efectivamente 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 puede optimizarse a través de archivos dentro del módulo, es decir, dentro de cada marco y dentro del código de aplicación real, pero no entre ellos. Debe usar esto para cualquier cosa crítica de 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 deshabilitadas sino optimizadas en función de que sean correctas. Si alguna vez llega a una afirmación, esto significa que tiene un comportamiento indefinido. Úselo con extrema precaución y solo si determina que el aumento de velocidad vale la pena (mediante pruebas). Si lo encuentra valioso para algún código, recomiendo separar ese código en un marco separado y solo deshabilitar las verificaciones de seguridad para ese módulo.

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- Github sample Quick-Sort

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

Swift 4.1 presenta un nuevo -Osizemodo de optimización.

En Swift 4.1, el compilador ahora admite un nuevo modo de optimización que permite optimizaciones dedicadas para reducir el tamaño del código.

El compilador Swift viene con potentes optimizaciones. Al compilar con -O, el compilador intenta transformar el código para que se ejecute con el máximo rendimiento. Sin embargo, esta mejora en el rendimiento del tiempo de ejecución a veces puede venir con una compensación de un mayor tamaño del código. Con el nuevo modo de optimización -Osize, el usuario tiene la opción de compilar para obtener un tamaño de código mínimo en lugar de una velocidad máxima.

Para habilitar el modo de optimización de tamaño en la línea de comando, use -Osize en lugar de -O.

Lectura adicional: https://swift.org/blog/osize/