O tema de otimização de código é inesgotável, e nesta coluna já falamos de desempenho em inúmeras oportunidades. Vimos desde otimizações implementadas pelas JVMs (como algoritmos de compilação JIT ou de garbage collection, recentemente na Edição 30) até APIs especificamente orientadas a programação de alto desempenho (como a java.util.concurrent, na Edição 20). Também mostramos técnicas de otimização específicas a certos domínios, como XML (Edição 22) ou JDBC (Edições 25 e 26).

Por outro lado, no dia-a-dia de todos os desenvolvedores Java, é comum trabalharmos com códigos que apresentam necessidades de alto desempenho, sem que existam opções da JVM ou APIs especiais à disposição para ajudar. Nestes casos, devemos utilizar técnicas mais gerais de otimização de algoritmos. São técnicas que precedem o Java em décadas, mas a cada nova geração de tecnologias, linguagens e programadores, elas devem ser continuamente lembradas e adaptadas.

Muito dessa teoria geral de otimização faz parte de cursos e livros sobre programação, algoritmos, e outros domínios da computação. Por exemplo, ao estudar muitas linguagens de programação, aprendemos que é mais eficiente fazer cálculos com variáveis inteiras do que com ponto flutuante[1]. Em algoritmos, aprendemos que um quicksort é mais eficiente que um bubblesort; em estruturas de dados, que uma lista encadeada é melhor que um array para inserções; e num domínio como bancos relacionais, aprendemos a utilizar índices, fazer joins eficientes etc. Mas não vamos falar dessas técnicas clássicas, que são muito bem cobertas por cursos e livros tradicionais.

Ao invés disso, vamos abordar a otimização de código com foco na exposição de princípios fundamentais, que são independentes de algoritmos ou de domínios específicos. O artigo usará dicas e exemplos em Java, explorando alguns "padrões" de ineficiência que são encontrados com freqüência em código Java escrito sem suficiente cuidado com questões de desempenho computacional[2]. Mas estes exemplos somente ilustram princípios sistêmicos que se aplicam a qualquer linguagem ou ambiente de programação.

Leis fundamentais da otimização de código

Para começar, vamos formalizar alguns "mandamentos" principais. Pesquisei e não encontrei nenhuma lista de "leis" desse tipo, portanto o que se segue é uma tentativa de organização de princípios fundamentais.

Otimização PREMATURA é a fonte de todo o mal

Esta lei, já famosa, foi enunciada por Tony Hoare (o criador do algoritmo quicksort, entre outras técnicas de alto desempenho). Também foi divulgada por Donald Knuth (o autor do clássico The Art of Computer Programming, uma série de livros com grande foco no desempenho de algoritmos). Vindo dessas fontes insuspeitas, é algo a ser levado muito a sério!

O problema é que otimizar código é uma atividade que implica em certos custos, perigos e possíveis efeitos colaterais. Um código otimizado pode sofrer de vários poréns:

  • Ainda não foi testado, enquanto a versão não-otimizada pode já ser um código "maduro".
  • É geralmente mais complexo, resultando em maior probabilidade de ocorrência de bugs.
  • É freqüentemente mais frágil. Muitas técnicas de otimização confiam em pressupostos "otimistas" sem os quais não são seguras. (Teremos exemplos disso neste artigo).
  • É mais difícil de dar manutenção. E com freqüência códigos de "gurus" responsáveis pelas otimizações têm que ser alterados por programadores menos experientes, já com o criador não mais disponível.

A conclusão desses itens pode ser resumida da seguinte forma: o custo de otimizar algum código não é somente o esforço da sua execução inicial. Bons coordenadores de projeto sabem disso, o que é importante, pois quando perguntamos a um programador quanto tempo precisa para implementar certa funcionalidade, é comum que o programador (daqueles que gosta de otimização) responda algo como:

"hmm... uma versão simplesinha em um dia, mas uma versão ultra turbinada, com muito mais desempenho, em três dias".

A verdade mais completa é que o código otimizado poderá ter outros custos e riscos, além desse tempo adicional de implementação.

O custo de otimizar algum código não é somente o esforço da sua execução inicial. A versão "ultra turbinada" poderá dar mais retrabalho de testes e correções, e ao longo dos anos exigirá mais esforço de manutenção.

Devemos fazer, no entanto, duas ressalvas:

  1. Nem toda otimização torna o código mais complexo. Muitas otimizações consistem simplesmente em usar recursos disponíveis de forma mais inteligente, e podem até mesmo simplificar o programa (por exemplo, explorando uma API especializada, que permite implementar certa funcionalidade com mais eficiência e também com menos código).
  2. O maior problema é a otimização prematura. O dito de Hoare e Knuth é frequentemente citado de forma incompleta, como somente "Otimização é a fonte de todo o mal". Otimização exige equilibrar fatores conflitantes, como o esforço de desenvolvimento e o desempenho da aplicação resultante. Deve-se otimizar quando o custo de otimizar é menor do que o custo de não otimizar.

Otimização envolve fatores conflitantes, como o esforço de desenvolvimento e o desempenho da aplicação. Deve-se otimizar quando o custo de otimizar é menor do que o custo de não otimizar.

O que não é medido não pode nem deve ser otimizado

Esta regra incorpora duas recomendações também bastante conhecidas. O primeiro é o de utilizar técnicas ou ferramentas de profiling: medir o desempenho real do código que você suspeita ser lento e importante para o desempenho da aplicação. Veja o quadro "Utilizando profilers".

Antes da otimização, o profiling ajuda a identificar os códigos ineficientes, o que nem sempre é óbvio. Por exemplo, é muito comum que códigos aparentemente ineficientes executem bem devido a otimizações feitas automaticamente pelo compilador. Não faz sentido se esforçar para fazer uma melhoria de desempenho que a JVM já faz de graça para você. Isso é especialmente verdadeiro para otimizações de baixo nível, de "velha escola". Por exemplo, substituir x * 8 por x << 3 (para x inteiro) é uma bobagem: torna seu código mais obscuro a troco de nada, pois é uma otimização trivial que qualquer compilador moderno faz certamente.

O profiling é igualmente importante para identificar trechos de código que valem a pena otimizar. Uma otimização que torne um método um minuto mais rápido tem pouco valor se o método for executado só uma vez por dia: uma economia de 1 minuto de 24*60, ou 1/1.440 = somente 0,0007% da sua cota diária de CPU. Já uma outra otimização que acelere em apenas 20 milissegundos um método que é executado dez vezes por segundo, economizará 20% dos seus recursos de CPU. Então, se é para correr os custos e riscos de otimizar código, deve-se fazê-lo preferencialmente nos casos que prometem alto retorno.

Após a otimização, também é importante medir o desempenho do novo código que você acredita ser mais eficiente que o anterior. Não é raro "otimizar" algum algoritmo e descobrir que o resultado é pior que a versão inicial. Às vezes isso acontece porque a versão otimizada é mais complexa. (Dissemos que código otimizado geralmente é mais complexo, mas a recíproca nem sempre é verdadeira.) O tamanho de um código tem relação com seu tempo de execução, e código complexo é mais difícil de analisar, podendo ocultar equívocos na sua análise do problema. Em outros casos, o pecado é a falta de informações de contexto; para mais detalhes veja a terceira lei, a seguir.

O segundo mandamento incorporado por esta segunda regra vem das disciplinas de qualidade de software, especialmente em Extreme Programming e Test-Driven Development: código que não é testado, por definição, não está correto. Se processos de desenvolvimento como XP insistem no testes unitários de alta granularidade de todo o código, é por boas razões. Muitos bugs surgem das causas mais tolas, como um "escorregão" no teclado que resulta no operador errado (como um '==' no lugar de um '+=') ou, com o auxílio de modernos editores com "auto-completar", na invocação de métodos equivocados. Aliás, às vezes é mais fácil se criar bugs em métodos triviais, de uma linha de código, do que em métodos complexos e difíceis, nos quais prestamos mais atenção.

