Contêineres e objetos em paralelo

  • Artigo

A PPL (Biblioteca de Padrões de Paralelismo) inclui vários contêineres e objetos que fornecem acesso thread-safe aos elementos.

Um contêiner simultâneo fornece acesso concurrency-safe para as operações mais importantes. Aqui, concurrency-safe significa que os ponteiros ou iteradores são sempre válidos. Não é uma garantia de inicialização do elemento ou de uma ordem de passagem específica. A funcionalidade desses contêineres é semelhante às fornecidas pela Biblioteca Padrão C++. Por exemplo, a classe concurrency::concurrent_vector é semelhante à classe std::vector, exceto pelo fato de que a classe concurrent_vector permite acrescentar elementos paralelamente. Use contêineres simultâneos quando tiver um código paralelo que exija acesso de leitura e gravação ao mesmo contêiner.

Um objeto simultâneo é compartilhado simultaneamente entre os componentes. Um processo que calcula o estado de um objeto simultâneo paralelamente produz o mesmo resultado que outro processo que calcula o mesmo estado serialmente. A classe concurrency::combinable é um exemplo de um tipo de objeto simultâneo. A classe combinable permite que você execute cálculos paralelamente e depois combine esses cálculos em um resultado final. Use objetos simultâneos quando você usaria um mecanismo de sincronização, por exemplo, um mutex, para sincronizar o acesso a uma variável ou recurso compartilhado.

Seções

Este tópico descreve os seguintes contêineres e objetos paralelos detalhadamente.

Contêineres simultâneos:

Objetos simultâneos:

Classe concurrent_vector

A classe concurrency::concurrent_vector é uma classe de contêiner de sequência que, assim como a classe std::vector, permite acessar aleatoriamente os elementos. A classe concurrent_vector permite operações de acesso ao elemento e acréscimo concurrency-safe. As operações de acréscimo não invalidam os ponteiros ou iteradores existentes. As operações de passagem e acesso do iterador também são concurrency-safe. Aqui, concurrency-safe significa que os ponteiros ou iteradores são sempre válidos. Não é uma garantia de inicialização do elemento ou de uma ordem de passagem específica.

Diferenças entre concurrent_vector e vector

A classe concurrent_vector é muito semelhante à classe vector. A complexidade das operações de acréscimo, acesso ao elemento e acesso ao iterador em um objeto concurrent_vector é a mesma de um objeto vector. Os seguintes pontos ilustram onde concurrent_vector é diferente de vector:

  • As operações de acréscimo, acesso ao elemento, acesso ao iterador e passagem do iterador em um objeto concurrent_vector são concurrency-safe.

  • Você pode adicionar elementos somente ao final de um objeto concurrent_vector. A classe concurrent_vector não fornece o método insert.

  • Um objeto concurrent_vector não usa a semântica de transferência de recursos, quando você acrescenta a ele.

  • A classe concurrent_vector não fornece o método erase ou pop_back. Assim como acontece com vector, use o método clear para remover todos os elementos de um objeto concurrent_vector.

  • A classe concurrent_vector não armazena os elementos contiguamente na memória. Portanto, você não pode usar a classe concurrent_vector de todas as maneiras que pode usar uma matriz. Por exemplo, para uma variável chamada v do tipo concurrent_vector, a expressão &v[0]+2 produz um comportamento indefinido.

  • A classe concurrent_vector define os métodos grow_by e grow_to_at_least. Esses métodos são semelhantes ao método resize, exceto pelo fato de que são concurrency-safe.

  • Um objeto concurrent_vector não realoca os elementos quando você acrescenta a ele ou o redimensiona. Isso permite que ponteiros e iteradores existentes permaneçam válidos durante operações simultâneas.

  • O runtime não define uma versão especializada do concurrent_vector para o tipo bool.

Operações concurrency-safe

Todos os métodos que acrescentam ou aumentam o tamanho de um objeto concurrent_vector ou acessam um elemento em um objeto concurrent_vector são concurrency-safe. Aqui, concurrency-safe significa que os ponteiros ou iteradores são sempre válidos. Não é uma garantia de inicialização do elemento ou de uma ordem de passagem específica. A exceção a essa regra é o método resize.

A tabela a seguir mostra os métodos e operadores comuns concurrent_vector que são concurrency-safe.

at
back
begin
capacity

empty
end
front
grow_by

