EDITAR : a partir de 2017, v8 ahora optimiza las matrices JS empaquetadas cuando se utilizan los arreglos integrados de matriz (mapa, filtro, etc.), incluida su inclusión en muchos casos, dándoles el mismo rendimiento que el habitual para los bucles [1]. Supongo que otros navegadores han dedicado esfuerzos para hacer lo mismo, ya que estos patrones son muy comunes en el código JavaScript en estos días.
Depende de la VM. Están tan optimizados como cualquier otro código en v8, la diferencia es que el algoritmo utilizado por map (), reduce () y amigos es muy diferente del bucle for que la mayoría de la gente usa para iterar matrices, porque las personas ignoran esas matrices en JavaScript puede tener agujeros (es decir: cualquier matriz puede ser escasa, por lo que su longitud no refleja el número de elementos que tiene la matriz).
¿Por qué Array.prototype.filter () no es rápido?
- ¿Hay alguna forma de imprimir todos los elementos de una lista enlazada en orden inverso sin usar la recursividad?
- ¿Es posible determinar el valor máximo de puntos que se puede otorgar para una sola palabra Scrabble?
- ¿Qué se puede lograr de los algoritmos de aprendizaje? ¿Conducirá a un individuo a ser un mejor programador?
- ¿Cómo puede funcionar un algoritmo con un conjunto de datos pequeño pero da valores incorrectos en un conjunto de datos más grande?
- ¿Cuán específicamente la memoria de la clase de almacenamiento cambiará las arquitecturas, los ecosistemas (incluidas las opciones de lenguaje de programación) y los algoritmos para big data?
Como ejemplo, veamos la implementación de v8 de Array.prototype.filter, que se implementa en JavaScript¹: https://github.com/v8/v8/blob/73…
Al leer ese código, notará que hay un comentario que dice que v8 realmente no puede hacer que el código sea eficiente, y eso se debe a la semántica en Array.prototype.filter. La función acepta matrices dispersas, por lo que la implementación debe analizar si hay algún índice presente o no en la matriz (línea 1158). Esta verificación particular, al igual que verificar si una clave está presente en un objeto, es lenta. Además, no se garantiza que las funciones pasadas como argumentos para filter () sean puras, y toman la matriz original como argumento, por lo que nada le impide escribir:
xs.filter (función (elemento, índice, matriz) {
eliminar matriz [~~ (Math.random () * array.length)];
volver verdadero;
})
La posibilidad de estos efectos secundarios dificulta la optimización de las cosas, por lo que las cosas adoptan un enfoque más conservador para que su programa se ejecute lo más rápido posible mientras se mantiene el comportamiento correcto.
¿Pueden las funciones de orden superior como filter () ser rápidas?
También notará que el código que ve en Array.prototype.filter () no es el mismo código que la gente suele escribir en un bucle for para iterar sobre la matriz. Entonces, comparar el rendimiento de un bucle for con esa implementación de Array.prototype.filter () es comparar manzanas con naranjas: no estás haciendo lo mismo.
Entonces, para asegurarnos de que estamos comparando lo mismo, volveremos a implementar map () y luego escribiremos el equivalente de ese código usando un bucle for:
// El mapa
mapa de funciones (xs, f) {
var ys = [];
para (var i = 0; i <xs.length; ++ i) {
ys [i] = f (xs [i]);
}
volver ys;
}
función inc (a) {
devuelve a + 1;
}
mapa (xs, inc)
// El bucle for
función forloop (xs) {
var ys = [];
para (var i = 0; i <xs.length; ++ i) {
ys [i] = xs [i] + 1;
}
volver ys;
}
forloop (xs)
Ahora ambas funciones hacen lo mismo. Podemos proceder a verificar si v8 trata a ambos de la misma manera. Esto se puede hacer simplemente analizando la representación intermedia que v8 usa al compilar. Vyacheslav Egorov, una de las personas que trabajan en el compilador v8, escribió una herramienta llamada IRHydra (http://mrale.ph/irhydra/2/), que se puede utilizar para analizar este IR.
Para el ejemplo anterior, v8 generará miles de líneas de código de ensamblaje (consulte 0-map.js y 0-for.js), que podemos cargar en IRHydra. El preámbulo de ambas funciones es muy similar, con la diferencia de que `map ()` toma 2 parámetros, mientras que `forloop ()` toma uno. Del mismo modo, `map ()` necesita verificar más valores, pero esto es solo una verificación antes del bucle real, por lo que realmente no tiene mucho impacto:
La parte previa al bucle tiene el código para asignar la nueva matriz, y verifica los objetos para asegurarse de que todavía estamos bajo los mismos supuestos para los que se optimizó este código (por lo tanto, si pasó una Cadena u Objeto para mapear () o forloop (), eso violaría los CheckMaps y haría que v8 vuelva a compilar esa función o la desaproveche).
Sin embargo, la parte interesante es el bucle, y si observa el bucle para `map ()` y el bucle para `forloop ()`, ¡notará que tienen aproximadamente las mismas instrucciones! v8 descubrió que era seguro alinear la función que se pasó a `map ()`, lo que hizo que las dos piezas de código fueran iguales (tenga en cuenta la falta de llamadas a funciones en la versión `map ()`, y la `Add `instrucción en el mismo lugar):
¿Puedo conocer el rendimiento sin todo esto?
“¡Pero eso es mucho trabajo!” “¿De alguna manera puedo predecir cómo funcionará mi código sin hacer todo esto?”
No, no puedes.
La única forma de saber cómo funciona algo en las máquinas virtuales JavaScript modernas es mediante un perfil cuidadoso y, si realmente debe hacerlo, mirando las partes internas de la máquina virtual. Ahora, la sección anterior era completamente sobre v8, mientras que las máquinas virtuales modernas logran un rendimiento similar, lo hacen a través de diferentes tipos de análisis y optimizaciones, por lo que lo que funciona bien para v8 podría no funcionar tan bien para SpiderMonkey, o JSC, o Chakra, o Nashorn o cualquier otra máquina virtual. Perfilar su aplicación real en cada plataforma que desea admitir sigue siendo la mejor manera de obtener comentarios útiles sobre su rendimiento y decidir qué hacer para abordar cualquier problema de rendimiento que pueda tener.
¡Las micro optimizaciones no importan!
Como dijo Mattias Petter Johansson en su respuesta a esta pregunta, las micro optimizaciones realmente no importan para el código del mundo real. Mejores algoritmos lo hacen. De hecho, la velocidad en la sección de referencia, en comparación con Array.prototype.map, se logró al tener un mejor algoritmo . Sin embargo, este mejor algoritmo no funciona bien con la semántica de JavaScript. Es decir, si bien es más rápido, también está mal, ¡porque falla para matrices dispersas y objetos similares a matrices! Un humano podría muy bien determinar que ese algoritmo particular es el adecuado para su aplicación , porque saben con qué tipo de datos están tratando. El compilador y el estándar del lenguaje no pueden hacer eso, por lo que terminará con la versión de gastos generales que se encuentra en la biblioteca estándar para admitir todos estos otros casos de uso.
Además, no está claro que Array.prototype.map () sea el cuello de botella en su aplicación. Solo puede saber qué vale la pena optimizar perfilando cuidadosamente su código. Y si Array.prototype.map () es lento en una ruta caliente de su código, tal vez Array no sea la estructura de datos correcta para su caso de uso. Por ejemplo, si está probando una colisión, usar un QuadTree reduciría la cantidad de objetos con los que necesita comparar en una gran cantidad, mientras que usar una matriz requeriría que verifique cada objeto contra cada otro objeto (no solo los cerca de eso).
Conclusión
Sí, las máquinas virtuales JavaScript modernas pueden optimizar las cosas muy bien, y eso significa que Array.prototype. {Filter, map, reduce, …} están lo más optimizados posible, sin dejar de ser lo más general posible. Por lo tanto, son lo suficientemente rápidos para cualquier aplicación que realmente los requiera.
Sin embargo, el rendimiento de esas funciones no solucionará los problemas de usar el algoritmo o la estructura de datos incorrectos en su aplicación. Siempre revise sus algoritmos y estructuras de datos antes de hacer cualquier otra optimización.
¹: Autohospedar la biblioteca estándar (es decir, escribir la biblioteca estándar de JS VM en JavaScript) es algo común entre las máquinas virtuales JavaScript modernas, y eso permite que la biblioteca estándar obtenga las mismas optimizaciones que se aplican a otro código (la función de alineación funciona , por ejemplo), sin tener la sobrecarga de hablar con la capa nativa.
Notas al pie
[1] 1956 – Mejora el rendimiento de los componentes integrados de la matriz – v8 – Monorriel