Código que não é testado, por definição, não está correto. Se você quer otimizar um código, ele deve ser medido quantitativamente por um profiler, e qualitativamente por testes unitários.

Se você quer otimizar um código, este deve ser medido não só quantitativamente (por um profiler), mas também qualitativamente (por testes unitários). O teste unitário é o melhor amigo do programador adepto da otimização, pois o protege de muitos daqueles itens que citamos na primeira lei – até melhor que o profiling, que eu classificaria como o segundo melhor amigo.

Código complexo, porém devidamente coberto por testes unitários, dá muito menos trabalho "imprevisto" na hora dos testes funcionais e de homologação, ou na hora da manutenção. Mesmo no cenário em que um programador menos experiente herda algoritmos "envenenados" por gurus, se estes códigos estiverem bem cobertos por testes, será muito menos arriscado modificá-los. Também será menos difícil fazer as mudanças, pois um dos benefícios menos divulgados dos testes unitários é que servem como documentação complementar, ajudando a entender o comportamento do que está sendo testado. Uma sessão de depuração com bons testes unitários vale por mil páginas de documentação imposta por processos pesados.

Desempenho raramente é um fator simples

Mesmo quando medimos o desempenho do nosso código, não devemos ter confiança demasiada em números simples e brutos, sem muito contexto. Por exemplo, converter um bubblesort em um quicksort pode não ser bom, se em 99% dos casos a coleção a ser ordenada tiver pouquíssimos elementos – pois nestes casos o algoritmo de bolha é mais rápido.

Uma solução para esse problema é fazer o profiling com massas de dados realistas. Infelizmente, "testar com dados reais" às vezes é mais fácil de dizer do que de fazer. Podemos ser obrigados a fazer testes (unitários, funcionais, de desempenho) com dados mais limitados que os reais em tamanho, complexidade ou distribuição. Mesmo quando os dados estão disponíveis, o volume dos dados pode tornar testes freqüentes proibitivos, devido ao tempo e o esforço necessários.

Quando for muito difícil fazer testes próximos dos cenários reais, uma alternativa é instrumentar a aplicação para fazer profiling em produção, gerando logs de desempenho de operações críticas.


public Image geraRelatorio (... dados ...) {

  long tempo = System.nanoTime();

  Image relatorio = // ... gera o relatório ...

  tempo = System.nanoTime() - tempo;

  if (tempo > 10000000) // Evita logar se < 0,01s

    Logger.getLogger.debug("calcula() demorou " +

      tempo / 1000000000 + "s");

  return relatorio;

}

Como mostra o exemplo, este profiling ad-hoc, improvisado, é simples, feito preferencialmente com a API System.nanoTime() (JSE 5). Em versões anteriores do JSE, deve-se usar System.currentTimeMillis(), que é bem menos precisa: para métodos que executem em menos de ~50 milissegundos, a precisão de currentTimeMillis() é pequena demais para gerar resultados úteis, o que nos obriga a executar o método repetidamente em loops, algo comum em benchmarks mas inviável em código de produção. Uma dica é criar um método utilitário que pode ser implementado com nanoTime() ou currentTimeMillis(), conforme a versão do JSE. Isso retorna um valor padronizado: um double com o número de segundos.

Em muitos casos, o log de desempenho pode já estar disponível. Por exemplo, no domínio de bancos de dados, a maioria dos SGBDs, drivers JDBC e ferramentas de mapeamento objeto-relacional pode ser configurada para gerar logs que revelam queries muito lentas. Containers J2EE também podem oferecer opções para registrar o desempenho de execução de requisições HTTP, invocações a EJBs e outras operações gerenciadas pelo container. Na sua aplicação, não é difícil fazer o mesmo para operações "macro" como geração de relatórios. Mas é difícil fazer o mesmo para operações "micro", mais simples, pois a quantidade de código necessária para medir e logar o desempenho de cada pequeno pedacinho de código (como todos os métodos individuais) seria excessiva[5].

Outra regra importante é tentar prever todas as possibilidades do comportamento de um código, inclusive cenários extremos (ainda que raros), e pensar não só no desempenho médio, mas também na escalabilidade e tolerância a falhas do sistema. Por exemplo, para ordenar 100 registros de um relatório diário, não se perceberá grande diferença entre diversos algoritmos de ordenação. Mas se uma vez por ano, tivermos que gerar um relatório consolidado de 36.500 registros, o algoritmo de bolha exigiria 36.5002 = 1.332.250.000 operações, provavelmente "travando" a aplicação e causando falhas como timeouts de requisições de um servidor. Já o quicksort só precisaria de uma média de 36.500 * log2(36.500) = ~553.179 operações (mais de 2 mil vezes menos).

Técnicas de otimização

Nesta seção vamos listar algumas dicas práticas de natureza "fundamental": técnicas que podem ser realizadas por milhares de otimizações diferentes. Ao invés de decorar truques específicos, é muito mais produtivo adquirirmos o conhecimento de como criar novas otimizações conforme necessário.

Evite cópias

Essa regra vem dos tempos do ábaco, mas ignorá-la ainda é uma dos descuidos de desempenho mais comuns. Evite copiar coisas: objetos, arrays, coleções, estruturas de dados.

Programadores conscientes com desempenho usam StringBuilder (JSE 5) ou StringBuffer (versões anteriores) para compor strings complexas – especialmente quando isso requer loops, para evitar o custo de concatenações que criam novas strings, copiando todos os caracteres das strings concatenadas. (Para expressões simples, como em Satelite.toXML(), uma seqüência única de concatenações sem nenhuma string temporária explícita, o compilador javac já faz esta otimização automaticamente.) Isso é bom, mas não é suficiente.

No exemplo, temos uma estrutura de dados hierárquica, com planetas que possuem satélites, de forma que a composição da representação XML da estrutura como um todo exige várias invocações a toXML(). O problema é que cada invocação dessas constrói uma nova string. Para um planeta como Júpiter, isso significa concatenar 63 strings de satélites ao StringBuilder do planeta. O uso de StringBuilder em cada método toXML() é insuficiente, devido à alta granularidade da operação. Dito de outra forma: A decomposição de algoritmos em muitas subrotinas, característica da programação estruturada e ainda mais de OO, é uma grande fonte de ineficiência. Ou, para reutilizar um clichê, pense globalmente: em muitos casos não adianta otimizar métodos individuais, é preciso considerar atividades mais abrangentes.

A decomposição de algoritmos em muitas subrotinas é uma grande fonte de ineficiência. Pense globalmente: em muitos casos não adianta otimizar métodos individuais, é preciso considerar atividades mais abrangentes.

Felizmente é fácil corrigir o problema do exemplo anterior. Basta modificar a assinatura dos nossos métodos, como mostrado na Listagem 2. Aqui todo o trabalho de geração do XML é feito por métodos que já recebem um StringBuilder. Assim, o mesmo buffer pode ser passado de um método para outro, ao visitarmos toda a hierarquia de objetos que compõe um planeta (O método com assinatura tradicional, String toXML(), pode continuar sendo oferecido para conveniência dos "usuários finais" destas classes.).

Chamamos esse estilo de programação de streaming: processar um conjunto de dados sem decompô-lo, passando a cada método ou classe uma referência para um buffer único para consumo ou produção destes dados. A técnica pode ser aplicada a muitos outros problemas. Por exemplo, vamos examinar a implementação do parsing de uma mensagem que recebemos de algum lugar (arquivo, socket etc.) como um array de bytes, e contém um comando seguido de parâmetros (veja a Listagem 3).

