JuliaLang/julia

BitVector has slow lexicographic compare due to storage order

Open

#28,993 opened on Aug 31, 2018

View on GitHub
 (6 comments) (0 reactions) (0 assignees)Julia (5,773 forks)batch import
arraysgood first issueperformance

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?

Contributor guide