grow_to_at_least
max_size
operator[]
push_back

rbegin
rend
size

As operações que o runtime fornece para compatibilidade com a Biblioteca Padrão C++, por exemplo, reserve, não são concurrency-safe. A tabela a seguir mostra os métodos e operadores comuns que não são concurrency-safe.

assign
clear

operator=
reserve

resize

shrink_to_fit

As operações que modificam o valor dos elementos existentes não são concurrency-safe. Use um objeto de sincronização, como um objeto reader_writer_lock, para sincronizar operações simultâneas de leitura e gravação com o mesmo elemento de dados. Para obter mais informações sobre objetos de sincronização, confira Estruturas de Dados de Sincronização.

Quando você converte o código existente que usa vector para usar concurrent_vector, as operações simultâneas podem fazer com que o comportamento do aplicativo seja alterado. Por exemplo, considere o programa a seguir que executa simultaneamente duas tarefas em um objeto concurrent_vector. A primeira tarefa acrescenta elementos adicionais a um objeto concurrent_vector. A segunda tarefa calcula a soma de todos os elementos no mesmo objeto.

// parallel-vector-sum.cpp
// compile with: /EHsc
#include <ppl.h>
#include <concurrent_vector.h>
#include <iostream>

using namespace concurrency;
using namespace std;

int wmain()
{
   // Create a concurrent_vector object that contains a few
   // initial elements.
   concurrent_vector<int> v;
   v.push_back(2);
   v.push_back(3);
   v.push_back(4);
   
   // Perform two tasks in parallel.
   // The first task appends additional elements to the concurrent_vector object.
   // The second task computes the sum of all elements in the same object.

   parallel_invoke(
      [&v] { 
         for(int i = 0; i < 10000; ++i)
         {
            v.push_back(i);
         }
      },
      [&v] {
         combinable<int> sums;
         for(auto i = begin(v); i != end(v); ++i) 
         {
            sums.local() += *i;
         }     
         wcout << L"sum = " << sums.combine(plus<int>()) << endl;
      }
   );
}

Embora o método end seja concurrency-safe, uma chamada simultânea ao método push_back faz com que o valor retornado por end seja alterado. O número de elementos que o iterador passa é indeterminado. Portanto, esse programa pode produzir um resultado diferente cada vez que é executado. Quando o tipo de elemento não é trivial, é possível que uma condição de corrida exista entre chamadas a push_back e end. O método end pode retornar um elemento alocado, mas não totalmente inicializado.

Segurança de Exceção

Se uma operação de crescimento ou atribuição gerar uma exceção, o estado do objeto concurrent_vector se tornará inválido. O comportamento de um objeto concurrent_vector que está em um estado inválido é indefinido, a menos que indicado de outra forma. No entanto, o destruidor sempre libera a memória alocada pelo objeto, mesmo que o objeto esteja em um estado inválido.

O tipo de dados dos elementos vector, T, deve atender aos requisitos a seguir. Caso contrário, o comportamento da classe concurrent_vector será indefinido.

  • O destruidor não deve ser gerado.

  • Se o construtor padrão ou de cópia for gerado, o destruidor não deve ser declarado usando a palavra-chave virtual e deve funcionar corretamente com a memória inicializada em zero.

[Parte superior]

Classe concurrent_queue

A classe concurrency::concurrent_queue, assim como a classe std::queue, permite acessar os elementos front e back. A classe concurrent_queue habilita operações de enfileiramento e remoção da fila concurrency-safe. Aqui, concurrency-safe significa que os ponteiros ou iteradores são sempre válidos. Não é uma garantia de inicialização do elemento ou de uma ordem de passagem específica. A classe concurrent_queue também fornece suporte ao iterador que não é concurrency-safe.

Diferenças entre concurrent_queue e queue

A classe concurrent_queue é muito semelhante à classe queue. Os seguintes pontos ilustram onde concurrent_queue é diferente de queue:

  • As operações de enfileiramento e remoção da fila em um objeto concurrent_queue são concurrency-safe.

  • A classe concurrent_queue fornece suporte ao iterador que não é concurrency-safe.

  • A classe concurrent_queue não fornece o método front ou pop. A classe concurrent_queue substitui esses métodos, definindo o método try_pop.

  • A classe concurrent_queue não fornece o método back. Portanto, você não pode referenciar o fim da fila.

  • A classe concurrent_queue fornece o método unsafe_size, em vez do método size. O método unsafe_size não é concurrency-safe.