A lógica nessa listagem simples: recebemos um array de bytes, cujo primeiro byte é o número de caracteres do comando (ex.: 5). Depois seguem bytes com os caracteres ASCII do comando (ex.: 'P','R','I','N','T'); e em seguida os bytes que contêm os parâmetros para o comando, sendo que isso é interpretado por outro método de parsing.

Ao escrever parseMensagem() dessa forma, passando a parseParametros() um array novo contendo somente os bytes dos parâmetros, quisemos evitar complicações – como ter que passar também a posição do primeiro byte de parâmetros e considerá-la neste método, ou seja, usar dados[pos + 5] para obter o quinto byte de parâmetros. Mas infelizmente temos novamente alocação e cópia redundantes, que irão tornar o parsing como um todo muito mais lento.

A solução, novamente, é bastante simples, como podemos ver na Listagem 4. Utilizamos a classe java.io.ByteArrayInputStream, que encapsula um byte[] num stream de memória, permitindo sua leitura com métodos tradicionais de I/O como read(). Uma vantagem desta classe é que ela mantém automaticamente o offset do próximo byte a ser lido; assim a nova versão do código é ainda mais simples que a anterior. E a invocação a parseParametros() não exige nenhuma cópia de dados, nem uma variável adicional para a posição inicial de leitura dos parâmetros. A implementação deste método terá a mesma facilidade de invocar métodos read() que já conhecem e atualizam a posição de leitura (o que também produz um código mais robusto, pois não precisamos especificar e calcular esta posição continuamente, à mão).

Várias outras classes e interfaces, além de StringBuilder (para strings) e ByteArrayInputStream/ ByteArrayOutputStream (memória), permitem programar em "estilo de streams". Para citar outras:

  • Coleções orientadas ao consumo eficiente de dados, como Queue e LinkedList.
  • Para dados de arquivos, rede, resources etc., diversas classes de java.io e java.net: todos os InputStream e OutputStream, bem como os Reader e Writer.
  • Iterator, para qualquer coleção.
  • Outras APIs com "estilo streaming", como StringTokenizer, Format, ResultSet, XmlEventReader, e várias outras mais obscuras.

Quanta diferença faz evitar estas alocações e cópias redundantes? Existe um mito que a alocação de memória é quase gratuita em JVMs atuais, graças a seus eficientes sistemas de heap com garbage collection (GC). Mas alocar memória a torto e a direito é sim um problema potencial.

Em arquiteturas de hardware modernas, um dos problemas da combinação de GC com alocação desnecessária é que isso tende a "esgotar" os caches da CPU. Grandes quantidades de objetos temporários alocados à toa, mas não imediatamente desalocados devido ao comportamento do garbage collector, enchem os caches L1 e L2 com lixo e forçam operações extras de I/O da memória RAM, que é lentíssima em comparação com as CPUs atuais de vários GHz.

Alocar memória demais é um problema potencial, mesmo com a tecnologia atual de garbage collection. A alocação desnecessária tem um alto custo ao esgotar os caches da CPU.

O pior é que o fenômeno é muito difícil de medir, pois estes custos de microarquitetura não aparecem em profilers comuns. Você pode executar uma ótima bateria de testes de desempenho e não ver nenhum indício que a alocação de objetos temporários está consumindo muito tempo, pois as operações de alocação em si são rápidas – os custos de erros de cache L1/L2 podem se distribuir uniformemente por todo o programa. Profilers que mostram o volume de alocações por método indicam fontes suspeitas de problemas, mas sem uma associação clara com outros fatores pode ser difícil de interpretar tais resultados. Você acha que um método que aloca 500 Kb de dados por segundo, num benchmark que só invoca este método em loop, é algo bom ou ruim? É muito difícil responder sem dados adicionais. O mais seguro é não copiar dados como se isso fosse grátis.

Outra dica na mesma linha: evite "cópias defensivas", preferindo objetos imutáveis. Veja por exemplo a Listagem 5.

A classe TabelaPeriodica ilustra várias maneiras de implementar um "getter" de uma coleção de objetos que deveriam ser fixos: para garantir esta propriedade, o código que invoca o getter não deve ter a liberdade de modificar a coleção privada da TabelaPeriodica.

A implementação getAtomos1() não nos serve, pois quem invocar este método poderá alterar o array recebido, que é o mesmo array privado (lembre que o final proíbe modificações somente à referência ATOMOS, mas não ao conteúdo de cada posição deste array). A versão getAtomos2() resolve o problema, retornando um array independente que, se alterado, não afetará o array privado. Infelizmente, esta versão tem um alto custo, ao copiar o array (desnecessariamente, diga-se de passagem, para os casos provavelmente muito comuns em que o chamador não modifica o array).

A versão getAtomos3() resolve o problema de forma definitiva. Primeiro, o método Arrays.asList() retorna uma List que encapsula um array (um wrapper). Este método não copia o array; apenas cria uma "casca" sobre ele. Assim, set(7, ...), por exemplo, modificaria o elemento 7 do array original. Como não queremos permitir essa modificação, usamos Collections.unmodifiableList() para criar mais um wrapper, que neste caso somente proíbe as alterações: métodos como set() geram exceções. Assim, o array privado ATOMOS fica totalmente protegido de alterações por código incorreto (ou malicioso), sem o custo de copiar o array.

Há várias outras maneiras de se cometer o pecado de copiar objetos sem necessidade, muitas vezes envolvendo a criação de objetos temporários. Quem usa string1.toUpperCase().equals(string2) para fazer uma comparação não sensível a maiúsculas e minúsculas está jogando CPU pela janela: use string1.equalsIgnoreCase(string2), muito mais eficiente por evitar a criação de uma nova string, e também mais simples. Idem para "new Integer(string).intValue()": prefira Integer.parseInt(string). Outro código comum, igualmente ruim, é stringbuilder.append(str.substring(x, y)). É bem mais eficiente, e também mais simples, usar stringbuilder.append(str, x, y) (JSE 5 ou superior). A lista de maneiras de criar e copiar objetos à toa é interminável.

Explore o código mais especializado

Há, é claro, infinitas soluções para qualquer problema de programação. E mesmo contando apenas as soluções que têm desempenho ótimo para pelo menos alguns cenários, há muitas respostas para qualquer problema de complexidade razoável.

Um dos tipos mais importantes de otimização consiste em selecionar a API mais específica para cada tarefa. Por exemplo, temos muitas APIs de coleções nos pacotes java.util e java.util.concurrent. Todas as implementações de Collection fazem basicamente a mesma coisa, com algumas variações de funcionalidade (elementos ordenados ou não etc.), mas também diferem nas suas características de desempenho.

Muitas dessas características são bem conhecidas. Por exemplo, dissemos na introdução que uma lista encadeada é mais eficiente que um array para inserções. Você pode ter aprendido isso num curso de algoritmos, ou lendo os javadocs destas APIs (que, por sinal, são particularmente bem documentadas quanto ao desempenho). Mas é preciso estar atento aos detalhes ou aos casos excepcionais.

Um exemplo: ArrayList é um array auto-extensível com crescimento exponencial. Se um ArrayList tem espaço para 100 elementos e o 101º é inserido, o espaço interno (um Object[]) é aumentado em 50% + 1, neste caso para 151 elementos. Isso cria uma "folga" que faz com que um novo crescimento só seja necessário após outras 50 inserções cumulativas, quando o array exceder 100 elementos, sendo então aumentado para 151 + 50% + 1 = 227, e assim por diante.

