Using find() is faster than direct logical indexing?

33 views (last 30 days)
Does it make sense that using find() instead of direct logical indexing is faster in this example:
A=randi(100,5e3,5e3);
timeit(@()useFind(A))
ans = 0.1410
timeit(@()useLogical(A))
ans = 0.1430
function B=useFind(A)
I=find(A==2);
B=A;
B(I)=3;
end
function B=useLogical(A)
B=A;
B(A==2)=3;
end
  4 Comments
Adam
Adam on 3 Aug 2022
I get similar results, albeit that my PC is about 2½ times slower! Find is typically around 8% slower for me on this example.
Bruno Luong
Bruno Luong on 3 Aug 2022
Wonder why I get faster than you guys, my PC is just a normal PC, I don't even have Nvidia card and I'm not a gammer (well if one consider MATLAB is not a game).

Sign in to comment.

Accepted Answer

Jan
Jan on 3 Aug 2022
No relevant difference in R2022a in the forum:
A=randi(100, 5e3, 5e3); % Few elements only
timeit(@() useFind(A))
ans = 0.1397
timeit(@() useLogical(A))
ans = 0.1419
But as soon as the number of occurences grows, the timings differ:
A = randi(2, 5e3, 5e3); % More occurences: about 50%
timeit(@() useFind(A))
ans = 0.4319
timeit(@() useLogical(A))
ans = 0.2875
function B = useFind(A)
I = find(A == 2);
B = A;
B(I) = 3;
end
function B = useLogical(A)
B = A;
B(A == 2) = 3;
end
My interpretation: find has a certain overhead and providing a vector as index is more expensive, because each element must be checked if it is inside the valid range with an integer value. The logical index must be checked only once.
For a tiny index vector, the find method has an advantage, because the logical indexing must process a lot of false elements. This seems to be implemented inefficiently in Matlab, see FEX: CopyMask, which ist much faster (up to 66%!) than Y = X(Mask) with logical indexing. It uses a simple method to avoid branching:
*Y = X[i];
Y += Mask[i];
If the index vector is larger, e.g. 50% of the data, the find() method is less efficient than logical indexing.
  6 Comments
Bruno Luong
Bruno Luong on 4 Aug 2022
Edited: Bruno Luong on 4 Aug 2022
But is not Jan's code suppose to do.
It carry out the same task as
Y = X(Mask)
where Mask is a logical array; and Jan claims it's can be twice faster.
There are some variation with working dimension, make Jan's code more flexible.
Jan
Jan on 5 Aug 2022
These two pieces of C code are equivalent:
% iTrue and fTrue are the first and last TRUE elements
% of the logical Mask vector
for (i = iTrue; i <= fTrue; i++) {
*Y = X[i];
Y += Mask[i]; // Advance pointer if Mask is TRUE
}
and
for (i = iTrue; i <= fTrue; i++) {
if (Mask[i]) {
*Y++ = X[i];
}
}
The 1st method avoids branching, which is faster on modern CPUs. If the Mask contains less than about 2.5% TRUE values, the 2nd method is faster.
FEX: CopyMask counts the number of TRUE values at first for a proper pre-allocation. This might be another cause for the speedup compared to X=Y(Mask).
For masking in a specific dimension like Y=X(:, Mask, :), the C-Mex CopyMask is only slightly faster for some specific inputs, but slower usually. So CopyMask is useful for vectors only.
I was really surprised, when I found this simple piece of code to be up to 7 times faster than Matlab's logical indexing.

Sign in to comment.

More Answers (0)

Products


Release

R2022a

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!