¿La inmutabilidad perjudica el rendimiento en JavaScript?

88

Parece que hay una tendencia reciente en JavaScript hacia el tratamiento de las estructuras de datos como inmutables. Por ejemplo, si necesita cambiar una sola propiedad de un objeto, es mejor crear un objeto completamente nuevo con la nueva propiedad, y simplemente copiar todas las demás propiedades del objeto antiguo, y dejar que el objeto antiguo sea basura recolectada. (Esa es mi comprensión de todos modos).

Mi reacción inicial es que parece que sería malo para el rendimiento.

Pero entonces las bibliotecas como Immutable.js y Redux.js son escritos por personas inteligentes que yo, y parecen tener una fuerte preocupación por el rendimiento, por lo que me hace pensar que mi comprensión de la basura (y su impacto en el rendimiento) es incorrecto.

¿Hay beneficios de rendimiento para la inmutabilidad que me falta, y superan las desventajas de crear tanta basura?

callum
fuente
8
Tienen una gran preocupación por el rendimiento en parte porque la inmutabilidad (a veces) tiene un costo de rendimiento, y quieren minimizar ese costo de rendimiento tanto como sea posible. La inmutabilidad, por sí sola, solo tiene beneficios de rendimiento en el sentido de que facilita la escritura de código multiproceso.
Robert Harvey
8
En mi experiencia, el rendimiento es solo una preocupación válida para dos escenarios: uno, cuando una acción se realiza más de 30 veces en un segundo, y dos, cuando sus efectos aumentan con cada ejecución (Windows XP una vez encontró un error donde el tiempo de actualización de Windows tomó O(pow(n, 2))para cada actualización en su historial ). La mayoría del otro código es una respuesta inmediata a un evento; un clic, solicitud de API o similar, y siempre que el tiempo de ejecución sea constante, la limpieza de cualquier cantidad de objetos difícilmente importa.
Katana314
44
Además, considere que existen implementaciones eficientes de estructuras de datos inmutables. Tal vez estos no sean tan eficientes como los mutables, pero probablemente aún sean más eficientes que una implementación ingenua. Véase, por ejemplo, estructuras de datos puramente funcionales por Chris Okasaki
Giorgio
1
@ Katana314: más de 30 veces para mí aún no sería suficiente para justificar la preocupación por el rendimiento. Porté un pequeño emulador de CPU que escribí en node.js y el nodo ejecutó la CPU virtual a unos 20MHz (eso es 20 millones de veces por segundo). Por lo tanto, solo me preocuparía el rendimiento si estuviera haciendo algo más de 1000 veces por segundo (incluso entonces, realmente no me preocuparía hasta que realice 1000000 operaciones por segundo porque sé que puedo hacer cómodamente más de 10 de ellas a la vez) .
slebetman
2
@RobertHarvey "La inmutabilidad, por sí sola, solo tiene beneficios de rendimiento en el sentido de que facilita la escritura de código multiproceso". Eso no es del todo cierto, la inmutabilidad permite un intercambio muy generalizado sin consecuencias reales. Lo cual es muy inseguro en un entorno mutable. Esto le da la posibilidad de O(1)dividir e O(log n)insertar una matriz en un árbol binario mientras aún puede usar el antiguo libremente, y otro ejemplo es tailsque toma todas las colas de una lista tails [1, 2] = [[1, 2], [2], []]solo toma O(n)tiempo y espacio, pero está O(n^2)en recuento de elementos
punto

Respuestas:

59

Por ejemplo, si necesita cambiar una sola propiedad de un objeto, es mejor crear un objeto completamente nuevo con la nueva propiedad, y simplemente copiar todas las demás propiedades del objeto antiguo, y dejar que el objeto antiguo se recoja basura.

Sin inmutabilidad, puede que tenga que pasar un objeto entre diferentes ámbitos, y no sabe de antemano si se cambiará el objeto y cuándo. Por lo tanto, para evitar efectos secundarios no deseados, comienza a crear una copia completa del objeto "por si acaso" y pasa esa copia, incluso si resulta que no se debe cambiar ninguna propiedad. Eso dejará mucha más basura que en su caso.

