---

Marzo de 2017

Volumen 32, número 3

.NET Framework: colecciones inmutables

Por Hadi Brais | Marzo de 2017

Los efectos secundarios comprometen la capacidad de comprender y la corrección del código. Un método que muta variables globales o estáticas tiene efectos secundarios. Un método que muta algunos de sus parámetros tiene efectos secundarios. Si quiere comprender un fragmento de código, debe consultar el código de todos los métodos llamados que tienen efectos secundarios. Los métodos con efectos secundarios requieren que la sincronización de subprocesos se ejecute correctamente cuando existen varios subprocesos.

¿Qué sucede si escribe métodos que no tienen efectos secundarios? ¿Qué aspecto tendría el código y cómo funcionaría? Para averiguarlo, haga que las instancias sean inmutables, lo que impedirá que se produzcan efectos secundarios.

En general, que una instancia de un tipo se describa para ser inmut­able, significa que su valor nunca va a cambiar. La inmutabilidad, como muchos aspectos de la ingeniería de software, es una opción de diseño. No tiene que usarla necesariamente, pero en algunos escenarios, puede resultarle útil en términos de rendimiento o capacidad de comprensión del código. De hecho, suele ser útil con tanta frecuencia, que es uno de los principios fundamentales del logrado paradigma de programación funcional. Teniendo en cuenta que F# es un lenguaje ante todo funcional, todas las instancias son inmutables, salvo que se especifique explícitamente de otro modo. Por otro lado, C# es un lenguaje principalmente orientado a objetos, donde todas las instancias son mutables, salvo que se especifique explícitamente de otro modo. En este artículo, le mostraré como aprovechar la inmutabilidad en C#. Primero definiré qué es la inmutabilidad en el contexto de este artículo.

Definición de inmutatibilidad

Técnicamente, existen muchos tipos de inmutabilidad. Cualquier tipo que restrinja de algún modo los cambios en su estado o en el estado de sus instancias se puede describir como inmutable en cierto modo. El tipo System.String es un tipo inmutable en el sentido de que el tamaño de la cadena, los caracteres y su orden no pueden cambiar. El tipo System.MulticastDelegate, que es el primario de todos los tipos delegados, es inmutable igual que System.String. Ambos usan una matriz como estructura de datos subyacente y crean una copia de esta para satisfacer un cambio solicitado, independientemente de cuan insignificante sea. Para obtener más información sobre los tipos de inmutabilidad, consulte el artículo de bit.ly/2kGVx4Z.

System.Collections.ObjectModel.ReadOnlyCollection<T> no es inmutable, pero implementa una interfaz inmutable para un objeto mutable IList<T> determinado. Esta interfaz no permite al consumidor cambiar el número de elementos de la colección ni su orden relativo. No obstante, no dice nada sobre la inmutabilidad de los elementos individuales, que depende de la jerarquía de tipos completa de T. Por supuesto, el código con una referencia a la lista subyacente puede cambiarlo sin restricciones.

Las colecciones inmutables tratadas en este artículo proporcionan otro tipo más de inmutabilidad. Para incitar que sean necesarias, considere el ejemplo siguiente:

Un editor de texto típico proporciona varias características o herramientas (como el corrector ortográfico o el análisis de código), que analizan o procesan texto escrito por el usuario. Con el predominio de equipos de varios núcleos, estas herramientas se pueden ejecutar en segundo plano mientras el usuario escribe. Si no es cauto, podría provocar problemas de seguridad de subprocesos. El analizador en segundo plano lee el búfer que contiene el texto al mismo tiempo que el usuario lo modifica. Ahora, imagine que, en lugar de un búfer, el proceso en segundo plano obtuviera de forma lógica una instantánea del texto.

¿Cómo lo conseguiría de manera correcta y eficaz? El uso de un tipo como String resuelve el problema correctamente, pero no de manera eficaz. Esto permitiría al usuario cambiar el texto mientras se ejecuta la herramienta, pero con cada cambio, se crea una nueva copia del texto, un proceso que puede ser lento y un derroche de memoria en el caso documentos de gran tamaño. Otra solución correcta sería usar un tipo mutable, como System.Text.StringBuilder. No obstante, esto también resulta ineficaz porque la herramienta necesita crear una copia bajo un bloqueo adquirido y el usuario no podría realizar ningún cambio hasta que se realizara la copia. El uso de ReadOnlyCollection<T> tampoco ayudaría, porque la colección subyacente es mutable y compartida.

