Esse artigo trata de otimizacoes e outras implementacoes para responder experimentalmente a probabilidade de tirar 3 caras em 5 jogadas de moeda de maneira confiavel que foi implementada em flipCoin3on5_notheoricalknowledge.go.
O problema das moedas é considerado Monte Carlo 101 e a utilizacao de um problema simples permite aprender sobre os temas relacionados a probabilidade para avançar com mais segurança.
Otimizações em flipCoin3on5_notheoricalknowledge.go
Metodo Batch x Incremental
Nosso algoritmo básico consiste em:
- Realizar totalSimulacoes de jogar 5X a moeda e tirar 3 caras.
- verificar as regras de parada/aceitação do resultado.
- se aprovado para o experimento.
- se não aprovado itera totalSimulacoes+stepSize e volta ao passo 1.
A cada iteração 1 o algoritmo executa de 0 a totalSimulacoes e por isso ele fica repetindo trabalho.
de 10Milhões de rodadas para 11Milhoes bastaria rodar mais 1 milhão de vezes, mas o algoritmo atual joga fora o conhecimento das 10 milhões de rodadas anteriores e começa do zero, jogando fora 90% do trabalho de executar 11milhões que ja estava realizado.
Vou refatorar para que mude esse comportamento de batch, de executar sempre todo o trabalho, para um comportamento incremental.
O resultado esta no diff do arquivo flibCoinExperiment.go e o impacto foi a redução do tempo de execução de 1m57,856s para 0m3,937s.
Gerador de jogar moeda.
A funcao lancaMoeda deixa claro como o programa funciona. Ela, assim como todo o algoritmo inicial, foi escrita para facilitar a leitura, porém existe espaço para a otimização da operação de lançar a moeda e contar as caras.
A ideia é alterar a maneira como o resultado de lancar a moeda é gerado e como ele é lido pela Rodada.
Utilizando math/rand
Substituir o lancamento da moeda em loop por uma unica chamada.
// 0= coroa, 1=cara
func lancaMoeda() int{
return rand.Intn(2)
}
for j := 0; j < lancamentosPorVez; j++ {
if lancaMoeda() == 1 {
carasNoExperimento++
}
}Vou utilizar math/rand para gerar um numero aleatorio de tamanho 5 contendo 0 |1’s e contar quantos 1 existem nesse numero. É a mesma ideia do loop.
Utilizando o gerador default do go utilize o seguinte código
const lancamentosPorVez = 5
// a operacao bitwise abaixo move lancamentosPorVez vezes o bit
// para a direita:00000001 << 5 = 32 => 00100000
// depois subtrai 1: 00100000 -1 =>= 31 => 00011111
const mascara = (1 << lancamentosPorVez) -1
// semeia a geração de aleatoriedade. Como ja vimos em outro artigo
// essa operação não deve ser realizada mais de uma vez.
rand.Seed(time.Now()/UnixNano())
// ao gerar um numero aleatório, digamos:
// 14 (01110)
//e aplicar um AND com o valor 00011111 (31 como mascara)
//estamos forçando uma situacao em que somente os
//ultimos 5 bits vão fazer parte da resposta (1&1=1, 0&1=0).
// 00001110 &
// 00011111
// 00001110 = 14
jogadas := rand.Uint32() & mascara
// se olhar para os bits temos 5 posicoes 0|1 (coroa|cara).
// se contar a quantidade de 1 como quantidade de caras
carasNoExperimento = bits.OnesCount32(res)
// e comparar com quantidade alvoCaras esperado
if carasNoExperimento == alvoCaras {
sucessos++
} Essa implementação troca 5 iteracoes no loop chamando um rand.Intn por uma única chamada de rand (rand.Uint32).
O tempo de execução foi de 0m3,937s para 0m0,836s
Porém, ainda tem espaço para otimização. O Randomizador default do Go foi desenhado para atender a todo o seu sistema de maneira transparente e para se proteger de concorrencia no caso de uso de rand em goroutines ele utiliza um mutex que da lock no valor. Esse mutex gera um delay sobre o qual voce pode ler mais aqui.
A solução é trocar o rand default por um rand privado, ou seja, um rand que não tem a preocupação de concorrencia e que por isso não utiliza um mutex.
const lancamentosPorVez = 5
const mascara = (1 << lancamentosPorVez) -1
r := rand.New(rand.NewSource(time.Now().UnixNano())
jogadas := r.Uint32() & mascara
carasNoExperimento = bits.OnesCount32(res)
// e comparar com quantidade alvoCaras esperado
if carasNoExperimento == alvoCaras {
sucessos++
} A otimização final fica então de 0m0,836s para 0m0,294s e voce pode ver o codigo nesse commit
Processamento paralelo com goroutine
Refactoring do código para paralelizar o processamento utilizando goroutines.
Sim, goroutines são concorrente por design, mas a ideia aqui não é fazer o processador ficar alterando entre tarefas; a ideia é dividir a tarefa entre os processadores lógicos disponíveis e assim garantir o paralelismo. Isso implica que maquinas com somente um core não irão se beneficiar dessa otimização e por isso deixei ela por ultimo.
Utilizando runtime.NumCPU() vamos saber quantas CPUs logicas temos disponível e a partir dai divido o tamanho da amostra entre os processadores(nao estou tratando o caso de divisao nao exata) e entrego a carga para uma goroutine.
A partir dessa informação, temos:
func rodadaParalela(simToRun int, totalSimulacoes int, sucessos int) (int, int) {
var wg sync.WaitGroup
numCPUs := runtime.NumCPU()
chunks := simToRun / numCPUs
var sucessosRodada int64 = int64(sucessos)
for c := 0; c < numCPUs; c++ {
wg.Add(1)
go func(n int) {
defer wg.Done()
r := rand.New(rand.NewSource(time.Now().UnixNano()))
localSucessos := 0
for i := 0; i < n; i++ {
res := r.Uint32() & mask
if bits.OnesCount32(res) == alvoCaras {
localSucessos++
}
}
atomic.AddInt64(&sucessosRodada, int64(localSucessos))
}(chunks)
}
wg.Wait()
return int(sucessosRodada), (totalSimulacoes + simToRun)
}essa otimização reduziu o tempo de processamento de 0m0,294s para 0m0,117s voce pode ver no commit
Removendo Prints
Enviar para stdout também consome um pouco de tempo. Essa otimização reduz de 0m0,117s para 0m0,091s e consiste em imprimir somente o resultado da otimização, removendo os printfs do caminho. Você pode ver o commit aqui
Era para parar por aqui, mas existe o custo de geração do numero randomizado. Acontence que até esse momento estou pagando o custo de gerar o numero e subutilizado o resultado.
Outra questão é que math/rand tem uma versão v2 que é explicada no artigo que já fiz referencia # Evolving the Go Standard Library with math/rand/v2
Espremendo o maximo!!!
Nessa última otimização são utilizados Loop Unrolling e o número randomico gerado é totalmente utilizado, o que significa que ao inves de gerar um número para cada iteração da rodada esse número passa a ser totalmente utilizado, extraindo 12 experimentos de 5 bits a cada vez.
func rodadaParalela(simToRun int, totalSimulacoes int, sucessos int) (int, int) {
var wg sync.WaitGroup
numCPUs := runtime.NumCPU()
iteracoesPorCPU := (simToRun / numCPUs) / 12
var sucessosGlobais int64 = int64(sucessos)
for c := 0; c < numCPUs; c++ {
wg.Add(1)
go func(n int, id int) {
defer wg.Done()
pcg := rand.NewPCG(uint64(time.Now().UnixNano()), uint64(id+1))
r := rand.New(pcg)
localSucessos := 0
for i := 0; i < n; i++ {
// Geramos 64 bits de uma vez
val := r.Uint64()
// 12 experimentos de 5 bits cada de um único número
// redução da carga sobre o gerador aleatório
if bits.OnesCount64(val & mask) == alvoCaras { localSucessos++ }
if bits.OnesCount64((val >> 5) & mask) == alvoCaras { localSucessos++ }
if bits.OnesCount64((val >> 10) & mask) == alvoCaras { localSucessos++ }
if bits.OnesCount64((val >> 15) & mask) == alvoCaras { localSucessos++ }
if bits.OnesCount64((val >> 20) & mask) == alvoCaras { localSucessos++ }
if bits.OnesCount64((val >> 25) & mask) == alvoCaras { localSucessos++ }
if bits.OnesCount64((val >> 30) & mask) == alvoCaras { localSucessos++ }
if bits.OnesCount64((val >> 35) & mask) == alvoCaras { localSucessos++ }
if bits.OnesCount64((val >> 40) & mask) == alvoCaras { localSucessos++ }
if bits.OnesCount64((val >> 45) & mask) == alvoCaras { localSucessos++ }
if bits.OnesCount64((val >> 50) & mask) == alvoCaras { localSucessos++ }
if bits.OnesCount64((val >> 55) & mask) == alvoCaras { localSucessos++ }
}
atomic.AddInt64(&sucessosGlobais, int64(localSucessos))
}(iteracoesPorCPU, c)
}
wg.Wait()
return int(sucessosGlobais), int(totalSimulacoes+simToRun)
} essa ultima otimização leva o tempo de execução de 0m0,117s para 0m0,041s e voce pode ver o commit aqui.
