BitVector has slow lexicographic compare due to storage order
#28,993 opened on Aug 31, 2018
Repository metrics
- Stars
- (48,709 stars)
- PR merge metrics
- (Avg merge 20d 6h) (157 merged PRs in 30d)
Description
julia> using BenchmarkTools
julia> a=BitVector(rand(Bool,1<<10)); b=copy(a);
julia> @btime ==($a,$b)
13.865 ns (0 allocations: 0 bytes)
true
julia> @btime <($a,$b)
2.252 μs (0 allocations: 0 bytes)
false
julia> versioninfo()
Julia Version 1.0.0
Commit 5d4eaca0c9 (2018-08-08 20:58 UTC)
The immediate problem is that lexicographic comparison falls back to AbstractArray. However, it is not clear how to write a fast (chunk-wise) comparison with the current layout, because the most significant bit of the bitvector (wrt julia's convention for vector comparison) is stored in the least significant bit of the unterlying UInt64 (wrt hardware integer comparison convention). See:
julia> a=BitVector(rand(Bool,1<<6));
julia> a
64-element BitArray{1}:
true
true
false
false
true
⋮
true
false
true
false
julia> bitstring(a.chunks[1])
"0101011000101101010100010100000110100011100101000000101011110011"
I'd propose to switch the layout of BitVector to match the machine convention. Then, one would need to also replace trailing_zeros by leading_zeros for iterations, but this has just as good hardware support. Or is there a strong reason for the current layout?