Fastest way to AND or OR together columns of a matrix

I'm using 2017b and I need to test whether each row of a matrix meets an inequality constraint. This test is done millions of times in my code, so I'm trying to make it as fast as possible. I'm wondering if there is any faster way to do it than this

testdata = rand(1000,26);  % setup some fake data
testref = rand(1,26)/20;   % setup a fake test reference
result = sum(testdata >= testref,2)==26;   % Actual test; can this be faster?  

Answer 1

[Fangjun Jiang]

try

result = all(testdata >= testref,2)

It is quite faster.

Elapsed time is 0.000445 seconds.

Elapsed time is 0.000294 seconds.

Elapsed time is 0.000426 seconds.

Elapsed time is 0.000254 seconds.

Elapsed time is 0.000406 seconds.

Elapsed time is 0.000255 seconds.

[Adrian Mariano]

I thought surely you had given the solution. But when I ran timing tests, I found that using all was slightly slower than using sum:

K>> tic; for i=1:1e5, result = sum(testdata>=testref,2)==26;end;toc
Elapsed time is 2.247037 seconds.
K>> tic; for i=1:1e5, result = all(testdata>=testref,2);end;toc
Elapsed time is 3.041877 seconds.

When I tried profiling it in my actual full program using all required about 24% more time.

[Matt J]

You need to test inside a function, not at the command line. ALL should be faster, but not by much

testdata = rand(1e7,26);  % setup some fake data
testref = rand(1,26)/20;   % setup a fake test reference

cmp=(testdata >= testref);

tic;
result = sum(cmp,2)==26;   
toc
%Elapsed time is 0.157098 seconds.

tic
result = all(cmp,2);
toc
%Elapsed time is 0.121624 seconds.

[Fangjun Jiang]

all() certainly should be faster than sum() in this case. But I am not sure how to interprete the result here. I ran it once. all() is faster. I ran it 1e5 times, sum() is faster. Both in command line. Some JIT optimization might mess up the clock here.

Is it practical to run the same check with the same data 1e5 times? In your real data, I would think the data is different very time. Could you switch between sum() and all() and see the difference?

[Adrian Mariano]

The real problem is not random, so I can actually test on the same input for each version and compare the results. That's what I did when I said I tested on my actual program. And as I said above, using all() was slower: the program line with this test in it took 24% more run time using all() according to the profiler.

Why should testing at the command line give invalid results? If JIT optimization was really working wouldn't it cleverly skip the whole loop and run it just once instead of 1e5 times? It would be pretty obvious if that had happened. As I've been working on optimizing the code the behavior at the command line has been pretty good at predicting performance in the code.

[Matt J]

No, the JIT will not skip whole loop.

[Adrian Mariano]

Like I said, if JIT skipped the loop it would be pretty obvious. But the question remains: what's wrong with testing run time at the command line? How or when will it give misleading results?

Is the conclusion about my original question that using sum() is the fastest method?

[Matt J]

But the question remains: what's wrong with testing run time at the command line?

Whatever optimizations Matlab does, it only does them in function files, so command line execution is never the reliable way to see the best that Matlab can do.

Is the conclusion about my original question that using sum() is the fastest method?

We certainly can't conclude that in general. As you can see from my timing tests above, I found all() to be faster, which makes sense because it involves fewer function calls. Possibly, though, you have a very strange computer...

Answer 2

[Fangjun Jiang]

It looks like depending on the size of the test data. If the data has 1e6 rows or less, sum() is faster. If the data has 1e7 rows or more, all() is faster.

rng(1);
testdata = rand(1e6,26);  % setup some fake data
testref = rand(1,26)/20;   % setup a fake test reference
cmp=(testdata >= testref);

tic;
result = sum(cmp,2)==26;   
t_sum=toc;

tic
result = all(cmp,2);
t_all=toc;

if t_sum<t_all
    fprintf('sum() is faster\n\n');
else
    fprintf('all() is faster\n\n');
end

[Adrian Mariano]

Hmmm. For me it appears sum() is always faster.

Is it my weird hardware? Intel(R) Xeon(R) CPU E5-2687W v3 @ 3.10GHz, 3101 Mhz, 10 Core(s), 20 Logical Processor(s)

[Fangjun Jiang]

Any Mathworkers give some insight?

1. Why all() is not always faster than sum() in this use case?
2. How to explain the fact that it depends on the data size?

[Matt J]

sum is very well multi-threaded, conceivably better so than all, because people use it so often. Maybe because you have so many cores, your machine is good at taking advantage of this.

In any case, the multi-threading done behind the scenes by Matlab has always been data size dependent, so that part is not a surprise.

[Fangjun Jiang]

I agree. Between "sum(cmp,2)==26" and "all(cmp,2)", "all(cmp,2)" should be much simpler and faster. It shouldn't need tic/toc to prove that, unless any Mathworker provides a reason.

[Adrian Mariano]

I looked at my CPU load during the computation. When I use the sum() method, I have about 50% CPU utilization. When I use any() I have 8% CPU utilization. So that seems to explain how it is that any() is not much faster---somehow it's much less effective at using the CPU. Multithreading only for arithmetic? In principle, doing 26 AND operations should be a lot faster than doing 26 arithmetic operations.

[Fangjun Jiang]

I did try cputime() but didn't find difference when running it once (both are zero). You could try it if you really want to find it out. Again, I thought the choice for using all() was clear but tic/toc indicated otherwise. I guess there are still some explanation needed.

[Adrian Mariano]

I tried cputime running on a case with 10^8 rows, and I get a big difference, 3 s for all and 12.4s for sum.