Uma análise simples demonstra que este crescimento exponencial produz um desempenho médio linear, pois cada crescimento, embora seja mais caro que o anterior, também será menos freqüente na mesma proporção. Ou seja, de 100 para 151 elementos, temos o custo de copiar 100 elementos, sendo que isso ocorreu após 34 inserções (o tamanho anterior a 100 é 66). Já no redimensionamento de 151 para 227, precisamos copiar 100 + 50% + 1 = 151 elementos, mas isso só é feito após 50 inserções (34 + 50% + 1). Na média, portanto, o custo de crescimento associado a cada inserção é constante. Bem, isso é o que você pode aprender nos próprios javadocs de ArrayList.

Mas existem consequências menos óbvias. Vamos à principal: inserções no final (ou muito próximas do final) de um ArrayList serão mais eficientes do que em listas encadeadas, quando houver espaço livre para a inserção. Por exemplo, num ArrayList com espaço para 20 elementos, mas apenas 19 utilizados, um add(17, item) será mais eficiente que inserir um elemento no final de uma LinkedList: o ArrayList só precisa mover os itens 17-18 para as posições 18-19, mas não faz nenhuma alocação. Já um add(item) será muito mais eficiente no ArrayList que na lista encadeada: basta colocar o novo elemento na posição 19, não sendo preciso alocar e nem sequer fazer qualquer cópia de dados. E, para completar, em muitos casos é viável prever o tamanho máximo de um ArrayList e prealocá-lo com este tamanho, o que reduz quase a zero os custos de alocação.

Otimizando mapas

Vamos a outro exemplo: qual é a maneira mais eficiente de criar um Map imutável (no sentido de ter uma população de elementos constante[12])? Muitos desenvolvedores experientes saberão escolher entre as várias implementações de Map. HashMap é melhor para o caso geral (acesso a dados não ordenados, equilíbrio entre inserções e acessos). TreeMap é melhor para dados ordenados. LinkedHashMap favorece a iteração na ordem da inserção. IdentityHashMap é otimizado para chaves que podem ser comparadas por identidade (== ao invés de equals(), como "singletons múltiplos"). No JSE 5, EnumMap é mais eficiente para chaves definidas como enums; e ConcurrentHashMap e ConcurrentSkipListMap são melhores para acesso por múltiplos threads.

Esse conhecimento sobre as implementações de Map já responde parte da questão. O uso da implementação ideal para determinado cenário já poderá gerar enormes ganhos de desempenho, se comparado ao uso de uma implementação genérica. Mas como especificamos que o Map é imutável, falta um pequeno truque, explorando alguns métodos utilitários de Collections que são pouco conhecidos, mas que vale a pena explorar:

  • Collections.emptyMap() retorna o Map imutável e vazio que seja o mais eficiente possível.
  • Collections.singletonMap(chave, valor) cria o Map imutável de um elemento, que seja o mais eficiente possível.

Os Map retornados por estes métodos são mais eficientes que qualquer outra implementação, em qualquer cenário. Por exemplo, em programação multithreaded, nem mesmo ConcurrentHashMap e ConcurrentSkipListMap serão melhores que um Map gerado por singletonMap(), não importa quantos threads você tenha. Os Map especiais para zero e um elementos são simplesmente melhores que todos os outros – sempre, sem exceções. E é fácil imaginar o porquê. Por exemplo, emptyMap() retorna uma instância de uma implementação especial de Map (privada), cujo get() é simplesmente "return null;", contains() é "return false;", size() é "return 0;" e assim por diante. É difícil ser mais eficiente que isso! Além disso, singletonMap() retorna sempre a mesma instância; portanto não exige alocar nenhuma memória a cada invocação.

O mesmo truque está disponível para List (emptyList(), singletonList()) e para Set (emptySet(), singleton()). Sendo que os métodos emptyXxx() existem apenas no JSE 5 ou superior.

Como explorar melhor estas APIs orientadas a alto desempenho? No exemplo, muitas aplicações têm um número razoavelmente grande de coleções que podem aproveitar estas otimizações. Isso é bastante comum em dados de configuração definidos seja por código, seja por arquivos lidos somente na inicialização da aplicação. Nestes casos, é possível usar estruturas de dados imutáveis.

Como é muito trabalhoso, a cada oportunidade de uso das coleções otimizadas, escrever todo o código adicional necessário para empregar (se possível) os métodos emptyXxx() e singletonXxx(), você pode definir métodos utilitários bastante simples, como o da Listagem 6.

Após criar seu Map de maneira normal, o método otimizaMap(), se possível, irá convertê-lo para uma versão mais eficiente. É um utilitário simples, mas que pode economizar bastante memória e tempo de CPU para aplicações que mantêm um grande número de coleções imutáveis e pequenas.

Estendendo a técnica

De uma forma mais abrangente, como aplicar esta dica a outras APIs? A resposta inicial é com suor e experiência. Depois de um bom tempo utilizando as APIs do JSE/JEE/JME, além de outras (como Struts, Hibernate etc.), acumulamos conhecimentos sobre estas APIs, e otimizações desse tipo aparecem "na ponta da língua" quando aplicáveis. Mas o programador menos experiente pode aprender a procurá-las. Muitas vezes até ferramentas comuns de pesquisa na internet ajudam, quando você já tem uma noção do que precisa. A partir de uma intuição como "mapas vazios são muito comuns, então deve haver alguma API que otimiza este caso", basta procurar no Google por "Java empty Map" e o primeiro resultado será um link para o javadoc de java.util.Collections.

Para problemas de programação envolvendo seu próprio código, basta ter a mesma noção de que as implementações especializadas são mais eficientes (em geral) do que implementações mais genéricas da mesma coisa. Se você estiver implementando (digamos) um sistema de cálculo de impostos, provavelmente terá uma classe CalculoIRPF, muito complexa. Mas há casos especiais – porém comuns – como o de contribuintes que podem optar pela declaração simplificada.

Talvez isso já tenha sido implementado, por exemplo com uma subclasse CalculoIRPFSimplificado, que herda da classe anterior e faz uma porção de invocações super() invocando as mesmas rotinas de cálculo genéricas, mas passando zeros para uma porção de parâmetros que não se aplicam à declaração simplificada (ex.: ganhos de capital). É um belo exemplo de reuso de código, mas não um bom exemplo de alto desempenho. No método genérico, um cálculo ganhosDeCapital * 0.25, se executado com ganhosDeCapital=0, usará o mesmo tempo de processamento que o mesmo cálculo com parâmetro não-zero. O jeito é fazer uma cópia do código genérico, substituir à mão as variáveis convertidas em valores constantes, e deletar manualmente as operações tornadas redundantes por estas constantes (como x + 0 ou x * 1). É feio, sim – mas é assim mesmo que se faz muito do que se entende por "otimização", desde que existem computadores.

Observamos, porém, que bons compiladores JIT poderão fazer esta otimização automaticamente, através de inlining das invocações de métodos genéricos passando parâmetros constantes, seguido da simplificação das expressões envolvendo as constantes. Assim vale mais a pena o esforço de fazer este tipo de otimização à mão quando o código for muito complexo. Por exemplo, se o cálculo de imposto for espalhado por dezenas de métodos, é menos provável que o compilador JIT consiga fazer inlining de todos estes métodos. E como saber se o compilador JIT dá conta do recado, ou se você tem que fazer a otimização à mão? Obviamente, com profiling.

Evite APIs muito genéricas

Este item pode ser considerado uma extensão ou conseqüência do anterior, mas merece uma discussão independente. Num projeto real, precisei fazer parsing de datas em grande volume (mensagens recebidas pela rede, cada uma contendo várias datas em formato ASCII). A maneira padrão de fazer isso é com a API DateFormat do JSE, por exemplo:


Date data = new SimpleDateFormat(

    "ddMMHHmmss").parse(str);

