Por que fiz um fork de `rand` em busca de uma API de números aleatórios menor e mais consistente

• O crate de números aleatórios mais conhecido do Rust, rand, espalha operações do dia a dia por vários traits, então foi criado o urandom com uma superfície pública e de implementação menor e uma experiência de uso mais consistente
• As operações de alto nível foram reunidas em uma única struct Random, e o trait Rng foi selado, priorizando descoberta da API e otimizações internas em vez de suporte a geradores arbitrários
• Sem introduzir novos algoritmos de números aleatórios, as funções de saída do Xoshiro256 foram escolhidas conforme o uso, registrando cerca de 31% mais throughput do que rand 0.10.2 em um benchmark gerando 1.000 valores f64
• A amostragem uniforme de inteiros foi unificada para caminhos reutilizáveis e pontuais com uma única implementação sem viés que calcula o limiar de forma preguiçosa; no benchmark do intervalo 500..20_000, foi mais rápida que os dois caminhos do rand
• A saída bruta com seed explícita garante reprodutibilidade nas arquiteturas suportadas e em releases compatíveis com SemVer, mas abre mão da conexão de geradores arbitrários e do amplo ecossistema de distribuições e integrações de terceiros do rand

---

API Random reunida em um só lugar

• As operações úteis do rand estão espalhadas por vários traits
  • Para gerar números em intervalos aleatórios é preciso RngExt, para escolher itens em sequências, IndexedRandom, e para embaralhar, SliceRandom
  • O rand 0.10 fornece helpers no nível da raiz, como rand::random_range, para chamadas pontuais
  • Mas, para manter um handle de RNG ou usar operações de sequência como seleção e embaralhamento, ainda é preciso encontrar métodos em vários traits
• Mesmo reduzindo imports com o prelude, ainda é necessário saber a que tipo os métodos de extensão se aplicam — RNG, slice ou iterador — então é difícil encontrá-los apenas com autocomplete da IDE
• O urandom coloca a API consumidora de alto nível em uma única struct wrapper Random
  • urandom::new() cria um Random<urandom::rng::Xoshiro256Rng>
  • É possível chamar uniform, choose e shuffle no mesmo objeto
  • O autocomplete mostra random, uniform, chance, choose, shuffle, sample etc.
  • Como todos são métodos próprios, não é necessário encontrar nem importar traits de extensão de alto nível

Rng selado: otimização em vez de extensibilidade

• O rand trata traits de RNG de baixo nível como pontos públicos de extensão, mas no urandom o trait Rng é selado, e os geradores suportados são escolhidos e implementados dentro do próprio crate
  • Não é possível conectar um gerador arbitrário ao Random
  • Para adicionar um novo gerador, é preciso alterar o próprio urandom
• Se o objetivo for um algoritmo melhor, Xoshiro256 e ChaCha já se consolidaram como escolhas padrão por função, e as recomendações mudam devagar
  • Se surgir uma opção melhor, ela pode ser adotada em um futuro major release
• Para compatibilidade com outros projetos, linguagens de programação, algoritmos legados, hardware especial ou geradores exclusivos para simulação, não basta ter o mesmo gerador
  • Algoritmos relacionados, como amostragem uniforme e embaralhamento, também precisam ser iguais, então uma implementação dedicada que cubra o contrato inteiro é mais adequada
• Graças ao trait selado, o urandom pode adicionar apenas as operações brutas de que precisa sem projetar nem documentar um contrato de implementação para geradores desconhecidos e casos excepcionais
  • Isso permite especializar geradores e algoritmos em conjunto, viabilizando algumas otimizações que o rand não pode usar
• Na maioria das aplicações, escolha de entropia é mais útil do que uma nova implementação de PRNG
  • Geradores concretos expõem construtores nativos from_seed
  • É possível criar um Random com seed explícita, como ChaCha12Rng::from_seed(seed)
  • Ele não aceita implementações arbitrárias de RNG, mas preserva os pontos de extensão que usuários avançados provavelmente precisam

Ganhos de desempenho com os mesmos algoritmos

