Esta notícia foi originalmente publicada em 27 de maio e faz parte da coleção das melhores notícias de 2008 publicadas na InfoQ
Em 1967 Gene Amdahl apresentou o que aparentemente seria o limite fundamental em o quão rápido você pode fazer código concorrente.Somente uma parcela do processamento de um programa pode ser executado inteiramente em paralelo, e somente esta parcela pode ser escalada diretamente em máquinas com mais e mais núcleos de processamento. O resto do trabalho de um programa é seqüencial. O problema principal apontado pela lei de Amdahl é a contenção de lock, um problema tão grave quanto o aumento do número de núcleos de processamento. A maior parte dos grandes sistemas de hardware de CPU de memória compartilhada suportam leituras concorrentes muito rápidas mas possuem a velocidade limitada para "1-cache-perdido-por-escrita" ou "1-memory-bus-alterado-por-escrita," então é importante evitar que todas as CPUs escrevam para um mesmo local. Mesmo com lock de leitura-escrita, não é possível ultrapassar o range da CPU de 50-100. Processamento multi-core é uma indústria que vem crescendo, com quase todos os fabricantes de hardware explorando atualmente suas possibilidades. A Azul está fabricando hardware de produção com 768 cores, O Rock da Sun esta em torno de 64, e até mesmo fabricantes de hardwares baseado no x86 estão expandindo o número de núcleos de utilização. Então o problema da contenção de lock está se tornando uma pedra no sapato dos desenvolvedores que escrevem código performático.
Dr. Cliff Click, um renomado engenheiro da Azul Systems, deu uma palestra (slides aqui) no JavaOne deste ano descrevendo um conjunto de técnicas que tem permitido que ele se dirigisse para um caminho escalável, com um estilo de codificação em Java "sem bloqueios". Em termos gerais, sua técnica é implementar um algoritmo "sem bloqueios" de maneira que, ao parar uma thread em particular, não vá parar o processo global
Os componentes mais importantes no trabalho de Click são:
- Um array grande e rápido que contém toda a informação que permite leituras paralelas rápidas das informações e que também permite uma cópia concorrente paralela e incremental.
- Alteração atômica nas palavras do array (utilizando java.util.concurrent.Atomic.*). A alteração atômica vai utilizar tanto Compare e Swap (CAS) se o processador for Azul/Sparc/x86, ou Load Linked/Store-conditional (LL/SC) na plataforma IBM.
- Uma Máquina de Estados Finita (ou Finite State Machine (FSM)) construída a partir da alteração atômica e logicamente replicada por palavra do array. O FSM suporta redimensionamento de array e é utilizado para controlar escritas.
Com todos estes elementos básicos na ordem, Click então constrói um algoritmo a partir de vários passos FSM que é livre de lock, ex. cada CAS tem um progresso. Um sucesso de um CAS é um sucesso local, enquanto que a falha de um CAS significa que outro CAS teve sucesso. Se o CAS tem sucesso o estado da máquina avança, enquanto a que a falha de um CAS tem um regresso.
Click implementou dois exemplos (Bit Vector e Hash Table) com o código disponível no SourceFourge e funcionando em um terceiro (uma fila FIFO). Para ter um exemplo ligeiramente mais detalhado, o hash table é um array de pares de Chave-Valor com as chaves em slots "normais" e os valores em slots "bizarros". Cada palavra é Comparada e Verificada separadamente, mas o estado da máquina move ambas palavras e durante a cópia inclui palavras de ambos os arrays. A implementação de hash table suporta inclusão concorrente, teste de remoção e redimensionamento e passa o Kit de Compabilidade Java (JCK) para o ConcurrentHashMap. No hardware da Azul ela obtém uma escala linear de até 768 CPUs com mais de um bilhão de leituras simultâneas por segundo com mais de 10 milhões de alterações por segundo.
InfoQ falou com o Dr. Click para ter um pouco mais de background do seu trabalho. Durante sua palestra no JavaOne ele destacou alguns pontos sobre a escrita na implementação de hash table em Java. Perguntamos a ele o quanto Java é indicado para este tipo de trabalho. Ele respondeu que "na verdade é altamente indicado... Java tem um modelo de memória bem definido (e bem implementado). Ele se perde em alguns pontos em controles específicos, o que eu posso ignorar, pois eles custam apenas um pouco de performance. Essa perda em controles específicos (ex. acesso ASM direto) poderia ser um problema com, por exemplo, design de um SO ou drivers de dispositivos, mas não para estruturas de dados performáticas.”
Nós também perguntamos quando ele recomendaria o uso de uma de suas estruturas de dados. Seu conselho geral era para utilizá-las quando as alternativas de "tentativa e erro" são muito lentas para serem úteis:
“Quando um única estrutura de dados é altamente sustentável, e você já tentou por exemplo java.util.concurrent.ConcurrentHashMap. Meu código é geralmente ligeiramente mais rápido sem carga (então sem nenhuma razão para utilizar isto), e funciona muito melhor
- com mais de 32 cpus competindo, ou
- com uma alta porcentagem de escritas vs leituras.
Sua velocidade pode variar, com certeza, então teste antes de usar.”
Existe uma série de atividades rolando ao redor de concorrência em Java no momento e o trabalho do Dr. Click aborda problemas similares no framework fork/join sendo considerado para Java 7. Apesar de não ser um membro do expert group, Click é regularmente consultado por eles.
Dr Cliff Click, Dr. Cliff Click, um renomado engenheiro da Azul Systems, deu uma palestra no JavaOne deste ano, descrevendo um conjunto de técnicas que tem permitido que ele se dirigisse para um caminho escalável, com um estilo de codificação em Java “sem bloqueios”. O estilo de codificação lhe permitiu construir várias estruturas de dados do tipo lock-free em Java que escalam com sucesso em processadores com centenas de núcleo. Cliff Click em um Estilo de Codificação Escalável sem Bloqueio