O problema é que, fazendo isso mil vezes por minuto, o custo em desempenho irá aparecer no radar do profiler. SimpleDateFormat é uma API muito poderosa, muito genérica, e suporta uma grande variedade de formatos de datas. Sua implementação é muito eficiente e otimizada (para o que se propõe a fazer). Por exemplo, quando construímos o objeto SimpleDateFormat, a string de formato passada no construtor é "compilada" para uma estrutura de dados (armazenada em atributos privados) que torna cada execução de parse() relativamente rápida. Ainda assim, a flexibilidade da API tem um custo em desempenho.

A solução é não usar esta API. Em vez disso, escrever código de parsing especializado em cada formato de data que precise ser suportado.

Esta solução, ilustrada na Listagem 7, é feia, mas é muitíssimo mais eficiente que usar SimpleDateFormat. E para uma aplicação que faz milhões de parsings de datas por dia, o ganho será significativo e compensa a "feiúra". Todavia, é muito importante enumerar os cuidados que temos de tomar com soluções desse tipo:

  1. Jamais misture código dessa espécie com o restante da sua aplicação. Encapsule-o em métodos utilitários, ex.: Date parseDdMMHHmmss(String).
  2. Tenha muito cuidado em reproduzir o mesmo comportamento da versão genérica. Por exemplo, SimpleDateFormat, ao criar uma Date a partir de valores de entrada que não incluem o ano, irá definir o ano como 1970 (início da epoch). O uso de qualquer outro ano arbitrário funcionará do mesmo jeito, pois a aplicação não usa o ano. O problema é que o comportamento do código otimizado, se não for exatamente igual ao do código original, pode causar bugs sutis. Por exemplo, num equals() entre uma data criada por SimpleDateFormat e outra criada pelo parser otimizado, uma diferença somente no ano fará a comparação falhar.
  3. Se é para sujar o código, vá até o fim. Pode ser necessário. Manipular os objetos de data do Java pode ser desafiador. Por exemplo, o código otimizado da Listagem 7 seria um pouco mais "bonito" se escrito com Calendar.getInstance() seguido de várias invocações a set(), como set(Calendar.MONTH, ...). Mas isso teria alguns custos. Código mais volumoso (tudo o mais sendo igual) sempre é menos eficiente. Também pagamos um preço de invocações polimórficas, por interfaces abstratas como Calendar (não confie demais no otimizador JIT). O argumento é que, já que você já cometeu um sacrifício considerável em nome do desempenho – código bem maior, mais complexo, difícil de alterar, menos legível etc. – algumas "barbeiragens" adicionais fazem pouca diferença. Para uma análise aprofundada dessa questão, veja o quadro "Otimizando até o fim: um estudo de caso".
  4. Fique atento a diferenças de comportamento ocultas. O código otimizado, mesmo levando em conta tudo o que dissemos, ainda possui algumas diferenças bem importantes em comparação com o original. É preciso ter estas diferenças em mente, e documentá-las nos javadocs do método utilitário. Primeiro, SimpleDateFormat suporta internacionalização: se tivéssemos usado um string de formato como "MMM" para o mês, SimpleDateFormat interpretaria a string "Fev" como fevereiro, mas só em países onde o mês de fevereiro tem estas iniciais. Segundo, o tratamento de erros é muito diferente: fornecer o valor "2A" no campo de mês iria produzir um valor null para SimpleDateFormat, mas o nosso método otimizado iria gerar uma NumberFormatException em Integer.parseInt(). Se esta diferença for importante, a versão otimizada poderia resolvê-la com um catch (NumberFormatException) { return null; }.

Evite trabalho inútil

Neste item, temos três técnicas que consistem em evitar trabalho inútil, duplicado, ou evitável.

Caching

Digamos que você está implementando uma classe Poligono, cujo método getArea(), conforme revelado por profiling, pode ser invocado várias vezes para a mesma instância. Mas não queremos executar repetidamente este método (que não é nada trivial para um polígono arbitrário, com um número qualquer de lados e podendo inclusive ser não-convexo). A solução para este problema de desempenho é simples: podemos manter a informação de área como parte do estado do objeto – veja a Listagem 8.

Esta solução resolve o problema enunciado: se invocarmos getArea() várias vezes para o mesmo Poligono, não teremos execuções repetidas do cálculo. É a técnica de caching, que já vimos em outros contextos nesta coluna, especialmente em "Persistência Turbinada" (Edição 25). É fácil definir qualquer tipo de cache: se você precisa com freqüência de alguma informação custosa de produzir, mantenha uma cópia desta informação à mão, ao invés de gerá-la sempre que precisar.

O caching tem alguns custos, como o consumo de memória (no exemplo, os 8 bytes ocupados pelo atributo área, que sendo redundante, não seria essencial para implementar a classe Poligono). E também há sempre um risco: deixar o cache inconsistente com os dados primários dos quais é derivado (sejam estes dados registros num banco de dados, ou os outros atributos de um objeto). No nosso exemplo, é óbvio que se for possível alterar o estado de um objeto Poligono após sua criação, deveremos tomar o cuidado de atualizar também o cache:


public void set (int indice, Point2D.Double ponto) {

  pontos[indice] = ponto;

  calculaArea();

}

Avaliação tardia

A partir daqui, no entanto, nossa otimização já começa a parecer problemática. Se o número de alterações num polígono exceder o número de invocações a getArea(), estaremos perdendo desempenho, devido aos recálculos repetidos da área. Além disso, sempre existe a possibilidade de criarmos um polígono cuja área nunca seja necessária. Portanto até o cálculo inicial feito pelo construtor é uma perda de desempenho.

Para resolver este novo problema, empregamos uma segunda técnica, mostrada na Listagem 9. Nesta versão, utilizamos a técnica de lazy evaluation (avaliação tardia ou "preguiçosa") para o atributo area. O cálculo só é feito quando realmente necessário. Utilizamos um valor negativo para o estado de "cache inválido"; o atributo já é inicializado com este valor, e é ressetado por qualquer método que possa tornar ilegal um cálculo de área anterior.

As técnicas de cache e avaliação tardia são com freqüência utilizadas em conjunto. Uma variante popular da avaliação tardia é a inicialização tardia, como o que fazemos ao implementar o pattern Singleton. Mas essa técnica é mais poderosa, podendo acelerar vários tipos de operações repetitivas.

Eliminação total

Finalmente, a melhor técnica desse item é a eliminação total de trabalho desnecessário. Isto pode ser feito em casos especiais que ocorrem com muitos algoritmos – casos que permitem que o algoritmo seja substituído por outro muito mais simples. Por exemplo, para o método Poligono.contem(ponto) que determina se o ponto está estritamente contido no polígono, existe um caso especial óbvio: para um polígono de área zero, a resposta é sempre false. Assim, se for comum a ocorrência de polígonos com área zero, podemos aproveitar que já temos o cache da área pré-calculada, e iniciar contains() pela condição: if (area == 0) return false;.

Para dar outro exemplo mais comum e amplamente aplicável, ao iterar qualquer coleção com iteradores, considere fazer isso:


if (!objs.isEmpty())

  for (Iterator iter = objs.iterator(); iter.hasNext(); )

    // ... processa elemento ...

O teste isEmpty() evita a alocação de um objeto Iterator, nos casos em que a coleção é vazia. A alocação desnecessária de um objeto pequenino como um Iterator pode fazer diferença, se ela ocorrer dentro de outros loops que executam milhares de iterações.

Explore caminhos rápidos

Vamos terminar com uma técnica fundamental de otimização que é muito importante e interessante, mas pouco óbvia. Veja o exemplo da Listagem 10.

O método obtemCategoria(), dada qualquer palavra da língua portuguesa, retorna sua categoria (verbo de determinada forma, substantivo etc.). Esta descoberta é feita preferencialmente por um dicionário, mas para palavras não pertencentes ao dicionário o algoritmo procura estimar a categoria da palavra analisando prefixos e sufixos comuns. Qual é o problema de desempenho?

