Is boolean indexing 100 times slower in 1.0?


#1
d = rand(100)
mask = [fill(false,20)...,fill(true,80)...];
@time for i in 1:100000
    d[mask]
end
  • Julia-1.0 and 0.7
  3.038767 seconds (41.20 M allocations: 1.197 GiB, 4.90% gc time)
  • Julia-0.6.4
  0.029932 seconds (300.00 k allocations: 74.768 MiB, 11.41% gc time)

#2

Don’t benchmark in global scope, but the conclusion remains the same:

d = rand(100)
mask = [fill(false,20)...,fill(true,80)...]
using BenchmarkTools
@btime $d[$mask]

22.229 μs on 1.0, 148.242 ns on 0.6.

See also https://github.com/JuliaLang/julia/issues/29418.


#3

good point, thanks.


#4

For reference the comprehension version is fast in 1.0

julia> function test1(d, mask)
       d[mask]
       end
test1 (generic function with 1 method)

julia> function test2(d, mask)
       [d[i] for i in eachindex(d) if mask[i]]
       end
test2 (generic function with 1 method)

julia> @btime test1($d, $mask)
  27.081 μs (412 allocations: 12.55 KiB)
80-element Array{Float64,1}:
 0.8054772608752572  
 0.05067482842558224 
 0.5388726134765767  
 0.692159153505675   
 0.7684311492067795  
 0.6711078136106581  
 0.6649141807497929  
 0.5985228802273888  
 0.3748395020447204  
 0.914509451795469   
 ⋮                   
 0.4337689060373162  
 0.793914486706204   
 0.5254852110421662  
 0.37372068234717726 
 0.9288662798362115  
 0.495094572109253   
 0.21356511652770882 
 0.022123152385092437
 0.2705493240621617  

julia> @btime test2($d, $mask)
  958.000 ns (12 allocations: 2.44 KiB)
80-element Array{Float64,1}:
 0.8054772608752572  
 0.05067482842558224 
 0.5388726134765767  
 0.692159153505675   
 0.7684311492067795  
 0.6711078136106581  
 0.6649141807497929  
 0.5985228802273888  
 0.3748395020447204  
 0.914509451795469   
 ⋮                   
 0.4337689060373162  
 0.793914486706204   
 0.5254852110421662  
 0.37372068234717726 
 0.9288662798362115  
 0.495094572109253   
 0.21356511652770882 
 0.022123152385092437
 0.2705493240621617  

#5

Try converting your mask to a BitArray, which has an optimized iterator.


#6

I realized that for my case the boolean indexing is not necessary. I could use an array of indexes.

d = rand(100)
mask = [fill(false,20)...,fill(true,80)...]
inds = collect(1:length(d))[mask];
@btime $d[$inds]

is back to right speed for 1.0

134.743 ns (2 allocations: 752 bytes)

#8

You can fix the problem by the following:

julia> using BenchmarkTools

julia> d=rand(10_000); m=rand(Bool, 10_000);

julia> @btime getindex($d,$m);
  742.062 μs (23906 allocations: 643.13 KiB)

julia> Base.@propagate_inbounds function Base.iterate(L::Base.LogicalIndex, s)
           # We're looking for the n-th true element, using iterator r at state i
           n = s[1]
           n > length(L) && return nothing
           idx, i = iterate(Base.tail(s)...)
           s = (n+1, s[2], i)
           L.mask[idx] && return (idx, s)

           
           while true
               idx, i = iterate(Base.tail(s)...)
               s = (n+1, s[2], i)
               L.mask[idx] && return (idx, s)
           end
           end

julia> @btime getindex($d,$m);
  49.477 μs (4 allocations: 38.63 KiB)

#9

@foobar_lv2, thank you for clarifying the problem,

What do you mean? Do you suggest to flag it or withdraw? I have not solved the problem just found a workaround. I guess it is a bug to be fixed.


#10

This is just a message that appears from Discourse when people withdraw their own posts.


#11

That is funny how I misunderstood it. Alright, thanks.


#12

I first posted a completely wrong explanation, so I withdrew the bad post (my fault). Once I had the proper explanation, I made the work-around and submitted it as a PR.

The explanation I did not post here, btw, is that iterate(L::LogicalIndex{Int}) was not correctly inferred, because the state s can change type after the first iteration in the above loop. Unrolling the first iteration fixes that.