More multiplication operations require less time

I would expect the execution times for the 3 operations below to get longer and longer. Where have I misled myself? Is it an issue with tic/toc as the timing method, or something else?

A=rand(500,500,500);

tic;
A.*A;
toc;

Elapsed time is 0.256989 seconds.

tic;
A.*A.*A;
toc;

Elapsed time is 0.124557 seconds.

tic;
A.*A.*A.*A.*A.*A;
toc;

Elapsed time is 0.099304 seconds.

Answer 1

[Walter Roberson]

It is because you are not recording the output.

I introduced T0 here because I was noticing that in my tests, T1 (the first operation) was consistently slower than T2 (the second operation), and I suspected that time to parse or something similar was being allocated against the first operation. With the T0 introduced, the measured time for A.*A reduces.

A=rand(500,500,500);

tic;
T0 = A;
toc;

Elapsed time is 0.001954 seconds.

tic;
T1 = A.*A;
toc;

Elapsed time is 0.199039 seconds.

tic;
T2 = A.*A.*A;
toc;

Elapsed time is 0.201588 seconds.

tic;
T3 = A.*A.*A.*A.*A.*A;
toc;

Elapsed time is 0.208999 seconds.

[Matt J]

That is interesting, but I still wonder why there isn't a linear increase in execution time with the number of operations.

[Torsten]

More or less linear if the A's are different. I guess a^n is easier to evaluate than a1*a2*...*an.

for i = 1:6
    A{i}=rand(500,500,500);
end

tic
M2 = A{1}.*A{2};
t(2) = toc;
tic
M3 = A{1}.*A{2}.*A{3};
t(3) = toc;
tic
M4 = A{1}.*A{2}.*A{3}.*A{4};
t(4) = toc;
tic
M5 = A{1}.*A{2}.*A{3}.*A{4}.*A{5};
t(5) = toc;
tic
M6 = A{1}.*A{2}.*A{3}.*A{4}.*A{5}.*A{6};
t(6) = toc;
plot(2:6,t(2:6))

[Matt J]

I guess a^n is easier to evaluate than a1*a2*...*an.

Hard to see why that would be true.

[Walter Roberson]

I remember that several years ago, someone posted the results of timing tests showing the time differences between:

• naive repeated multiplication
• .^ operation
• realpow()
• log(), multiply, exp()
• decomposition of integer powers -- e.g., x.^12 -> temp1 = x.^3, temp2 = temp1.^2, result = temp2.^2. I seem to recall that someone (@John D'Errico maybe?) posted a FEX contribution to do this kind of decomposition

... though thinking back I am not sure that the time for the log approach was measured.

[Christine Tobler]

Part of the reason that the cost doesn't grow linearly here is that several .* calls in one operation are optimized so that the results are computed in one go, without intermediate arrays being constructed.

For the operation here, I'd say most of the time isn't spent in the multiplication, but in accessing the memory of each of the input arrays, and writing this into the output arrays (cache effects).

So when we have the same array A 6 times, only the elements of that one array are being traversed and loaded from RAM to the CPU. Doing 5 multiplications instead of just 1 isn't much more expensive if the relevant numbers are all already available in the CPU registers, compared to the cost of getting the data to the CPU in the first place.

For 6 different arrays A, the corresponding element of each array now has to be loaded into the CPU at the same time, which is more expensive.

[Bruno Luong]

I just recently test .^ with base scalar and integer power and it seems MATLAB does NOT use power2 decomposition, but straighfoward successive multiplications.

IIRC James Tursa have submited something on power-2 decomposition.

EDIT: https://www.mathworks.com/matlabcentral/fileexchange/25782-mpower2-a-faster-matrix-power-function?s_tid=srchtitle

[Walter Roberson]

Oh, right, it makes sense for James to have done that work! (But it would also have made sense for John to have done it as part of his high precision packages.)

[Matt J]

Part of the reason that the cost doesn't grow linearly here is that several .* calls in one operation are optimized so that the results are computed in one go, without intermediate arrays being constructed.

I see. Well, that seems like a very well-intentioned optimization, but hazardous for users trying to compare algorithms. It makes it impossible for the user to know if the operations they code are implemented literally.