Certamente em algum momento de sua jornada como desenvolvedor Java você deve ter se deparado com problemas de performance, e, se ainda não se deparou, é bom se preparar, pois esse pode ser um problema mais comum do que parece.
No artigo de hoje, vou apresentar algumas ferramentas para fazer benchmark da performance do seu código, e encontrar onde a lentidão ocorre.
Pontos importantes
Antes de começar a sair analisando todas suas aplicações e otimizando sua performance, é importante saber que antes de se considerar a hipótese de melhorar o desempenho de sua aplicação, você deve se perguntar se performance está realmente sendo um problema. Otimizar sem antes saber disso é um grande risco que estará correndo, você pode perder bastante tempo nessa tarefa e introduzir mais código sujeitos a bugs, e que irão dificultar a manutenção.
Então, quando exatamente isso se tornar necessário? A resposta é complicada, existem certos tipos de aplicações que dependem fortemente do desempenho, e quando ele não é bom o suficiente, isso se torna um problema crítico, no caso dessas aplicações, elas devem ser desenvolvidas sempre pensando nas melhores escolhas para ter desempenho e manutenibilidade. Essas aplicações precisam que testes de desempenho sejam feitos com certa frequência, ou até mesmo automatizados, o que é assunto para um outro artigo. Fora esses tipos de aplicações, as melhorias de performance acabam se tornando necessário quando o desempenho começa a afetar o usuário final de seu produto de forma negativa, como por exemplo, uma aplicação para troca de mensagens em tempo real que demora tempo de mais para entregar a mensagem ao destinatário, um processo de salvamento de mudanças de perfil que demora de mais para terminar, e assim por diante.
E quando não é necessário? A quantidade de casos que as melhorias não são necessárias são incrivelmente maiores do que a quantidade dos que são. Exemplo, se você tem uma plataforma que o servidor demora para iniciar mas depois disso não tem problemas (não tratando de serverless), ou sua aplicação precisa alocar recursos físicos para finalizar a operação, ou qualquer outro fator externo fora do seu controle que atrase a operação, a solução não será fazer otimizações no código, em casos específicos, como quando fatores externos afetam a performance, o melhor seria abordar o caso de outra maneira, como por exemplo, deixando o seu sistema assíncrono e informando o usuário sobre as tarefas rodando em segundo plano.
Tecnologias e ambiente
Agora chega de tanta falação (ou leitura teórica), vamos partir para as ferramentas disponíveis para analisar a performance. Neste artigo estaremos utilizando as seguintes tecnologias:
Nosso ambiente de desenvolvimento é o seguinte:
O Java 12 pode ser utilizado também em todos experimentos, ele foi utilizado nesse para rodar nossa aplicação e ativar o Profiling da VisualVM, que no momento que escrevi esse artigo, não tinha suporte para o Java 13. Entretanto, os testes de benchmark são rodados com o Java 13.
JMH (Java Microbenchmark Harness)
Esta é a principal ferramenta (ou conjunto de ferramentas) que iremos utilizar nesse artigo. Esse toolkit irá garantir que nossos benchmarks estão corretos, isso porque a máquina virtual Java tem uma série de peculiaridades que poderiam afetar seus benchmarks de diversas formas se fossem feitos sem a ferramenta.
O famoso loop calculando a média de tempo de um trecho de código não é uma boa maneira de se escrever um teste de desempenho para a JVM, da mesma maneira que ele pode apontar performance excepcional, ele pode apontar uma performance medíocre, e ambos casos podem estar totalmente errados.
VisualVM
Onde exatamente a lentidão está? Seria naquele loop onde processo cada um dos elementos individualmente? Ou no meu contains que verifica 1.000.000 de elementos tentando encontrar algum que seja semelhante? Ou nos dois lugares? A VisualVM irá nos ajudar a responder essas perguntas, dispondo de duas coisas: Sampling e Profiling. Esta ferramenta também nos ajuda a visualizar o uso de memória e de CPU, bem como outros detalhes, mas que não são o foco deste artigo.
Sampling
Nesse artigo não iremos utilizar o Sampling, esse método faz uma captura do estado da JVM em certos momentos, o que não é muito ideal para capturamos dados precisos, mas funciona muito bem pois é menos intrusivo.
Profiling
Iremos utilizar essa técnica, ela modifica nossas classes carregadas na JVM inserindo métodos que irão reportar as estatisticas ao VisualVM, trazendo dados mais precisos, mas também é mais intrusivo e pode não funcionar em aplicações específicas.
Usando o JMH
Primeiramente, você deve criar uma classe para residir os métodos que irão ser feitos os benchmark. Como estamos usando o plugin do JMH para o Gradle, temos que ter um diretório jmh dentro do src do projeto, como acontecem com os testes de unidade, que ficam no diretório test. E dentro do diretório jmh o diretório da linguagem que estamos usando, no caso java e depois, nossos pacotes e classes, do mesmo jeito que funciona os testes. Na nossa classe de benchmark, temos que anotar nossos métodos com as anotações do JMH, veja o exemplo abaixo:
Agora podemos rodar nossos benchmarks com o comando gradle jmh.
Nossa aplicação
Agora que sabemos o que estaremos utilizando, e como utilizar, é hora de testarmos algo prático. Vamos começar com um exemplo simples, suponhamos que estamos escrevendo uma aplicação que armazena dados de uma linhagem de gatos e que nós temos uma arvore com todos ascendentes de um gato em especifico. Além disso, cada gato também tem nome, gênero e uma uma identificação única, como se fosse um RG, nesse caso vamos usar um UUID gerado aleatóriamente.
Dada essa hierarquia, nós queremos agora buscar quem são os irmãos e meio irmãos de um gato específico, para isso escrevemos um algoritmo que verifica se um dos gatos tem a mesma mãe ou o pai do gato especificado:
Agora imagina que precisamos mostrar ao usuário os irmãos de cada um dos gatos que temos na lista. Umas das maneiras seriam: tendo outra classe que armazena os irmãos de cada gato e o próprio gato; tornando nossa classe de gatos mutável e adicionando os campos necessários para isso; ou armazenando os irmãos durante a criação do objeto. Nós vamos escolher a primeira opção (apenas por motivos didáticos).
Agora nós vamos criar o método que cria as instâncias dessa classe para cada gato da nossa lista:
Dado todos esses métodos, vamos analisar a performance de nossos algoritmos:
Dado um numero N de gatos, para cada um, percorremos N gatos e comparamos cada um com o atual para verificarmos se são irmãos. Mesmo usando Stream, podemos notar que caminhamos na lista duas vezes, sendo a primeira para mapear os gatos e salvar seus irmãos, e a segunda para buscar esses irmãos, a complexidade do nosso algoritmo é N ao quadrado.
Não vou abordar muito complexidade de algoritmo nesse artigo, se você tem maior interesse no tópico, você vai encontrar muito mais aqui.
Vamos então escrever nosso benchmark:
E agora vamos rodar e ver nossos resultados:
Disclaimer: apenas os resultados do benchmark não devem ser usados como verdade absoluta, os resultados dos testes são relativos e a análise de performance é um tópico muito vasto e complexo, existem diversas formas de mensurar a performance de um código e diversas maneiras de descobrir quando um algoritmo precisa ser melhorado ou não, lembrando que neste caso em específico, estamos tratando de um ambiente controlado e fizemos uma pequena análise da complexidade do nosso algoritmo, essas informações, junto ao resultado do benchmark, nos servem como métricas para chegarmos a nossa conclusão.
Os valores mudarão dependendo das especificações da máquina.
Agora imagine se nós dobramos o número de elementos da nossa lista de gatos, considerando a complexidade quadrática de nosso algoritmo, se fizermos um calculo proporcional, podemos encontrar a quantidade aproximada de operações que o algoritmo irá executar por segundo, veja a fórmula abaixo:
OP/s = O * ((1000²)/(Q²))
Sendo O o número médio de operações/s apontadas no benchmark (nesse caso: 103.911).
Sendo Q a quantidade de elementos.
Lembrando que essa fórmula não leva em consideração centenas de outras variáveis, como carga atual do sistema, temperatura do processador, decisões internas do kernel com relação a priorização dos processos, etc.
Mas antes de começarmos otimizar nosso algoritmo, devemos lembrar que em um ambiente comum, normalmente não saberemos onde o problema de performance estará, para isso, vamos usar o VisualVM para encontrar a fonte da lentidão do algoritmo. Antes disso, vamos preparar um caso onde consigamos pausar a execução, para que dê tempo de conectar a VisualVM:
E rodamos a aplicação.
Usando a VisualVM
Após abrirmos a VisualVM, na esquerda vamos ter varias entradas com as máquinas virtuais rodando, vamos escolher a que tem o nome de nossa classe, depois disso vamos na aba Profiling e escolhemos CPU. Se uma janela de calibragem abrir, apenas aperte Ok e espere a calibragem terminar.
No final teremos uma tela similar a essa, em CPU settings temos uma whitelist com pacotes que a VisualVM irá fazer profiling e quais ela deve excluir da exibição (ou incluir), dependendo da aplicação, você terá que configurar isso você mesmo. Na seção de Profiling results, teremos informações de todos métodos que foi feito o Profiling.
Voltando na aplicação, vamos apenas apertar Enter para continuar a execução, no final uma janela de dialogo como essa irá aparecer:
Apenas pressione Yes e uma captura dos dados será salva, veja abaixo:
Como podemos observar, temos 250.000 chamadas do nosso método, como configuramos para 500 elementos, e a complexidade é quadrática, se obter o quadrado de 500 teremos exatamente esse valor. Alias, se observar nós temos uma chamada de lambda com o valor de 250.000, mas outra chamada com 249.500, isso porque um dos nossos filter exclui os elementos que são iguais ao atual (o primeiro filter), esse é chamado o total de vezes que calculamos, já o segundo será chamado menos que o primeiro devido a isso (se notar, são exatamente 500 vezes a menos).
Vamos agora utilizar um total de 2000 elementos, mas dessa vez sem cerimônia, vamos direto aos resultados:
Como podemos observar, são 4.000.000 de invocações agora, e o tempo total de execução chega quase aos 3 segundos, mesmo a quantidade de elementos ainda sendo pequena. E o método que demorou mais tempo foi exatamente o getSibligns.
Otimizando
Agora que encontramos exatamente onde o problema está, vamos otimizar nosso algoritmo. Mas, como?
Existem várias maneiras de otimizar nosso algoritmo, nesse artigo vamos explorar um deles. Até então, percebemos que cada iteração tem um custo total dela vezes a quantidade de elementos da lista. Se você precisa de 1 elemento de uma lista de 1000, o custo dela é 1*1000, se precisa de 2, 2*1000, se precisar de todos, 1000*1000.
Nossa abordagem
A mais simples abordagem é utilizando um HashMap mais uma implementação própria de Set com filtro. O maior problema do nosso algoritmo é que temos duas iterações, uma encadeada na outra. Uma das formas de separar duas iterações encadeadas em uma só, é utilizando um HashMap, primeiro vamos construir um mapa que contem uma ligação de Mãe-Filhos e Pai-Filhos:
O mesmo pode ser feito com um simples for-loop, mas como estivemos utilizando Stream no artigo todo, vamos manter isso para não ter nossos resultados afetados pela mudança.
Nesse caso, temos que criar nosso próprio Collector que extrai duas chaves de um mapa, isso pois os Collectors convencionais disponíveis podem extrair apenas uma chave.
Agora que temos uma relação de Pais-filhos, o que nos permite obter todos os filhos de uma mãe ou pai. Como cada mãe e pai é um elemento único que não se repete, nós podemos guardar ambos no mesmo mapa e eles não irão se sobrescrever. Então, quando buscarmos os filhos com base na chave de mãe e pai, ele irá aparecer nas duas coleções, veja o diagrama de relação abaixo:
Molly e Tiger são meio irmãos por parte de Pai. Garfield, Scot e Tiger por parte de mãe. Garfield e Scot são filhos dos mesmos pais. No fim nós teremos a seguinte relação chave-valor no mapa:
Sacha -> Molly
Simba -> Tiger, Molly
Misty -> Tiger, Garfield, Scot
Sam -> Garfield, Scot
Note agora que se estivermos trabalhando com Molly e pegarmos os filhos de sua mãe e seu pai, obtemos seu meio irmão Tiger, mas se estivermos tratando de Tiger, ao pegar os filhos de seu pai e sua mãe, encontramos sua meia irmã Molly e seus meio irmãos Garfield e Scot. Com base nesse mapa, apenas precisamos juntar os filhos da mãe e do pai do elemento atual. Entretanto, se olharmos bem a relação, ao tratar de Garfield, quando pegarmos sua mãe e seu pai, vamos encontrar seu irmão Scot duas vezes, sem contar que ainda encontramos o próprio Garfield duas vezes.
O que poderíamos pensar de forma óbvia seria: vamos então filtrar os elementos duplicados, tirar o próprio elemento tratado, e criar uma nova lista com os irmãos dele. Só que note que precisaremos criar uma nova lista, além de ter que filtrar os próprios elementos, mesmo que usando um Set - que tem uma complexidade média constante (O(1)) - copiar elementos de uma coleção para outra envolve duplicar a memória, e essa operação é linear (O(n)) e nós já estaremos dentro de um loop, então acabariamos com uma complexidade quadrática novamente e com mais código.
Então o que podemos fazer?
Uma boa solução para esse caso seria criar um Set com filtro, que une o Set de filhos de pais e o Set de filhos de mãe e filtra os elementos que forem iguais ao elemento atual, tudo isso sem copiar os dados em nenhum momento. Vamos usar um AbstractSet e implementar nosso próprio Iterator.
Lembrando que implementar sua própria coleção deve ser feito com bastante calma e deve se ter conhecimento do comportamento que se espera dela, e ela deve ser bem documentada. Essa é uma tarefa complicada, mas que raramente você precisará fazer.
E agora na nossa função que obtém os irmãos do gato, nós criamos esse Set usando os valores do Mapa de relações:
Isso acarreta em algumas mudanças na classes CatSiblings, como mudar de um List para um Set, mas não falarei dessas mudanças por serem triviais.
Performance Final
Agora vamos testar a performance de nossas mudanças:
Olhando estes resultados, podemos ver uma melhora extremamente considerável em nossos testes de benchmark, mesmo se aumentar a quantidade de elementos, a performance ainda será boa. Nós conseguimos diminuir a complexidade do nosso algoritmo de quadratica para linear, e diminuimos a quantidade de copias de coleções que criamos para cada nova instância de irmãos de gatos. Se você tem curiosidade, nossa fórmula para calular as operações agora seria:
OP/s = O*(1000/Q)
Sendo O o número médio de operações/s relatadas no benchmark (nesse caso: 2822.754).
Sendo Q o número de elementos.
Informação importante: Nosso gerador de gatos é bastante simples, já que todos os gatos tem mãe e pai nulo, fazendo deles irmãos uns dos outros, mas sem ligação com nenhuma mãe ou pai real, podemos tratar isso em nosso código, mas para isso antes precisaríamos de um gerador de gatos mais robusto, podendo gerar linhagens mais complexas, mas isso levaria um tempo considerável para algo que não é tão relevante para nossos testes atuais.
Conclusão
Apesar das melhorias que fizemos, nosso código ainda tem vários problemas que podem ser abordados de outra maneira, como por exemplo, usar uma estrutura de dados de árvore. Mas o foco do artigo é mostrar o efeito das melhorias de performance nos nossos testes de benchmark e como encontrar o foco dos problemas de performance, e não detalhes de melhoria de performance, isso pode ser assunto para outro artigo.
Como vimos, podemos utilizar o JMH, VisualVM mais uma análise de complexidade de algoritmo para descobrir a performance do nosso código e servir para estudos de como melhorar sua performance.
O caso de problema apresentado nesse artigo tem como foco o teste de benchmark e o uso da VisualVM e não foca nos casos práticos que podem ser encontrados no dia-a-dia. Cada caso deve ser avaliado minuciosamente e bem estudado para descobrir qual a melhor abordagem para melhorar sua performance, e se isso é realmente necessário.
