Otimizando aplicações simples em Go

Após uns 6 meses estudando essa linguagem, confesso que estou bastante empolgado. Vasto material de estudo, comunidade solícita e a performance das aplicações produzidas é impressionante!

A ideia desse artigo começou quando ouvi um colega reclamando de dificuldades com uma tarefa bastante básica: ele estava usando um “gerador de combinações” para jogos de sorteio (como a megasena) e o windows dele travou. Segundo ele, porque estava gerando todas as possíveis combinações, isso consumia muita memória e, em alguns casos, gerava arquivos com quase 3Gb. Discordei na hora do motivo e decidi tomar para mim o desafio!

No caso da megasena, um volante pode ser marcado com 6 ou mais números, sendo que a quantidade de combinações aumenta como um “fatorial”. 6 números combinados 6 a 6 só geram uma combinação, 7 números geram 7, 8 números geram 28… Lembrando que, não pode haver repetições e que mudar a ordem não afeta a quantidade de combinações resultantes.

Um exemplo com proporções menores. Imaginem que temos uma lista com os dígitos de 1 a 5 para combinar 3 a 3 (N=3). Ficaria assim:

1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5

O meu código original recebia a lista e a quantidade de posições como parâmetros, validava-os e ordenava a lista antes de processá-la.

Para simplificar este exercício e para termos uma quantidade razoável de processamento e escrita em disco, coloquei valores fictícios direto no código. Uma lista de 32 números que serão combinados 8 a 8.

A primeira versão do código parecia com essa:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

package main

import "fmt"

func combine(nums []int, list map[int]int, start, end, index, size int) {
    if index == size {
        for j := 0; j < size; j++ {
            fmt.Printf(" %2d", list[j])
        }
        fmt.Println("")
        return
    }

    for i := start; i <= end && end >= size-index; i++ {
        list[index] = nums[i]
        combine(nums, list, i+1, end, index+1, size)
    }
}

func main() {
    size := 8
    nums := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16,
        17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32}
    list := make(map[int]int)
    combine(nums, list, 0, len(nums)-1, 0, size)
}

Nos próximos códigos, inibirei algumas linhas para focar no que interessa.

A saída gerada é enviada direto para a saída padrão (terminal). Para salvar num arquivo basta redirecionar assim: “./loteria > output.txt”. Nessa primeira versão, o arquivo ficou com 251Mb e o processo durava cerca de 2 minutos.

De cara, vi que dava pra melhorar e lembrei de uma dica da comunidade go-br do telegram1. Usar o pacote “bufio” para operações de IO. Daí chegamos nessa versão:

 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

func combine(nums []int, list map[int]int, start, end, index, size int) {
    if index == size {
        for j := 0; j < size; j++ {
            fmt.Fprint(writer, " ", list[j])
        }
        fmt.Fprintln(writer, "")
        return
    }

    for i := start; i <= end && end >= size-index; i++ {
        list[index] = nums[i]
        combine(nums, list, i+1, end, index+1, size)
    }
}

var writer *bufio.Writer

func main() {
    size := 8
    nums := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16,
        17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32}
    list := make(map[int]int, size)
    writer = bufio.NewWriter(os.Stdout)
    combine(nums, list, 0, len(nums)-1, 0, size)
    writer.Flush()
}

Apenas algumas linhas alteradas e o tempo já caiu para 10,5 SEGUNDOS! Já foi um ótimo avanço, mas aí eu já estava viciado e queria mais!

Usando uma ferramenta do próprio linux, o perf2, percebi que a Função Fprintf (linhas 12 e 14) estavam consumindo bastante tempo de CPU e optei por uma saída mais simples trocando para Fprint, o tempo caiu para 9,8 segundos e de quebra, com a diminuição dos espaços em branco o tamanho do arquivo foi para 229Mb.

Também troquei o “map[int]int” da linha 29 por um “[]int” (slice) e ganhei mais 1 segundo.

Percebi também que bufio.Writer tinha uma função WriteString e resolvi experimentar. Para a minha surpresa o tempo caiu para 2,6 segundos!

Com essas 3 alterações, meu arquivo ficou assim:

 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

func combine(nums []int, list []int, start, end, index, size int) {
    if index == size {
        for j := 0; j < size; j++ {
            writer.WriteString(" ", strconv.Itoa(list[j]))
        }
        writer.WriteString("\n")
        return
    }

    for i := start; i <= end && end >= size-index; i++ {
        list[index] = nums[i]
        combine(nums, list, i+1, end, index+1, size)
    }
}

var writer *bufio.Writer

func main() {
    size := 8
    nums := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16,
        17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32}
    list := make([]int, size)
    writer = bufio.NewWriter(os.Stdout)
    combine(nums, list, 0, len(nums)-1, 0, size)
    writer.Flush()
}

Mais uma vez, consultando os gurus do grupo de estudos, a galera me sugeriu a ferramenta pprof3 (nativa do Go). Esta apontou que a função strconv.Itoa da linha 12 era a vilã atual. Então pensei, já que não estou fazendo operações matemáticas com esse números, eles poderiam ser strings desde o começo e eu evitaria essa conversão. 2,4 segundos.

Também não tinha por que concatenar aquele espaço na frente do primeiro caractere. Um simples “if” resolveu. Como isso diminui a saída, ganhamos em performance também (além de economizar espaço em disco). 1,25s.

Aqui estão alguns gráficos que gerei:

gráfico estruturado mostrando o tempo de execução consumido por cada função do código

figura 4: Primeira versão. Gerado pelo pprof. Tempo de execução 130s

gráfico estruturado mostrando o tempo de execução consumido por cada função do código

Versão final otimizada (até agora). Gerado pelo pprof. Tempo de execução 1,40s

flamegraph mostrando o tempo consumido por cada parte do código

Versão final (até agora). Gerado a partir da análise do perf.

Conclusão. Reduzi o tempo de execução para perto de 1%. 100X MAIS RÁPIDO! Na maioria das máquinas, o limite agora deverá estar na escrita em disco. Pra quem tem um SSD com conexão PCIexpress, pode ser que o gargalo ainda seja processamento.

Quem quiser dar uma olhada ou até me mandar um “pull request” com melhorias, o código está no github4. Atualizarei este artigo sempre que aparecerem melhorias e citarei os colaboradores.

Ainda tentei usar uma goroutine separada só pra escrever no buffer, aumentar o tamanho desse buffer, channels… Não consegui melhorar, mas também não posso dizer que já domino bem essas técnicas. Talvez esperar escrever bastante em memória e em intervalos razoáveis, mandar tudo pro disco (antes que estoure o uso de memória)…

Aguardo sugestões e/ou dúvidas.

  1. Grupo do telegram: https://t.me/go_br ↩︎

  2. Perf: https://jvns.ca/perf-zine.pdf ↩︎

  3. Pprof: https://blog.golang.org/profiling-go-programs ↩︎

  4. Projeto no github: https://github.com/hitalos/exercicio-loteria ↩︎