Necesita un tipo de inmutabilidad diferente que le permita realizar cambios con seguridad sin usar mecanismos de sincronización de subprocesos costosos, y compartir al mismo tiempo el mayor volumen de datos posible entre subprocesos sin exigir ninguna copia o una cantidad mínima. Las colecciones inmutables proporcionan exactamente este tipo de inmutabilidad, que se conoce como persistencia. No solo son útiles en el escenario descrito anteriormente, sino también en otros escenarios multiproceso o uniproceso, como podrá ver más adelante en este artículo.

En este artículo se ofrece una discusión detallada del diseño, la implementación y el rendimiento de las colecciones inmutables, para que pueda usarlas de manera eficaz e incluso escribir sus tipos y colecciones inmutables propios. Estas colecciones pueden usarse en cualquier plataforma .NET que admita .NET Standard 1.0 y versiones posteriores (lo que significa que puede usarlas en todas las plataformas de Windows, Xamarin y .NET Core). Las colecciones inmutables son relativamente nuevas y se distribuyen como un paquete NuGet, de modo que no las use .NET Framework, aunque existen muchas API de marco para las cuales las colecciones inmutables habrían sido beneficiosas. En su lugar, estas API usan la clase ReadOnlyCollection<T>, que puede no resultar tan idónea, o bien una copia de una colección mutable. Yo usaré la versión del paquete 1.3.0. El código fuente está disponible como parte de CoreFX.

Tenga en cuenta la posibilidad de usar código no seguro o Reflexión para cesar prácticamente cualquier garantía de inmutabilidad. En general, cuando un tipo se describe para ser inmutable, existe una advertencia implícita que avisa de que estas técnicas pueden eludir cualquier garantía de inmutabilidad. Esto se aplica a las colecciones inmutables que se tratan en este artículo.

Definición de colecciones inmutables

Antes de tratar los aspectos internos de las colecciones inmutables, debo definirlas. Una colección inmutable es una colección de instancias que mantiene su estructura todo el tiempo y deniega las asignaciones de nivel de elemento, aunque sigue ofreciendo las API para realizar mutaciones. Por la estructura de una colección, me refiero al número de elementos y a su orden relativo (que viene determinado por sus índices en el caso de una estructura de matriz y por sus vínculos en una estructura de vínculo).

Por ejemplo, si inserta un elemento en una clase ImmutableStack<T>, obtendrá dos pilas inmutables aisladas: una con el nuevo elemento y otra sin él. Por otro lado, la inserción de un elemento en una clase Stack<T> mutable cambia efectivamente la pila, y solo tendrá una pila que contendrá el nuevo elemento. Tenga en cuenta que ni las colecciones inmutables ni las mutables ofrecen garantías en relación con los propios elementos. Si T fuera Int32 o String, los elementos también serían inmutables. Sin embargo, si T fuera algo como StringBuilder, los elementos serían muy mutables.

Para poder construir cualquier objeto inmutable, este debe inicializarse. Por lo tanto, durante la inicialización, el objeto es mutable. Después de publicar una referencia al objeto (mediante su devolución desde un método no privado), el objeto se convierte efectivamente en inmutable para toda su duración.

Las colecciones inmutables están diseñadas con dos objetivos. El primero, reutilizar la máxima memoria posible a fin de evitar la copia y de reducir la presión sobre el recolector de elementos no utilizados (este tipo de implementación suele denominarse persistente). El segundo objetivo es admitir las mismas operaciones que ofrecen las colecciones mutables con complejidades de tiempo competitivas.

Pilas inmutables

El tipo mutable Stack<T> se implementa mediante una matriz. Las matrices, sin embargo, no son adecuadas para las colecciones inmutables, porque la única manera de mantener la instancia actual es copiar la matriz completa y realizar el cambio en la nueva matriz. Esto provocaría una lentitud inaceptable de la pila inmutable. Las listas de vínculo se pueden usar de manera elegante para su implementación. Cada elemento contiene un puntero al elemento que tiene debajo (o null para el último elemento). Una pila inmutable se representa como un puntero al primer elemento. De esta manera, puede insertar y sacar elementos de una pila determinada sin cambiarla, al mismo tiempo que comparte todos sus elementos con la pila resultante. Este sencillo diseño convierte la pila inmutable en la colección inmutable más simple. Más adelante en este artículo, muestro las diferencias entre las pilas mutables e inmutables.

Veamos cómo crear y usar las pilas inmutables. La clase Immut­ableStack<T> y todas las demás colecciones inmutables están definidas en el espacio de nombres System.Collections.Immutable. Para maximizar el uso compartido de la memoria, las colecciones inmutables no ofrecen constructores públicos. Para poder crear una instancia de una colección inmutable, debe usar uno de los métodos CreateXxx<T> definidos en un tipo estático que corresponda a la colección inmutable. Para la pila inmut­able, este tipo se denomina ImmutableStack y ofrece los siguientes patrones de diseño Factory Method:

public static ImmutableStack<T> Create<T>();
public static ImmutableStack<T> Create<T>(T item);
public static ImmutableStack<T> Create<T>(params T[] items);
public static ImmutableStack<T> CreateRange<T>(IEnumerable<T> items);

Todos los métodos tienen un parámetro T de tipo genérico, que especifica el tipo de elementos almacenados en la colección. El primer método crea una pila inmutable vacía, que internamente solo devuelve el singleton ImmutableStack<T>.Empty. El segundo método crea una pila con el elemento especificado insertado en ella, lo que equivale a ImmutableStack<T>.Empty.Push(item). Los métodos tercero y cuarto crean una pila con los elementos especificados insertados en ella de manera ordenada. El método CreateRange<T> se implementa de la siguiente manera:

var stack = ImmutableStack<T>.Empty;
foreach (var item in items)
{
  stack = stack.Push(item);
}
return stack;

Todos los patrones de diseño Factory Method de todas las colecciones inmutables se proporcionan por comodidad. Todos ellos se inician internamente con la colección vacía, a la que agregan los elementos especificados. Estos elementos siempre se copian de manera superficial.

Ahora, considere la siguiente secuencia de operaciones, empezando por la pila vacía:

ImmutableStack<Int32> s1 = ImmutableStack<Int32>.Empty;
ImmutableStack<Int32> s2 = s1.Push(1);
ImmutableStack<Int32> s3 = s2.Push(2);
ImmutableStack<Int32> s4 = s3.Push(3);
ImmutableStack<Int32> s5 = s4.Push(4);
ImmutableStack<Int32> s6 = s4.Pop();
ImmutableStack<Int32> s7 = s6.Pop();

Observe que los métodos Push y Pop devuelven una referencia a la pila inmutable resultante. En cambio, los métodos Push y Pop de la pila mutable Stack<T> devuelven void y T, respectivamente. Este diseño refleja el hecho de que la modificación conceptual de una pila inmutable da lugar a una pila completamente diferente, mientras que la modificación de una pila mutable cambia en realidad la pila. Si la misma secuencia de operaciones se realiza en una pila mutable, obtendrá un resultado final distinto, como se muestra en la Figura 1. Lo que hace que la pila inmutable sea inmutable es que no existe ningún método para cambiar los punteros y los valores de los nodos.

Figura 1 Un cambio en una pila inmutable crea una nueva pila a diferencia de una pila mutable

Tenga en cuenta que el nodo de la pila inmutable vacía almacena el valor predeterminado de T, que es 0 para Int32. Asimismo, la pila mutable solo establece los valores de los elementos sacados en el valor predeterminado en lugar de reducir el tamaño de la matriz. La parte no ocupada de la matriz se denomina espacio desperdiciado.

Para obtener el elemento de la parte superior de una pila inmutable, puede usar el método Peek u otra sobrecarga de Push, que tiene un parámetro de salida a través del cual se devuelve el elemento.

Listas inmutables

La estructura de datos de lista es más compleja que la pila, principalmente debido a la operación de indexación. La estructura de lista permite la recuperación, adición y eliminación de elementos en el índice especificado. El uso de una matriz, tal como se realiza en la clase mutable List<T>, sería razonable, pero, como expliqué antes, resultaría ineficiente para una lista inmutable de uso general. El uso de una lista de vínculo tampoco resulta adecuado, ya que existe la posibilidad de tener que cruzar muchos elementos para llegar al elemento en un índice específico. En su lugar, los árboles binarios equilibrados permiten implementar todas las operaciones con un rendimiento respetable. La mayoría de las colecciones inmutables se implementan con árboles binarios equilibrados. El resto usan listas de vínculo y solo una, en concreto la matriz inmutable, usa matrices, como se explica en la siguiente sección.

Cada nodo del árbol contiene un elemento de la lista y, por tanto, tiene un índice. El tipo ImmutableList<T> organiza el árbol, de manera que un cruce seguro en orden y en profundidad del árbol corresponde a un cruce seguro de la lista ordenado desde el elemento en el índice 0 hasta el último elemento.

Considere el siguiente programa:

ImmutableList<Int32> l1 = ImmutableList.Create<Int32>();
ImmutableList<Int32> l2 = l1.Add(1);
ImmutableList<Int32> l3 = l2.Add(2);
ImmutableList<Int32> l4 = l3.Add(3);
ImmutableList<Int32> l5 = l4.Replace(2, 4);