• O urandom não usa novos algoritmos de geração de números aleatórios
  • Em sistemas 64-bit, urandom::new() para uso não criptográfico e rand::rngs::SmallRng usam a mesma família Xoshiro256
  • Para uso criptográfico, urandom::csprng() e rand::rngs::StdRng usam ChaCha12
  • O gerador interno da função de conveniência rand::rng() também é ChaCha12
• A interface de geradores do rand fornece palavras inteiras e preenchimento de bytes, então até distribuições que precisam de f64 acabam pedindo um u64 inteiro primeiro
• O urandom::Rng oferece não só next_u32 e next_u64, mas também next_f32 e next_f64
  • Números aleatórios de ponto flutuante exigem menos bits aleatórios do que uma palavra inteira
  • O gerador pode redefinir esses métodos com funções de saída mais baratas
• A implementação do Xoshiro compartilha a mesma transição de estado, mas separa os caminhos de saída
  • Para u64, mantém Xoshiro256++
  • Para u32 e ponto flutuante, usa o mais rápido Xoshiro256+, cujos bits superiores foram pensados para esses usos
• Os resultados dos microbenchmarks gerando 1.000 números aleatórios com urandom 1.0 e rand 0.10.2 foram os seguintes
  • Xoshiro u64: ambos 814ns
  • Xoshiro u32: rand 836ns, urandom 788ns
  • Xoshiro f64: rand 1.033ns, urandom 788ns
  • ChaCha12 f64: rand 2.199ns, urandom 2.011ns
• O throughput de ponta a ponta para Xoshiro f64 foi cerca de 31% maior e o tempo de execução 24% menor, enquanto o caminho u64, que faz o mesmo trabalho, ficou praticamente empatado
• Como o ChaCha12 não redefine next_f64, o desempenho ficou em grande parte parecido
• Os tempos exatos variam conforme máquina e compilador; as condições detalhadas estão nas notas completas de benchmark

Caminho de amostragem uniforme unificado

• Aplicar uma operação simples de resto ao comprimento de um intervalo inteiro introduz viés, então uma amostragem uniforme correta de inteiros precisa rejeitar parte da saída do gerador
• Calcular o limiar exato de rejeição exige uma operação de resto cara
  • Se o amostrador for reutilizado repetidamente, isso pode ser amortizado como custo de setup inicial
  • Ao gerar apenas um valor, esse custo se torna relativamente alto
• O rand expõe essa diferença por meio do trait UniformSampler
  • O UniformInt construído pré-calcula o limiar para amostrar sem viés
  • Rng::random_range usa hooks separados sample_single ou sample_single_inclusive para evitar o custo de setup
  • Na funcionalidade padrão, o caminho rápido pontual usa um segundo algoritmo levemente enviesado
  • O recurso opcional unbiased substitui isso por uma versão iterativa mais complexa
• O urandom calcula o limiar de forma preguiçosa e usa uma única implementação sem viés baseada em multiplicação e rejeição tanto para intervalos reutilizados quanto para usos pontuais
  • Segue a abordagem descrita no artigo de 2018 de Daniel Lemire, Fast Random Integer Generation in an Interval
  • Na maioria dos intervalos práticos, o primeiro candidato é retornado antes da divisão
  • Se o primeiro candidato não puder ser retornado, o limiar exato é calculado e a repetição continua sem viés
  • Também trata a exceção range == 0, quando o intervalo inteiro é solicitado
• A mesma implementação atende distribuições reutilizadas e intervalos pontuais, sem método separado, segundo algoritmo, custo de setup antecipado nem caminho rápido enviesado
• No benchmark extraindo 1.000 valores do intervalo 500..20_000, os resultados foram os seguintes
  • UniformInt reutilizado: rand 1.098ns, urandom 950ns
  • Intervalo pontual: rand 1.079ns, urandom 942ns
• Os resultados do rand consideram a funcionalidade padrão, então até a linha pontual mais rápida usa um caminho levemente enviesado, enquanto o urandom foi mais rápido que ambos mantendo ausência de viés

Reprodutibilidade entre releases e arquiteturas

