JuliaLang/julia

BitVector has slow lexicographic compare due to storage order

Open

#28.993 aperta il 31 ago 2018

Vedi su GitHub
 (6 commenti) (0 reazioni) (0 assegnatari)Julia (5773 fork)batch import
arraysgood first issueperformance

Metriche repository

Star
 (48.709 star)
Metriche merge PR
 (Merge medio 20g 6h) (157 PR mergiate in 30 g)

Descrizione

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?

Guida contributor