StatsBase.jl icon indicating copy to clipboard operation
StatsBase.jl copied to clipboard

Add @inbounds in alias table sampling

Open vancleve opened this issue 5 years ago • 3 comments

Seems like one could add @inbounds to this line

https://github.com/JuliaStats/StatsBase.jl/blob/41669cd8dfeadce35db0c4e07ac7afe5d10fb957/src/sampling.jl#L624

In fact its here already when using alias table sampling for Categorical in Distributions: https://github.com/JuliaStats/Distributions.jl/blob/d6de7214e6d84df77d1eb3ec7a98d23862d1232d/src/samplers/aliastable.jl#L19

vancleve avatar Jan 07 '21 22:01 vancleve

Sure, why not. Though it seems we need an additional check that the indices of a match those of x.

nalimilan avatar Jan 16 '21 21:01 nalimilan

@ParadaCarleton Can you argument on why you want to close this?

nalimilan avatar Oct 28 '23 17:10 nalimilan

@ParadaCarleton Can you argument on why you want to close this?

I don't like correctness bugs, and thought this was just hanging around because it was old enough to be before that Yuri post on all the correctness issues in JuliaStats packages.

ParadaCarleton avatar Oct 28 '23 18:10 ParadaCarleton

This optimization would be unsafe because it is possible for make_alias_table! to produce invalid alias tables:

julia> StatsBase.alias_sample!(Random.default_rng(), rand(10), weights(fill(0, 10)), rand(10))
ERROR: BoundsError: attempt to access 10-element Vector{Float64} at index [281471800382896]
Stacktrace:
 [1] throw_boundserror(A::Vector{Float64}, I::Tuple{Int64})
   @ Base ./essentials.jl:14
 [2] getindex
   @ ./essentials.jl:891 [inlined]
 [3] alias_sample!(rng::TaskLocalRNG, a::Vector{Float64}, wv::Weights{Int64, Int64, Vector{Int64}}, x::Vector{Float64})
   @ StatsBase ~/.julia/packages/StatsBase/ebrT3/src/sampling.jl:729
 [4] top-level scope
   @ REPL[10]:1

With @inbounds this would be undefined behavior.

LilithHafner avatar Apr 08 '24 14:04 LilithHafner