En la Figura 2 se muestra qué sucede en el árbol binario subyacente al ejecutar la secuencia de operaciones empezando por la lista inmutable vacía. Cada cuadro representa un nodo del árbol. El cuadro que contiene la letra E representa el singleton del árbol vacío (las flechas que no apuntan a ninguna parte deben interpretarse como si apuntaran al cuadro E). Los cuadros y las flechas del lado derecho de la figura son inmutables, mientras que los de la izquierda son mutables temporalmente. Esto se indica mediante una marca booleana interna denominada frozen. Esta marca atiende a dos propósitos, que explicaré a continuación.

Figura 2 Estado interno de los árboles (izquierda) y estado públicamente accesible resultante después de completar las mutaciones (derecha)

Para agregar el primer elemento al árbol, se crea un nuevo código con ambos punteros que señalan el nodo vacío. Todos los nodos recién creados comienzan con la marca frozen establecida en false (temporalmente mutable). Llegado este punto, no se tiene que hacer nada más y, por tanto, el árbol se ha hecho inmutable al establecer la marca frozen en true, tal como se indica en el lado derecho de la figura. El árbol se hace inmutable para toda su duración.

Para agregar un segundo elemento, dada la manera en que se organiza el árbol, su nodo debe ser el elemento secundario correcto del primer nodo. No obstante, dado que el nodo es inmutable, no se pueden cambiar sus punteros. La única manera de agregar el segundo elemento es no solo crear un nodo para este, sino también crear otro nodo para el primer elemento. Por eso l2 e l3 apuntarán a árboles totalmente independientes.

De manera similar, el tercer elemento debe ser el elemento secundario correcto del segundo nodo. La única manera de agregarlo es crear nuevos nodos para el primer elemento y el segundo. No obstante, el árbol resultante no está equilibrado esta vez. Esta situación se produce cuando la diferencia entre la altura de los subárboles izquierdo y derecho de la raíz es de 2 como mínimo. Para mantener el árbol equilibrado, se debe reorganizar para convertirlo en el árbol que se muestra en la parte inferior derecha de la Figura 2. Esto se puede llevar a cabo porque el árbol sigue siendo mutable y ningún código fuera del tipo Immutable­List<T> puede acceder a este ni observar ninguna de las mutaciones. Antes de la devolución de una referencia al árbol, se inmoviliza mediante la definición de la marca frozen de cada nodo en true para hacerlo inmutable. Esto demuestra el primer propósito de la marca frozen.

La última línea de código llama a la función Replace, que busca el elemento especificado y lo reemplaza por otro. En este caso, se crea un nuevo nodo que contendrá el nuevo elemento, y los demás nodos del mismo árbol se reutilizan en el nuevo.

Dada la manera en que está organizado el árbol, cualquier operación única en la lista, ya sea de adición, inserción, eliminación o búsqueda tiene una complejidad de tiempo de O(log N), donde N es el número de elementos de la lista. En cambio, las operaciones en la lista mutable List<T> son O(1) (donde la operación se puede realizar in situ) y O(N) (donde se debe copiar la matriz subyacente).

Es posible realizar rápidamente una operación única en una lista inmutable. No obstante, si quiere realizar un número M elevado de operaciones de manera consecutiva, tomará O(M log N). Para hacerlo mejor, aproveche la marca frozen y agrupe todas las mutaciones. Esta optimización la proporciona Builders.

La mayoría de las colecciones inmutables, incluida ImmutableList<T>, definen tipos denominados generadores que usan las mismas estructuras de datos subyacentes y ofrecen las mismas API. La diferencia es que un generador no establece la marca frozen después de cada operación. Mantiene todos los nodos nuevos que se han creado en un estado mutable, para que pueda realizar muchas operaciones de manera más eficiente. El tipo de generador de la lista inmutable es ImmutableList<T>.Builder.

Para crear una instancia de generador, necesita una instancia de colección inmutable. Puede comenzar con una colección vacía y usar el método estático ImmutableList.CreateBuilder<T> o el método de instancia ToBuilder en una colección inmutable determinada. En el último caso, todos los nodos existentes se mantendrán inmutables, según lo prometido. Solo esos nodos nuevos serán mutables. Después de realizar todas las operaciones, puede llamar al método de instancia ToImmutable para inmovilizar todos los nodos y convertir la colección en inmutable de manera eficaz. ImmutableList<T> proporciona varios métodos de instancia, como AddRange y RemoveRange, que toman una referencia a IEnumerable<T> y usan un patrón Builder internamente para realizar la operación en los elementos especificados.