Lo que esto demuestra es: si crea el escenario hipotético correcto, puede probar cualquier cosa, especialmente en lo que respecta al rendimiento. Mi ejemplo, sin embargo, no es tan hipotético como podría parecer. Trabajé el mes pasado en un programa en el que tropezamos exactamente con ese problema porque inicialmente decidimos no usar una estructura de datos inmutable, y dudé en refactorizar esto más tarde porque no parecía que valiera la pena.

Entonces, cuando mira casos como este de una publicación SO anterior , la respuesta a sus preguntas probablemente sea clara, depende . En algunos casos, la inmutabilidad perjudicará el rendimiento, para algunos lo contrario puede ser cierto, para muchos casos dependerá de cuán inteligente sea su implementación, y para aún más casos la diferencia será insignificante.

Una nota final: un problema del mundo real que puede encontrar es que necesita decidir temprano a favor o en contra de la inmutabilidad de algunas estructuras de datos básicas. Luego construye mucho código sobre eso, y varias semanas o meses después verá si la decisión fue buena o mala.

Mi regla general personal para esta situación es:

  • Si diseña una estructura de datos con solo unos pocos atributos basados ​​en primitivos u otros tipos inmutables, intente primero la inmutabilidad.
  • Si desea diseñar un tipo de datos en el que intervienen matrices con un tamaño grande (o indefinido), acceso aleatorio y contenido cambiante, use la mutabilidad.

Para situaciones entre estos dos extremos, use su juicio. Pero YMMV.

Doc Brown
fuente
8
That will leave a lot more garbage than in your case.y para empeorar las cosas, su tiempo de ejecución probablemente no podrá detectar la duplicación sin sentido y, por lo tanto (a diferencia de un objeto inmutable expirado que nadie está usando) ni siquiera será elegible para la colección.
Jacob Raihle
37

En primer lugar, su caracterización de estructuras de datos inmutables es imprecisa. En general, la mayor parte de una estructura de datos no se copia, sino que se comparte , y solo se copian las partes modificadas. Se llama una estructura de datos persistente . La mayoría de las implementaciones pueden aprovechar las estructuras de datos persistentes la mayor parte del tiempo. El rendimiento es lo suficientemente cercano a las estructuras de datos mutables que los programadores funcionales generalmente lo consideran insignificante.

En segundo lugar, encuentro que muchas personas tienen una idea bastante inexacta de la vida útil típica de los objetos en los programas imperativos típicos. Quizás esto se deba a la popularidad de los lenguajes gestionados por memoria. Siéntese alguna vez y observe realmente cuántos objetos temporales y copias defensivas crea en comparación con las estructuras de datos verdaderamente longevas. Creo que te sorprenderá la proporción.

He tenido personas que comentan en las clases de programación funcional que enseño sobre la cantidad de basura que crea un algoritmo, luego muestro la típica versión imperativa del mismo algoritmo que crea la misma cantidad. Solo por alguna razón la gente ya no lo nota.

Al alentar el uso compartido y desalentar la creación de variables hasta que tenga un valor válido para poner en ellas, la inmutabilidad tiende a fomentar prácticas de codificación más limpias y estructuras de datos más longevas. Esto a menudo conduce a niveles de basura comparables, si no más bajos, dependiendo de su algoritmo.

Karl Bielefeldt
fuente
8
"... entonces muestro la típica versión imperativa del mismo algoritmo que crea lo mismo". Esta. Además, las personas que son nuevas en este estilo, y especialmente si son nuevas en el estilo funcional en general, inicialmente pueden producir implementaciones funcionales subóptimas.
wberry
1
"desalentar la creación de variables" ¿No es eso válido solo para idiomas donde el comportamiento predeterminado es copiar en la asignación / construcción implícita? En JavaScript, una variable es solo un identificador; No es un objeto en sí mismo. Todavía ocupa espacio en alguna parte, pero eso es insignificante (especialmente porque la mayoría de las implementaciones de JavaScript, que yo sepa, todavía usan una pila para llamadas a funciones, lo que significa que a menos que tenga mucha recursión, terminará reutilizando el mismo espacio de pila para la mayoría variables temporales). La inmutabilidad no tiene relación con ese aspecto.
JAB
33

