2025-07-24 –, Main Room 2
By using novel optimizations on top of Walker's alias method for random sampling, AliasTables.jl implements a discrete random sampler that supports arbitrary category weights and provides O(n) construction and O(1) sampling with a constant factor of 20-40 clock cycles for construction and 5-10 clock cycles for sampling.
This talk will lay out the accuracy and performance guarantees the algorithms provide, showcase performance across problem size, and delve into the details of the algorithm itself. Specifically it will focus on:
- The novel optimizations this package contributes which allow it to more efficiently utilize random bits;
- How AliasTable sampling is integrated with Julia's Xoshiro rng to provide efficient bulk generation;
- Correctness proofs and empirical verification of perfect sampling accuracy
While less than a year old, AliasTables.jl is mature and widely deployed with tens of thousands of monthly downloads and over 1000 indirect dependents.
Artist, Scientist, Open source developer.