---

Março de 2017

Volume 32 - Número 3

.NET Framework - Coleções imutáveis

Por Hadi Brais | Março de 2017

Os efeitos colaterais comprometem a compreensibilidade e a correção do código. Um método que modifica variáveis globais ou estáticas tem efeitos colaterais. Um método que modifica alguns desses parâmetros tem efeitos colaterais. Se você quiser entender um pedaço de código, terá que percorrer o código de todos os métodos chamados e que têm efeitos colaterais. Os métodos com efeitos colaterais exigem sincronização de thread para execução correta quando há vários threads.

E se você escrevesse métodos sem efeitos colaterais? Quais seriam a aparência e o desempenho do código? Você pode descobrir gerando instâncias imutáveis, de modo que não possa haver efeitos colaterais.

Em geral, quando uma instância de um tipo é descrita como imutável, significa que seu valor nunca muda. Imutabilidade, como muitas coisas em engenharia de software, é uma opção de design. Seu uso não é, de fato, obrigatório, mas, em alguns cenários, você pode se beneficiar com ela em termos de desempenho ou compreensibilidade de códigos. Na verdade, frequentemente é útil que ela seja um dos princípios fundamentais do paradigma de programação funcional bem sucedido. Considerando que F# é uma linguagem functional-first, todas as instâncias são imutáveis, a menos que claramente especificado de outra forma. Por outro lado, C# é uma linguagem ***first orientada a objetos na qual todas as instâncias são mutáveis, a menos que claramente especificado de outra forma. Neste artigo, mostrarei como aproveitar a imutabilidade em C#. Primeiramente, vou definir imutabilidade no contexto deste artigo.

Definição de imutabilidade

Tecnicamente, há muitos tipos de imutabilidade. Qualquer um que, de algum modo, restrinja alterações no seu estado ou no estado de suas instâncias, pode ser descrito como imutável de alguma forma. O tipo System.String é imutável considerando-se que o tamanho da cadeia de caracteres, os caracteres e sua ordem não podem mudar. O tipo System.MulticastDelegate, que é o pai de todos os tipos delegados, é imutável tal como System.String. Ambos usam uma matriz como estrutura de dados subjacente e a copiam para atender a uma mudança solicitada, por menor que seja. Para obter mais informações sobre os tipos de imutabilidade, consulte o artigo em bit.ly/2kGVx4Z.

System.Collections.ObjectModel.ReadOnlyCollection<T> não é imutável, mas implementa uma interface imutável para um determinado objeto mutável IList<T>. Essa interface não permite que o consumidor mude o úmero de itens da coleção ou sua ordem relativa. No entanto, ela não diz nada sobre a imutabilidade dos itens individuais, que depende de toda a hierarquia de tipos de T. Naturalmente, o código com uma referência à lista subjacente pode alterá-la sem restrições.

As coleções imutáveis discutidas neste artigo oferecem também um outro tipo de imutabilidade. Para reforçar a necessidade de seu uso, considere este exemplo:

Um editor de texto clássico oferece vários recursos ou ferramentas (como corretor ortográfico ou análise de código) que analisam ou processam um texto escrito pelo usuário. Com a prevalência de computadores multicore, essas ferramentas podem ser executadas em segundo plano enquanto o usuário digita. Se você não tiver cuidado, pode enfrentar problemas de segurança de threads. O analisador que atua em segundo plano lê o buffer que contém o texto ao mesmo tempo que o usuário o modifica. Agora, imagine se, em vez de um buffer, o processo em segundo plano obtivesse logicamente um instantâneo do texto.

Como se pode chegar a isso de modo correto e eficiente? O uso correto de um tipo como String resolve o problema, mas não é eficiente. Isso permitiria ao usuário alterar o texto simultaneamente à execução da ferramenta, mas, a cada mudança, seria gerada uma nova cópia do texto, em um processo possivelmente longo e com grande consumo de memória no caso de documentos grandes. Outra solução correta seria o uso de um tipo mutável, como System.Text.StringBuilder. Mas isso também não seria eficiente, pois a ferramenta precisaria fazer uma cópia em um ***acquired ***lock e o usuário não poderia fazer qualquer alteração até a conclusão da cópia. O uso de ReadOnlyCollection<T> também não seria interessante, pois a coleção subjacente é mutável e compartilhada.

