Swift Beta performance: ordenando matrices




sorting xcode6 (6)

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.


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


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.


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.


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.


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


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





compiler-optimization