Llegué tarde a estas preguntas y respuestas con excelentes respuestas, pero quería entrometerme como un extranjero acostumbrado a mirar las cosas desde el punto de vista de nivel inferior de bits y bytes en la memoria.

Estoy muy entusiasmado con los diseños inmutables, incluso desde una perspectiva C, y desde la perspectiva de encontrar nuevas formas de programar efectivamente este hardware bestial que tenemos en estos días.

Más lento / más rápido

En cuanto a la pregunta de si hace las cosas más lentas, sería una respuesta robótica yes. En este tipo de nivel conceptual muy técnico, la inmutabilidad solo podría hacer las cosas más lentas. El hardware funciona mejor cuando no está asignando esporádicamente memoria y puede simplemente modificar la memoria existente en su lugar (por qué tenemos conceptos como localidad temporal).

Sin embargo, una respuesta práctica es maybe. El rendimiento sigue siendo en gran medida una métrica de productividad en cualquier base de código no trivial. Por lo general, no encontramos que las bases de código horribles para mantener las condiciones de carrera sean las más eficientes, incluso si ignoramos los errores. La eficiencia es a menudo una función de elegancia y simplicidad. El pico de micro optimizaciones puede entrar en conflicto, pero generalmente están reservadas para las secciones de código más pequeñas y críticas.

Transformando bits y bytes inmutables

Viniendo desde el punto de vista de bajo nivel, si conceptos como que de rayos X objectsy stringsy así sucesivamente, en el corazón de la misma es sólo bits y bytes en diversas formas de memoria con diferentes características de velocidad / tamaño (velocidad y el tamaño de hardware de memoria siendo típicamente mutuamente excluyentes).

ingrese la descripción de la imagen aquí

A la jerarquía de memoria de la computadora le gusta cuando accedemos repetidamente a la misma porción de memoria, como en el diagrama anterior, ya que mantendrá esa porción de memoria a la que se accede con frecuencia en la forma más rápida de memoria (caché L1, por ejemplo, que es casi tan rápido como un registro). Podríamos acceder repetidamente a la misma memoria (reutilizándola varias veces) o acceder repetidamente a diferentes secciones del fragmento (por ejemplo, recorrer los elementos en un fragmento contiguo que accede repetidamente a varias secciones de ese fragmento de memoria).

Terminamos lanzando una llave inglesa en ese proceso si la modificación de esta memoria termina deseando crear un bloque de memoria completamente nuevo en el lateral, así:

ingrese la descripción de la imagen aquí

... en este caso, acceder al nuevo bloque de memoria podría requerir fallas de página obligatorias y errores de caché para volver a colocarlo en las formas más rápidas de memoria (hasta un registro). Eso puede ser un verdadero asesino de rendimiento.

Hay formas de mitigar esto, sin embargo, utilizando un grupo de reserva de memoria preasignada, ya tocada.

Grandes agregados

Otro problema conceptual que surge de una vista de nivel ligeramente superior es simplemente hacer copias innecesarias de agregados realmente grandes a granel.

Para evitar un diagrama demasiado complejo, imaginemos que este simple bloque de memoria es de alguna manera costoso (quizás caracteres UTF-32 en un hardware increíblemente limitado).

ingrese la descripción de la imagen aquí

En este caso, si quisiéramos reemplazar "AYUDA" con "KILL" y este bloque de memoria fuera inmutable, tendríamos que crear un bloque completamente nuevo en su totalidad para crear un nuevo objeto único, aunque solo hayan cambiado partes de él. :

ingrese la descripción de la imagen aquí

Estirando un poco nuestra imaginación, este tipo de copia profunda de todo lo demás solo para hacer que una pequeña parte sea única podría ser bastante costoso (en casos del mundo real, este bloque de memoria sería mucho, mucho más grande para plantear un problema).

Sin embargo, a pesar de tal gasto, este tipo de diseño tenderá a ser mucho menos propenso al error humano. Cualquiera que haya trabajado en un lenguaje funcional con funciones puras probablemente pueda apreciar esto, y especialmente en los casos de subprocesos múltiples donde podemos multiprocesar dicho código sin preocuparnos en el mundo. En general, los programadores humanos tienden a tropezar con los cambios de estado, especialmente los que causan efectos secundarios externos a estados fuera del alcance de una función actual. Incluso recuperarse de un error externo (excepción) en tal caso puede ser increíblemente difícil con cambios de estado externo mutable en la mezcla.

