Coleções atuais em 10 minutos

^{Foto de Robert V. Ruggiero}

O tópico não é novo. Mas fazendo a pergunta "o que são coleções simultâneas e quando usá-las?" em uma entrevista ou revisão de código, quase sempre recebo uma resposta que consiste em uma frase: "eles nos protegem completamente das condições da corrida" (o que é impossível mesmo em teoria). Ou: “é como coleções comuns, mas tudo dentro está trancado”, o que também não corresponde exatamente à realidade.

O objetivo deste artigo é decifrar o tópico em 10 minutos. Será útil para conhecer rapidamente algumas sutilezas. Ou para refrescar sua memória antes da entrevista.

Primeiro, examinaremos rapidamente o conteúdo do espaço para nome System.Collections.Concurrent . Em seguida, discutimos as principais diferenças entre coleções concorrentes e clássicas, observe alguns pontos não óbvios. Em conclusão, discutimos possíveis armadilhas e quando vale a pena usar os tipos de coleções.

O que está em System.Collections.Concurrent

O Intellisense diz um pouco:



Vamos discutir brevemente o objetivo de cada classe.

ConcurrentDictionary : uma coleção de uso geral segura para threads, aplicável a uma ampla variedade de cenários.

ConcurrentBag, ConcurrentStack, ConcurrentQueue : coleções para fins especiais. "Especialidade" consiste nos seguintes pontos:

• Falta de API para acessar um elemento arbitrário
• Stack e Queue (como todos sabemos) têm uma determinada ordem de adição e extração de elementos
• ConcurrentBag para cada thread mantém sua própria coleção para adicionar itens. Ao recuperar, ele "rouba" elementos de um fluxo vizinho se a coleção estiver vazia para o fluxo atual

IProducerConsumerCollection - contrato usado pela classe BlockingCollection (veja abaixo). Implementado pelas coleções ConcurrentStack , ConcurrentQueue e ConcurrentBag .

BlockingCollection - usado em cenários quando alguns fluxos preenchem uma coleção, enquanto outros extraem elementos dela. Um exemplo típico é uma fila de tarefas reabastecida. Se a coleção estiver vazia no momento da solicitação do próximo elemento, o leitor entrará no estado de espera do novo elemento (polling). Ao chamar o método CompleteAdding () , podemos indicar que a coleção não será mais reabastecida e, quando a leitura da pesquisa não for realizada. Você pode verificar o status da coleção usando as propriedades IsAddingCompleted ( true se os dados não serão mais adicionados) e IsCompleted ( true se os dados não forem mais adicionados e a coleção estiver vazia).

Particionador, OrderablePartitioner, EnumerablePartitionerOptions - construções básicas para implementar a segmentação de coleções . Usado pelo método Parallel.ForEach para especificar como distribuir itens pelos threads de processamento.

Posteriormente neste artigo, focaremos nas coleções: ConcurrentDictionary e ConcurrentBag / Stack / Queue .

Diferenças entre coleções concorrentes e clássicas

Proteção do estado interno

As coleções clássicas são projetadas com o máximo desempenho em mente; portanto, seus métodos de instância não garantem a segurança do encadeamento.

Por exemplo, dê uma olhada no código fonte do método Dictionary.Add .
Podemos ver as seguintes linhas (o código é simplificado para facilitar a leitura):

if (this._buckets == null) { int prime = HashHelpers.GetPrime(capacity); this._buckets = new int[prime]; this._entries = new Dictionary<TKey, TValue>.Entry[prime]; } 

Como podemos ver, o estado interno do dicionário não está protegido. Ao adicionar itens de vários segmentos, o seguinte cenário é possível:

1. Thread 1 chamado Add , execução interrompida imediatamente após inserir a condição if
2. O segmento 2 chamado Adicionar , inicializou a coleção, adicionou o item
3. O fluxo 1 retornou ao trabalho, reinicializou a coleção, destruindo os dados adicionados pelo fluxo 2.

Ou seja, as coleções clássicas não são adequadas para a gravação de vários fluxos.

A API é tolerante com o estado atual da coleção.

Como sabemos, chaves duplicadas não podem ser adicionadas ao dicionário . Se chamarmos Add duas vezes com a mesma chave, a segunda chamada lançará uma ArgumentException .

Essa proteção é útil em cenários de thread único. Mas com multithreading, não podemos ter certeza do estado atual da coleção. Naturalmente, verificações como as seguintes nos salvam apenas quando nos envolvemos constantemente:

 if (!dictionary.ContainsKey(key)) { dictionary.Add(key, “Hello”); } 

A API baseada em exceção é uma opção ruim e não permitirá um comportamento estável e previsível em cenários com vários threads. Em vez disso, você precisa de uma API que não faça suposições sobre o estado atual da coleção, não gere exceções e deixe uma decisão sobre a admissibilidade de um estado específico para o chamador.

Nas coleções simultâneas, as APIs são criadas no padrão TryXXX . Em vez dos métodos Add , Get e Remove, usamos os métodos TryAdd , TryGetValue e TryRemove . E, se esses métodos retornarem falso , decidimos se essa é uma situação excepcional ou não.

Vale a pena notar que as coleções clássicas agora também têm métodos tolerantes ao estado. Mas nas coleções clássicas, essa API é uma boa adição e, nas coleções simultâneas, é uma obrigação.

API que minimiza as condições de corrida

Considere a operação mais simples de atualização de elemento:

 dictionary[key] += 1; 