Você precisa de outro tipo de imutabilidade, que permita fazer alterações com segurança e sem o uso de mecanismos dispendiosos de sincronização de threads, mantendo o compartilhamento do máximo possível de dados entre threads com pouca ou nenhuma necessidade de cópia. As coleções imutáveis oferecem exatamente esse tipo de imutabilidade, conhecido como persistência. Elas não são úteis apenas no cenário já descrito, mas também em outros, dos tipos multi- e single-threaded, como você verá adiante.

Este artigo traz uma discussão detalhada sobre design, implementação e desempenho de coleções imutáveis, para que você as use e até mesmo grave suas próprias coleções imutáveis e seus tipos com eficácia. Essas coleções podem ser usadas em qualquer plataforma .NET com suporte para .NET Standard 1.0 e versões posteriores (o que significa que você pode usá-las em todas as plataformas Windows, Xamarin e .NET Core). As coleções imutáveis são relativamente novas e distribuídas como pacote NuGet, e não são usadas pelo .NET Framework em si, embora muitas ***APIs de estrutura possam se beneficiar das coleções imutáveis. Em vez disso, tais APIs usam o recurso ReadOnlyCollection<T>, possivelmente não tão interessante, ou uma cópia de uma coleção mutável. Usarei a versão do pacote 1.3.0. O código-fonte está disponível como parte do CoreFX.

Observe que é possível usar código não seguro ou Reflection para quebrar quase todas as garantias de imutabilidade. Em termos gerais, quando um tipo é descrito como imutável, há uma ressalva implícita de que essas técnicas podem contornar todas as garantias de imutabilidade. Isso se aplica às coleções imutáveis discutidas neste artigo.

Definição de coleções imutáveis

Antes de discutir aspectos internos das coleções imutáveis, vamos defini-las. Uma coleção imutável é um conjunto de instâncias que preserva sempre sua estrutura e não permite designações no nível de elementos, embora ofereça APIs para executar mutações. A expressão estrutura de uma coleção refere-se ao número de elementos e sua ordem relativa (determinada por seus índices, no caso de uma estrutura de matriz, e por seus vínculos, no caso de uma estrutura vinculada).

Por exemplo, se você colocar um elemento em uma ImmutableStack<T>, terá duas pilhas imutáveis isoladas: uma com o novo elemento e outra sem ele. Por outro lado, colocar um elemento em uma Stack<T> mutável altera efetivamente a pilha, e você terá apenas uma que contém o novo elemento. Observe que as coleções imutáveis e mutáveis não oferecem garantias sobre os elementos em si. Se T fosse Int32 ou String, os elementos também seriam imutáveis. Mas, se T fosse algo como StringBuilder, os elementos seriam altamente mutáveis.

Para se construir qualquer objeto imutável, ele deve ser inicializado. Assim, durante a inicialização, o objeto é mutável. Uma vez publicada uma referência ao objeto (retornando-o de um método não particular), o objeto se torna efetivamente imutável, para sempre.

As coleções imutáveis são projetadas com duas metas em mente. A primeira é reutilizar o máximo de memória possível, para evitar cópia, e reduzir a pressão sobre o coletor de lixo (essa implementação normalmente é chamada de persistente). A segunda é suportar as mesmas operações oferecidas pelas coleções mutáveis com complexidades de tempo concorrentes.

Pilhas imutáveis

O tipo mutável Stack<T> é implementado usando-se uma matriz. No entanto, as matrizes não são adequadas para as coleções imutáveis, pois o único modo para preservar a instância atual é copiar toda a matriz e executar a alteração nessa nova matriz. Isso tornaria a pilha imutável inaceitavelmente lenta. As listas vinculadas podem ser usadas para implementá-la ***elegantemente. Cada elemento contém um ponteiro que indica o elemento abaixo (ou nulo, no caso do elemento da extremidade inferior). Uma pilha imutável é representada como um ponteiro para o elemento da extremidade superior. Assim, você pode executar push e pop de elementos de determinada pilha sem alterá-la e, ao mesmo tempo, compartilhando todos os seus elementos com a pilha resultante. Esse projeto simples transforma a pilha imutável na coleção imutável mais simples. Mostro adiante as diferenças entre as pilhas mutáveis e imutáveis.