O problema é que temos, logo no início da lista de testes, casos raros como verbos no gerúndio. Se analisarmos uma amostra de texto aleatória e comum (por exemplo, todo o conteúdo de um jornal), encontraremos bem poucos gerúndios. Portanto, não faz sentido colocar os testes destes casos no início do método, pois os 99% de palavras que não pertencem a tais casos terão que passar pelos seus ifs, para só depois, mais ao final do método, ser executada a condição de sucesso.

Entra a otimização do "caminho rápido" (fast path): numa lista de condições que exija busca linear (ou seja, que não permite o uso de um switch ou de uma pesquisa num Map), coloque em primeiro lugar os casos mais comuns (o código "quente"). Estatisticamente ganharemos desempenho, ao evitar a avaliação de muitas condições para os casos menos comuns (código "frio").

Uma parte importante da otimização fast path é a simplificação dos métodos. Os trechos de código quente e frio são segregados em métodos distintos:


public TipoPalavra obtemCategoria (String palavra) {

  RegistroPalavra reg = Dicionario.get(palavra);

  if (reg != null)

    return reg.getCategoria();

  else

    return estimaCategoria(palavra);

}

private TipoPalavra estimaCategoria (String palavra) {

  // ... lista de if()s...

}

Na nova versão, executamos em obtemCategoria() somente o caso mais freqüente, que é o de palavras conhecidas pelo dicionário. Os demais casos são delegados a um método complementar. Além da melhor estruturação de código, também ganhamos desempenho. Quando o compilador JIT, como o HotSpot, decidir otimizar obtemCategoria(), terá um método menor para compilar. Isso resulta numa compilação mais rápida e em código nativo mais enxuto e eficiente. De fato, se nosso dicionário for muito bom e cobrir 99,99% das palavras, é possível que o método estimaCategoria() nem precise ser compilado, economizando tempo e memória gasta com sua otimização.

Mesmo em linguagens sem as características de compilação dinâmica do Java, a otimização fast path é benéfica, pois tende a produzir uma organização de código mais eficiente. Se analisarmos o layout de métodos ou procedimentos na memória (pressupondo bons compiladores), os métodos que constituem fast paths tendem a ficar agrupados. Isso torna mais eficiente o uso dos caches da CPU.

Esses caches são divididos em páginas, ex.: de 128 bytes contíguos para o cache L2 do Pentium IV. Quando a CPU lê da RAM uma página que contém um método "quente" como o obtemCategoria() otimizado, se este método ocupar apenas 50 bytes desta página, a mesma operação poderá trazer "de carona" para o cache até 78 bytes pertencentes a outros métodos "quentes". Já se estivéssemos trabalhando com a versão original do método, um bom pedaço do código "frio" seria trazido para o cache – sem necessidade, nos casos comuns em que este código não é acionado. O efeito é ainda mais significativo para paginação de memória virtual, que utiliza páginas de 4 Kb e às vezes bem mais. Certos programas podem ficar várias vezes mais lentos ou mais rápidos, só devido a este fator: a organização de código na memória.

O problema é difícil de identificar diretamente, mas podemos usar profilers que fazem cobertura de código no nível de linhas ou statements. Se o profiler revelar que um método é invocado com muita freqüência, mas que somente algumas linhas do método são executadas na maioria das vezes, deve-se considerar a possibilidade de otimizar este trecho "quente" com técnicas de fast path. Ou seja, privilegiar a ordem do código quente no método, ou até segregá-lo num método especializado.

Conclusões

O número de dicas, técnicas e APIs para otimização de código é interminável, mas não precisamos de um conhecimento enciclopédico sobre o assunto. O mais importante é dominar os conceitos fundamentais sobre desempenho de software, e conhecer as técnicas e ferramentas necessárias para analisar e otimizar o desempenho quando for preciso. A prática com otimização, com o tempo, irá desenvolver um "instinto" que leva a escrever código cada vez mais eficiente já na primeira versão.

Mas mesmo para quem atinge este nível, é essencial desenvolver e manter uma disciplina de "programação defensiva". Otimização pode ser arriscada, e código lento pode ser melhor do que código otimizado que é muito frágil ou de caríssima manutenção. Além disso, é preciso manter sempre a disciplina de medir o desempenho do que é utilizado. Os programadores mais experientes são os que mais pecam em escrever código "eficiente logo de início", muitas vezes sem uma real necessidade que justifique o resultado mais complexo e frágil. Mas se tivermos a disciplina de seguir regras simples, como analisar o desempenho do código num profiler, podemos focar nossos esforços nas áreas que contribuirão para o desempenho global da aplicação.

Otimizando até o fim: um estudo de caso

Para exercitar nossas técnicas de otimização, nada melhor que um pequeno benchmark. Escrevi um programa (disponível nos downloads) que mede o consumo de CPU e memória de várias implementações que fazem parsing de um string contendo uma data no formato "ddMMHHmmss". Os resultados para cada algoritmo são mostrados a seguir.

SDF: Utiliza SimpleDateFormat, criando uma nova instância deste objeto para cada parsing:


return new SimpleDateFormat("ddMMHHmmss").parse(s);

Desempenho: 15 µs (microssegundos) e 1.770 bytes. Você leu direito: 1,7Kb de memória alocada para uma única operação de parsing! Eu avisei sobre essas APIs ultra-flexíveis...

SDFCached: Também usa SimpleDateFormat, mas cria este objeto uma única vez, invocando sempre a mesma instância:


private static SimpleDateFormat fmt =

  new SimpleDateFormat("ddMMHHmmss");

...

return fmt.parse(s);

Desempenho: 4,1 µs, 574 bytes. Podemos constatar que boa parte do custo de SimpleDateFormat é a construção deste objeto, especialmente a compilação da string de formato para a representação interna que permite fazer o parsing de forma eficiente. É um grande avanço – três vezes melhor tanto na velocidade quanto no consumo de RAM. Mas exige que você possa usar repetidamente o mesmo objeto SimpleDateFormat (que, lembrando, não é thread-safe!).

Hardcoded: Faz o parsing de campos individuais com Integer.parseInt() e cria a data com new GregorianCalendar(...).getTime():


return new GregorianCalendar(1970, Integer.parseInt(s.substring(2, 4)),

   Integer.parseInt(s.substring(0, 2)) - 1, Integer.parseInt(s.substring(4, 6)),

   Integer.parseInt(s.substring(6, 8)), Integer.parseInt(s.substring(8, 10))).getTime();

Desempenho: 2 µs, 574 bytes. Ganhamos outros 50% de uso de CPU. O consumo de memória é igual, o que mostra que a implementação de SimpleDateFormat.parse() (graças à representação compilada da string de formato) não aloca nenhuma memória. Isso é impressionante para uma operação dessa complexidade. Ainda assim, a melhoria de tempo de CPU já vale a pena.

Otimização extrema

Quando cheguei a este ponto, me perguntei se haveria mais alguma coisa a melhorar. Mas entramos naquela fase de "tirar leite de pedra" e a partir daqui qualquer otimização tenderia a ter retornos reduzidos, dificilmente compensando o aumento de complexidade e feiúra do código. Mesmo contra meus instintos, fiz e testei uma nova versão:

VeryHardcoded: Substituí Integer.parseInt() por um algoritmo próprio de parsing de números compostos por precisamente dois dígitos (é o caso de todos os componentes da string de formato usada). Além disso, eliminei as operações substring(), passando ao parser de números a posição do primeiro dígito (o que nos remete à regra de não copiar dados!):


return new GregorianCalendar(1970,  parseNN(s, 2),

  parseNN(s, 0) - 1,  parseNN(s, 4),  parseNN(s, 6),

  parseNN(s, 8)).getTime();

