Otimização de programas

Tive um problema de programação neste fim de semana. Era algo funcionava tão lentamente, mas que eu achei uma solução simples, porém tão efetiva, para otimizar, que preciso compartilhar aqui.

Eu tinha que simular uma cadeia de Markov. Não é meu objetivo aqui explicar o que é uma cadeia de Markov. Basta que vocês saibam que, ao final da minha simulação, eu teria uma matriz de tamanho 5000000 por 14.

Isso mesmo: 5 milhões por 14.

Qualquer um pode ver que é muita coisa.

A primeira versão do meu programa funcionava muito bem. Quer dizer, funcionava muito bem no sentido de convergir para os valores que eu esperava. O problema é que demorava muito.

Para vocês terem uma ideia, na primeira vez em que fiz o programa rodar, ele levou 8 horas pra fazer 160 mil iterações. Com esta velocidade, eu minha simulação não terminaria até o dia seguinte (aka prazo final).

O pior é que o tempo de execução do programa era não-linear.

Explico.

Quando algo é linear, como por exemplo deslocar-se a uma velocidade constante, para cada unidade que tu aumenta numa unidade, tu aumenta x unidades na outra. Quem só caminha a 6km/h, por exemplo, leva uma hora para caminhar 6km, duas horas pra caminhar 12km, 10 horas pra caminhar 60km.

Meu programa não era assim. Se ele rodava mil iterações em 10 segundos, ele estava levando 600 segundos pra rodar 10 mil, em vez dos 100 que se esperaria de algo linear.

E quanto mais iterações ele fazia, mais lento ele ficava. Se havia levado 8 horas pra rodar 160 mil vezes, para as 5 milhões de iterações que eu precisava, eu teria que esperar uns 318 anos para ter os resultados. Imaginem: um ano pra cada pastor que a Igreja Universal manda pra Israel para participar da fogueira santa.

Mas aí li e reli o código, removi uns dois comandos redundantes, loops dentro de loops e tudo o que mais eu pude. A velocidade baixou para a metade, o que ainda não era ideal.

E foi aí que dei o pulo do gato. Se o gargalo era a memória RAM, tratei de acabar com isto. Como o programa rodava muito bem para mil iterações, resolvi que, a cada milhar, eu escreveria os resultados obtidos até o momento num arquivo texto e reiniciaria minha matriz do zero. Assim, a cada mil iterações eu praticamente zeraria a memória da máquina, mas sem perder o que tinha feito até o momento.

Mas não valeria a pena utilizar apenas escalares, em vez de uma matriz de tamanho 1000 por 14 para armazenar os dados, porque a memória RAM trabalha mais rápido que o acesso ao disco. Assim, escrever no arquivo texto a cada iteração poderia deixar meu programa ainda mais lento. O ideal, como fiz, seria trabalhar com blocos. Usar a memória RAM enquanto ela fosse rápida e passar escrever no disco quando ela se tornasse muito lenta.

Obviamente, deve haver um valor ótimo para o bloco. Provavelmente não é 1000, como o que usei, mas com certeza há um valor para o tamanho de bloco que faça meu programa rodar ainda mais rápido.

Assim, com esta técnica simples, baixei ainda mais o tempo de execução. Para rodar as 5 milhões de vezes que eu precisava, levei 2 horas e meia, 1/3 do tempo que precisei para rodar “apenas” 160 mil iterações com o código velho.