Vejamos como criar e usar pilhas imutáveis. A Immut­ableStack<T> e todas as outras coleções imutáveis são definidas no namespace System.Collections.Immutable. Para maximizar o compartilhamento de memória, as coleções imutáveis não oferecem construtores públicos. Para criar uma instância de uma coleção imutável, você deve usar um dos métodos CreateXxx<T> definidos em um tipo estático correspondente à coleção imutável. No caso da pilha imutável, esse tipo chama-se ImmutableStack e oferece os seguintes métodos de fábrica:

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 os métodos têm um parâmetro T de tipo genérico que especifica o tipo dos itens armazenados na coleção. O primeiro método cria uma pilha imutável vazia, que, internamente, apenas retorna o singleton ImmutableStack<T>.Empty. O segundo método cria uma pilha com o item especificado ali colocado, o que equivale a ImmutableStack<T>.Empty.Push(item). O terceiro e o quarto métodos criam uma pilha com os itens especificados ali colocados em ordem. O método CreateRange<T> é implementado do seguinte modo:

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

Todos os métodos de fábrica para todas as coleções imutáveis são fornecidos para maior comodidade. Todos começam internamente com a coleção vazia e adicionam a ela os itens especificados. Os itens são sempre copiados de forma superficial.

Agora, consideremos esta sequência de operações iniciada com a pilha vazia:

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 os métodos Push e Pop retornam uma referência para a pilha imutável resultante. Ao contrário, os métodos Push e Pop da pilha mutável Stack<T> retornam void e T, respectivamente. Esse design reflete o fato de a alteração de uma pilha imutável resultar, sob o aspecto conceitual, em uma pilha totalmente diferente, e a alteração de uma pilha mutável mudar, na verdade, a pilha. Se a mesma sequência de operações for executada em uma pilha mutável, teremos um resultado final diferente, como mostra a Figura 1. O que torna a pilha imutável é o fato de não haver modo para alterar os ponteiros e valores dos nós.

Figura 1 A mudança em uma pilha imutável resulta em outra pilha, ao contrário do que ocorre com as pilhas mutáveis

Observe que o nó da pilha imutável vazia armazena o valor padrão de T, que é 0 para Int32. Além disso, a pilha mutável apenas define os valores de itens disparados como o valor padrão, em vez de reduzir o tamanho da matriz. A parte desocupada da matriz é chamada de espaço desperdiçado.

Para colocar o item no topo de uma pilha imutável, você pode usar o método Peek ou outra sobrecarga de Push, que tem um parâmetro out pelo qual o item é retornado.

Listas imutáveis

A estrutura de dados de lista é mais complexa do que a pilha, principalmente devido à operação de indexação. A estrutura de lista oferece a recuperação, adição e remoção de itens em um índice especificado. Seria razoável o uso de uma matriz, como ocorre na List<T> mutável, mas, como já foi explicado, isso não seria eficiente para uma lista imutável de uso geral. O uso de uma lista vinculada também não é adequado, pois você pode ***transferir muitos elementos para chegar ao item em um índice específico. Em vez disso, as árvores binárias equilibradas permitem implementar todas as operações com desempenho considerável. Grande parte das coleções imutáveis é implementada usando-se árvores binárias equilibradas. O restante usa listas vinculadas e apenas uma, a matriz imutável, usa matrizes como explicado na próxima seção.

Todos os nós da árvore contêm um item da lista e, por isso, têm um índice. ***O tipo ImmutableList<T> organiza a árvore de modo que uma transversal depth-first, in-order da árvore corresponda a uma transversal da lista in-order do item que está no índice 0 até o último item.

Considere o programa a seguir:

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);

A Figura 2 mostra o que ocorre com a árvore binária subjacente durante a execução da sequência de operações iniciada com a lista imutável vazia. Cada caixa representa um nó na árvore. A caixa que contém a letra E representa o singleton da árvore vazia (as setas que apontam para o vazio devem ser interpretadas com se apontassem para a caixa E). As caixas e setas à direita da figura são imutáveis e as da esquerda são temporariamente mutáveis. Isso é indicado por um sinalizador booliano interno chamado frozen. Esse sinalizador tem duas finalidades, como explicarei a seguir.

Figura 2 Estado interno das árvores (à esquerda) e o estado publicamente acessível resultante após a conclusão das mutações (à direita)

