ios - map vs for
Rendimiento rápido: map() y reduce() vs for loops (3)
¿No deberían los métodos Array incorporados ser más rápidos que el enfoque ingenuo para realizar tales operaciones? Quizás alguien con más conocimientos de bajo nivel que yo pueda arrojar algo de luz sobre la situación.
Solo quiero tratar de abordar esta parte de la pregunta y más desde el nivel conceptual (con poca comprensión de la naturaleza del optimizador de Swift de mi parte) con un "no necesariamente". Proviene más de una experiencia en diseño de compiladores y arquitectura de computadoras que de un conocimiento profundo de la naturaleza del optimizador de Swift.
Llamando por encima
Con funciones como
map
y
reduce
funciones de aceptación como entradas, ejerce una mayor presión sobre el optimizador para decirlo de una manera.
La tentación natural, en tal caso, de una optimización muy agresiva es ramificarse constantemente entre la implementación de, digamos, el
map
y el cierre que proporcionó, y también transmitir datos a través de estas ramas dispares de código (a través de registros y pila , típicamente).
Ese tipo de sobrecarga de llamadas / ramificaciones es muy difícil de eliminar para el optimizador, especialmente dada la flexibilidad de los cierres de Swift (no imposible pero conceptualmente bastante difícil).
Los optimizadores de C ++ pueden alinear llamadas a objetos de función, pero con muchas más restricciones y técnicas de generación de código necesarias para hacerlo, donde el compilador efectivamente tendría que generar un conjunto completamente nuevo de instrucciones para el
map
para cada tipo de objeto de función que pase (y con ayuda explícita del programador que indica una plantilla de función utilizada para la generación de código).
Por lo tanto, no debería ser una gran sorpresa descubrir que sus bucles enrollados a mano pueden funcionar más rápido: ejercen una gran presión sobre el optimizador.
He visto a algunas personas citar que estas funciones de orden superior deberían poder ir más rápido como resultado de que el proveedor pueda hacer cosas como paralelizar el bucle, pero para paralelizar efectivamente el bucle primero requeriría el tipo de información que normalmente permita que el optimizador alinee las llamadas de función anidadas dentro de un punto donde se vuelven tan baratas como los bucles enrollados a mano.
De lo contrario, la implementación de función / cierre que pasará será efectivamente opaca para funciones como
map/reduce
: solo pueden llamarlo y pagar la sobrecarga de hacerlo, y no pueden paralelizarlo ya que no pueden asumir nada sobre la naturaleza del lado efectos y seguridad de hilos al hacerlo.
Por supuesto, todo esto es conceptual: Swift puede optimizar estos casos en el futuro, o ya puede hacerlo ahora (vea
-Ofast
como una forma comúnmente citada para hacer que Swift vaya más rápido a costa de algunos la seguridad).
Pero, al menos, ejerce una mayor presión sobre el optimizador para utilizar este tipo de funciones sobre los bucles enrollados a mano, y las diferencias de tiempo que ve en el primer punto de referencia parecen reflejar el tipo de diferencias que uno podría esperar con esta sobrecarga adicional de llamadas.
La mejor manera de averiguarlo es mirar el ensamblaje y probar varios indicadores de optimización.
Funciones estándar
Eso no es para desalentar el uso de tales funciones. Expresan intenciones de manera más concisa, pueden aumentar la productividad. Y confiar en ellos podría permitir que su base de código sea más rápida en futuras versiones de Swift sin ninguna participación de su parte. Pero no siempre serán necesariamente más rápidos: es una buena regla general pensar que una función de biblioteca de nivel superior que exprese más directamente lo que quiere hacer será más rápida, pero siempre hay excepciones a la regla (pero mejor descubierto en retrospectiva con un perfilador en la mano, ya que es mucho mejor errar por el lado de la confianza que la desconfianza aquí).
Puntos de referencia artificiales
En cuanto a su segundo punto de referencia, es casi seguro que es el resultado de que el compilador optimiza el código que no tiene efectos secundarios que afecten la salida del usuario. Los puntos de referencia artificiales tienden a ser notoriamente engañosos como resultado de lo que hacen los optimizadores para eliminar los efectos secundarios irrelevantes (efectos secundarios que no afectan la producción del usuario, esencialmente). Por lo tanto, debe tener cuidado al construir puntos de referencia con tiempos que parecen demasiado buenos para ser verdad que no son el resultado del optimizador simplemente omitiendo todo el trabajo que realmente quería comparar. Como mínimo, desea que sus pruebas generen algunos resultados finales recopilados del cálculo.
Estoy escribiendo código de rendimiento crítico en Swift.
Después de implementar todas las optimizaciones que se me ocurrieron y de perfilar la aplicación en Instrumentos, me di cuenta de que la gran mayoría de los ciclos de CPU se dedican a realizar operaciones
map()
y
reduce()
en matrices de flotadores.
Entonces, solo para ver qué sucedería, reemplacé todas las instancias de
map
y
reduce
con bucles anticuados.
Y para mi sorpresa ... ¡los bucles
for
fueron mucho, mucho más rápidos!
Un poco desconcertado por esto, decidí realizar algunos puntos de referencia aproximados.
En una prueba, hice que el
map
devolviera una matriz de Flotadores después de realizar una aritmética simple como esta:
// Populate array with 1,000,000,000 random numbers
var array = [Float](count: 1_000_000_000, repeatedValue: 0)
for i in 0..<array.count {
array[i] = Float(random())
}
let start = NSDate()
// Construct a new array, with each element from the original multiplied by 5
let output = array.map({ (element) -> Float in
return element * 5
})
// Log the elapsed time
let elapsed = NSDate().timeIntervalSinceDate(start)
print(elapsed)
Y el equivalente
for
implementación del bucle:
var output = [Float]()
for element in array {
output.append(element * 5)
}
Tiempo promedio de ejecución para el
map
: 20.1 segundos.
Tiempo promedio de ejecución del ciclo
for
: 11.2 segundos.
Los resultados fueron similares usando números enteros en lugar de flotadores.
Creé un punto de referencia similar para probar el rendimiento de la
reduce
de Swift.
Esta vez,
reduce
y
for
bucles logró casi el mismo rendimiento al sumar los elementos de una gran matriz.
Pero cuando hago la prueba 100,000 veces así:
// Populate array with 1,000,000 random numbers
var array = [Float](count: 1_000_000, repeatedValue: 0)
for i in 0..<array.count {
array[i] = Float(random())
}
let start = NSDate()
// Perform operation 100,000 times
for _ in 0..<100_000 {
let sum = array.reduce(0, combine: {$0 + $1})
}
// Log the elapsed time
let elapsed = NSDate().timeIntervalSinceDate(start)
print(elapsed)
vs:
for _ in 0..<100_000 {
var sum: Float = 0
for element in array {
sum += element
}
}
El método de
reduce
toma 29 segundos mientras que el ciclo
for
toma (aparentemente) 0.000003 segundos.
Naturalmente, estoy listo para ignorar esa última prueba como resultado de una optimización del compilador, pero creo que puede dar una idea de cómo el compilador se optimiza de manera diferente para los bucles frente a los métodos de matriz incorporados de Swift.
Tenga en cuenta que todas las pruebas se realizaron con la optimización -Os en un MacBook Pro i7 de 2.5 GHz.
Los resultados variaron según el tamaño de la matriz y el número de iteraciones, pero
for
bucles siempre superaron a los otros métodos en al menos 1.5x, a veces hasta 10x.
Estoy un poco perplejo sobre el rendimiento de Swift aquí. ¿No deberían los métodos Array incorporados ser más rápidos que el enfoque ingenuo para realizar tales operaciones? Quizás alguien con más conocimientos de bajo nivel que yo pueda arrojar algo de luz sobre la situación.
Hice un conjunto rápido de pruebas de rendimiento que miden el rendimiento de las transformaciones repetidas en una matriz de cadenas, y mostró que
.map
era mucho más eficaz que un bucle for, por un factor de aproximadamente 10x.
Los resultados en la siguiente captura de pantalla muestran que las transformaciones encadenadas en un solo bloque de
map
superan a varios
map
con una sola transformación en cada uno, y cualquier uso de
map
supera a los bucles.
Código que usé en un patio de juegos:
import Foundation
import XCTest
class MapPerfTests: XCTestCase {
var array =
[
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString",
"MyString"
]
func testForLoopAllInOnePerf() {
measure {
var newArray: [String] = []
for item in array {
newArray.append(item.uppercased().lowercased().uppercased().lowercased())
}
}
}
func testForLoopMultipleStagesPerf() {
measure {
var newArray: [String] = []
for item in array {
let t1 = item.uppercased()
let t2 = item.lowercased()
let t3 = item.uppercased()
let t4 = item.lowercased()
newArray.append(t4)
}
}
}
func testMultipleMapPerf() {
measure {
let newArray = array
.map( { $0.uppercased() } )
.map( { $0.lowercased() } )
.map( { $0.uppercased() } )
.map( { $0.lowercased() } )
}
}
func testSingleMapPerf() {
measure {
let newArray = array
.map( { $0.uppercased().lowercased().uppercased().lowercased() } )
}
}
}
MapPerfTests.defaultTestSuite.run()
No puedo decir mucho sobre su primera prueba (
map()
vs
append()
en un bucle) pero puedo confirmar sus resultados.
El ciclo append se vuelve aún más rápido si agrega
output.reserveCapacity(array.count)
después de la creación de la matriz. Parece que Apple puede mejorar las cosas aquí y puede presentar un informe de error.
En
for _ in 0..<100_000 {
var sum: Float = 0
for element in array {
sum += element
}
}
el compilador (probablemente) elimina todo el ciclo porque los resultados calculados no se utilizan en absoluto. Solo puedo especular por qué no ocurre una optimización similar en
for _ in 0..<100_000 {
let sum = array.reduce(0, combine: {$0 + $1})
}
pero sería más difícil decidir si llamar a
reduce()
con el cierre tiene algún efecto secundario o no.
Si el código de prueba se modifica ligeramente para calcular e imprimir una suma total
do {
var total = Float(0.0)
let start = NSDate()
for _ in 0..<100_000 {
total += array.reduce(0, combine: {$0 + $1})
}
let elapsed = NSDate().timeIntervalSinceDate(start)
print("sum with reduce:", elapsed)
print(total)
}
do {
var total = Float(0.0)
let start = NSDate()
for _ in 0..<100_000 {
var sum = Float(0.0)
for element in array {
sum += element
}
total += sum
}
let elapsed = NSDate().timeIntervalSinceDate(start)
print("sum with loop:", elapsed)
print(total)
}
entonces ambas variantes toman alrededor de 10 segundos en mi prueba.