Por toda a sua simplicidade, o código executa três ações: obtém o valor da coleção, adiciona 1, escreve o novo valor. Na execução multithread, é possível que o código recupere um valor, execute um incremento e depois apague com segurança o valor que foi gravado por outro thread enquanto o incremento estava em execução.

Para resolver esses problemas, a API de coleções simultâneas contém vários métodos auxiliares. Por exemplo, o método TryUpdate , que usa três parâmetros: a chave, o novo valor e o valor atual esperado. Se o valor na coleção não corresponder ao esperado, a atualização não será executada e o método retornará falso .

Considere outro exemplo. Literalmente, todas as linhas do código a seguir (incluindo Console.WriteLine ) podem causar problemas com a execução multithread:

 if (dictionary.ContainsKey(key)) { dictionary[key] += 1; } else { dictionary.Add(key, 1); } Console.WriteLine(dictionary[key]); 

Adicionar ou atualizar um valor e, em seguida, executar uma operação com o resultado, é uma tarefa bastante típica. Portanto, o dicionário simultâneo possui o método AddOrUpdate , que executa uma sequência de ações em uma chamada e é seguro para threads:

 var result = dictionary.AddOrUpdate(key, 1, (itemKey, itemValue) => itemValue + 1); Console.WriteLine(result); 

Há um ponto que vale a pena conhecer.

A implementação do método AddOrUpdate chama o método TryUpdate descrito acima e passa o valor atual da coleção para ele. Se a atualização falhar (o encadeamento vizinho já alterou o valor), a tentativa será repetida e o delegado de atualização transmitido será chamado novamente com o valor atual atualizado. Ou seja, o delegado da atualização pode ser chamado várias vezes , portanto, não deve conter efeitos colaterais.

Algoritmos livres de bloqueios e bloqueios granulares

A Microsoft fez um ótimo trabalho no desempenho de coleções simultâneas, e não apenas envolveu todas as operações com bloqueios. Estudando a fonte, você pode ver muitos exemplos do uso de bloqueios granulares, o uso de algoritmos competentes em vez de bloqueios, bem como o uso de instruções especiais e primitivas de sincronização mais "leves" que o Monitor .

Quais coleções simultâneas não fornecem

A partir dos exemplos acima, é óbvio que as coleções simultâneas não fornecem proteção completa contra as condições de corrida, e devemos projetar nosso código adequadamente. Mas isso não é tudo, há alguns pontos que vale a pena conhecer.

Polimorfismo com coleções clássicas

Coleções simultâneas, como as clássicas, implementam as interfaces IDictionary , ICollection e IEnumerable . Mas parte da API dessas interfaces não pode ser segura por thread, por definição. Por exemplo, o método Add , que discutimos acima.

Coleções simultâneas implementam esses contratos sem segurança de encadeamento. E para "ocultar" uma API insegura, eles usam uma implementação explícita das interfaces. Vale a pena lembrar quando passamos coleções simultâneas para métodos que recebem entradas, por exemplo, ICollection.

Além disso, coleções simultâneas não cumprem o princípio de substituição de Liskov em relação às coleções clássicas.

Por exemplo, o conteúdo de uma coleção clássica não pode ser modificado durante a iteração , o código a seguir lançará uma InvalidOperationException para a classe List :

 foreach (var element in list) { list.Remove(element); } 

Se falamos de coleções simultâneas, a modificação no momento da enumeração não leva a uma exceção, para que possamos executar leitura e gravação simultânea de diferentes fluxos.

Além disso, coleções simultâneas implementam diferentemente a possibilidade de modificação durante a enumeração. O ConcurrentDictionary simplesmente não realiza nenhuma verificação e não garante o resultado da iteração, e o ConcurrentStack / Queue / Bag bloqueia e cria uma cópia do estado atual, através da qual itera.

Possíveis problemas de desempenho

Mencionamos acima que o ConcurrentBag pode "roubar" elementos de threads vizinhos. Isso pode levar a problemas de desempenho se você escrever e ler no ConcurrentBag a partir de diferentes threads.

Além disso, as coleções simultâneas impõem bloqueios completos ao consultar o estado de toda a coleção ( Count , IsEmpty , GetEnumerator , ToArray etc.) e, portanto, são significativamente mais lentas do que suas contrapartes clássicas.

Conclusão: o uso de coleções concorrentes só vale a pena se forem realmente necessárias, pois essa escolha não é "gratuita".

Quando que tipos de coleções usar

• Scripts de thread único: somente coleções clássicas com o melhor desempenho.
• Registro de vários fluxos: apenas coleções simultâneas que protegem o estado interno e têm uma API adequada para gravação competitiva.
• Leitura de vários threads: sem recomendações definidas. Coleções simultâneas podem criar problemas de desempenho com solicitações intensas de estado para toda a coleção. No entanto, para coleções clássicas, a Microsoft não garante desempenho, mesmo para operações de leitura. Por exemplo, uma implementação interna de uma coleção pode ter propriedades ociosas que são iniciadas ao ler dados e, portanto, é possível destruir o estado interno ao ler a partir de vários encadeamentos. Uma boa opção de média é usar coleções imutáveis .
• E leitura e gravação de vários threads: coleções simultâneas exclusivas, implementando proteção de estado e uma API segura.

Conclusões

Neste artigo, estudamos brevemente as coleções simultâneas, quando usá-las e quais são as especificidades delas. Obviamente, o artigo não esgota o tópico e, com um trabalho sério com coleções multithread, você deve ir mais fundo. A maneira mais fácil de fazer isso é examinar o código fonte das coleções usadas. Isso é informativo e nada complicado, o código é muito, muito legível.