Para adicionar o primeiro item à árvore, é criado um novo nó com ambos os ponteiros indicando o nó vazio. Todos os nós recém-criados começam com o sinalizador frozen definido como false (temporariamente mutável). Nesse ponto, nada mais precisa ser feito e, assim, a árvore é tornada imutável definindo-se o sinalizador frozen como true, como indicado no lado direito da figura. Isso torna a árvore imutável, para sempre.

Para adicionar um segundo item, devido ao modo como a árvore se organiza, seu nó deve ser o filho à direita do primeiro nó. Mas, como esse nó é imutável, não é possível alterar seus ponteiros. O único modo para adicionar o segundo item é não só criar um nó para ele, mas também criar outro nó para o primeiro item. Por isso l2 e l3 apontam para árvores totalmente separadas.

Da mesma forma, o terceiro item deve ser o filho à direita do segundo nó. O único modo para adicioná-lo é criando novos nó para os primeiro e segundo itens. Porém, nesse momento a árvore resultante fica desequilibrada. Isso ocorre quando a diferença entre a altura das subárvores da esquerda e da direita da raiz é no mínimo 2. Para manter o equilíbrio da árvore, você deve reorganizá-la para que ela tenha a forma mostrada no canto inferior direito da Figura 2. Isso pode ser feito porque a árvore ainda é mutável e nenhum código externo ao tipo Immutable­List<T> pode acessá-la ou observar qualquer uma das mutações. Antes que uma referência à árvore seja retornada, ela é congelada definindo-se o sinalizador frozen de dada nó como true, para torná-la imutável. Isso demonstra a primeira finalidade do sinalizador frozen.

A última linha do código chama a função Replace, que encontra o item especificado e o substitui por outro. Nesse caso, é criado um novo código que contém o novo item e os outros nós da mesma árvore são reutilizados na nova árvore.

Devido ao modo como a árvore é organizada, qualquer operação isolada realizada na lista, seja adição, inserção, remoção ou pesquisa, tem uma complexidade de tempo O(log N) em que N é o número de itens atualmente na lista. Ao contrário, as operações na lista mutável List<T> são O(1) (quando puderem ser executadas no local) ou O(N) (quando a matriz subjacente precisar ser copiada).

Você pode executar rapidamente uma operação única em uma lista imutável. Mas, se quiser realizar um grande número M de operações consecutivas, será preciso O(M log N). É mais interessante aproveitar o sinalizador frozen e reunir todas as mutações. Essa otimização é oferecida ***pelos Builders.

Grande parte das coleções imutáveis, inclusive ImmutableList<T>, define tipos chamados de ***construtores, que usam estruturas de dados subjacentes e oferecem as mesmas APIs. A diferença é que um ***construtor não define o sinalizador frozen após cada operação. Ele mantém todos os novos nós criados em estado mutável, para que você possa executar muitas operações com mais eficiência. O tipo de ***construtor para a lista imutável é ImmutableList<T>.Builder.

Para criar uma instância de ***construtor, precisa-se de uma instância de coleção imutável. Você pode começar com uma coleção vazia e usar o método estático ImmutableList.CreateBuilder<T>, ou usar o método de instância ToBuilder em uma determinada coleção imutável. Nesse último caso, todos os nós existentes permanecerão imutáveis, como prometido. Apenas os novos nós será mutáveis. Feitas todas as operações, você pode chamar o método de instância ToImmutable para congelar todos os nós, tornando a coleção imutável. ImmutableList<T> fornece vários métodos de instância, como AddRange e RemoveRange, que referenciam IEnumerable<T> e usam um ***Builder internamente para executar a operação nos itens especificados.

Algumas operações não são beneficiadas com os ***Builders, e seu custo é inerentemente alto. O método de instância Reverse precisa copiar todos os nós que não sejam folhas na árvore para reverter a ordem dos itens. O método de instância Sort é implementado copiando-se todos os itens em uma matriz, classificando a matriz e, em seguida, criando-se a lista imutável com base na matriz classificada.