Algunas operaciones no se benefician de Builders y resultan costosas por naturaleza. El método de instancia Reverse debe copiar todos los nodos que no son hojas del árbol para invertir el orden de los elementos. Para implementar el método de instancia Sort se deben copiar todos los elementos en una matriz, ordenar la matriz y, después, crear la lista inmutable de la matriz ordenada.

La lista mutable List<T> usa una matriz internamente. La inserción o eliminación de elementos del centro de la matriz requiere la creación de una nueva matriz y la copia de todos los demás elementos. Asimismo, la asignaciones de matrices extremadamente grandes podría no ser posible en un espacio de direcciones fragmentado. La lista mutable LinkedList<T> resuelve ambos problemas. ImmutableList<T> ofrece las ventajas de ambas opciones, pero disminuye la eficacia de las operaciones. ImmutableList<T> es la colección inmutable que corresponde a List<T> y LinkedList<T>. Tenga en cuenta que StringBuilder es esencialmente List<Char>.

Matrices inmutables

El tipo ImmutableArray<T>, igual que ImmutableList<T>, implementa una lista inmutable, pero de manera diferente. ImmutableArray<T> es solo un contenedor fino alrededor de una matriz de tipo T[ ]. Es "fino" porque es un tipo de valor que contiene un solo campo de tipo de referencia. La propia matriz se asigna desde el montón administrado. Para realizar cualquier operación de mutación, se crea una copia de la matriz completa y la operación se realiza en esta. Desde este punto de vista, ImmutableArray<T> es una generalización de String, ya que puede representar cadenas de elementos de cualquier tipo, no solo Char.

Todas las operaciones de mutación toman el tiempo O(N) con Immutable­Array<T>, pero el tiempo O(log N) con ImmutableList<T>. No obstante, ImmutableArray<T> es superior en tres aspectos. El primero, toma el tiempo O(1) para acceder a un elemento dado su índice con ImmutableArray<T>, mientras se toma el tiempo O(log N) con ImmutableList<T>. El segundo, aunque ambas implementaciones ofrecen una iteración de tiempo lineal, la matriz ImmutableArray<T> es apta para la caché porque todos los elementos se almacenan de manera consecutiva. La iteración sobre una matriz ImmutableArray<T> puede ser muchas veces más rápida que la iteración sobre una lista ImmutableList<T>. Y el tercero, la matriz Immutable­Array<T> consume menos memoria porque no usa punteros. En general, podría tener que realizar una medición para determinar cuál se debe usar en una situación concreta. Ambos tipos implementan la interfaz ImmutableList<T>. Puede usar esta interfaz en su código para cambiar fácilmente entre los tipos.

Como siempre, puede mejorar el rendimiento y reducir la presión de la recolección de elementos no utilizados (GC) mediante la realización de operaciones masivas y la agrupación de los objetos Builder. Puede usar los métodos de las operaciones masivas XxxRange o ImmutableArray<T>.Builder, que se implementa de manera similar a List<T>.

Tenga en cuenta que, dado que el diseño estándar de los operadores LINQ funciona en referencias IEnumerable<T>, aplicarlas en el tipo de valor ImmutableArray<T> requiere la conversión boxing. El paquete NuGet de las colecciones inmutables incluye una implementación de algunos operadores LINQ diseñados específicamente para ImmutableArray<T> a fin de evitar la conversión boxing. Se puede encontrar en System.Linq.ImmutableArrayExtensions.

Diccionarios inmutables

El tipo ImmutableDictionary<TKey, TValue> usa un árbol binario equilibrado para representar el diccionario. Cada nodo del árbol contiene ImmutableList<KeyValuePair<TKey, TValue>> (que también es un árbol binario equilibrado), que contiene todos los elementos que aplican el logaritmo hash al mismo valor. Por otro lado, la clase mutable Dictionary<TKey, TValue> usa una matriz de pares de clave-valor con direccionamiento abierto para la resolución de colisiones. En general, ImmutableDictionary<TKey, TValue> es muchas veces más lento y consume mucha más memoria que Dictionary<TKey, TValue>. El uso del generador de diccionarios solo ayuda un poco, ya que la estructura subyacente sigue siendo un árbol de árboles. Definitivamente, debería medir el rendimiento al usar ImmutableDictionary<TKey, TValue> para determinar si es o no aceptable. Si no lo es, es posible que deba escribir su propio diccionario inmutable personalizado.

Rendimiento y consumo de memoria de las colecciones inmutables

Ahora, aunque el uso de una colección inmutable sea ideal, podría no producir un rendimiento aceptable. Por eso es importante comprender cómo se implementan y su impacto en el rendimiento.