Una forma de mitigar este trabajo de copia redundante es hacer que estos bloques de memoria se conviertan en una colección de punteros (o referencias) a caracteres, de esta manera:

Disculpas, no me di cuenta de que no necesitamos hacer algo Lúnico al hacer el diagrama.

El azul indica datos copiados poco profundos.

ingrese la descripción de la imagen aquí

... desafortunadamente, esto sería increíblemente costoso para pagar un puntero / costo de referencia por personaje. Además, podríamos dispersar el contenido de los caracteres por todo el espacio de direcciones y terminar pagándolo en forma de un montón de fallas de página y errores de caché, lo que hace que esta solución sea aún peor que copiar todo en su totalidad.

Incluso si fuéramos cuidadosos al asignar estos caracteres de manera contigua, digamos que la máquina puede cargar 8 caracteres y 8 punteros a un carácter en una línea de caché. Terminamos cargando memoria como esta para atravesar la nueva cadena:

ingrese la descripción de la imagen aquí

En este caso, terminamos requiriendo 7 líneas diferentes de caché de memoria contigua para cargar esta cadena, cuando idealmente solo necesitamos 3.

Trocear los datos

Para mitigar el problema anterior, podemos aplicar la misma estrategia básica pero a un nivel más grueso de 8 caracteres, p. Ej.

ingrese la descripción de la imagen aquí

El resultado requiere que se carguen 4 líneas de caché de datos (1 para los 3 punteros y 3 para los caracteres) para atravesar esta cadena que está a solo 1 menos del óptimo teórico.

Así que eso no está nada mal. Hay un poco de pérdida de memoria, pero la memoria es abundante y usar más no ralentiza las cosas si la memoria adicional va a ser datos fríos a los que no se accede con frecuencia. Es solo para los datos calientes y contiguos donde el uso reducido de la memoria y la velocidad a menudo van de la mano donde queremos colocar más memoria en una sola página o línea de caché y acceder a todo antes del desalojo. Esta representación es bastante amigable con el caché.

Velocidad

Por lo tanto, utilizar una representación como la anterior puede proporcionar un equilibrio de rendimiento bastante decente. Probablemente, los usos más críticos para el rendimiento de las estructuras de datos inmutables tomarán esta naturaleza de modificar piezas de datos gruesas y hacerlas únicas en el proceso, mientras copian piezas poco modificadas. También implica cierta sobrecarga de operaciones atómicas para hacer referencia a las piezas copiadas poco profundas de forma segura en un contexto multiproceso (posiblemente con algún recuento de referencia atómica en curso).

Sin embargo, siempre que estos fragmentos de datos estén representados en un nivel lo suficientemente grueso, gran parte de esta sobrecarga disminuye y posiblemente incluso se trivializa, al tiempo que nos brinda la seguridad y la facilidad de codificar y multiprocesar más funciones en una forma pura sin un lado externo. efectos

Mantener datos nuevos y antiguos

Donde veo la inmutabilidad como potencialmente más útil desde el punto de vista del rendimiento (en un sentido práctico) es cuando podemos sentir la tentación de hacer copias completas de datos grandes para que sean únicos en un contexto mutable donde el objetivo es producir algo nuevo a partir de algo que ya existe de una manera en la que queremos mantener tanto lo nuevo como lo antiguo, cuando podríamos hacer pequeños pedazos únicos con un diseño cuidadoso e inmutable.

Ejemplo: Deshacer sistema

Un ejemplo de esto es un sistema de deshacer. Podríamos cambiar una pequeña porción de una estructura de datos y queremos mantener tanto el formulario original que podemos deshacer como el nuevo formulario. Con este tipo de diseño inmutable que solo hace que las secciones pequeñas y modificadas de la estructura de datos sean únicas, simplemente podemos almacenar una copia de los datos antiguos en una entrada de deshacer mientras solo pagamos el costo de memoria de los datos de porciones únicas agregadas. Esto proporciona un equilibrio muy efectivo de productividad (haciendo que la implementación de un sistema de deshacer sea pan comido) y el rendimiento.

