Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

faster rand!(::MersenneTwister, ::Array{Bool}) #33721

Merged
merged 4 commits into from
May 4, 2020
Merged

faster rand!(::MersenneTwister, ::Array{Bool}) #33721

Changes from 1 commit
Commits
Show all changes
4 commits
Select commit Hold shift + click to select a range
46bff79
faster rand!(::MersenneTwister, ::Array{Bool})
rfourquet Oct 30, 2019
7647d66
write non-zero bits only in lower bit of each byte, and get faster
rfourquet Oct 31, 2019
de39674
more comments, and re-arrange structure
rfourquet Apr 27, 2020
751d0b7
add NEWS.md entry
rfourquet May 2, 2020
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Prev Previous commit
Next Next commit
write non-zero bits only in lower bit of each byte, and get faster
  • Loading branch information
@rfourquet
rfourquet committed May 2, 2020
commit 7647d661e7e316daedb107d0d203155df6fc237f
39 changes: 34 additions & 5 deletions stdlib/Random/src/RNGs.jl
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -607,11 +607,40 @@ end

#### arrays of Bool

function rand!(r::MersenneTwister, A::Array{Bool}, sp::SamplerType{Bool})
GC.@preserve A rand!(r,
UnsafeView(Ptr{UInt8}(pointer(A)), length(A)),
SamplerType{UInt8}())
A
# similar to Array{UInt8}, but we need to mask the result so that only the LSB
# in each byte can be non-zero

function rand!(r::MersenneTwister, A1::Array{Bool}, sp::SamplerType{Bool})
n1 = length(A1)
n128 = n1 ÷ 16

GC.@preserve A1 begin
A = UnsafeView{UInt128}(pointer(A1), n128)
rand!(r, UnsafeView{Float64}(A.ptr, 2*n128), CloseOpen12())
# without masking, non-zero bits could be observed in other
# positions than the LSB of each byte
mask = 0x01010101010101010101010101010101
if n128 > 0
# we need up to 15 bits of entropy for the last loop;
# A[1] % UInt64 contains 52 bits of entropy, but 8
# of them will be used for A[i] itself (the first of
# each byte). To compensate, we xor with (A[1] >> 65),
# which gets the entropy from the second bit of each byte
# of the upper-half of A[i].
bits = (A[1] % UInt64) ⊻ (A[1] >> 65) % UInt64
else
bits = rand(r, UInt52Raw())
end
for i = 1:n128
# << 5 to randomize the first bit of the 8th byte
A[i] = (A[i] ⊻ A[i] << 5) & mask
end
end
for i = 16*n128+1:n1
@inbounds A1[i] = bits % Bool
bits >>= 1
end
A1
end


Expand Down