Performance of logical indexing in Julia 0.7

[yanncalec]

According to the documentation

Indexing by a boolean vector B is effectively the same as indexing by the vector of integers that is returned by findall(B).

This seems to be confirmed on 1d array. However a big difference of performance can be observed on 2d array. Compare the following two ways of logical indexing

X = rand(10^4,10^4)
idx = X.>0.5

# method 1:  indexing by boolean vector
@time for n=1:size(X,2)
    view(X, idx[:,n], n) 
end

# method 2:  indexing by position
@time for n=1:size(X,2)
    view(X, findall(idx[:,n]), n) 
end

In general the second method is 2x more efficient

 0.857407 seconds (138.47 k allocations: 398.172 MiB, 37.71% gc time)
 0.413342 seconds (118.47 k allocations: 397.715 MiB, 13.95% gc time)

and the gap can be even larger in realistic situations.

[mauro3]

On Julia 0.6 I get:

julia> # method 1:  indexing by boolean vector
       @time for n=1:size(X,2)
           view(X, idx[:,n], n) 
       end
  0.535158 seconds (276.94 k allocations: 400.753 MiB, 2.66% gc time)

julia> # method 2:  indexing by position
       @time for n=1:size(X,2)
           view(X, find(idx[:,n]), n) 
       end
  0.516425 seconds (286.43 k allocations: 400.440 MiB, 2.95% gc time)

versus Julia 1.0:

julia> # method 1:  indexing by boolean vector
       @time for n=1:size(X,2)
           view(X, idx[:,n], n) 
       end
  0.570310 seconds (138.47 k allocations: 398.164 MiB, 1.86% gc time)

julia> # method 2:  indexing by position
       @time for n=1:size(X,2)
           view(X, findall(idx[:,n]), n) 
       end
  0.401205 seconds (118.47 k allocations: 397.707 MiB, 2.23% gc time)

So 1 regressed, 2 improved.

[sosiristseng]

X = rand(10^4,10^4)
idx = X.>0.5
using BenchmarkTools

Method1:

# method 1:  indexing by boolean vector
@benchmark for n=1:size($X,2)
    view($X, $idx[:,n], n) 
end

gives

BenchmarkTools.Trial:
  memory estimate:  396.51 MiB
  allocs estimate:  70000
  --------------
  minimum time:     610.871 ms (2.31% GC)
  median time:      625.740 ms (2.48% GC)
  mean time:        631.945 ms (2.63% GC)
  maximum time:     675.288 ms (3.01% GC)
  --------------
  samples:          8
  evals/sample:     1

Method 2:

# method 2:  indexing by position
@benchmark  for n=1:size($X,2)
    view($X, findall($idx[:,n]), n) 
end

gives

BenchmarkTools.Trial:
  memory estimate:  396.05 MiB
  allocs estimate:  50000
  --------------
  minimum time:     437.751 ms (3.35% GC)
  median time:      442.768 ms (3.38% GC)
  mean time:        442.053 ms (3.43% GC)
  maximum time:     445.133 ms (3.40% GC)
  --------------
  samples:          12
  evals/sample:     1

Could confirm that method2 is faster.

[yanncalec]

Method 2 seems faster on large arrays whatever the shape:

X = rand(10^8)
idx = X.>0.5

# method 1:  indexing by boolean vector
@time view(X, idx) 

# method 2:  indexing by position
@time view(X, findall(idx));

gives similar results.

[aaowens]

There does seem to be a regression from 0.6 here, see https://discourse.julialang.org/t/is-boolean-indexing-100-times-slower-in-1-0/16286 .

[nalimilan]

Cc: @mbauman

[nalimilan]

https://discourse.julialang.org/t/is-boolean-indexing-100-times-slower-in-1-0/16286/8 shows code with a 150× regression from 0.6 to 1.0. Citing @tkoolen:

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.

[chethega]

I think the rather extreme issue from discourse (logical indexing by Bool arrays) is separate from the original issue (logical indexing by BitArray). The PR #29633 mostly resolves the problem with logical indexing by Array{Bool}, but does not affect logical indexing by BitArray.

[mbauman]

Yes, this is a different issue from the discourse thread.

Note that you're not really doing any indexing here — you're just creating lazy views that can subsequently be indexed into. Of course, that means that these two indexing types really should be equivalent as views eagerly convert logical masks into arrays of indices. The difference boils down to the internals of how we actually do this task:

julia> @btime collect(Base.LogicalIndex($(idx[:,n])));
  64.773 μs (4 allocations: 39.19 KiB)

julia> @btime findall($(idx[:,n]));
  43.334 μs (2 allocations: 39.14 KiB)

In short, we have a specialized BitArray implementation for findall that seems to be only partially implemented for LogicalIndex.