Why is vecnorm So Slow?

Why is vecnorm so much slower than the raw calculation and why does such difference increase as the input gets larger. I can see it being a bit slower if there is some overhead for argument checks or something like that, but that shouldn't scale with input size. And what happens between 2e4 < n < 3e4?

n = round(logspace(2,5,20));
for ii = 1:numel(n)
    x = rand(n(ii),3);
    tvec(ii) = timeit(@() vecnorm(x,2,2)    );
    tsq(ii)  = timeit(@() sqrt(sum(x.^2,2)) );
end

Warning: The measured time for F may be inaccurate because it is running too fast. Try measuring something that takes longer.

Warning: The measured time for F may be inaccurate because it is running too fast. Try measuring something that takes longer.

figure
semilogx(n,tvec,n,tsq),grid
legend('vecnorm','sqrtsumsq')

Answer 1

[John D'Errico]

The jump is often a question of algorithm changes. You would be surprised how often algorithms exhibit nonlinear breaks. As I recall, even something as simple as a matrix multiply can show a break, with bumps and even non-monotonicites. However, I would point out that you are not pushing things nearly far enough. And you are running in the domain where timeit is having problems just measuring the time at all.

So what you are seeing is just actually a relatively very tiny break near 20k-30k. It might be some sort of system caching issue. It might be when your CPU decides to start extra threads.

n = round(logspace(4,7,25));
for ii = 1:numel(n)
    x = rand(n(ii),3);
    tvec(ii) = timeit(@() vecnorm(x,2,2)    );
    tsq(ii)  = timeit(@() sqrt(sum(x.^2,2)) );
end
semilogx(n,tvec,n,tsq),grid
legend('vecnorm','sqrtsumsq')

That was run in MATLAB online. However, if I try the same thing on my Mac, I get very different results. (Sorry about the black background. I was too lazy to change it.)

In fact, I do see a little bump near 20k. I was watching my activity monitor on the Mac when I did it though. It all ran so rapidly that even with this test, I had to use a very fast update rate to catch the CPU load. With 16 cores on my computer, it was using at least 9 cores, but the entire test was done in around a second. Note that on my CPU, the two algorithms are literally neck and neck over the entire domain for n.

[Paul]

The warnings only came for a few samples, so I thought it was ok to ignore them for this post.

Rerunning. On my local machine vecnorm wins at around n = 5e4. I'm still suprised that sqsumsq outperforms vecnorm and wonder what vecnorm is doing that takes the extra time, but the absolute timings are pretty small, at least for the 3-column case that I'm typicaly interested in.

n = round(logspace(3,7,50));
for ii = 1:numel(n)
    x = rand(n(ii),3);
    tvec(ii) = timeit(@() vecnorm(x,2,2)    );
    tsq(ii)  = timeit(@() sqrt(sum(x.^2,2)) );
end
semilogx(n,tvec./tsq),grid
legend('vecnorm/sqrtsumsq')