Rust: Estrutura de dados e seu impacto na performance
Engenheiro de Software
Este artigo visa mostrar a importância de conhecer a estrutura de dados certa para o problema, mostrando como ela pode aumentar muito a velocidade de execução do seu código, e como a utilização inconsequente de estruturas de dados consideradas 'mais rápidas' pode piorar a performance do código.
Contexto
Eu estava treinando a sintaxe da linguagem de programação Rust na plataforma Exercism, através de diversos exercícios com dificuldades variadas, quando me deparei com um exercício classificado como fácil, chamado Sum of Multiples.
Nas regras eles dizem basicamente que deve ser calculado a quantidade de energia que um jogador deve ganhar ao finalizar uma fase dentro do jogo, baseado no:
- Nível que o jogador completou (número da fase).
- Valor de cada item mágico coletado pelo jogador durante o nível (vetor de inteiros).
Exemplo
Para contextualizar melhor o modo de resolver esse problema é mostrado um exemplo contendo a “execução” do programa com os parâmetros de entrada 20 e [3, 5], sendo o nível da fase e os níveis dos dois itens mágicos coletados pelo jogador durante o jogo, respectivamente.
Para calcular os pontos de energia ganhos pelo jogador, precisamos achar todos os múltiplos únicos dos itens mágicos desde que não ultrapasse o nível da fase, e somá-los.
- Multiplos de 3 =>
[3, 6, 9, 12, 15, 18] - Multiplos de 5 =>
[5, 10, 15] - Combine os múltiplos e remova os duplicados =>
{3, 5, 6, 9, 10, 12, 15, 18} - Some os múltiplos únicos =>
3 + 5 + 6 + 9 + 10 + 12 + 15 + 18 = 78 - Resposta =>
78
Solução
Decidi então começar da maneira mais intuitiva possível, utilizando Vetores e laços aninhados, assim como pode ser observado no código a seguir.
pub fn sum_of_multiples_vector(limit: u32, factors: &[u32]) -> u32 {
let mut energy_earned: Vec<u32> = Vec::new();
for i in factors {
let mut count = 1;
loop {
let energy_point = i * count;
if energy_point < limit {
if !energy_earned.contains(&energy_point) {
energy_earned.push(energy_point);
}
count += 1;
} else {
break;
}
}
}
energy_earned.iter().sum()
}
No entanto, por mais que essa implementação passe em todos os testes eu queria saber qual era o tempo que ele levava para me retornar o resultado, baseado em um número irreal de fase, como por exemplo a fase número 10.000 e uma lista simples como por exemplo [2, 3, 5, 7, 11].
Benchmark
Querendo saber o resultado em formato de tempo, da solução que eu havia criado, decidi montar essa função genérica para realizar o teste de performance do meu próprio código.
fn benchmark<F>(function_name: F) -> (Duration, u32)
where
F: Fn(u32, &[u32]) -> u32
{
let now = Instant::now();
let result = function_name(10_000, &[2, 3, 5, 7, 11]);
let elapsed = now.elapsed();
(elapsed, result)
}
Essa função recebe como parâmetro um genérico F que está sendo especificado na cláusula where, onde podemos ver que o parâmetro de entrada da função benchmark é na realidade uma outra função, que recebe como parâmetro um u32 (inteiro não assinado de 32 bits) e a &[u32] (referência a um vetor de inteiros não assinados de 32 bits), tendo como valor de retorno da função passada como parâmetro um u32.
O corpo da função em sí não faz nada muito mirabolante, ele simplemente pega a data antes de executar a função que desejamos testar, e após sua execução, já faz o cálculo de quanto tempo levou, utilizando a função elapse() da struct Instant.
Também montei outra função para fazer a média de tempo das 10 execuções. Onde ela irá receber um vetor contendo as durações de cada execução do benckmark e retornar a duração média através da divisão da soma de todas as durações, pelo total de durações que haviam no vetor.
fn average_time(elapsed: Vec<Duration>) -> Duration {
let sum = elapsed.iter().sum::<Duration>();
let average = sum / elapsed.len() as u32;
average
}
Por fim liguei tudo na função main e deixei rodando para ver qual resultado me seria retornado. E foi aí que eu obtive os seguintes resultados:
- Desenvolvimento:
325ms - Produção:
38ms
Mesmo com esse tempo em mãos não temos como dizer se ele é bom ou ruim, pois ele é a única solução que nós desenvolvemos até aqui. Pensando nisso, devemos recriar a função utilizando uma outra estrutura de dados, assim como pode ser visto na próxima sessão.
HashSet
A estrutura de HashSet se trata de um conjunto que nunca contém várias cópias de um mesmo valor, sendo um mapa que possui somente chaves, em formato hash, ao invés de um HashMap convencional que armazena chave e valor.
Como esse conjunto pode ler e armazenar valores em formato de hash, a leitura e escrita de uma quantidade pequena de informações pode ser mais demorada do que um vetor convencional, mas quando temos um número muito grande de informações para lidar essa estrutura se sai muito bem, já que estamos buscando por um índice ao invés de ir pegando sempre o próximo da lista. Esse conceito também se aplica na escrita de dados do HashSet, e é justamente aqui que nós economizamos tempo, já que os dados inseridos no HashSet terão uma chave equivalente, e quando tentarmos inserir o mesmo número, a própria estrutura já irá acusar a existência de um valor para a mesma chave hash, ignorando a inserção duplicada.
Era justamente na verificação da existência de um número dentro do nosso vetor que o código começava a “patinar”… já que era necessário verificar item a item antes que fosse possível inserir um novo número e a cada novo número o tempo da verificação crescia. A utilização de vetores nesse contexto pode ser resumida em um Big O(n), enquanto a utilização de um HashSet seria um Big O(1).
Além de tudo isso, a troca de um Vec<u32> para um HashSet<u32> é muito simples, basta importarmos a struct do HashSet direto da biblioteca padrão do Rust e realizarmos as pequenas alterações destacadas, em formato de comentário, no código.
use std::collections::HashSet; // Realizando a importação da struct do HashSet
pub fn sum_of_multiples_hashset(limit: u32, factors: &[u32]) -> u32 {
let mut energy_earned: HashSet<u32> = HashSet::new(); // Alteramos de Vec para HashSet
for i in factors {
if i == &0 { // Adicionamos essa verificação
continue; //
} //
let mut count = 1;
loop {
let energy_point = i * count;
if energy_point < limit {
// Removemos o if que verificava se o número já existia dentro do vetor
energy_earned.insert(energy_point);
count += 1;
} else {
break;
}
}
}
energy_earned.iter().sum()
}
Essas pequenas alterações nos deram esse resultado:
- Desenvolvimento:
5.7ms - Produção:
410µs
Conclusão
A implementação da estrutura de dados correta para esse exercício nos deu um código ~57X mais rápido em desenvolvimento e ~92X mais rápido em Produção. Essa é uma gigantesca melhoria no desempenho, o que nos mostra a importância de conhecer diferentes estruturas de dados.
Outro ponto importante que deve ser levado em consideração é a Notação Big O, que para esse exercício, nos mostrou que um HashSet seria mais eficiente do que um Vetor quando utilizado por números de fases exageiradamente grandes. O que não é verdade, se invertermos a comparação.
Faça o teste você mesmo, e troque o valor da função de teste por um nível de fase baixo, mas com uma lista gigantesca de números e veja qual se sai melhor.
Exemplo
Alterando o número da fase para 20 e passando a lista de itens mágicos coletados como [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20] o Vetor se saiu melhor do que o HashSet, mas conforme vamos incrementando o nível da fase, o tempo entre eles começa a se igualar até que o HashSet se torne o mais rápido entre eles.
Extra
Você pode testar o código por conta própria para verificar a diferença de tempo direto pelo seu navegador através deste link: Sum of Multiplos.
É claro que os tempos exibidos neste artigo irão divergir dos resultados gerados após a execução do código através do link fornecido, já que você estará executando a linguagem de programação Rust compilada para WASM (WebAssembly), através da plataforma Rust Playground, mas ainda sim será possível ver a diferença de tempo entre os resultados da função escrita utilizando Vetor e utilizando HashSet.
← Artigos