Pregunta Rendimiento rápido: ordenar matrices


Estaba implementando un algoritmo en Swift 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 necesita 0.6s (sin trucos, solo y = ordenado (x) para 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 se necesita 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 versiones "Release" vs. "Debug" son similares.

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


Editar: mweathers notó que el cambio -O3 a -Ofast hace que este código se ejecute casi tan rápido como la versión de C ++. Sin embargo, -Ofast cambia mucho la semántica del lenguaje - en mi prueba, inhabilitó 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])

Asi que -Ofast no es lo que queremos; El objetivo 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 por un factor mucho menor que 2. Y en Clang y GCC tenemos -ftrapv para 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?


Editar 2: Hice algunos benchmarking más, 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 ningún control relacionado para desbordamientos enteros)

Una vez más, hubo una gran diferencia en el rendimiento entre -O3 y -Ofast. Así que eché un vistazo al código de ensamblaje:

  • Con -Ofast Me sale más o menos lo que esperaría. La parte relevante es un ciclo 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 traté de comprenderlo 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!


Editar 3: En los comentarios, Ferruccio solicitó puntos de referencia que son justos en el sentido de que no dependen de las funciones incorporadas (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 tenemos que preocuparnos por los desbordamientos de enteros. Lo único que hacemos es solo muchas referencias de matriz. Y los resultados están aquí: Swift -O3 pierde por factor casi 500 en comparación con -Official:

  • C ++ -O3: 0.05 s
  • C ++ -O0: 0.4 s
  • Java: 0.2 s
  • Python con PyPy: 0.5 s
  • Pitón: 12 s
  • Swift-Fast: 0.05 s
  • Swift -O3: 23 s
  • Swift -00: 443 s

(Si le preocupa que el compilador pueda optimizar los bucles sin sentido por completo, puede cambiarlo a, p. x[i] ^= x[j]y agrega una declaración de impresión que genera 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 ints y bucles anidados. Debería ser mucho más lento que Swift no optimizado. Algo parece estar seriamente roto con Swift y la indexación de matriz.


Editar 4: Estos problemas (así como algunos otros problemas de rendimiento) parecen haberse resuelto en Xcode 6 beta 5.

Para ordenar, ahora tengo los siguientes tiempos:

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

Para bucles anidados:

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

Parece que ya no hay razón para usar lo inseguro -Ofast (a.k.a. -Ounchecked); llanura -O produce un código igualmente bueno.


829
2018-06-07 23:53


origen


Respuestas:


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

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

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 son llamados 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 optimació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 [-En uno] 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 respuesta de mweathers, ajuste [-Ofast] hace la verdadera diferencia, 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 comparación, esto es con [-En uno] para n = 1_000_000:

Swift:            142.659763258
C:                0.162065333
Swift_sort:       114.095478272

Así que Swift sin optimizaciones fue casi 1000 veces más lenta que C en este punto de referencia, en esta etapa de su desarrollo. Por otro lado, con ambos compiladores configurados en [-Ofast], Swift realmente se desempeñó al menos igual o mejor que C.

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

Un nuevo nivel de optimización: Fast, disponible en LLVM, permite optimizaciones agresivas. -Ofest relaja algunas restricciones conservadoras, principalmente para operaciones de coma flotante, que son seguras para la mayoría del código. Puede generar ganancias significativas de alto rendimiento del compilador.

Todos lo defienden. Si eso es inteligente o no, no podría decirlo, pero por lo que puedo decir, parece lo suficientemente razonable como para usar [-Ofast] en un lanzamiento si no se está haciendo una aritmética de punto flotante de alta precisión y no se tiene ningún número entero o Los desbordamientos de matriz son posibles en su programa. Si necesitas alto rendimiento y controles de desbordamiento / aritmética precisa, luego 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 bastante.

ACTUALIZACIÓN FINAL:

[-En uno]:

Swift:   0.678056695
C:       0.000973914

[-O]:

Swift:   0.001158492
C:       0.001192406

[-Desconocido]:

Swift:   0.000827764
C:       0.001078914

404
2018-06-08 01:36



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

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

Time profiling on -O3 Time profiling on -Ofast

Como lo dijeron muchos otros, -Ofast es totalmente inseguro y cambia la semántica del lenguaje. Para mí, está en la etapa "Si va a usar eso, simplemente use otro idioma". Volveré a evaluar esa opción más adelante, si cambia.

-O3 nos da un montón de swift_retain y swift_release lo llama, honestamente, no parece que deberían estar ahí para este ejemplo. El optimizador debería haberle quitado (la mayoría) a AFAICT, ya que conoce la mayoría de la información sobre la matriz, y sabe que tiene (al menos) una fuerte referencia a la misma.

No debería emitir más retenciones cuando ni siquiera está llamando funciones que podrían liberar los objetos. No creo que un constructor de matriz pueda devolver una matriz que sea más pequeña de lo que se solicitó, lo que significa que muchos de los controles emitidos son inútiles. También sabe que el número entero nunca será superior a 10k, por lo que las comprobaciones de desbordamiento poder estar optimizado (no por -Ofast rareza, pero debido a la semántica del lenguaje (nada más está cambiando esa var ni puede acceder a ella, y agregar hasta 10k es seguro para el tipo Int)

Sin embargo, el compilador puede no ser capaz de deshacer la matriz o los elementos de la matriz, ya que se pasan a sort(), que es una función externa y debe obtener los argumentos que espera. Esto nos obligará a usar el Int valores indirectamente, lo que lo haría ir un poco más lento. Esto podría cambiar si sort() la función genérica (no en el método de múltiples métodos) estaba disponible para el compilador y se introdujo.

Este es un lenguaje muy nuevo (públicamente), y está pasando por lo que supongo son muchos cambios, ya que hay personas (muy involucradas) con el lenguaje Swift que piden comentarios y todos dicen que el idioma no está terminado y que será 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")

P.S: No soy un experto en Objective-C ni todas las instalaciones de Cacao, Objective-C o los tiempos de ejecución Swift. También podría estar asumiendo algunas cosas que no escribí.


100
2018-06-09 06:30



Decidí echarle un vistazo a esto por diversión, y aquí están los tiempos 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 haber habido una regresión de rendimiento de Swift 2.0 a Swift 3.0, y también veo 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 pareció 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 estas líneas, el tipo de Swift es rápido, pero aún no 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.


42
2017-10-26 21:47



De The Swift Programming Language:

La biblioteca estándar de Sort Function Swift proporciona una función llamada   sort, que ordena una matriz de valores de un tipo conocido, basado en   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 de la misma   tipo y tamaño como el anterior, con sus elementos en el orden correcto   orden.

los sort la funció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 solo parámetro (la matriz) y está "codificada para usar el comparador inferior".

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

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

Probé una versión modificada de tu código en un patio de recreo con el cierre agregado para poder controlar 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 utilizar 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 de Swift para ella. 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. quickSort () recibió una llamada unas 650 veces,
  2. Se hicieron alrededor de 6000 intercambios,
  3. y hay alrededor de 10,000 comparaciones

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


29
2018-06-08 00:29



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

enter image description here


15
2018-06-11 16:56



Rendimiento de Swift Array revisitado:

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 candidato nuevo, por lo que es bastante rápido. Sin embargo, genera 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 el uso de matrices rápidas normales y el uso de búferes de memoria inseguros Swift utilizando la semántica de matriz.

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

Los resultados de las pruebas parecen ser bastante similares con la optimización de código más rápida, más pequeña ([-0s]) o la optimización más rápida, 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 C malloc'd array son los más rápidos, por un margen modesto

Swift con buffers inseguros toma alrededor de 1.19X - 1.20X más tiempo que los arreglos Malloc'd de C cuando usa la optimización de código más rápida y más pequeña. la diferencia parece un poco menor con la optimización rápida y agresiva (Swift toma más como 1.18x a 1.16x más que C.

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

Los arreglos Swift regulares son DRAMATICALLY más rápido que en Swift 1.2 / Xcode 6. Su rendimiento es muy similar al de las matrices basadas en búfer inseguro de Swift, que el uso de memorias intermedias inseguras en realidad 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 ordenació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.


8
2018-02-26 01:31



El problema principal que otros mencionan pero que no se menciona lo suficiente es que -O3 no hace nada en Swift (y nunca lo ha hecho) así que cuando se compila con eso no se optimiza efectivamente (-Onone)

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

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

La optimización del módulo completo tiene una compilación más lenta, pero puede optimizar en todos los 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. Deberías usar esto para cualquier cosa crítica de rendimiento)

También puede desactivar las comprobaciones de seguridad para obtener aún más velocidad, pero con todas las afirmaciones y condiciones previas no solo deshabilitadas sino optimizadas sobre la base de que son correctas. Si alguna vez aciertas una afirmación, 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 (mediante pruebas). Si lo encuentras 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.


5
2018-04-13 10:58



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 clasificación rápida- Muestra Github Quick-Sort

Puede ver el algoritmo de particionamiento de Lomuto en Particionado de la lista. Escrito en Swift


4
2017-12-06 11:12