Operações concurrency-safe

Todos os métodos de enfileiramento ou remoção da fila de um objeto concurrent_queue são concurrency-safe. Aqui, concurrency-safe significa que os ponteiros ou iteradores são sempre válidos. Não é uma garantia de inicialização do elemento ou de uma ordem de passagem específica.

A tabela a seguir mostra os métodos e operadores comuns concurrent_queue que são concurrency-safe.

empty

get_allocator

push

try_pop

Embora o método empty seja concurrency-safe, uma operação simultânea pode fazer com que a fila aumente ou diminua antes que o método empty retorne.

A tabela a seguir mostra os métodos e operadores comuns que não são concurrency-safe.

clear

unsafe_begin

unsafe_end

unsafe_size

Suporte ao Iterador

O concurrent_queue fornece iteradores que não são concurrency-safe. Recomendamos que você use esses iteradores somente para depuração.

Um iterador concurrent_queue passa os elementos apenas na direção para frente. A tabela a seguir mostra os operadores aos quais cada iterador dá suporte.

Operador Descrição
operator++ Avança para o próximo item na fila. Esse operador é sobrecarregado para fornecer as semântica de pré-incremento e pós-incremento.
operator* Recupera uma referência ao item atual.
operator-> Recupera um ponteiro para o item atual.

[Parte superior]

Classe concurrent_unordered_map

A classe concurrency::concurrent_unordered_map é uma classe de contêiner associativa que, assim como a classe std::unordered_map, controla uma sequência de tamanho variado de elementos do tipo std::p air<const Key, Ty>. Pense em um mapa não ordenado como um dicionário para o qual você pode adicionar um par de chave e valor ou pesquisar um valor por chave. Essa classe é útil quando você tem vários threads ou tarefas que precisam acessar simultaneamente um contêiner compartilhado, inserir nele ou atualizá-lo.

O exemplo a seguir mostra a estrutura básica para usar concurrent_unordered_map. Este exemplo insere chaves de caractere no intervalo ['a', 'i']. Como a ordem das operações é indeterminada, o valor final de cada chave também é indeterminado. No entanto, é seguro executar as inserções paralelamente.

// unordered-map-structure.cpp
// compile with: /EHsc
#include <ppl.h>
#include <concurrent_unordered_map.h>
#include <iostream>

using namespace concurrency;
using namespace std;

int wmain() 
{
    //
    // Insert a number of items into the map in parallel.

    concurrent_unordered_map<char, int> map; 

    parallel_for(0, 1000, [&map](int i) {
        char key = 'a' + (i%9); // Geneate a key in the range [a,i].
        int value = i;          // Set the value to i.
        map.insert(make_pair(key, value));
    });

    // Print the elements in the map.
    for_each(begin(map), end(map), [](const pair<char, int>& pr) {
        wcout << L"[" << pr.first << L", " << pr.second << L"] ";
    });
}
/* Sample output:
    [e, 751] [i, 755] [a, 756] [c, 758] [g, 753] [f, 752] [b, 757] [d, 750] [h, 754]
*/

Para obter outro exemplo que usa concurrent_unordered_map para executar uma operação de mapeamento e redução paralelamente, confira Instruções: executar operações de mapeamento e redução paralelamente.

Diferenças entre concurrent_unordered_map e unordered_map

A classe concurrent_unordered_map é muito semelhante à classe unordered_map. Os seguintes pontos ilustram onde concurrent_unordered_map é diferente de unordered_map:

  • Os métodos erase, bucket, bucket_count e bucket_size são chamados de unsafe_erase, unsafe_bucket, unsafe_bucket_count e unsafe_bucket_size, respectivamente. A convenção de nomenclatura unsafe_ indica que esses métodos não são concurrency-safe. Para obter mais informações sobre concurrency-safe, confira Operações concurrency-safe.

  • As operações de inserção não invalidam os ponteiros ou iteradores existentes, nem alteram a ordem dos itens que já existem no mapa. As operações de inserção e passagem podem ocorrer simultaneamente.

  • concurrent_unordered_map dá suporte somente à iteração para frente.

  • A inserção não invalida nem atualiza os iteradores retornados por equal_range. A inserção pode acrescentar itens desiguais ao final do intervalo. O iterador inicial aponta para um item igual.

