Rodrigo Kumpera Weblog

Otimizar um programa paralelo é bem diferente de fazer o mesmo para um programa seqüêncial. O ganhos maiores nem sempre estão em tentar utilizar o mínimo possivel de cpu para cada operação. A seguir vou apresentar uma série de técnicas que visam fazer as várias threads de um sistema serem mais legais umas com as outras. Vou dividir em três categorias essas técnicas: sincronização, estruturas de dados e contenção externa.

Contenção externa
Esta é o primeiro passo para otimizar um sistema, aqui é possivel conseguir ganhos enormes com pouco esforço. Nessa categoria podemos entender pausas para I/O e coleta de lixo (Garbage Collection).

Logging é o melhor exemplo de problemas com muita pausa de I/O, um buffer muito pequeno vai exigir contantes paradas no teu sistema enquanto ocorre o flush para disco, por isso não economize espaço para o tamanho do buffer a ser utilizado. O mesmo é importante que seja feito com qualquer outro buffer compartilhado por todas threads e que tenha um custo alto para ser descarregado.

Outras fontes de pausas comuns são sockets, que podem ser tanto para os clientes (requições HTTP), ou para recursos externos (banco de dados), estas fontes fazem que a thread fique parada até os dados estarem disponíveis. Se o sistema possui poucas threads simultâneas, vai acabar ocioso e rendendo menos do que poderia, caso possua threads em excesso, vai atrapalhar o escalonador do SO e diminuir o rendimento. O número de threads dos vários pools da aplicação precisa ser dimensionado corretamente para maximizar seu throughput.
Por fim temos o garbage collector como vilão, nesse ponto existem duas coisas importantes a serem feitas, configurar a aplicação com uma quantidade de memória suficiente, com um coletor adequado e seus parâmetros afinados. Por exemplo, um sistema com um coletor geracional pode estar fazendo muitas coletas completas porque possui pouca memória disponivel para as gerações mais novas permitirem a maioria dos objetos morrerem.
Em resumo, fazer o ajuste do tamanho do buffer de logging, do tamanho dos thread-pools e quantidade de memória podem trazer resultados significativos para a aplicação com esforço mínimo. A seleção de parâmetros para o garbage colletor é complicada o suficiente para exigir um post próprio, leia a documentação da sua VM para começar.

Sincronização
Sincronização é a parte mais dificil de implementar corretamente, imagine então para otimizar. De fato realmente não existem boas formas de otimizar sincronização, mas sim de ajustar a semântica de um programa de forma a torná-lo mais eficiênte. São o moral equivalente de uma refatoração, alteramos o sistema, mas mantemos a semântica dele.

A primeira, e mais facil, dessas modificações e substituir o uso de blocos sincronizados por variáveis atômicas (vide pacote java.util.concurrent.atomic), elas podem ser usadas muito como contadores e variaveis condicionais no lugar onde antes existia um bloco sincronizado. Uma variavel atômica permite que operações como “comparar e atribuir” e “ler e incrementar” sejam executadas como se estivessem dentro de um bloco sincronizado.

Uma mudança útil é fazer “greedy fetching”. Greedy fetching é mais facil de explicar por um exemplo: suponha que o sistema distribua uma tarefa para cada thread executa a partir de um bloco sincronizado; com greedy fetching cada thread, ao ganhar acesso ao bloco sincronizado, pegaria uma quantidade maior para executar, de forma a não voltar a precisar de mais tarefas por um tempo maior. A função dessa mudança é tentar aumentar o intervalo que uma thread precisa concorrer por um recurso sincronizado.

Uma alteração que é ignorada pela maioria é o uso de outros tipos de locks, como r/w locks e semáforos. Uma primitiva de sincronização read/write permite que o acesso seja em paralelo para todos que vão apenas ler dados. Read/Write locks também permitem que um lado seja beneficiado, o dos que escrevem ou o dos que leêm, este aspecto permite fazer um ajuste fino em qual thread ganha acesso ao recurso.

Por fim vale lembrar, a que provavelmente é a mais dificil das alterações, o refinamento de locks com granulosidade grossa (coarse-grained) para fina (fine-grained). O primeiro problema disso é entender, qual a diferença entre uma e outra. No caso de coarse-grained locking, me refiro ao uso de poucas, normalmente uma, primitivas de sincronização para proteger o acesso a um conjunto grande de recursos; de forma análoga, fine-grained locking é quando cada lock é responsavel pela proteção de poucos recursos.

Por exemplo, uma estrutura de diretórios, no caso de coarse-grained locking, apenas um lock existe para proteger todos objetos desta estrutura; com fine-grained locking, cada alteração precisaria obter os locks correspontes ao objeto em questão e os de seus parentes imediatos.

O uso de fine-grained locking introduz a necessidade de criarmos um protocolo de sincronização, isto é, dizer em qual ordem os locks precisam ser obtidos a fim de evitar deadlocks. Isso é dificil, muito dificil, de fazer corretamente então guarde esse recurso para último caso. Um bom exemplo de como podem ser cabeludos, basta dar uma olhada na documentação de java.nio.channels.Selector.

Estruturas de dados
Estruturas de dados fazem um papel fundamental em todo sistema paralelo, principalmente quando são compartilhadas entre várias threads. Quando falamos de estruturas de dados para programas paralelos, podemos dividir elas em 3 tipos: síncronas, paralelas e livre de espera.

As síncronas são as que estamos acostumados, são aquelas que o acesso a qualquer operação é sincronizado tais como Hashtable e Collections.synchronizedXXX. As paralelas permitem que várias operações ocorram simultâneamente, java.util.concurrent.ConcurrentHashMap permite leitura sem sincronização e um número configuravel de atualizações em paralelo. Por fim, as estruturas livres de espera não usam qualquer tipo de sincronização e são indicadas para evitar contenção desnecessária. Uma estrutura livre de espera apesar de operar de forma mais eficiente com pouco paralelismo, costuma ser pior que as paralelas no caso de muita contenção.

Somando tudo
Otimizar um programa paralelo é diferente que para um programa seqüêncial, nunca é demais dizer que para começar é preciso fazer muito profiling e ter metas de performance bem claras para saber quando parar. Por mais interessante que seja, eu considero que o ideal de otimização é o suficiente para tornar o programa escalavel, de forma que seja possível usar mais recursos (cpu e memória) e o trabalho ser feito mais rápido. Otimizar além disso vai tornar o programa dificil de manter e provavalmente com mais bugs.