Interfaces de alto nivel

Sin embargo, algo incómodo surge con el caso anterior. En un tipo de contexto de función local, los datos mutables son a menudo los más fáciles y más fáciles de modificar. Después de todo, la forma más fácil de modificar una matriz a menudo es simplemente recorrerla y modificar un elemento a la vez. Podemos terminar aumentando la sobrecarga intelectual si tuviéramos una gran cantidad de algoritmos de alto nivel para elegir para transformar una matriz y tuviéramos que elegir el apropiado para asegurarnos de que todas estas copias superficiales gruesas se realicen mientras las partes que se modifican son hecho único

Probablemente, la forma más fácil en esos casos es usar buffers mutables localmente dentro del contexto de una función (donde generalmente no nos hacen tropezar) que cometen cambios atómicamente en la estructura de datos para obtener una nueva copia inmutable (creo que algunos idiomas llaman estos "transitorios") ...

... o podríamos simplemente modelar funciones de transformación de nivel superior e superior sobre los datos para poder ocultar el proceso de modificación de un búfer mutable y comprometerlo en la estructura sin una lógica mutable involucrada. En cualquier caso, este aún no es un territorio ampliamente explorado, y tenemos que cortar nuestro trabajo si adoptamos diseños inmutables más para crear interfaces significativas sobre cómo transformar estas estructuras de datos.

Estructuras de datos

Otra cosa que surge aquí es que la inmutabilidad utilizada en un contexto crítico para el rendimiento probablemente querrá que las estructuras de datos se descompongan en datos gruesos donde los fragmentos no son demasiado pequeños pero tampoco demasiado grandes.

Las listas vinculadas pueden querer cambiar un poco para acomodar esto y convertirse en listas no desarrolladas. Las matrices contiguas grandes pueden convertirse en una matriz de punteros en trozos contiguos con indexación de módulo para acceso aleatorio.

Potencialmente cambia la forma en que vemos las estructuras de datos de una manera interesante, al tiempo que empuja las funciones de modificación de estas estructuras de datos para que se parezcan a una naturaleza más voluminosa para ocultar la complejidad adicional de copiar algunos bits aquí y hacer que otros bits sean únicos allí.

Actuación

De todos modos, esta es mi pequeña visión de nivel inferior sobre el tema. Teóricamente, la inmutabilidad puede tener un costo que varía de muy grande a más pequeño. Pero un enfoque muy teórico no siempre hace que las aplicaciones sean rápidas. Puede que sean escalables, pero la velocidad del mundo real a menudo requiere adoptar una mentalidad más práctica.

Desde una perspectiva práctica, cualidades como el rendimiento, el mantenimiento y la seguridad tienden a convertirse en un gran desenfoque, especialmente para una base de código muy grande. Si bien el rendimiento en cierto sentido absoluto se degrada con la inmutabilidad, es difícil argumentar los beneficios que tiene para la productividad y la seguridad (incluida la seguridad de los hilos). Con un aumento de estos, a menudo puede venir un aumento en el rendimiento práctico, aunque solo sea porque los desarrolladores tienen más tiempo para ajustar y optimizar su código sin ser abrumados por errores.

Entonces, desde este sentido práctico, creo que las estructuras de datos inmutables podrían ayudar al rendimiento en muchos casos, por extraño que parezca. Un mundo ideal podría buscar una combinación de estos dos: estructuras de datos inmutables y mutables, siendo los muy mutables muy seguros de usar en un ámbito muy local (ej .: local a una función), mientras que los inmutables pueden evitar el lado externo. efectúa directamente y convierte todos los cambios en una estructura de datos en una operación atómica que produce una nueva versión sin riesgo de condiciones de carrera.

ChrisF
fuente
11

ImmutableJS es realmente bastante eficiente. Si tomamos un ejemplo:

var x = {
    Foo: 1,
    Bar: { Baz: 2 }
    Qux: { AnotherVal: 3 }
}

Si el objeto anterior se vuelve inmutable, entonces modifica el valor de la propiedad 'Baz', lo que obtendría es:

var y = x.setIn('/Bar/Baz', 3);
y !== x; // Different object instance
y.Bar !== x.Bar // As the Baz property was changed, the Bar object is a diff instance
y.Qux === y.Qux // Qux is the same object instance

