Uma primeira experiência com a linguagem Julia

Imaginem a seguinte situação: Existe um grilo no jardim e o mesmo pula de forma aleatória. Basicamente ele escolhe um ângulo e pula. Escolhe outro ângulo e pula mais uma vez. E assim segue, até o momento que ele cansa. Desejamos responder a pergunta sobre qual a localização do grilo após os muitos pulos dados por ele.

Uma das muitas opções de resolver este problema (e acredito que a mais simples) é simular os respectivos pulos do grilo muitas vezes e ver onde foi a posição final. Simples assim.
Inicialmente foi implementada uma solução escrita em R, menos de 20 linhas, e como era de esperar, o desempenho não foi um dos pontos fortes (demorou cerca de 30 minutos). Então veio a assombrosa pergunta que paira a cabeça de 
Um exemplo do grilo dando 5 pulos.
todos: Tem como fazer melhor? E é claro, a resposta é sim !



Sobre a implementação em si não teria muito o que mudar, afinal o código já não tinha nenhum for ou while, todas as operações ou eram vetoriais ou estavam sendo feitas com a utilização de funções de alta ordem (os famosos applys). Então tive a ideia de executar o código em paralelo, utilizando os muitos núcleos de um HPC (High Performance Computer) que tenho acesso. A adaptação foi relativamente simples, dado que o código já estava utilizando os applys. Tudo que tinha que ser feito era trocar o lapply por um mclapply (que faz parte do pacote multicore). Adaptações feitas. No meu modesto computador utilizando 4 cores, o código passou a demorar 17 minutos ! Bela melhora, pensei. O próximo passo foi executar o código diretamente no HPC, afinal lá teria acesso a 12 cores. O novo tempo? 5 minutos ! Surpreendente, pensei. Estava simulando 100.000 vezes o grilo pulando 1.000 vezes. Isto dá um total de 100 milhões de operações pelo menos. Então novamente veio a pergunta a cabeça: Dá para fazer melhor? Inicialmente pensei em implementar o problema utilizando Python, mas foi neste momento que lembrei da linguagem Julia, que era tão comentada por sua incrível performance em computação científica.

Acessei o site e comecei a ler a documentação. Não tinha muito o que fazer, ou aprender. Tinha um problema e tinha que resolvê-lo. Li o básico sobre criação e tipos de objetos e lá fui eu com a mão na massa. Após cerca de 3 horas, tinha terminado a implementação. Algo próximo de 40 linhas. Então chegou a hora da verdade. Executei esperando pelo menos os 5 minutos alcançados pelo R sendo executado em 12 cores. Me decepcionei, afinal demorou apenas 30 segundos !

Novamente veio a pergunta a cabeça: Dá para fazer melhor? Então comecei a implementação utilizando Python, apenas curiosidade. Após feito, lá estava o resultado: 200 segundos. Porém não parou por aí, afinal Julia utiliza um compilador JIT (just-in-time) . Resolvi reescrever o código em Python utilizando um JIT para Python que é o pypy. Então aí que veio a surpresa: 10 segundos. Sem dúvidas este é um belo tempo, comparado aos 30 minutos iniciais.

Apesar de ter conseguido tempos de execuções razoavelmente bons, a grande pergunta ainda martela a minha cabeça: Dá para fazer melhor? Provavelmente sim, em especial utilizando o R. Nas próximas semanas vou ver como posso melhorar o código, talvez utilizar um compilador JIT também ajude. Claro que não espero bater os 10 segundos do pypy, mas se fizer em menor de 1 minuto vai ser uma boa performance. Sobre a linguagem Julia, que bela impressão que tive, afinal sem fazer muitos esforços ou otimizar o código consegui 30 segundos executando em single core.

Bom, e para quem ficou curioso sobre a posição final do grilo, aqui vai um heatmap com a posição (x,y) e a freqûencia. 



Os códigos fontes nas diversas linguagens podem ser achados aqui

:)


12 comentários:

  1. Muito bom, gostei da forma que escreveu!

    ResponderExcluir
  2. Respostas
    1. Tem ideia do quanto o desempenho poderia melhorar?

      Excluir
  3. Acho que o topo seria programar em Assembly utilizando os registradores do processador.

    ResponderExcluir
    Respostas
    1. Mas será que o ganho de performance compensaria o trabalho total?

      Excluir
    2. Extamente! Esse trade-off tem que ser pensando antes sempre.

      https://xkcd.com/1319/

      Excluir
  4. Bem legal o seu post, Evandro. Uma coisa que todo mundo tem que ter em mente é que o tempo total que a pessoa quer minimizar não é só o tempo de execução. Tempo total = (tempo pensando em como escrever) + (tempo escrevendo) + (tempo arrumando os dados) + (tempo debugando) + (tempo de execução) + (tempo de manutenção do código). Então às vezes uma linguagem pode ser muito rápida em um desses componentes, mas extramemente lenta em outros (você gasta o dobro do tempo escrevendo, elaborando o código e debugando e pena para fazer manutenção. Abs

    ResponderExcluir
    Respostas
    1. Sem dúvidas, Carlos. Estas linguagens de alto nível possuem a vantagem de ter uma sintaxe bem simples de entender. E acho que isto pesa um pouco em relação ao R, pelo fato de que para escrever uma função otimizada tem que usar uma série de artifíios, como operações vetorias e substituir loops convencionais pelos famosos applys, enquanto que em Julia e Python dá pra operar naturalmente dentro dos loops.

      Excluir
  5. Dá pra fazer melhor ainda, você pode criar um modelo matemático que retorna a distribuição sem precisar de simulação! A minha intuição é que se o número de pulos for para infinito, então o resultado é uma gaussiana centrada na posição inicial. Mas é chute meu, teria que fazer as contas.

    ResponderExcluir
    Respostas
    1. O resultado é uma gaussiana, de fato. Porém a grande vantagem de fazer isto via simulação é que esta é uma tarefa trivial, enquanto que resolver analiticamente pode ser complicado.

      Excluir
    2. Pensando melhor eu acho que no infinito não é uma gaussiana não, é uniforme no espaço inteiro. Começa como uma gaussiana, mas aí vai abrindo, abrindo, até que a variância é infinita.

      Excluir
  6. Assim como sugerido, eu também pensei: e Assembly.?! rs... Fica a dica (ou seria o desafio?!). rsrsrs...

    ResponderExcluir