• O urandom trata reprodutibilidade como parte do contrato público
  • Com a mesma seed explícita e a mesma sequência de chamadas de RNG de baixo nível, a saída bruta de um gerador determinístico é preservada
  • A estabilidade é garantida em todas as arquiteturas suportadas e releases compatíveis com SemVer
  • Um servidor 64-bit e um cliente WebAssembly 32-bit podem usar a mesma base de gerador para replay
• Para manter essa compatibilidade, ele sacrifica desempenho em arquiteturas 32-bit
• Trata-se de uma garantia mais forte do que a política de reprodutibilidade do rand
  • A saída dos geradores portáveis e dos algoritmos de amostragem do rand pode mudar em minor releases
  • SmallRng e StdRng explicitamente não são portáveis e podem mudar conforme a plataforma ou o release da biblioteca

O custo da escolha e quando usar

• O urandom reúne operações comuns em Random, tornando-as fáceis de encontrar sem traits de extensão
• Ele projeta geradores e distribuições em conjunto para implementar caminhos de saída Xoshiro mais baratos e um único caminho de amostragem uniforme sem viés
• O fluxo bruto estável de geradores com seed explícita pode ser usado em jogos determinísticos e simulações
• Em troca, não é possível trazer geradores arbitrários, e ele também não oferece a lista maior de distribuições nem o ecossistema de integrações de terceiros do rand
• Se você precisa de um ecossistema amplo, o rand é a opção certa; se prefere uma superfície de API pequena, boa descoberta, otimizações integradas e uma política forte de reprodutibilidade, pode escolher o urandom
• O pacote pode ser encontrado em crates.io, na documentação da API e no código-fonte no GitHub

[GN⁺]

Comentários no Lobste.rs

• Há bons motivos para fazer um fork do rand, mas o nome urandom soa como uma biblioteca relacionada a /dev/urandom

  • Parece útil, mas o nome pode causar confusão. Se eu tivesse visto só o nome, sem ler o texto, teria achado que dependia de E/S de arquivos e provavelmente nem teria investigado

• Concordo com a preocupação, mas não gosto de pub fn new() -> Random<impl Rng + Clone>
  Parametrizar a aplicação inteira como Random<T> where T: Rng aumenta o trabalho chato, e os problemas de tempo de compilação e relacionados a dyn ficam sérios. Eu preferiria que struct Random tivesse um tipo concreto ou, como segunda opção, usaria struct Random<T = rng::Xoshiro256Rng>

• Por frustrações parecidas, eu mesmo já fiz algo, mas não é um fork e tem muito menos recursos que o rand

• Fico feliz que alguém que sentia o mesmo problema que eu tenha realmente tentado resolvê-lo. O Rust parece ter uma tendência estranha a levar as pessoas a criarem bibliotecas de sopa de traits
  O tipo de dado central do banco de dados com que trabalho precisa implementar pelo menos 15 traits, então o autocompletar fica uma bagunça e a documentação também confunde. Reduzimos um pouco o número de traits, mas frequentemente esbarramos em dependências circulares ou na impossibilidade de escrever testes essenciais

  • Isso acontece porque astronautas da arquitetura vindos do Java aplicam o mesmo estilo orientado a objetos ao Rust. Dependências circulares são sinal de que você dividiu à força algo que ainda não pode ser separado, ou de que não distinguiu corretamente três coisas. Se você controla todo o código, pode usar enums em vez de traits
  • No ecossistema de criptografia do Rust, o problema da sopa de traits é especialmente forte, a ponto de enlouquecer

• Esta biblioteca me lembra tanto as interfaces profundas de APOSD quanto o trabalho de criptografia do Filippo projetado para ser difícil de usar errado, e ambos são grandes elogios

  • Ainda assim, urandom::new() não retorna um gerador de números aleatórios criptograficamente seguro, então o design não é totalmente à prova de erro. Isso fica ainda mais confuso porque, no Linux, /dev/urandom é seguro

• Outra alternativa ao rand é o fastrand, um gerador de números aleatórios simples e rápido. Ele é mais simples que rand e urandom, mas também tem menos recursos