A lista mutável List<T> usa uma matriz internamente. A inserção ou remoção de itens do meio da matriz requer a criação de uma nova matriz e a cópia de todos os outros itens. Além disso, a alocação de matrizes extremamente grandes talvez não seja possível em um espaço de endereço fragmentado. A LinkedList<T> mutável resolve esses dois problemas. ImmutableList<T> tem as vantagens de ambos os métodos, mas diminui a eficiência de outras operações. ImmutableList<T> é a coleção imutável que corresponde a List<T> e LinkedList<T>. Observe que StringBuilder é, em essência, List<Char>.

Matrizes imutáveis

O tipo ImmutableArray<T>, tal como ImmutableList<T>, implementa uma lista imutável, porém de outro modo. ImmutableArray<T> é apenas um wrapper fino em torno de uma matriz do tipo T[ ]. Ele é “fino” porque é um tipo de valor que contém um único campo do tipo referência. A matriz em si é alocada com base no heap gerenciado. Para executar qualquer operação de mutação, é feita uma cópia de toda a matriz e a operação é realizada ali. Sob esse ponto de vista, ImmutableArray<T> é uma generalização de String, pois pode representar cadeias de caracteres de itens de qualquer tipo, não apenas Char.

Todas as operações de mutação adotam ***tempo O(N) usando Immutable­Array<T>, mas ***tempo O(log N) usando ImmutableList<T>. No entanto, ImmutableArray<T> é superior em três aspectos. O primeiro é que adota ***tempo O(1) para acessar um item devido à sua indexação usando ImmutableArray<T>, e ***tempo O(log N) usando ImmutableList<T>. O segundo é que, embora ambas as implementações ofereçam iteração de tempo linear, ImmutableArray<T> é amigável aos mecanismos de cache, pois todos os itens são armazenados de forma consecutiva. A iteração em uma ImmutableArray<T> pode, muitas vezes, ser mais rápida do que em uma ImmutableList<T>. Por fim, Immutable­Array<T> consome menos memória, pois não usa ponteiros. Em termos gerais, talvez você precise medir para determinar qual deve ser usada em uma situação específica. Ambos os tipos implementam a interface IImmutableList<T>. Você pode usar essa interface em todo o código para alternar facilmente entre os tipos.

Como sempre ocorre, pode-se aprimorar o desempenho e reduzir a pressão sobre a coleta de lixo (GC) executando operações em massa e o pooling dos objetos de ***Builder. Pode-se também usar o método de operação em massa XxxRange ou ImmutableArray<T>.Builder, implementado de modo semelhante à List<T>.

Observe que, como o design padrão dos operadores LINQ funciona em referências de IEnumerable<T>, sua aplicação no tipo de valor ImmutableArray<T> requer boxing. O pacote de coleções imutáveis NuGet inclui uma implementação de alguns operadores LINQ projetados especificamente para ImmutableArray<T>, para evitar boxing. Ele está em System.Linq.ImmutableArrayExtensions.

Dicionários imutáveis

O tipo ImmutableDictionary<TKey, TValue> usa uma árvore binária equilibrada para representar o dicionário. Cada nó da árvore contém um ImmutableList<KeyValuePair<TKey, TValue>> (que também é uma árvore binária equilibrada) que contém todos os itens que fazem hash para o mesmo valor. Por outro lado, o Dictionary<TKey, TValue> mutável usa uma matriz de pares chave-valor com endereçamento aberto para a solução de colisão. Em termos gerais, ImmutableDictionary<TKey, TValue> muitas vezes é mais lento e consome muito mais energia do que Dictionary<TKey, TValue>. O uso do ***construtor de dicionário ajuda pouco, pois a estrutura subjacente não deixa de ser uma árvore formada por outras árvores. Deve-se, sem dúvida, medir o desempenho ao usar ImmutableDictionary<TKey, TValue>, para determinar se ele é ou não aceitável. Se não for, talvez seja preciso escrever seu próprio dicionário imutável personalizado.

Desempenho e consumo de memória das coleções imutáveis

Agora, mesmo que o uso de uma coleção imutável seja basicamente ideal, talvez o desempenho resultante não seja aceitável. Por isso é importante entender como ocorre sua implementação e qual é o seu impacto sobre o desempenho.

