Performance issue when searching for an occurrence in larger matrix

General Usage Performance
1

I wrote some code that searches a large matrix to find occurrences of a given vector. MWE:

A = repeat([1 2 3; 4 5 6; 7 8 9], 100, 1);
b = [4; 5; 6];

In this case, what I would want is a boolean vector that is true for every 2+3*i term.
I am comparing two possible solutions. The first is by using array comprehension:

@time ids = Bool[ b == A[j,:] for j=1:size(A,1)]
0.000403 seconds (903 allocations: 47.312 KiB)

while the second uses broadcasting:

@time ids = all(b'.==A,dims=2)
0.000032 seconds (14 allocations: 4.859 KiB)

Long story short, there’s almost a factor of 10 between the two methods. Why is that the case?
Also, why is the first method yielding a Boolean array while the second yields a BitArray? I would like to use the latter method for speed, but the BitArray is proving harder to work with in the remainder of the code.

2

Each slice, A[j, :], creates a new temporary array. Use views instead:

foo(A, b) = [b == A[j, :] for j in axes(A,1)]  # no need for Bool in front of vector
bar(A, b) = [b == @view A[j, :] for j in axes(A,1)]
baz(A, b) = all(b'.==A; dims=2)

The @time macro isn’t generally suitable for micro benchmarks, use BenchmarkTools instead:

julia> using BenchmarkTools

julia> @btime foo($A, $b);
  16.535 μs (303 allocations: 33.27 KiB)

julia> @btime bar($A, $b);
  3.320 μs (303 allocations: 14.52 KiB)

julia> @btime baz($A, $b);
  4.091 μs (11 allocations: 4.80 KiB)

The comprehension with views is now faster than the all version.

1 Like
3

A nicer way to write bar is

bar_(A, b) = [b == a for a in eachrow(A)]

I would have expected this to have identical performance to bar, but for some reason it it very slightly slower.

1 Like
4

Thank you very much, @view seems to be the best choice in this case!
And yeah, sorry I was reporting @time results, I know it shouldn’t be used to asses code performance.