javascript - react - Rendimiento: Immutable.js Map vs List vs plain JS
inmutable react (2)
Pregunta
¿Hay algo mal con mi punto de referencia? ¿Cómo puede Immutable.js encontrar () ser 8 veces más lento que array.find ()?
Ok, no del todo justo, ya que estoy usando Immutable.Map dentro de Immutable.List. Pero para mí este es un ejemplo del mundo real. Si utilizo Immutable.js, se trata de proteger la inmutabilidad y obtener un rendimiento en algunos aspectos (donde el intercambio estructural viene a jugar). No tendría sentido usar Immutable.js solo en la raíz del objeto.
El siguiente punto de referencia es en realidad de otra pregunta (la mía también). Me sorprendieron tanto los resultados que tuve que publicarlo por separado para aclararlo. ¿He hecho algo mal en mis puntos de referencia o la diferencia de rendimiento es realmente tan grande?
Fondo
Algunos de los datos en mi aplicación podrían considerarse metadatos de la aplicación. Los datos originales viven en una base de datos en el servidor. Las actualizaciones de los metadatos no se harán a menudo. La aplicación comprobará los metadatos actualizados en el inicio.
Estoy usando Immutable.js en todas partes, pero volveré a js simple para los metadatos. No es necesario un intercambio estructural elegante para este tipo de datos.
La prueba es encontrar valores por clave en una colección.
Colección de 10 artículos
Encuentra un valor un millón de veces.
Mac mini core i7 2.6
Resultado:
Objeto JS simple con claves coercitivas: 8 ms
Matriz JS simple utilizando find (): 127 ms
Mapa inmutable con teclas numéricas: 185 ms
Inmutable.Lista usando find (): 972 ms !! Estoy desconcertado
Cuando estoy usando React Native, siempre tengo que fijarme en el límite de 16 ms si quiero alcanzar los 60 fps. Los valores de referencia no parecen ser lineales. La ejecución de la prueba con solo 100 búsquedas lleva 1 ms con el Mapa y 2 ms con la Lista. Eso es bastante caro.
Código de prueba
let Immutable = require(''immutable'');
let mapTest = Immutable.Map()
.set(1, Immutable.Map({value: ''one''}))
.set(2, Immutable.Map({value: ''two''}))
.set(3, Immutable.Map({value: ''three''}))
.set(4, Immutable.Map({value: ''four''}))
.set(5, Immutable.Map({value: ''five''}))
.set(6, Immutable.Map({value: ''six''}))
.set(7, Immutable.Map({value: ''seven''}))
.set(8, Immutable.Map({value: ''eight''}))
.set(9, Immutable.Map({value: ''nine''}))
.set(10, Immutable.Map({value: ''ten''}));
let listTest = Immutable.fromJS([
{key: 1, value: ''one''},
{key: 2, value: ''two''},
{key: 3, value: ''three''},
{key: 4, value: ''four''},
{key: 5, value: ''five''},
{key: 6, value: ''six''},
{key: 7, value: ''seven''},
{key: 8, value: ''eight''},
{key: 9, value: ''nine''},
{key: 10, value: ''ten''}
])
let objTest = {
1: {value: ''one''},
2: {value: ''two''},
3: {value: ''three''},
4: {value: ''four''},
5: {value: ''five''},
6: {value: ''six''},
7: {value: ''seven''},
8: {value: ''eight''},
9: {value: ''nine''},
10: {value: ''ten''}
};
let arrayTest = [
{key: 1, value: ''one''},
{key: 2, value: ''two''},
{key: 3, value: ''three''},
{key: 4, value: ''four''},
{key: 5, value: ''five''},
{key: 6, value: ''six''},
{key: 7, value: ''seven''},
{key: 8, value: ''eight''},
{key: 9, value: ''nine''},
{key: 10, value: ''ten''}
];
const runs = 1e6;
let i;
let key;
let hrStart;
console.log('' '')
console.log(''mapTest -----------------------------'')
key = 1;
hrstart = process.hrtime();
for(i=0; i<runs; i++) {
let result = mapTest.getIn([key, ''value''] )
key = (key >= 10) ? 1 : key + 1;
}
hrend = process.hrtime(hrstart);
console.info("Execution time (hr): %dms", hrend[0] * 1000 + hrend[1]/1000000);
console.log('' '')
console.log(''listTest -----------------------------'')
key = 1;
hrstart = process.hrtime();
for(i=0; i<runs; i++) {
let result = listTest
.find(item => item.get(''key'') === key)
.get(''value'');
key = (key >= 10) ? 1 : key + 1;
}
hrend = process.hrtime(hrstart);
console.info("Execution time (hr): %dms", hrend[0] * 1000 + hrend[1]/1000000);
console.log('' '')
console.log(''arrayTest -----------------------------'')
key = 1;
hrstart = process.hrtime();
for(i=0; i<runs; i++) {
let result = arrayTest
.find(item => item.key === key)
.value
key = (key >= 10) ? 1 : key + 1;
}
hrend = process.hrtime(hrstart);
console.info("Execution time (hr): %dms", hrend[0] * 1000 + hrend[1]/1000000);
console.log('' '')
console.log(''objTest -----------------------------'')
key = 1;
hrstart = process.hrtime();
for(i=0; i<runs; i++) {
let result = objTest[key].value
key = (key >= 10) ? 1 : key + 1;
}
hrend = process.hrtime(hrstart);
console.info("Execution time (hr): %dms", hrend[0] * 1000 + hrend[1]/1000000);
La respuesta corta es que la representación de las estructuras de datos utilizadas por Immutable.js requiere una gran cantidad de sobrecarga adicional para recorrer los elementos de una Lista, en comparación con una matriz JS nativa.
Benchmarking Immutable.List.find y Array.find
Su índice de referencia es bueno, pero podemos simplificar un poco las cosas eliminando el mapa anidado; tiene razón al considerar el rendimiento para problemas realistas, pero puede ser útil para comprender las diferencias de rendimiento para simplificar el problema tanto como sea posible. También suele ser útil en la evaluación comparativa para considerar cómo cambia el rendimiento en diferentes tamaños de entrada. Por ejemplo, es posible que en List.prototype.find , List.prototype.find se implemente de tal manera que la configuración y la llamada iniciales tomen un tiempo, pero que la iteración subsiguiente a través de la Lista se realice de manera similar a las matrices JS nativas; en este caso, la diferencia de rendimiento entre las listas JS Arrays nativas y Immutable.js disminuiría para las longitudes de entrada largas (esto no es el caso).
También creamos nuestra propia función de búsqueda para matrices JS nativas, Array.prototype.ourFind para compararla con Array.prototype.find nativa para determinar si la diferencia podría deberse en parte al rendimiento de las funciones JS en sí mismas frente al rendimiento de las funciones creadas -En la implementación.
Array.prototype.ourFind = function(predicate) {
for (let i = 0; i < this.length; i++) {
if (predicate(this[i])) return this[i];
}
}
function arrayRange(len) {
return new Array(len).fill(null).map((_, i) => i);
}
function immutListRange(len) {
return Immutable.fromJS(arrayRange(len));
}
function timeFind(coll, find, iters) {
let startTime = performance.now();
for (let i = 0; i < iters; i++) {
let searchVal = i % coll.length,
result = find.call(coll, item => item === searchVal);
}
return Math.floor(performance.now() - startTime);
}
const MIN_LEN = 10,
MAX_LEN = 1e4,
ITERS = 1e5;
console.log(''/t/tArray.find/tArray.ourFind/tList.find'');
for (let len = MIN_LEN; len <= MAX_LEN; len *= 10) {
console.log(`${len}/t/t/t` +
`${timeFind(arrayRange(len), Array.prototype.find, ITERS)}/t/t/t` +
`${timeFind(arrayRange(len), Array.prototype.ourFind, ITERS)}/t/t/t` +
`${timeFind(immutListRange(len), Immutable.List.prototype.find, ITERS)}`)
}
<script src="https://cdnjs.cloudflare.com/ajax/libs/immutable/3.8.1/immutable.js"></script>
En Chrome, obtengo:
Length . Array.find Array.ourFind List.find
10 28 13 96
100 60 44 342
1000 549 342 3016
10000 5533 3142 36423
Obtuve unos resultados similares en Firefox y Safari. Algunos puntos a tener en cuenta:
- La diferencia entre
List.findfrente aArray.findno se debe simplemente a implementaciones nativas (es decir, intérprete integrado) frente a implementaciones JS, porque una implementación JS deArray.ourFindfunciona al menos tan bien comoArray.find. - Todas las implementaciones funcionan en tiempo O (n) (es decir, el tiempo de ejecución es lineal con respecto a la longitud de entrada). Esto es de esperar, ya que un algoritmo de búsqueda siempre tendrá que funcionar mediante la iteración a través de los elementos de la colección hasta que encuentre uno para el cual el predicado devuelva verdadero.
-
Immutable.List.findes ~ 6 veces más lento queArray.find, consistente con sus resultados de evaluación comparativa.
Inmutable.Lista de representación de datos.
Para comprender por qué Immutable.List.find es mucho más lento, primero debe considerar cómo Immutable.List representa el contenido de la lista.
Una forma rápida de hacer esto es generar un Immutable.List y examinarlo en la consola:
console.log(immutListRange(1000)); // immutListRange defined above
Esencialmente, parece que Immutable.List representa los contenidos como un árbol con un factor de ramificación de 32.
Ahora considere lo que se necesitará para ejecutar una operación de búsqueda en datos que están representados de esta manera. Deberá comenzar en el nodo raíz y atravesar el árbol hasta el primer nodo de la hoja (que contiene una matriz con los datos reales), e iterar a través del contenido de la hoja; Si no se encuentra el elemento, debe ir al siguiente nodo de hoja y buscar esa matriz, y así sucesivamente. Es una operación más compleja que la simple búsqueda a través de una sola matriz, y requiere una sobrecarga para ejecutarse.
Viendo Immutable.List.find en el trabajo
Una excelente manera de apreciar el trabajo que hace Immutable.List.find es establecer un punto de interrupción en el depurador de su elección y pasar por la operación. Verá que Immutable.List.Find no es una operación tan simple como simplemente realizar un bucle a través de un solo Array.
Comentarios adicionales
La representación en árbol de los datos en Immutable.js presumiblemente acelera otras operaciones, pero conlleva una penalización de rendimiento con algunas funciones, como buscar.
Como nota al margen, no creo que en la mayoría de los casos la decisión de usar estructuras de datos inmutables esté impulsada por consideraciones de rendimiento. Puede haber algunos casos en los que las estructuras de datos inmutables se desempeñen mejor que las mutables (y ciertamente las estructuras de datos inmutables hacen que la computación paralela sea menos compleja, lo que permite un aumento significativo del rendimiento), pero habrá muchos casos en los que lo contrario es cierto. Más bien, la elección de la inmutabilidad se debe, en la mayoría de los casos, a consideraciones de diseño, es decir, el uso de estructuras de datos inmutables obliga a que los diseños de los programas sean más sólidos y, a la larga, aumenten la productividad del desarrollador.
Los motores JS son muy buenos para optimizar las operaciones ''calientes'', que se repiten mucho y son lo más simples posible (por ejemplo, TurboFan en V8 ). Los objetos JS simples y las funciones de matriz siempre van a superar una biblioteca como Immutable.js, donde la List llamadas Collection llamadas Seq llama Operations (y así sucesivamente), especialmente cuando las acciones se repiten muchas veces.
Immutable.js parece estar diseñado para la comodidad de uso y evitar la desagradable colección de JS mutables, en lugar del rendimiento puro.
Si tiene un millón de cosas, use una matriz o un objeto JS de bajo nivel (o Web Assembly, si el rendimiento es crítico). Si tiene mil cosas y necesita estar seguro de no dejar caer un marco, entonces el JS simple sigue siendo el camino a seguir. Sin embargo, estos son casos especializados; para la mayoría de los casos de uso, la conveniencia de Immutable.js vale la pena por la reducción de velocidad.