Eu costumava pensar que conhecia as leis de otimização de código. Na minha opinião (não tão) humilde, elas eram:
- Faça um diagrama UML antes de otimizar
- Depois que o diagrama te disser qual é o problema, tente uma melhor estratégia (estrutura ou algoritmo de dados)
- Ajuste o código como um último recurso
Existe um raciocínio puramente econômico que está por trás disso: se seu código não é rápido o suficiente, primeiro, encontre o principal culpado e elimine-o. Removendo-o, você adiciona valor, e ao usar algo mais rentável, ganha mais. Pequenos ajustes no código ou mudando para uma linguagem de programação de mais baixo nível, só oferece fatores de melhoria, então, se você puder escolher, use a maior arma.
Suponha, como exemplo, que o diagrama que revela o seu custo pode ser escrito assim:
Cost = 0.8 * BiggestCulprit + 0.2 * EverythingElse
Você sabe o que fazer: matar o BiggestCulprit. A propósito, Pareto diz que é geralmente algo assim (80-20). Ok, utilizando um grande martelo você substituiu o BiggestCulprit com algo que é 100 vezes mais barato.
Cost2 = 0.8 * 0.01 * BiggestCulprit + 0.2 * EverythingElse = 0.208 * Cost
Se você precisar ir ainda mais rápido, você deve tentar otimizarEverythingElse. Você pode fazer isso? Depende. Talvez você possa dividir EverythingElse em
EverythingElse = 0.8 * TheNextHurdle + 0.2 * NotInteresting
Se você não pode, ele termina aqui.
A estratégia é racional, mas às vezes o diagrama aponta para a direção errada.
Um exemplo de um erro que cometi
O que segue abaixo é um relato do que aconteceu com uma parte do código durante um período de dois anos. Espero que você, ao ler sobre isso, conclua que os erros eram óbvios, mas, na época, eles não foram. A experiência mostra 20/20.
O problema
Como um pequeno passo na resolução de um problema maior, nós precisamos gerar um exemplo de tamanho n de um conjunto de tamanho p. Detalhe importante: nenhum valor pode ser escolhido mais de uma vez.
O tamanho da população (p) está mais ou menos em algum lugar entre 4000 e 16000, enquanto que o tamanho do exemplo é geralmente muito pequeno, às vezes mais do que 2000, mas nunca mais do que 2500 (conhecemos a sua distribuição).
Vamos analisar o problema de forma isolada. O código mostrado abaixo é um microbenchmark que é representativo para o nosso caso, e estamos interessados em minimizar o tempo total de execução, melhorando a implementação do módulo Sampler.
let micro_bench ns k p =
let test_one n =
let sample = Sampler.create n p in
let use_choice _ = () in
let rec loop k =
if k = 0
then ()
else
begin
if k mod 1000 = 0 then Printf.eprintf ".%!";
let () = Sampler.fill_sample sample n p in
let () = Sampler.iter sample use_choice in
let () = Sampler.clear_sample sample in
loop (k-1)
end
in
let t0 = Unix.gettimeofday() in
let () = loop k in
let t1 = Unix.gettimeofday() in
let d = t1 -. t0 in
Printf.printf "%i | %f \n" n d
in
List.iter test_one ns;;
let main () =
let k = 100 * 1000 in
let p = 10000 in
micro_bench [1;2;3;4;5;6;7;8;9;10;20;40;80;160;320;640;1000;2000;2500] k p;;
let () = main ();;
A nossa solução deve seguir a seguinte assinatura:
module type S = sig type t val create : int -> int -> t val fill_sample: t -> int -> int -> unit val clear_sample: t -> unit val iter: t -> (int -> unit) -> unit end
A primeira solução, a que eu codei em busca de correção e simplicidade, era exatamente assim, simples e correta:
module S0 = (struct
type t = {mutable c: int; es:int array}
let create n p = {c = 0; es = Array.make n 0}
let in_sample t x =
let rec loop i =
if i < 0 then false
else
if t.es.(i) = x
then true
else loop (i-1)
in
loop (t.c -1)
let add2_sample t x =
let i = t.c in
t.es.(i) <- x;
t.c <- i+1
let fill_sample sample n p =
let rec loop i =
if i = 0
then ()
else
let rec find_new () =
let x = random_range p in
if in_sample sample x
then find_new()
else add2_sample sample x
in
let () = find_new () in
loop (i-1)
in
loop n
let clear_sample t = t.c <- 0
let iter t f =
let rec loop i =
if i = t.c
then ()
else
let () = f t.es.(i) in
loop (i+1)
in
loop 0
end : S)
O exemplo é acumulada em um array, e testamos cada candidato para ver se já temos isso. Se já tivermos, a gente tenta de novo. Limpar o exemplo é colocar o contador a zero, e a iteração está meramente iterando a parte utilizada do array. Bem simples, e suficiente por quase 6 meses. A execução do microbenchmark (leva alguns segundos 1700) revela o que está acontecendo:
1 | 0.017802 2 | 0.017753 3 | 0.025648 4 | 0.033298 5 | 0.040910 6 | 0.050635 7 | 0.056496 8 | 0.065127 9 | 0.073126 10 | 0.081244 20 | 0.170436 40 | 0.402476 80 | 1.060872 160 | 3.131289 320 | 10.381503 640 | 36.543450 1000 | 85.969717 2000 | 408.716565 2500 | 1127.268196
A primeira coluna é o tamanho do exemplo, a segunda é o tempo necessário para 100.000 exemplos. Como você pode ver, é muito rápido para pequenos exemplos, mas rapidamente sucumbe. O diagrama mostra que é culpa da função in_sample. É preciso analisar todo o array do exemplo até o momento. Ele fica ainda pior com a chance de escolher um elemento que foi escolhido antes de aumentar.
Bem, não é tão difícil ter um teste de melhor adesão. O tamanho da população não é tão grande, por isso podemos bancar um BitSet. A adição de um membro em O(1), o teste de adesão em O(1)…Vamos fazê-lo, ele deve voar.
module S1 = (struct
type t = bool array
let create n p = Array.make p false
let in_sample t x = t.(x)
let add2_sample t x = t.(x) <- true
let clear_sample t =
let rec loop i =
if i < 0 then ()
else
let () = t.(i) <- false in
loop (i-1)
in
loop (Array.length t -1)
let fill_sample sample n p =
let rec loop i =
if i = 0
then ()
else
let rec find_new () =
let x = random_range p in
if in_sample sample x
then find_new()
else add2_sample sample x
in
let () = find_new () in
loop (i-1)
in
loop n
let iter t f =
let s = Array.length t in
let rec loop i =
if i = s then ()
else
let () = if t.(i) then f i in
loop (i+1)
in
loop 0
end : S)
Vamos ver o que ele faz:
1 | 3.760345 2 | 3.716187 3 | 3.730672 4 | 3.795472 5 | 3.799934 6 | 3.961258 7 | 3.804574 8 | 3.775391 9 | 3.807858 10 | 3.914987 20 | 3.949764 40 | 4.159262 80 | 4.430131 160 | 4.953897 320 | 6.132642 640 | 8.438193 1000 | 11.140795 2000 | 19.150232 2500 | 23.508719
Leva alguns 124 segundos para executá-lo. No geral, é mais de 10 vezes mais rápido, mas os exemplos pequenos estão muito mais lentos. O que aconteceu?
Uma análise mais atenta (com o diagrama) revelou duas coisas:
- Limpar a bitset é O(p)
- Iteração do bitset também é O(p)
Então tentamos resolver isso usando uma representação melhor de um bitset. Um array de palavras com 64 bits. Limpar é muito mais rápido lá.
A iteração também será mais rápida, já que o bitset deverá ser escasso, e pode avançar, inspecionando os numberOfTrailingZeroes.
Nós otimizamos o clearing do bitset, e envolvemos em sequências De Bruijn para iteração super rápida. É muito assunto, e talvez interessante o suficiente para outro artigo. A razão pela qual eu não estou divagando aqui é que era o caminho errado a seguir.
No final, depois de um longo desvio, nos estabelecemos em uma estratégia completamente diferente: sparse sets.
module S2 = (struct
type t = { mutable n: int;
mutable dense: int array;
mutable sparse: int array;}
let create n p =
{ n = 0;
dense = Array.make p 0;
sparse = Array.make p 0;
}
let add2_sample t x =
let n = t.n in
t.dense.(n) <- x;
t.sparse.(x) <- n;
t.n <- (n+1)
let in_sample t x =
let rsi = t.sparse.(x) in
let ok = rsi < t.n in
ok && (t.dense.(rsi) = x)
let iter t f =
let n = t.n in
let rec loop i =
if i = n then ()
else
let x = t.dense.(i) in
let () = f x in
loop (i+1)
in
loop 0
let clear_sample t = t.n <- 0
let fill_sample sample n p =
let rec loop i =
if i = 0
then ()
else
let rec find_new () =
let x = R.random_range p in
if in_sample sample x
then find_new()
else add2_sample sample x
in
let () = find_new () in
loop (i-1)
in
loop n
end: S)
Vamos ver o que este faz:
1 | 0.019265 2 | 0.021046 3 | 0.030151 4 | 0.034281 5 | 0.040782 6 | 0.048158 7 | 0.055332 8 | 0.061747 9 | 0.068712 10 | 0.075462 20 | 0.144088 40 | 0.276297 80 | 0.539943 160 | 1.069994 320 | 2.143328 640 | 4.334955 1000 | 6.893774 2000 | 14.607145 2500 | 18.819379
Ele roda em menos de um minuto, e tem a ordem desejada de magnitude para nossas operações (adição, teste, clearing, iteração).
Enquanto isso, se precisar voltar aqui, eu tenho um às na manga: sempre posso usar um caso especial – se o tamanho do exemplo estiver no limite do SO, então use algo mais adequado para exemplos maiores.
Isso vai me dar o melhor de ambos os mundos ao custo de feiúra.
Meu erro
Você já descobriu o que eu fiz de errado estrategicamente? No exemplo acima, fiz isso várias vezes: eu permiti ao diagrama definir o scope dos meus esforços de otimização. Diagramas UML são excelentes para descobrir gargalos e os possíveis ganhos de removê-los, mas vai te dar uma espécie de limitação na sua visão do código, o que limita o grau de sucesso. Uma vez que você descobriu um gargalo, você precisa voltar um passo atrás, e também olhar o contexto. Quanto maior o trecho que você otimizar, maiores os ganhos possíveis. No meu caso real, eu deveria estar procurando um método melhor de exemplo.
Em vez disso, eu procurei por um melhor conjunto de representação. O problema é que você tende a encontrar o que está procurando.
Armado com a nova visão, proponho as seguintes leis de otimização.
- Faça um diagrama UML antes de otimizar
- Caso encontre um gargalo, tente otimizar o contexto amplo que o contém
- Ajuste o código como um último recurso
Confissões de um revisionista
Devo confessar que mudei o exemplo de seu contexto original, que era uma base de código C. Eu recriei as diferentes versões que tivemos do código C em OCaml para o seu prazer.
Então, sim, cometemos o erro comum de ir a um menor nível de linguagem de programação muito cedo, pensando ingenuamente que tínhamos um bom conhecimento do problema que estávamos tentando resolver.
Como resultado, perdemos mais tempo do que deveríamos. De qualquer forma, no fim, espero ter compensado o suficiente escrevendo livremente sobre meus erros, para que você possa evitá-los.
Para os interessados no código em si: https://github.com/toolslive/Sampling
Se divirta!
***
Texto original disponível em http://blog.incubaid.com/2012/01/17/share-your-mistakes-adventures-in-optimization/
De 0 a 10, o quanto você recomendaria este artigo para um amigo?