Oi, habrozhiteli! A linguagem C ++ é escolhida quando você precisa criar aplicativos realmente rápidos. E o processamento competitivo de alta qualidade os tornará ainda mais rápidos. Os novos recursos do C ++ 17 permitem que você use todo o poder da programação multithread para resolver facilmente os problemas de processamento gráfico, aprendizado de máquina, etc. Anthony Williams, especialista em processamento competitivo, considera exemplos e descreve tarefas práticas, além de compartilhar segredos que serão úteis para todos os envolvidos. incluindo os desenvolvedores mais experientes.
No livro • Uma visão geral completa dos recursos do C ++ 17. • Controle de lançamento e fluxo. • Sincronização de operações competitivas. • Desenvolvimento de código competitivo. • Depurando aplicativos multithread. O livro é adequado para desenvolvedores de nível médio usando C e C ++. Experiência de programação competitiva não é necessária.
Desenvolvimento de Código Competitivo
8.1 Maneiras de distribuir trabalho entre threads
Imagine que você precisa construir uma casa. Para fazer isso, você terá que cavar um poço de fundação, preencher a própria fundação, erguer paredes, instalar canos e fiação elétrica, etc. Teoricamente, com habilidades suficientes, tudo pode ser feito de forma independente, mas provavelmente levará muito tempo e você precisará mudar de um trabalho para outro. outro. Mas você pode contratar assistentes. Em seguida, será necessário escolher quantos assistentes contratar e decidir o que eles devem ser capazes. Você pode, por exemplo, contratar dois trabalhadores e trabalhar com eles. Então você ainda precisa mudar de um trabalho para outro, mas agora as coisas vão mais rápido, pois haverá mais artistas.
Você pode escolher outra opção - contratar uma equipe de especialistas, como pedreiro, carpinteiro, eletricista e encanador. Cada um deles trabalhará em sua própria especialidade; portanto, até que o encanador tenha uma frente de trabalho, ele ficará ocioso. E, no entanto, as coisas vão mais rápido do que antes, pois há mais trabalhadores e, embora o eletricista conduza a fiação na cozinha, o encanador pode ir ao banheiro. Porém, quando não há trabalho para um especialista específico, é obtido mais tempo de inatividade. No entanto, pode-se notar que, mesmo com o tempo de inatividade em consideração, o trabalho se move mais rapidamente quando especialistas chegam ao trabalho, em vez de uma equipe de trabalhadores. Os especialistas não precisam mudar constantemente as ferramentas e, com certeza, cada um deles executará sua tarefa mais rapidamente do que o trabalhador. Se isso realmente será assim, depende das circunstâncias específicas: tudo é aprendido na prática.
Mesmo se você envolver especialistas, ainda precisará escolher um número diferente de trabalhadores de várias especialidades. Talvez faça sentido contratar, por exemplo, mais pedreiros do que eletricistas. Além disso, a composição da sua equipe e a eficácia geral do seu trabalho podem mudar se você precisar construir várias casas ao mesmo tempo. Mesmo se houver pouco trabalho para um encanador em uma única casa, ao construir várias casas ao mesmo tempo, ela poderá ser utilizada durante todo o dia. Além disso, se você não precisar pagar a especialistas por tempo de inatividade, poderá recrutar uma equipe maior, mesmo que o número de pessoas trabalhando simultaneamente não seja alterado.
Mas pare de falar sobre a construção. O que tudo isso tem a ver com threads? E você pode aplicar considerações semelhantes a eles. Você deve decidir quantos threads usar e quais tarefas eles devem executar. Precisamos de encadeamentos universais que executam o trabalho necessário em um momento específico ou encadeamentos especializados que estão bem adaptados a apenas uma coisa? Ou talvez valha a pena combinar os dois? Essas decisões devem ser tomadas independentemente das razões para paralelizar o programa, e o desempenho e a clareza do código dependem significativamente de quão bem-sucedidos eles são. Portanto, é tão importante imaginar quais opções estão disponíveis para tomar uma decisão competente ao desenvolver a estrutura do aplicativo. Nesta seção, consideraremos vários métodos para distribuir tarefas, começando com a distribuição de dados entre os threads até que qualquer outro trabalho seja concluído.
8.1.1 Distribuição de dados entre threads antes do processamento
Os mais fáceis de paralelizar são algoritmos simples, como std :: for_each, que executam operações em cada elemento de um conjunto de dados. Para paralelizar esse algoritmo, você pode atribuir cada elemento a um dos encadeamentos de processamento. No futuro, ao considerar problemas de desempenho, ficará claro que a melhor opção de distribuição para obter o desempenho ideal depende das características da estrutura de dados.
Ao distribuir dados, o caso mais simples é quando os primeiros N elementos são atribuídos a um fluxo, os próximos N elementos a outro, e assim por diante (Fig. 8.1), mas outros esquemas podem ser usados. Independentemente do método de distribuição de dados, cada thread processa apenas os elementos atribuídos a ele, sem interagir com outros threads até concluir o processamento.
A estrutura deve ser familiar para todos que lidam com programação na Message Passing Interface (MPI,
www.mpi-forum.org ) ou OpenMP (http://www.openmp.org/): a tarefa é dividida em várias tarefas executadas em paralelo, os fluxos de trabalho os executam independentemente um do outro e os resultados são coletados no estágio final das informações. Essa abordagem foi usada no exemplo com a função acumular da seção 2.4: as tarefas paralelas e o estágio de redução são acumulação. Para um algoritmo for_each simples, a etapa final está faltando, pois não há nada a reduzir.
O fato de um mix ser definido como a essência do estágio final desempenha um papel muito importante: uma implementação elementar semelhante à mostrada na Listagem 2.9 executará esse mix como um estágio sequencial final. Mas geralmente esse estágio também é paralelo: a acumulação é uma operação de redução; portanto, o código na Listagem 2.9 pode ser alterado para obter uma chamada recursiva do mesmo código quando, por exemplo, o número de encadeamentos é maior que o número mínimo de elementos processados pelo encadeamento. Você também pode forçar fluxos de trabalho a executar etapas de rollup assim que cada um deles concluir sua tarefa, em vez de iniciar novos threads a cada vez.
Por toda a sua eficácia, essa técnica não é versátil. Às vezes, os dados não podem ser precisamente divididos com antecedência, pois a composição de cada parte é conhecida apenas durante o processamento. Em particular, isso é evidente ao usar algoritmos recursivos como o Quicksort, portanto eles exigem uma abordagem diferente.
8.1.2 Distribuição recursiva de dados
O algoritmo Quicksort possui dois estágios principais: dividir os dados em duas partes - tudo o que chega a um dos elementos (referência) e tudo depois na ordem de classificação final, e classificação recursiva dessas duas metades. É impossível paralelizar isso pela divisão preliminar dos dados, pois é possível determinar em qual "metade" eles se enquadram apenas durante o processamento dos elementos. Se você pretende paralelizar esse algoritmo, precisará usar a própria essência da recursão. Em cada nível de recursão, mais e mais chamadas para a função quick_sort são realizadas, pois é necessário classificar as que são maiores que a referência e as que são menores que ela. Essas chamadas recursivas são independentes uma da outra porque se referem a conjuntos separados de elementos. Por esse motivo, eles são os primeiros candidatos à competitividade. Esta distribuição recursiva é mostrada na Fig. 8.2
Essa implementação já foi atendida no Capítulo 4. Em vez de fazer duas chamadas recursivas para as metades maiores e menores, usamos a função std :: async (), que executa tarefas assíncronas para a metade menor a cada etapa. Devido ao uso de std :: async (), a Biblioteca de Threads C ++ precisou decidir quando iniciar a tarefa em um novo thread e quando - no modo síncrono.
Há uma circunstância importante: ao classificar um grande conjunto de dados, iniciar um novo encadeamento para cada recursão levará a um rápido aumento no número de encadeamentos. Ao examinar problemas de desempenho, será mostrado que muitos threads podem diminuir a velocidade do aplicativo. Além disso, com um grande conjunto de fluxos de dados pode simplesmente não ser suficiente. A própria idéia de dividir a tarefa inteira em um modo tão recursivo parece muito bem-sucedida; você só precisa monitorar cuidadosamente o número de threads. Em casos simples, a função std :: async () lida com isso, mas existem outras opções.
Uma delas é usar a função std :: thread :: hardware_concurrency () para selecionar o número de threads, como foi feito na versão paralela da função acumulate () da Listagem 2.9. Em vez de iniciar um novo encadeamento para cada chamada recursiva, você pode colocar o fragmento a ser classificado em uma pilha segura de encadeamentos, por exemplo, como discutido nos capítulos 6 e 7. Se o encadeamento não tiver nada a fazer ou terminar de processar todos os seus fragmentos ou aguardar o fragmento classificado, ele poderá pegue um fragmento da pilha e classifique-o.
A Listagem 8.1 mostra uma implementação simples dessa tecnologia. Como na maioria dos outros exemplos, ele apenas demonstra a intenção e não é um código pronto para uso prático. Se você usa o compilador C ++ 17 e sua biblioteca suporta, você deve usar os algoritmos paralelos fornecidos pela biblioteca padrão de acordo com as descrições fornecidas no capítulo 10.
Listagem 8.1. Um algoritmo Quicksort paralelo que usa uma pilha de fragmentos aguardando classificação
Aqui, a função parallel_quick_sort
(19) coloca a maior parte das responsabilidades funcionais na classe classificador
(1) , que fornece uma maneira fácil de agrupar a pilha de fragmentos não classificados
(2) e vários encadeamentos
(3) . O trabalho principal é realizado na função do componente do_sort
(9) , que é ocupada pelo particionamento de dados usual
(10) . Dessa vez, em vez de iniciar um novo encadeamento para cada fragmento, ele empurra esse fragmento na pilha (11) e inicia um novo encadeamento apenas se houver um recurso de processador livre (12). Como um fragmento com valores menores que o da referência pode ser processado por outro fluxo, devemos aguardar sua prontidão
(13) . Para que o tempo não seja desperdiçado (caso tenhamos um único thread ou todos os outros threads já estejam ocupados), é feita uma tentativa de processar fragmentos da pilha durante esse período de espera
(14) . A função try_sort_chunk recupera um fragmento da pilha
(7) , classifica-o
(8) e salva os resultados na promessa de promessa para que eles possam receber o fluxo que colocou esse fragmento na pilha
(15) .
Agora, os threads iniciados estão em um loop e tentam classificar fragmentos da pilha
(17) se o sinalizador end_of_data
(16) não estiver definido. Entre as verificações, eles entregam o recurso de computação a outros encadeamentos, para que possam enviar trabalho adicional para a pilha. O trabalho do código em termos de ordem desses encadeamentos depende do destruidor da sua classe classificadora
(4) . Quando todos os dados são classificados, a função do_sort retornará o controle (mesmo mantendo a atividade dos threads de trabalho), o thread principal retornará de parallel_quick_sort
(20) e destruirá o objeto classificador. Ele definirá o sinalizador end_of_data
(5) e aguardará o término do trabalho
(6) .A definição do sinalizador interromperá o loop na função de threads (16).
Com essa abordagem, o problema do número ilimitado de threads inerentes à função spawn_task que lançou o novo thread desaparecerá e a dependência da biblioteca de threads C ++, que seleciona o número de threads para você, como ocorre ao usar std :: async (), desaparecerá. Em vez disso, para impedir a alternância de tarefas com muita frequência, o número de threads é limitado pelo valor retornado pela função std :: thread :: hardware_concurrency (). Mas surge outro problema: gerenciar esses fluxos e trocar dados entre eles complica bastante o código. Além disso, apesar de os threads processarem elementos de dados individuais, todos eles acessam a pilha, adicionando novos fragmentos a ela e levando fragmentos para processamento. Uma concorrência tão intensa pode reduzir o desempenho, mesmo que uma pilha sem bloqueio (portanto, sem bloqueio) seja usada, e as razões para isso serão consideradas em breve.
Essa abordagem é uma versão especial do conjunto de encadeamentos - um conjunto de encadeamentos, cada um dos quais recebe trabalho da lista de trabalhos adiados, o executa e depois passa para a lista para um novo. Alguns problemas em potencial inerentes ao conjunto de encadeamentos (incluindo a concorrência ao acessar a lista de obras) e as formas de resolvê-los são discutidos no Capítulo 9. Ao escalonar o aplicativo criado para que ele seja executado em vários processadores, discutiremos este capítulo um pouco mais adiante (consulte 8.2.1).
Ao distribuir dados antes do processamento e no modo recursivo, presume-se que eles sejam corrigidos com antecedência e que esteja em andamento uma pesquisa para sua distribuição. Mas isso nem sempre acontece: se os dados são criados no modo dinâmico ou provêm de uma fonte externa, essa abordagem não funciona. Nesse caso, pode ser mais razoável distribuir o trabalho de acordo com o tipo de tarefa e não com base nos próprios dados.
8.1.3 Distribuição do trabalho por tipo de tarefa
A distribuição do trabalho entre os segmentos, atribuindo cada um deles (antecipadamente ou recursivamente durante o processamento de dados) diferentes pedaços de dados, em qualquer caso, baseia-se no pressuposto de que os segmentos farão o mesmo trabalho em cada pedaço. Uma distribuição alternativa de trabalho é a especialização de fluxos, onde cada um executa uma tarefa separada, pois encanadores e eletricistas realizam tarefas diferentes na construção de uma casa. Os fluxos podem trabalhar com dados diferentes ou com os mesmos dados, mas, no último caso, eles fazem isso para propósitos diferentes.
Essa divisão peculiar do trabalho surge como resultado da separação de tarefas com a ajuda da concorrência: cada segmento tem uma tarefa separada, que é executada independentemente de outros fluxos. Às vezes, outros encadeamentos podem entregar dados ao fluxo ou produzir eventos aos quais devem responder, mas, em geral, cada fluxo se concentra no desempenho de alta qualidade de uma única tarefa. Esse é um bom design básico, no qual cada parte do código deve ser responsável por uma coisa.
Distribuição do trabalho por tipo de tarefa, a fim de compartilhar responsabilidades
Um aplicativo de thread único precisa lidar com conflitos relacionados ao princípio de responsabilidade única, quando há várias tarefas que devem ser executadas continuamente por um certo tempo, ou o aplicativo deve lidar com o processamento de eventos de entrada em tempo hábil (por exemplo, um usuário pressiona uma tecla ou os dados chegam pela rede) na presença de outras tarefas inacabadas. Em um ambiente de computação de thread único, é necessário criar independentemente o código que executa parte da tarefa A, parte da tarefa B, verifica se a tecla foi pressionada e se não há pacotes de rede e, em seguida, retorna ciclicamente para a próxima parte da tarefa A. Isso complica o código a ser executado tarefas A devido à necessidade de manter seu estado e retornar periodicamente o controle ao loop principal. Se você adicionar muitas tarefas ao ciclo, o trabalho poderá diminuir significativamente e o usuário provavelmente notará uma reação lenta ao pressionamento de teclas. Estou certo de que todos observaram as manifestações extremas de uma situação semelhante em certos aplicativos: você define uma tarefa para o aplicativo e a interface não reage a nada até que seja concluída.
Aqui os fluxos entram no palco. Se você executar cada tarefa em um encadeamento separado, o sistema operacional poderá fazer isso em vez de você. No código da tarefa A, você pode se concentrar em concluir a tarefa sem se preocupar em manter o estado e retornar ao loop principal, ou sobre quanto tempo passará antes que isso aconteça. Ou seja, o sistema operacional salvará automaticamente o estado e passará para a tarefa B ou C no momento certo e, se o sistema no qual o programa será executado tiver vários núcleos ou processadores, será possível executar simultaneamente as tarefas A e B. O código para processar pressionamentos de tecla ou recibos pacotes de rede agora podem ser executados em tempo hábil, e todos se beneficiarão: o usuário receberá uma resposta adequada do programa e você, como desenvolvedor, receberá código simplificado, pois cada fluxo pode ser direcionado executar operações diretamente relacionadas às suas funções, sem misturá-las com o fluxo de controle e a interação do usuário.
Uma imagem ideal está surgindo. Mas tudo pode acontecer dessa maneira? Como sempre, tudo depende das circunstâncias específicas. Se a independência total for respeitada e os fluxos não precisarem trocar dados entre si, é exatamente isso que acontecerá. Infelizmente, uma situação semelhante é observada muito raramente. Freqüentemente, as ações necessárias para o usuário têm a forma de tarefas em segundo plano convenientes e precisam notificar o usuário sobre a tarefa, atualizando a interface do usuário de alguma forma. Ou o usuário pode precisar interromper a tarefa; portanto, a interface do usuário precisará enviar uma mensagem para a tarefa em segundo plano, fazendo com que ela pare de executar. Nos dois casos, é necessário considerar cuidadosamente o design e a sincronização adequada, mas as tarefas executadas permanecerão fragmentadas. O thread da interface do usuário ainda controla essa interface, mas pode ser atribuído para executar uma atualização a pedido de outros threads. O encadeamento que implementa a tarefa em segundo plano ainda se concentra nas operações necessárias para concluí-la; também acontece que um dos encadeamentos em segundo plano permite que a tarefa interrompa o outro encadeamento. Nos dois casos, os fluxos não se importam de onde a solicitação vem, é importante apenas para eles que se destina a eles e está diretamente relacionada às suas responsabilidades.
Existem dois perigos sérios no compartilhamento de responsabilidades entre vários threads. Primeiro, pode acontecer que responsabilidades inadequadas sejam distribuídas. Um sinal disso é o excesso de dados compartilhados pelos fluxos ou o fato de que diferentes fluxos precisam esperar um pelo outro. . . , , , , . , , — , , .
. , , .
, . : , , .
— . , , . , , , .
, 8.1.1, , . , .
, : , . , 20 , 3 . , . , , , , 12 , 24 — . . 20 . . . , , , , 12 . , 12 , . , : , , , , , . 3 12 .
, 9 , . . , , . 25 , — . , , : , 100 , , 1 , 100 , 1 100 . , , . , , , .
, , , , .
8.2. ,
, , . , , . , 16 , .
, — , , ( ), . , : ?
8.2.1. ?
( ) , . , , , . , . , . , , ( ) . , , , .
16- 16 : 16 . , 16 . , , ( ). , 16 , , , 1. (oversubscription).
, , C++11 (Standard Thread Library) std::thread::hardware_concurrency(). .
std::thread::hardware_concurrency() : - , , . , , std::thread::hardware_concurrency(), . std::async() , . .
, , , . — , , . , , , , C++. , std::async(), , , . , . , , std::thread::hardware_concurrency(), . , , , .
, . , , , , .
, — .
»Mais informações sobre o livro podem ser encontradas no
site do editor»
Conteúdo»
Trecho25% —
C++Após o pagamento da versão impressa do livro, um livro eletrônico é enviado por e-mail.