-
-
Notifications
You must be signed in to change notification settings - Fork 5.6k
Open
Labels
performanceMust go fasterMust go fasterrandomnessRandom number generation and the Random stdlibRandom number generation and the Random stdlib
Description
I suspect that changes in Julia's random number generation has caused micro-optimisations in the implementation of shuffle!
to harm rather than help performance.
julia/stdlib/Random/src/misc.jl
Lines 208 to 221 in 4db8c1b
function shuffle!(r::AbstractRNG, a::AbstractArray) | |
# keep it consistent with `randperm!` and `randcycle!` if possible | |
require_one_based_indexing(a) | |
n = length(a) | |
@assert n <= Int64(2)^52 | |
n == 0 && return a | |
mask = 3 | |
@inbounds for i = 2:n | |
j = 1 + rand(r, ltm52(i, mask)) | |
a[i], a[j] = a[j], a[i] | |
i == 1 + mask && (mask = 2 * mask + 1) | |
end | |
return a | |
end |
On my machine, I observe a naive Fisher-Yates shuffle outperforms an array of 10,000 floats by a factor of ~2 (x86_64 Linux, with Julia 1.11.4)
julia> function myshuf!(vec)
for i in eachindex(vec)
j = rand(i:length(vec))
vec[i], vec[j] = vec[j], vec[i]
end
vec
end
myshuf! (generic function with 1 method)
julia> vec = rand(10000);
julia> @b shuffle!(vec)
40.325 μs
julia> @b myshuf!(vec)
20.085 μs
Metadata
Metadata
Assignees
Labels
performanceMust go fasterMust go fasterrandomnessRandom number generation and the Random stdlibRandom number generation and the Random stdlib