Using find() is faster than direct logical indexing?

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

[Bruno Luong]

Can't reproduce your result on my Laptop

ans =

0.0731 % find


ans =

0.0693 % logical

[dpb]

I'd contend the difference isn't significant to begin with...

[Adam]

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]

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).

Answer 1

[Jan]

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.

[Bruno Luong]

IMO there are more reasons why find should be slower

• Check validity of the index (as you pointed out)
• Convert integer index to double
• Convert double index back to integer index
• Perform pointer arithmetics
• Non contiguous accessing of the data

Of course this overhead depends on the density of the index; also as you pointed out.

Actually Matt timing still surprise me because I expect the difference is more than that in favor of logical, even if the density is 1%.

[Matt J]

@Jan regarding CopyMask, I don't see why summing Mask[i] into Y would be appropriate. Shouldn't it be

*Y = X[i]*Mask[i];

[Bruno Luong]

@Matt J There is no "summing Mask to Y" in Jan's code, It's pointer arithmetics,

Y += Mask[i];

means destination pointer Y move to next address of Maks[i] is 1.

[Matt J]

If Mask[i] is not binary, but rather represents the jump between non-zero elements of the Mask, it seems virtually identical to using find().

[Bruno Luong]

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]

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.