Esto crea algunas mejoras de rendimiento realmente geniales para modelos de objetos profundos, donde solo necesita copiar tipos de valores en objetos en la ruta a la raíz. Cuanto más grande sea el modelo de objetos y más pequeños sean los cambios que realice, mejor será el rendimiento de la memoria y la CPU de la estructura de datos inmutable, ya que terminan compartiendo muchos objetos.

Como han dicho las otras respuestas, si contrasta esto con tratar de proporcionar las mismas garantías copiando a la defensiva xantes de pasarlo a una función que pueda manipularlo, el rendimiento es significativamente mejor.

Bringer128
fuente
4

En línea recta, el código inmutable tiene la sobrecarga de la creación de objetos, que es más lenta. Sin embargo, hay muchas situaciones en las que el código mutable se vuelve muy difícil de administrar de manera eficiente (lo que resulta en una gran cantidad de copias defensivas, lo que también es costoso), y hay muchas estrategias inteligentes para mitigar el costo de 'copiar' un objeto , como lo mencionaron otros.

Si tiene un objeto como un contador, y se incrementa muchas veces por segundo, hacer que ese contador sea inmutable podría no valer la pena de rendimiento. Si tiene un objeto que está siendo leído por muchas partes diferentes de su aplicación, y cada uno de ellos quiere tener su propio clon ligeramente diferente del objeto, será mucho más fácil organizarlo de manera eficiente utilizando un buen Implementación de objetos inmutables.

Perros
fuente
4

Para agregar a esta pregunta (ya excelentemente respondida):

La respuesta corta es ; afectará el rendimiento porque solo está creando objetos en lugar de mutar los existentes, lo que resulta en una mayor sobrecarga de creación de objetos.


Sin embargo, la respuesta larga no es realmente .

Desde un punto de vista de tiempo de ejecución real, en JavaScript ya crea una gran cantidad de objetos de tiempo de ejecución: las funciones y los literales de objetos están en todas partes en JavaScript y nadie parece pensar dos veces antes de usarlos. Yo diría que la creación de objetos es bastante barata, aunque no tengo citas para esto, así que no la usaría como un argumento independiente.

Para mí, el mayor aumento de "rendimiento" no está en el rendimiento del tiempo de ejecución sino en el rendimiento del desarrollador . Una de las primeras cosas que aprendí mientras trabajaba en aplicaciones de Real World (tm) es que la mutabilidad es realmente peligrosa y confusa. ¡Perdí muchas horas persiguiendo un hilo (no el tipo de concurrencia) de ejecución tratando de descubrir qué está causando un error oscuro cuando resulta ser una mutación del otro lado de la maldita aplicación!

Usar la inmutabilidad hace que las cosas sean mucho más fáciles de razonar. Puede saber de inmediato que el objeto X no va a cambiar durante su vida útil, y la única forma de que cambie es clonarlo. Valoro esto mucho más (especialmente en entornos de equipo) que cualquier micro optimización que pueda traer la mutabilidad.

Hay excepciones, sobre todo estructuras de datos como se señaló anteriormente. Raramente me he encontrado con un escenario en el que he querido alterar un mapa después de la creación (aunque es cierto que estoy hablando de mapas de pseudoobjetos literales en lugar de mapas ES6), lo mismo para las matrices. Cuando se trata de estructuras de datos más grandes, la mutabilidad puede dar sus frutos. Recuerde que cada objeto en JavaScript se pasa como una referencia en lugar de un valor.


Dicho esto, un punto mencionado anteriormente fue el GC y su incapacidad para detectar duplicaciones. Esta es una preocupación legítima, pero en mi opinión es solo una preocupación cuando la memoria es una preocupación, y hay formas mucho más fáciles de codificarse en una esquina, por ejemplo, referencias circulares en los cierres.


En última instancia, preferiría tener una base de código inmutable con muy pocas (o ninguna) secciones mutables y tener un rendimiento ligeramente menor que tener mutabilidad en todas partes. Siempre puede optimizar más adelante si la inmutabilidad, por alguna razón, se convierte en una preocupación por el rendimiento.

Dan Pantry
fuente