Vamos a comparar el rendimiento de la lista inmutable con el de su equivalente mutable. Puede encontrar las complejidades de tiempo de las operaciones comunes en las colecciones inmutables en bit.ly/2ko07HS. Esto no dice mucho y es mejor obtener un poco más de práctica. He escrito tres programas que simplemente anexan o anteponen 10 millones de enteros de 8 bytes a una lista mutable, una lista inmutable y un generador de listas inmutables, respectivamente. En la Figura 3 se muestran los resultados. (Los números que se muestran son aproximados. El tiempo se indica en segundos. La memoria se indica en megabytes. Las optimizaciones JIT están habilitadas. El constructor predeterminado se usa para crear la lista mutable).

Figura 3 Cantidad de tiempo y memoria que usan las listas mutables, las listas inmutables y las matrices inmutables

	Mutable	ImmutableList	ILBuilder	ImmutableArray	IABuilder
Anexar	0,2	12	8	Horrible	0,2
Anteponer	Horrible	13,3	7,4	Horrible	Horrible
32 bits de tamaño	128	320	320	128	128
64 bits de tamaño	128	480	480	128	128

La opción de anexar a una lista mutable es económica porque se basa en una matriz. La matriz dobla su tamaño ocasionalmente y, después de eso, agregar un elemento es una operación rápida. Por otro lado, agregar un elemento a una lista inmutable resulta mucho más caro porque se basa en un árbol. Incluso si se usa el generador, sigue siendo unas 40 veces más lento. La diferencia es enorme. No obstante, la comparación no es del todo equitativa. Una comparación equitativa sería entre la lista inmutable y una lista mutable que usara la sincronización de subprocesos para proporcionar una semántica de instantáneas similar. Aún así, esto hace que las colecciones inmutables sean mucho menos atractivas en escenarios de subproceso único. Aunque la complejidad de tiempo solo es O(log N), el factor de constante oculta es bastante alto. Explicaré el motivo en breve.

Es una historia totalmente diferente para la operación de anteponer. La ejecución de List<T> tardaría muchas horas en finalizar porque tiene que asignar y copiar 10 millones de matrices de corta duración y de tamaños cada vez mayores. La lista inmutable y su generador mantienen más o menos el mismo rendimiento.

En la Figura 4 se muestra parte del gráfico de asignación de memoria administrada que se genera mediante las herramientas de diagnóstico de Visual Studio 2015 mientras se anexan elementos a una lista inmutable. Los marcadores de la parte superior del gráfico indican GC registradas de cualquier generación. El gráfico muestra que las GC se dan con frecuencia, aproximadamente cada varias decenas de milisegundos. Usé PerfView para determinar la cantidad total de tiempo invertido en crear todas esas pequeñas GC. Sin usar el generador, el tiempo de GC es de 4 segundos aproximadamente. Esta es la diferencia entre el uso de la lista inmutable directamente y el uso del generador. Para determinar si esta diferencia se debe realmente a la GC o si se trata de una mera coincidencia, también usé PerfView en el programa que usa el generador. Resulta que esto es así ciertamente. Esto se puede explicar fácilmente observando cómo funciona cada uno. La lista inmutable crea muchos objectos de corta y media duración, mientras que el generador muta los punteros de objetos existentes. El uso de la lista inmutable directamente desencadenó más de 100 GC, mientras que el uso del generador y la lista mutable desencadenó menos de 10.

Figura 4 La GC se ejecuta con mucha más frecuencia cuando se anexan elementos a la lista inmutable

Por tanto, el generador es mucho más lento que la lista mutable. Esto se debe a cuatro motivos interrelacionados. Primero, usa una estructura de vínculo que provoca muchos errores de caché. Segundo, después de anexar dos elementos cualesquiera, el árbol se desequilibra y requiere una rotación para volver a equilibrarse. Tercero, para anexar un elemento se deben cruzar nodos (log N). Y cuarto, cada vez que se agrega un elemento, este desencadena una asignación de memoria diferente para el nodo de hospedaje.

Esto no significa que la GC forme parte del problema. Por el contrario, la administración de memoria automática lo simplifica enormemente con la escritura y el uso de colecciones inmutables. Limpia automáticamente todos esos objetos inmutables que nadie utiliza.