Vamos comparar os desempenhos da lista imutável e de sua contraparte mutável. Vemos as complexidades de tempo das operações comuns nas coleções imutáveis em bit.ly/2ko07HS. Esse material não traz informações relevantes; por isso, sejamos um pouco mais práticos. Escrevi três programas que anexam ou precedem 10 milhões de ***inteiros de oito bytes em uma lista mutável e em um ***construtor de lista imutável, respectivamente. A Figura 3 mostra os resultados. (Os números mostrados são aproximados. O tempo está expresso em segundos. A memória, em megabytes. As otimizações JIT estão ativadas. O construtor padrão é usado para criar a lista mutável.)

Figura 3 Consumo de tempo e memória das listas mutáveis, imutáveis e pelas matrizes imutáveis

	Mutáveis	ImmutableList	ILBuilder	ImmutableArray	IABuilder
Anexar	0,2	12	8	Horrível!	0,2
Preceder	Horrível!	13.3	7.4	Horrível!	Horrível!
Tamanho 32 bits	128	320	320	128	128
Tamanho 64 bits	128	480	480	128	128

A anexação a uma lista mutável tem baixo custo por basear-se em uma matriz. Ocasionalmente, o tamanho da matriz é dobrado e, depois disso, a adição de um item é uma operação rápida. Por outro lado, adicionar um item a uma lista imutável é uma operação muito mais dispendiosa, pois baseia-se em uma árvore. Mesmo que se use o ***construtor, a lentidão é cerca de 40 vezes maior. É uma grande diferença. No entanto, esta não é propriamente uma comparação justa. A comparação correta deve ser feita entre listas imutável e mutável que usem sincronização de thread para fornecer semântica de instantâneo similar. Mesmo assim, as coleções imutáveis ficam muito menos atrativas em cenários de threading simples. Embora a complexidade de tempo seja apenas O(log N), o fator constante oculto é bastante grande. Vou explicar o motivo, resumidamente.

A história é totalmente diferente no caso da operação de ***precedência. A conclusão de List<T> demoraria muitas horas, pois ela precisa alocar e copiar 10 milhões de matrizes com curta duração e tamanhos cada vez maiores. A lista imutável e seu ***construtor mantiveram aproximadamente o mesmo desempenho.

A Figura 4 mostra parte do gráfico de alocação de memória gerenciada usando as Ferramentas de Diagnóstico do Visual Studio 2015 durante a anexação de itens a uma lista imutável. Os marcadores na parte superior do gráfico indicam GCs ***registrados de qualquer geração. O gráfico mostra que os GCs ocorrem frequentemente, a cada doze milissegundos aproximadamente. Usei o PerfView para determinar o tempo total gasto na execução de todos esses pequenos GCs. Sem o uso do ***construtor, o tempo de GC é de cerca de quatro segundos. Essa é a diferença entre o uso direto da lista imutável e o uso do construtor. Para determinar se ela se deve ao GCs ou é apenas uma coincidência, eu também usei o PerfView no programa que usa o ***construtor. Fica claro que é, de fato, o caso. Isso pode ser facilmente explicado se observarmos o funcionamento de cada um. A lista imutável cria muitos objetos com curta e média duração, enquanto o ***construtor faz a mutação dos ponteiros de objetos existentes. O uso direto da lista imutável disparou mais de 100 GCs; com o ***construtor e a lista mutável, foram acionados menos de 10.

Figura 4 O GC tem execução muito mais frequente ao anexar itens à lista imutável

O *construtor é muito mais lento do que a lista mutável. Há quatro motivos interligado para isso. Primeiramente, ele usa uma estrutura vinculada que causa muitas perdas de cache. Em segundo lugar, após a anexação de dois itens de qualquer tipo, a árvore fica desequilibrada e exige um processo de rotação para retomar o equilíbrio. O terceiro motivo é que a anexação de um item requer a ***transferência de nós (log N). Por último, sempre que um item é adicionado, ele dispara uma alocação de memória separada para o nó do host.

Isso não significa que o GC seja parte do problema. Ao contrário, o gerenciamento automático de memória facilita muito a escrita e o uso de coleções imutáveis. Ele limpa automaticamente todos os objetos imutáveis que estão fora de uso.