Para ajudar a evitar deadlock, nenhum método de concurrent_unordered_map mantém um bloqueio quando chama o alocador de memória, as funções de hash ou outro código definido pelo usuário. Além disso, você deve garantir que a função de hash sempre avalie chaves iguais ao mesmo valor. As melhores funções de hash distribuem as chaves uniformemente no espaço de código de hash.

Operações concurrency-safe

A classe concurrent_unordered_map permite operações de acesso ao elemento e inserção concurrency-safe. As operações de inserção não invalidam os ponteiros ou iteradores existentes. As operações de passagem e acesso do iterador também são concurrency-safe. Aqui, concurrency-safe significa que os ponteiros ou iteradores são sempre válidos. Não é uma garantia de inicialização do elemento ou de uma ordem de passagem específica. A tabela a seguir mostra os métodos e operadores concurrent_unordered_map usados normalmente que são concurrency-safe.

at
begin
cbegin
cend

count
empty
end
equal_range

find
get_allocator
hash_function
insert

key_eq
max_size
operator[]
size

Embora o método count possa ser chamado com segurança a partir de threads executados simultaneamente, threads diferentes podem receber resultados diferentes se um novo valor for inserido simultaneamente no contêiner.

A tabela a seguir mostra os métodos e operadores usados normalmente que não são concurrency-safe.

clear
load_factor

max_load_factor

operator=

rehash

Além desses métodos, qualquer método que comece com unsafe_ também não é concurrency-safe.

[Parte superior]

Classe concurrent_unordered_multimap

A classe concurrency::concurrent_unordered_multimap é muito semelhante à classe concurrent_unordered_map, exceto pelo fato de permitir que vários valores sejam mapeados para a mesma chave. Ela também é diferente de concurrent_unordered_map nestes aspectos:

  • O método concurrent_unordered_multimap::insert retorna um iterador, em vez de std::pair<iterator, bool>.

  • A classe concurrent_unordered_multimap não fornece o método operator[] nem at.

O exemplo a seguir mostra a estrutura básica para usar concurrent_unordered_multimap. Este exemplo insere chaves de caractere no intervalo ['a', 'i']. concurrent_unordered_multimap permite que uma chave tenha vários valores.

// unordered-multimap-structure.cpp
// compile with: /EHsc
#include <ppl.h>
#include <concurrent_unordered_map.h>
#include <iostream>

using namespace concurrency;
using namespace std;

int wmain() 
{
    //
    // Insert a number of items into the map in parallel.

    concurrent_unordered_multimap<char, int> map; 

    parallel_for(0, 10, [&map](int i) {
        char key = 'a' + (i%9); // Geneate a key in the range [a,i].
        int value = i;          // Set the value to i.
        map.insert(make_pair(key, value));
    });

    // Print the elements in the map.
    for_each(begin(map), end(map), [](const pair<char, int>& pr) {
        wcout << L"[" << pr.first << L", " << pr.second << L"] ";
    });
}
/* Sample output:
    [e, 4] [i, 8] [a, 9] [a, 0] [c, 2] [g, 6] [f, 5] [b, 1] [d, 3] [h, 7]
*/

[Parte superior]

Classe concurrent_unordered_set

A classe concurrency::concurrent_unordered_set é muito semelhante à classe concurrent_unordered_map, exceto pelo fato de gerenciar valores, em vez de pares de chave e valor. A classe concurrent_unordered_set não fornece o método operator[] nem at.

O exemplo a seguir mostra a estrutura básica para usar concurrent_unordered_set. Este exemplo insere valores de caractere no intervalo ['a', 'i']. É seguro executar as inserções paralelamente.

// unordered-set-structure.cpp
// compile with: /EHsc
#include <ppl.h>
#include <concurrent_unordered_set.h>
#include <iostream>

using namespace concurrency;
using namespace std;

int wmain() 
{
    //
    // Insert a number of items into the set in parallel.

    concurrent_unordered_set<char> set; 

    parallel_for(0, 10000, [&set](int i) {
        set.insert('a' + (i%9)); // Geneate a value in the range [a,i].
    });

    // Print the elements in the set.
    for_each(begin(set), end(set), [](char c) {
        wcout << L"[" << c << L"] ";
    });
}
/* Sample output:
    [e] [i] [a] [c] [g] [f] [b] [d] [h]
*/

[Parte superior]

Classe concurrent_unordered_multiset