...

private static int parseNN (String s, int pos) {

  return (s.charAt(pos) - '0') * 10 + (s.charAt(pos + 1) - '0');

}

O resultado: 1,6 µs, 430 bytes. Este ganho ainda é decente: 25% a menos de CPU e 33% a menos de memória. Mas já não é um ganho tão espetacular, talvez não o bastante para justificar o código cada vez mais complexo (lembre-se que começamos com uma implementação de uma só linha!).

Nesse ponto, impliquei com o consumo de memória. Torrar 430 bytes parece algo excessivo para uma operação tão simples quanto criar uma data (considerando que o parsing em si, nesta versão, já não aloca nenhuma memória temporária).

Concluí que o problema era o uso de GregorianCalendar. Há muito tempo (no JDK 1.0.x) poderíamos invocar os construtores de Date, mas estes construtores se tornaram deprecated a partir do JDK 1.1. E por boas razões: estes construtores têm parâmetros de ano que utilizam um valor-base implícito de 1900, ou seja, deve-se usar new Date(87, ...) para uma data com o ano 1987, e new Date(106, ...) para 2006. Além disso ser inconveniente, não é muito compatível com a virada do ano 2000 (lembra?).

Dito isto, abandonei minhas últimas "boas práticas" e parti para mais uma versão.

ExtremelyHardcoded: similar ao anterior, mas usa new Date(...) ao invés de criar um GregorianCalendar e convertê-lo para Date com getTime():


return new Date(70, parseNN(s, 2), parseNN(s, 0) - 1,

  parseNN(s, 4), parseNN(s, 6), parseNN(s, 8));

Resultado: 1 µs, 143 bytes. O resultado é surpreendente – mais um salto importante de desempenho: 40% de economia de CPU e 66% de memória. A pergunta, nesse ponto, é: será que vale a pena? Agora temos não só código complexo e "feio", mas também o uso de APIs deprecated, que talvez deixem de ser suportadas algum dia (pelo menos em princípio, pois isso jamais ocorreu com qualquer API oficial do Java).

Para uma aplicação que fizer parsing de uns 5 milhões de datas diariamente, a economia agregada é de 70 segundos por dia (pouco importante) – mas de 8,1 gigabytes de alocação (o que é mais importante). Todavia, para atingir este desempenho máximo, tive que cometer até mesmo o pecado de utilizar APIs obsoletas. Nada é de graça!

Otimização fanática

Enfim, chegamos ao algoritmo mais rápido possível para parsing de datas em Java? A resposta é um enérgico não! Existe uma maneira muito mais econômica, tanto em tempo quanto em memória: usar o construtor Date (long milissegundos). Se você examinar o código-fonte, verá que o construtor é excepcionalmente eficiente:


public void Date (long date) {

  fastTime = date;

}

Esse construtor é dezenas de vezes mais rápido que os que recebem o ano, mês, dia etc., e não aloca nenhum objeto temporário. A única alocação feita é a do objeto Date, que só ocupa 24 bytes.

O único problema é que, para usar o construtor Date(long), você terá que fazer à mão a conversão dos componentes ano/mês/etc. para a unidade "milissegundos desde 1º. de janeiro de 1970". O algoritmo de Date é complexo, pois considera fusos horários, horários de verão, validação de dados ilegais, anos bissextos, e até o segundo extra de alguns anos. Parece complicado? Mas há uma solução que não é tão ruim.

O propósito desta última iteração de otimização é somente ilustrar o processo de decisões sobre otimização de código. É muito improvável que você precise descer até este nível, a não ser que esteja programando um kernel de sistema operacional ou algo equivalente.

Algoritmo Fanatic: Usa as APIs do Java para calcular, de forma fácil e confiável, o valor em milissegundos do início do ano atual, por exemplo 01/01/2006 00:00:00, e também uma tabela com o número de dias de cada mês deste ano (veja abaixo). Com estes dados, cada parsing pode obter o valor correto para qualquer data do mesmo ano, com um cálculo simples.


// Variáveis auxiliares

private static long anoBase;

private static final int[] DIA_POR_MES = new int[12];

private static final long MS_SEG = 1000L;

private static final long MS_MIN = MS_SEG * 60;

private static final long MS_HORA = MS_MIN * 60;

private static final long MS_DIA = 24 * MS_HORA;

...

// Inicialização de dados do ano-base

Calendar c = Calendar.getInstance();

c.set(c.get(Calendar.YEAR), 1, 1, 0, 0, 0);

c.set(Calendar.MILLISECOND, 0);

anoBase = c.getTimeInMillis();

for (int i = 0; i < DIA_POR_MES.length; ++i) {

  c.set(Calendar.MONTH, i);

  DIA_POR_MES[i] =

        c.getActualMaximum(Calendar.DAY_OF_MONTH);

}

...

return new Date(anoBase +

   (DIA_POR_MES[parseNN(s, 2) - 1] + parseNN(s, 0)) * MS_DIA +

   parseNN(s, 4) * MS_HORA + parseNN(s, 6) *

   MS_MIN + parseNN(s, 8) * MS_SEG);

Resultado: 0,084 µs, 24 bytes. Isto é 12 vezes mais rápido que a versão anterior, e consome seis vezes menos memória. São vantagens descomunais sobre um código que já era ultra-eficiente. Dessa vez, chegamos de fato aos limites do hardware: uma versão do mesmo algoritmo escrita em Assembly otimizado à mão, provavelmente não seria melhor.

Esta solução funciona, mas tem vários pontos frágeis: só permite criar datas do ano atual, exige recalcular a data-base ao virar o ano, não suporta fusos horários... mas, e daí? Você não está escrevendo código bonito (robusto, flexível, reusável, compreensível), e sim, código ultra-eficiente. É uma questão de escolha.

E agora você também sabe como algumas pessoas conseguem programar sistemas operacionais, animações 3D sem aceleração de hardware, e outras coisas "impressionantes" em Java (ou mesmo, qualquer linguagem de alto nível). Basta pegar todos os seus livros de boas práticas de programação de aplicações – e escondê-los bem!

Utilizando profilers

O profiler é a principal ferramenta especializada em apoiar atividades de análise de desempenho e otimização de código. Existem muitos profilers para Java, incluindo:

  • O hprof, embutido na própria JVM (veja java -Xrunhprof:help). Apesar de ser uma ferramenta de linha de comando pouco amigável, gerando saída no console ou em arquivos, é um profiler razoavelmente poderoso, e está sempre disponível (pelo menos nas JVMs da Sun e derivadas).
  • Outros profilers embutidos em diferentes JVMs, como o JRockit Runtime Analyzer, ou em servidores de aplicações.
  • O NetBeans Profiler, disponível para o IDE NetBeans 5.0 ou superior.
  • O TPTP (Test and Performance Tools Project, antigamente conhecido como Hyades), para usuários do Eclipse.
  • Outros profilers gratuitos/livres, como jMechanic e Eclipse Profiler.
  • Produtos comerciais, como o JProfiler, OptimizeIt, DevPartner/Java, JProbe etc.
  • Profilers nativos que também suportam Java, como o VTune.
  • Ferramentas de sistema, mas também úteis para Java, especialmente o DTrace do Solaris 10 (cujo suporte para o Java está sendo desenvolvido no Mustang).

Escolhida a ferramenta, os princípios de uso são bastante semelhantes. Primeiro, profilers são tipicamente lentos, e a atividade de profiling é repetitiva e produz grandes volumes de dados. Assim, é bom começar com testes unitários elaborados de forma a exercitar o código de interesse de forma ágil, isolada e automatizada.

 Profiler visualizando detalhes de execução do benchmark de parsing de datas
Figura 1. Profiler visualizando detalhes de execução do benchmark de parsing de datas (algoritmo "Fanatic").