Vamos a comparar también la pila inmutable con la pila mutable. Esta comparación permite cuantificar el costo de las asignaciones de objetos y sus errores de caché asociados (que solo son una pequeña parte de los errores de caché totales que pueden producirse posteriormente) derivados del uso de estructuras de datos vinculados. La pila inmutable es apta para GC porque solo asigna objetos que formarán parte de la pila resultante. Es tan eficiente que ni tan solo tiene un generador. La inserción de 10 millones de enteros de 8 bytes en una pila mutable tarda unos 0,17 segundos, mientras que esta misma inserción en una pila inmutable tarda 1 segundo aproximadamente. La velocidad es 6 veces inferior, que no está mal. La iteración a través de una pila inmutable de gran tamaño o de cualquier estructura de vínculo puede ser muchas veces más lenta que la iteración a través de la colección mutable correspondiente, lo que se debe principalmente a los errores de caché y los errores de página (y las transferencias entre nodos NUMA en arquitecturas NUMA debido al uso compartido).

Dicho esto, las colecciones mutables basadas en matrices sufren la merma de espacio desperdiciado. Si quita la mayoría de los elementos de una colección de gran tamaño, la matriz subyacente no se reducirá y seguirá ocupando memoria innecesariamente. Las colecciones inmutables basadas en vínculos siempre mantienen un objeto por elemento. No obstante, esto apenas supone una ventaja para las colecciones vinculadas, teniendo en cuenta los casos de uso típicos.

Cuándo usar las colecciones inmutables

La ventaja fundamental de la inmutabilidad es que facilita considerablemente deducir cómo funciona el código, lo que permite escribir código correcto y elegante rápidamente. Considere un programa uniproceso. En una línea de código determinada, podría preguntarse por el estado de una colección inmutable. Puede determinarlo fácilmente mediante la localización de estas ubicaciones en el código donde se creó la colección. Habitualmente, solo existe una de estas ubicaciones. Al continuar con este proceso, obtendrá un origen mutable o vaciará la colección. No importa si la colección inmutable se pasó a métodos para garantizar que se mantuviera su estructura, por lo que no tiene que tener en cuenta qué sucede en esos métodos. Asimismo, si los elementos estaban en un tipo inmutable, podrá deducir el estado general de la colección. Esto es igual de sencillo en los programas uniproceso, pero se complica enormemente al usar colecciones mutables compartidas. Por lo tanto, la inmutabilidad puede ser un principio de diseño general igual que en la programación funcional.

Ahora, tenga en cuenta la signatura de método siguiente:

void Foo<T>(Stack<T> s);

Este método tiene un parámetro de pila mutable, de modo que el método podría modificar la pila. Esta podría ser ciertamente la finalidad del método. No obstante, cuando modifica la pila, el estado antiguo se pierde a menos que el autor de la llamada haya realizado una copia. Tenga en cuenta que el método no tiene que devolver nada, aunque haya modificado la pila. Una cosa más que transmite esta signatura es que no ofrece ninguna garantía se seguridad para subprocesos.

Esto está bien si la seguridad para suprocesos no es una preocupación, y si se prevé que el método modifique la pila y está interesado en estas modificaciones. Si la finalidad del método solo es leer o inspeccionar la pila (o podría modificarla, pero el autor de la llamada nunca se preocupa por las modificaciones), esta signatura podría ser más adecuada:

void Foo<T>(ReadOnlyCollection<T> s);

Existen dos problemas al respecto. Primero, la clase ReadOnlyCollection<T> requiere la construcción de una lista List<T>, de modo que el autor de la llamada debe copiar la pila en una lista. Hacer que el parámetro sea del tipo de interfaz IReadOnly­Collection<T> evita este problema, ya que Stack<T> lo implementa, pero luego el método podría volver a convertirlo en Stack<T> con esta facilidad. Segundo, si el método suele realizar cambios en la pila, debe copiarla primero en una colección mutable. Esta signatura tampoco ofrece ninguna garantía de seguridad para subprocesos. Solo resulta conveniente cuando la colección mutable original es List<T> y el método no la cambia.

En escenarios donde potencialmente hay varios subprocesos que acceden a la colección, esta signatura podría resultar más adecuada:

void Foo<T>(ConcurrentStack<T> s);

La pila concurrente es mutable, de modo que todos los subprocesos verán todos los cambios. Solo es adecuada cuando se da como mínimo una de las dos condiciones siguientes: Está previsto que el método considere los cambios potenciales que otros subprocesos realizan en el preciso instante en que se realizan, o bien otros subprocesos quieran ver los cambios que el método realiza en cuanto los realiza. Tenga en cuenta que cualquier subproceso puede ver cualquier cambio específico por separado. De lo contrario, si algunos subprocesos solo pueden ver un lote de cambios o no pueden ver ninguno, deben adquirir un bloqueo global y crear una copia privada de la pila. Estas dos situaciones se conocen como semántica de instantáneas.