Vamos comparar também as pilhas imutável e mutável. Tal comparação permite quantificar o custo de alocação de objetos e as perdas de cache associadas (que são apenas um pequena parte das perdas de cache totais que podem ocorrer mais tarde) resultantes do uso de estruturas de dados vinculados. A pilha imutável é amigável aos mecanismos de GC, pois só aloca objetos que serão parte da pilha resultante. Ela é tão eficiente que não tem nem mesmo um ***Builder. O push de 10 milhões de inteiros de oito bytes em uma pilha mutável demora cerca de 0,17 segundo; já a mesma operação em uma pilha imutável demora cerca de um segundo. ***Temos um retardamento cerca seis vezes maior, o que não é mau. A iteração em uma pilha imutável grande ou em qualquer estrutura vinculada pode ser muitas vezes mais lenta em comparação àquela verificada na coleção mutável correspondente, devido às perdas de cache e falhas de página (e às transferências em nós NUMA em arquiteturas NUMA, devido ao compartilhamento).

Por outro lado, as coleções mutáveis baseadas em matriz sofrem o problema do desperdício de espaço. Se retirarmos a maioria dos itens de uma coleção de grande porte, a matriz subjacente não será reduzida e continuará ocupando memória desnecessariamente. As coleções imutáveis baseadas em vínculo sempre mantêm um objeto por item. No entanto, a vantagem é mínima no caso de coleções vinculadas, considerando os casos de uso típicos.

Quando usar coleções imutáveis

O benefício fundamental da imutabilidade é que ela facilita significativamente o raciocínio em torno do funcionamento do código, permitindo escrever rapidamente códigos corretos e ***elegantes. Consideremos um programa do tipo single-thread. Em uma determinada linha do código, talvez interesse o estado de uma coleção imutável. É fácil determinar esse dado localizando no código os pontos onde a coleção foi criada. Normalmente há apenas um ou muito poucos locais desse tipo. Continuando neste processo, chegaremos a uma origem mutável ou ***coleção vazia. Não importa se a coleção imutável foi transmitida aos métodos, pois sua estrutura é preservada; você não precisa se preocupar com o que ocorre nesses métodos. Se os itens forem do tipo imutável, você também pode pensar sobre o estado completo da coleção. A facilidade é a mesma em programas do tipo multi-thread, mas a dificuldade aumenta muito quando se usa coleções mutáveis compartilhadas. Por isso, a imutabilidade pode ser um princípio de design geral, como ocorre na programação funcional.

Consideremos a seguinte assinatura de método:

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

Esse método usa um parâmetro de pilha mutável; logo, a pilha pode ser modificada por ele. Essa pode ser, na verdade, a finalidade do método. Mas quando ele modifica a pilha, o estado antigo se perde, a menos que o chamador tenha feito uma cópia. Observe que o método não precisa retornar nada, mesmo que tenha modificado a pilha. Outro ponto sobre essa assinatura é que ela não oferece qualquer garantia de segurança de threads.

Isso não é problema, se a segurança de threads não for uma preocupação e se a expectativa for que o método modifique a pilha e essas modificações forem do seu interesse. Se a finalidade do método for somente ler ou inspecionar a pilha (ou, talvez, modificá-la, mas isso não for importante para o chamador), é possível que essa assinatura seja mais adequada:

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

Temos aqui dois problemas. O primeiro é que ReadOnlyCollection<T> requer a construção de uma List<T>; por isso, o chamador deve copiar a pilha em uma lista. Transformar o parâmetro no tipo de interface IReadOnly­Collection<T> evita esse problema, pois Stack<T> faz a implementação, mas o método pode converter de volta para Stack<T> com a mesma facilidade. O segundo é que, se o método mudar normalmente a pilha, ele deve primeiramente copiá-la em uma coleção mutável. Essa assinatura não oferece qualquer garantia de segurança de threads. Ela só é interessante quando a coleção mutável original for List<T> e o método não fizer alterações.

Em cenários com a possibilidade de vários threads acessando a coleção, essa assinatura pode ser mais adequada:

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

A pilha simultânea é mutável; logo, todos os threads verão todas as mudanças. Isso só é adequado em pelo menos uma das seguintes condições: Espera-se que o método considere as mudanças possivelmente feitas por outros threads logo que ocorram, ou que, da mesma forma, outros threads queiram ver as mudanças feitas pelo método. Observe que qualquer thread pode ver qualquer mudança específica separadamente. Caso contrário, se alguns threads tiverem que ver somente um lote de mudanças, ou nenhuma delas, eles devem obter um bloqueio global e fazer uma cópia particular da pilha. Essas duas situações chamam-se semântica de instantâneo.