Segundo, é importante aprender a analisar os dados gerados por profilers. A Figura 1 mostra uma saída do TPTP, que é bastante típica de ferramentas deste tipo (ilustrando o benchmark que discutimos no quadro "Otimizando até o fim: um estudo de caso"). Vamos examinar algumas das informações principais mostradas. Primeiro, no grupo "Execution Statistics":

  • Base time é o tempo gasto na execução de código de um método, classe etc., de forma estrita, ou seja, sem incluir o tempo gasto em métodos disparados por este.
  • Cumulative Time é o tempo de execução de um método, acumulado ao tempo dos seus métodos-filhos.

Por exemplo, se o método m1() utiliza 5ms e invoca um método m2() que usa 3ms, então m1() tem tempo base de 5ms e cumulativo de 8ms. Na análise, ambos os tempos são importantes. O tempo base permite estimar a necessidade de otimizações "locais" (de métodos individuais), e o tempo cumulativo detecta problemas "globais", cuja otimização pode exigir mudanças em vários lugares.

  • Calls: Número de invocações a um método. Métodos rápidos, se invocados muitas vezes, podem ser importantes.

Além desses dados brutos, muitos profilers modernos também permitem visualizar a hierarquia de invocações, permitindo analisar a complexidade de uma atividade envolvendo muitos métodos. Esta análise pode sugerir melhorias estruturais, como combinar vários métodos correlacionados num único método (inlining manual), ou usar um algoritmo ou estrutura de dados mais simples.

Na Figura 1, podemos ver que o TPTP é especialmente bom para este tipo de análise, pois é capaz de gerar um diagrama de seqüência UML da execução do seu código. O diagrama ilustrado detalha o algoritmo Fanatic (o mais rápido no nosso estudo de caso): temos um método principal parseFanatic(), que invoca várias vezes o método auxiliar parseNN(), e finalmente o construtor de Date. É bem fácil avaliar a complexidade de um programa desta forma (o diagrama equivalente para o algoritmo SDF, se exibido sem nenhum filtro, tomaria esta revista inteira e ainda faltaria espaço).

Também podemos ver, na janela "Memory Statistics", dados sobre alocação de objetos, e em "Method Invocation Details", os métodos aferentes (que invocam um determinado método) e eferentes (que são invocados por este). Outras visualizações de dados estão disponíveis no TPTP e em outros profilers, mas em geral estas são as mais importantes: tempo de execução de métodos, objetos alocados, e algum tipo de visualização estrutural das seqüências ou árvores de invocação entre diferentes métodos.

Listagem 1. Construção de string ineficiente, com cópia de dados de saída.


public class Planeta {

  private String nome;

  private Satelite[] satelites;

  public String toXML () {

    StringBuilder sb = new StringBuilder("<planeta nome='");

    sb.append(nome).append("'>");

    for (int i = 0; i < satelites.length; ++i)

      sb.append("\n\t").append(satelites[i].toXML()); // Cópia!

    return sb.append("\n</planeta>").toString();

  }

}

 

public class Satelite {

  private String nome;

  public String toXML () {

    return "<satelite nome='" + nome + "'/>";

  }

}
Listagem 2. Construção de string eficiente, com streaming de dados de saída.


public class Planeta {

  private String nome;

  private Satelite[] satelites;

  public String toXML () {

    StringBuilder sb = new StringBuilder();

    toXML(sb);

    return sb.toString();

  }

  public void toXML (StringBuilder sb) {

    sb.append("<planeta nome='").append(nome).append("'>");

    for (int i = 0; i < satelites.length; ++i) {

      sb.append("\n\t");

      satelites[i].toXML(sb); // Sem cópia: usa mesmo buffer!

    }

    sb.append("\n</planeta>");

  }

}

 

public class Satelite {

  private String nome;

  public void toXML (StringBuilder sb) {

    sb.append("<satelite nome='").append(nome).append("'/>");

  }

}
Listagem 3. Parsing ineficiente, com cópia de dados de entrada.


public Mensagem parseMensagem (byte[] dados) {

  int tamComando = dados[0];

  String comando = new String(dados, 1, tamComando);

  byte[] dadosParam = new byte[dados.length - tamComando - 1]; // Mais cópia!

  System.arraycopy(dados, tamComando + 1, dadosParam, 0, dadosParam.length);

  Parametros param = parseParametros(dadosParam);

  return new Mensagem(comando, param);

}
Listagem 4. Parsing eficiente, com streaming de dados de entrada.


public Mensagem parseMensagem (ByteArrayInputStream dados)

    throws IOException

{

  byte[] bytesNome = new byte[dados.read()];

  dados.read(bytesNome);

  String comando = new String(bytesNome);

  Parametros param = parseParametros(dados); // Sem cópia!

  return new Mensagem(comando, param);

}
Listagem 5. Várias formas de ler o estado de um objeto.


public class TabelaPeriodica {

  private static final Atomo[] ATOMOS = {...};

  public static Atomo[] getAtomos1 () {

    return ATOMOS;

  }

  public static Atomo[] getAtomos2 () {

    Atomo[] a = new Atomo[ATOMOS.length];

    System.arraycopy(ATOMOS, 0, a, 0, a.length);

    return a;

  }

  public static List<Atomo> getAtomos3 () {

    return Collections.unmodifiableList(Arrays.asList(ATOMOS));

  }

}
Listagem 6. Otimizando Maps imutáveis, para os casos comuns de 0 e 1 elementos.


public <K,V> Map<K,V> otimizaMap (Map<K,V> map) {

  if (map.size() > 1)

    return map;

  else if (map.size() == 1) {

    Map.Entry<K,V> entry = map.entrySet().iterator().next();

    return Collections.singletonMap(entry.getKey(), entry.getValue());

  }

  else

    return Collections.emptyMap();

}
Listagem 7. Otimizando o parsing de datas.


Date data = new GregorianCalendar(1970,

  Integer.parseInt(str.substring(2, 4)),

  Integer.parseInt(str.substring(0, 2)) - 1,

  Integer.parseInt(str.substring(4, 6)),

  Integer.parseInt(str.substring(6, 8)),

  Integer.parseInt(str.substring(8, 10))).getTime();
Listagem 8. Eliminando trabalho repetido.


public class Poligono {

  private Point2D.Double[] pontos;

  private double area;

  public Matriz (Point2D.Double[] pontos) {

    this.pontos = pontos;

    calculaArea();

  }

  private void calculaArea () {

    // .. algoritmo complexo de cálculo de área

  }

  public double getArea () { return area; } // rapidinho!

}
Listagem 9. Caching e avaliação tardia.


public class Poligono {

  private Point2D.Double[] pontos;

  private double area;

  public Matriz (Point2D.Double[] pontos) {

    this.pontos = pontos;

    this.area = -1.0d; // Cache inicial inválido

  }

  private void calculaArea () {

    // .. algoritmo complexo de cálculo de área

  }

  public double getArea () {

    if (area < 0) // Cria o cache, somente se necessário

      calculaArea();

    return area;

  }

  public void set (int indice, Point2D.Double ponto) {

    area = -1.0d; // Invalida o cache

    pontos[indice] = ponto;

  }

}
Listagem 10. Identificando caminhos rápidos.

public TipoPalavra obtemCategoria (String palavra) {

  RegistroPalavra reg = Dicionario.get(palavra);

  if (reg != null)

    return reg.getCategoria();

  else if (palavra.endsWith("ar") || palavra.endsWith("er") || palavra.endsWith("ir"))

    return TipoPalavra.VERBO_INFINITIVO;

  else if (palavra.endsWith("ndo"))

    return TipoPalavra.VERBO_GERUNDIO;

  // ... mais um monte de condições ...

}