Observe como, en distintos escenarios, se deben usar tipos de colecciones diferentes. Asimismo, una buena documentación podría ser aconsejable para explicar cómo funciona el método o cómo debe usarse. Las colecciones inmutables lo simplifican todo. Las dos signaturas siguientes se ajustan a la mayoría de los escenarios:

void Foo1<T>(ImmutableStack<T> s);
ImmutableStack<T> Foo2<T>(ImmutableStack<T> s);

Observe la belleza de estas API. La primera signatura se usa cuando los cambios que realiza el método no son una preocupación para nadie. De lo contrario, se puede usar la segunda signatura. Solo existen dos situaciones en las que las colecciones inmutables no resultan adecuadas: rendimiento (velocidad a la que se procesan los elementos) y semántica de productor-consumidor. Como se demostró anteriormente, las colecciones inmutables de uso general presentan un rendimiento inferior, especialmente en los escenarios uniproceso. En la semántica de productor-consumidor, las colecciones mutables concurrentes son más elegantes y producen un rendimiento superior. La diferencia entre la semántica de productor-consumidor y la semántica de instantáneas radica en el comportamiento de los agentes de lectura o de consumo. En la primera, los elementos se consumen (se eliminan de manera permanente), mientras que, en la segunda, los elementos se procesan y solo las pueden quitar los agentes de escritura o producción. Me gustaría hacer referencia a la semántica de instantáneas como semántica de cambiador-procesador, ya que existen agentes de cambio y agentes de procesamiento. Los agentes de procesamiento pueden realizar cambios, siempre que estos cambios se mantengan en una copia independiente, que sea necesaria junto con otras copias. Si estos cambios tuvieran que llevarse a cabo de manera global, estaría en el ámbito de la semántica de productor-consumidor.

Interfaces y API prácticas

Existen muchos métodos de extensión ToXxx que realizan la conversión de colecciones mutables o interfaces relacionadas con colecciones a colecciones inmutables. Estos métodos copian la colección mutable, en lugar de reutilizarla para mantener la inmutabilidad. Muchas colecciones inmutables ofrecen métodos prácticos, como los de orden y búsqueda, similares a los que ofrecen las colecciones mutables. Esto favorece la combinación de código que usa ambos tipos de colecciones.

Para que las colecciones inmutables sean más útiles en las bases de código existentes, algunas de ellas implementan interfaces comunes adecuadas, como IEnumerable<T>, IList<T> e ICollection<T>. Algunos de los métodos declarados, como IList<T>.Insert, están destinados a mutar la colección. Para su implementación, se genera una excepción NotSupported­Exception. Las colecciones inmutables también implementan las interfaces inmutables correspondientes que se definen en el paquete NuGet.

El tipo System.Collections.Immutable.ImmutableInterlocked ofrece varios métodos que implementan mecanismos de intercambio entrelazados para actualizar correctamente los elementos de las colecciones inmutables o las referencias a estas. Por ejemplo, el siguiente método toma una referencia a un elemento y lo actualiza de acuerdo con el transformador especificado:

public static bool Update<T>(ref T location, Func<T, T> transformer) where T : class;

Aunque todos los subprocesos pueden observar los efectos de estas operaciones, garantiza que todos ellos observarán siempre el mismo elemento.

Resumen

En este artículo se explican las ventajas de las colecciones inmutables y se ofrece una discusión detallada del diseño y la implementación de las pilas, las listas, las matrices y los diccionarios inmutables. Existen otras muchas colecciones inmutables que se incluyen con el paquete NuGet. Casi todas las colecciones mutables tienen una colección inmutable correspondiente, que puede encontrar allí. Espero que pueda usar de manera eficaz estos tipos en su código. Si le gusta el patrón de inmutabilidad y le gustaría escribir sus propios tipos inmutables, Andrew Arnott escribió una herramienta basada en Roslyn que hace que la escritura de tipos inmutables sea tan fácil como la de los tipos mutables. Encontrará más información en bit.ly/2ko2s5O.

---

Hadi Brais es un investigador doctor en el Instituto Indio de Tecnología de Delhi, donde investiga sobre las optimizaciones de los compiladores para los sistemas de memoria de próxima generación. Dedica la mayor parte de su tiempo a escribir código en C, C++ y C#, y a profundizar en tiempos de ejecución, marcos de compiladores y arquitecturas de equipos. Publica en el blog en hadibrais.wordpress.com y puede ponerse en contacto con él en hadi.b@live.com.

---

Gracias a los siguientes expertos técnicos por revisar este artículo: Andrew Arnott y Immo Landwerth

---