A classe concurrency::concurrent_unordered_multiset é muito semelhante à classe concurrent_unordered_set, exceto pelo fato de permitir valores duplicados. Ela também é diferente de concurrent_unordered_set nestes aspectos:

  • O método concurrent_unordered_multiset::insert retorna um iterador, em vez de std::pair<iterator, bool>.

  • A classe concurrent_unordered_multiset não fornece o método operator[] nem at.

O exemplo a seguir mostra a estrutura básica para usar concurrent_unordered_multiset. Este exemplo insere valores de caractere no intervalo ['a', 'i']. concurrent_unordered_multiset permite que um valor ocorra várias vezes.

// unordered-set-structure.cpp
// compile with: /EHsc
#include <ppl.h>
#include <concurrent_unordered_set.h>
#include <iostream>

using namespace concurrency;
using namespace std;

int wmain() 
{
    //
    // Insert a number of items into the set in parallel.

    concurrent_unordered_multiset<char> set; 

    parallel_for(0, 40, [&set](int i) {
        set.insert('a' + (i%9)); // Geneate a value in the range [a,i].
    });

    // Print the elements in the set.
    for_each(begin(set), end(set), [](char c) {
        wcout << L"[" << c << L"] ";
    });
}
/* Sample output:
    [e] [e] [e] [e] [i] [i] [i] [i] [a] [a] [a] [a] [a] [c] [c] [c] [c] [c] [g] [g]
    [g] [g] [f] [f] [f] [f] [b] [b] [b] [b] [b] [d] [d] [d] [d] [d] [h] [h] [h] [h]
*/

[Parte superior]

Classe combinable

A classe concurrency::combinablefornece armazenamento thread-local reutilizável que permite executar cálculos refinados e mesclar esses cálculos em um resultado final. É possível pensar em um objeto combinable como uma variável de redução.

A classe combinable é útil quando você tem um recurso compartilhado entre vários threads ou tarefas. A classe combinable ajuda você a eliminar o estado compartilhado, fornecendo acesso aos recursos compartilhados de uma maneira livre de bloqueios. Portanto, essa classe fornece uma alternativa ao uso de um mecanismo de sincronização, por exemplo, um mutex, para sincronizar o acesso aos dados compartilhados a partir de vários threads.

Métodos e Recursos

A tabela a seguir mostra alguns dos métodos importantes da classe combinable. Para obter mais informações sobre os métodos de classe combinable, confira Classe combinable.

Método Descrição
local Recupera uma referência à variável local associada ao contexto de thread atual.
clear Remove todas as variáveis thread-local do objeto combinable.
combine

combine_each		 Usa a função de combinação fornecida para gerar um valor final a partir do conjunto de todos os cálculos thread-local.

A classe combinable é uma classe de modelo parametrizada no resultado mesclado final. Se você chamar o construtor padrão, o tipo de parâmetro de modelo T deve ter um construtor padrão e um construtor de cópia. Se o tipo de parâmetro de modelo T não tiver um construtor padrão, chame a versão sobrecarregada do construtor que usa uma função de inicialização como parâmetro.

Você pode armazenar dados adicionais em um objeto combinable, depois de chamar os métodos combine ou combine_each. Você também pode chamar os métodos e combine os combine_each métodos várias vezes. Se nenhum valor local em um objeto combinable for alterado, os métodos combine e combine_each produzirão o mesmo resultado sempre que forem chamados.

Exemplos

Para obter exemplos sobre como usar a classe combinable, confira os tópicos a seguir:

[Parte superior]

Como usar contêineres em paralelo para aumentar a eficiência
Mostra como usar contêineres paralelos para armazenar e acessar dados paralelamente com eficiência.

Como usar combinável para melhorar o desempenho
Mostra como usar a classe combinable para eliminar o estado compartilhado e, assim, melhorar o desempenho.

Como usar combinável para combinar conjuntos
Mostra como usar uma função combine para mesclar conjuntos de dados thread-local.

Biblioteca de padrões paralelos (PPL)
Descreve o PPL, que fornece um modelo de programação imperativo que promove a escalabilidade e a facilidade de uso para o desenvolvimento de aplicativos simultâneos.

Referência

Classe concurrent_vector

Classe concurrent_queue

Classe concurrent_unordered_map

Classe concurrent_unordered_multimap

Classe concurrent_unordered_set

Classe concurrent_unordered_multiset

Classe combinable