Observe como devem ser usados diferentes tipos de coleção em diferentes cenários. Também é interessante uma boa documentação para explicar como o método funciona e como deve ser usado. As coleções imutáveis simplificam tudo. As duas assinaturas a seguir são satisfatórias na maioria dos cenários:

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

Veja a beleza destas APIs. A primeira assinatura é usada quando não há preocupação quando às mudanças feitas pelo método. Se não for esse o caso, pode-se usar a segunda assinatura. Há apenas duas situações em que as coleções imutáveis não são adequadas: taxa de transferência (a taxa na qual os itens são processados) e semântica de ***produtor-consumidor. Como já foi demonstrado, as coleções imutáveis de uso geral têm taxa de transferência inferior, especialmente em cenários de single-thread. Na semântica de ***produtor-consumidor, as coleções mutáveis simultâneas são mais ***elegantes e resultam em melhor desempenho. A diferença entre essa semântica e a de instantâneo está no comportamento dos agentes de leitura ou de consumo. Na primeira, os elementos são consumidos (removidos permanentemente) e, na segunda, são processados e a remoção é feita apenas pelos ***agentes de gravação ou de produção. Eu gostaria me referir à semântica de instantâneo como sendo do tipo ***alterador-processador, pois há agentes de mudança e de processamento. Os agentes de processamento podem fazer alterações, desde que elas sejam mantidas em uma cópia separada, necessária em conjunto com outras. Se essas mudanças precisarem ser globalizadas, entraremos nos domínios da semântica de ***produtor-consumidor.

Interfaces e APIs interessantes

Há muitos métodos de extensão ToXxx que fazem a conversão de extensões mutáveis ou interfaces relacionadas a coleções para coleções imutáveis. Eles copiam a coleção mutável, em vez de reutilizá-la para manter a imutabilidade. Muitas coleções imutáveis oferecem métodos interessantes, como os de classificação e pesquisa, semelhantes aos oferecidos pelas mutáveis. Isso ajuda a combinar códigos que usam ambos os tipos de coleções.

Para que as coleções imutáveis sejam mais facilmente utilizáveis nas bases de códigos existentes, há algumas implementações de interfaces comuns adequadas, como em IEnumerable<T>, IList<T> e ICollection<T>. Alguns dos métodos declarados, como o IList<T>.Insert, se destinam a fazer a mutação da coleção. Eles são implementados por meio de uma NotSupported­Exception. As coleções imutáveis também implementam as interfaces imutáveis correspondentes definidas no pacote NuGet.

O agente System.Collections.Immutable.ImmutableInterlocked type oferece vários métodos que implementam mecanismos de troca ***sincronizada para atualizar corretamente itens em coleções imutáveis ou referências desse tipo. Por exemplo, o método a seguir usa uma referência a um item e a atualiza segundo o transformador especificado:

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

Embora os efeitos de tais operações possam ser observados por todos os threads, ele garante que todos observarão sempre o mesmo item.

Conclusão

Este artigo discutiu os benefícios das coleções imutáveis e abordou detalhadamente o design e a implementação de pilhas, listas, matrizes e dicionários imutáveis. Há muitas outras coleções imutáveis no pacote NuGet. Quase todas as coleções mutáveis têm sua correspondente imutável, que você pode encontrar lá. Espero que todos sejam muito úteis a você no trabalho com seus códigos. Se você gosta do padrão de imutabilidade e quiser escrever seus próprios tipo nesse modelo, Andrew Arnott criou uma ferramenta baseada em Roslyn que torna a escrita de tipos imutáveis e mutáveis igualmente fácil. Veja mais sobre ela em bit.ly/2ko2s5O.

---

Hadi Brais é acadêmico com doutorado do Instituto Indiano de Tecnologia de Délhi e pesquisa otimizações do compilador para sistemas de memória da próxima geração. Ele passa a maior parte do tempo escrevendo código em C/C++/C# e aprofundando-se em tempos de execução, em estruturas de compilador e em arquiteturas do computador. O endereço do seu blog é hadibrais.wordpress.com e seu e-mail é hadi.b@live.com.

---

Agradecemos aos seguintes especialistas técnicos pela revisão deste artigo: Andrew Arnott e Immo Landwerth

---