small matrix multiplication *much slower* in R2016b than R2016a

Hi all,

I find that multiplication of small matrices seems much smaller in R2016b than R2016a. Here's a minimal example:

r = rand(50,100);
s = rand(100,100);
tic; r * s; toc

This takes about 0.0012s in R2016a and 0.018s R2016b.

Creating an artificial loop to make sure this isn't just some initial overhead or something leads to the same loss factor:

tic; for i = 1:1000, a = r*s; end, toc

This takes about 0.18s in R2016a and 2.1s R2016b.

Once I make the matrices much bigger, say r = rand(500,1000); and s = rand(1000,1000), the version behave similarly (R2016b even seems to be ~15% faster). Anyone have any insight as to why this is, or can verify this behavior on another system?

I wonder if it has to do with the new arithmetic expansions implementation (if this feature has some cost for small matrix multiplication): http://blogs.mathworks.com/loren/2016/10/24/matlab-arithmetic-expands-in-r2016b/

Thank you

- Adrian

[Walter Roberson]

My testing on my OS-X system shows the times to be pretty much indistinguishable between R2016a and R2016b. I thought at first that R2016b was faster, but repeated executions with

timeit(@() r*s, 0)

showed that the times varied by a lot on the same version and the two could not be reliably distinguished.

[Adrian]

Thank you for following up!

After many tests, I discovered that this difference was not between versions (my apologies).

Instead, it seems to be a difference of what's in my base workspace... and worse, the type of variable that's in the base workspace.

I cleared a huge workspace (which had many large cell arrays with many small, differently sized matrix entries). If I clear the variables and do the timing of r*s, I get much faster runtime (x10-x100) than before the workspace was loaded.

So the question is, why does having variables in the workspace affect the matrix multiplication of two small variables? And even more, why does having certain types of variables slow down the workspace dramatically.

Here's an example where a large variable in cell form in the workspace affects the runtime of the matrix multiplication or two unrelated matrices. If I collapse this cell to a matrix, the effect goes away.

clear;
ticReps = 10000;
nCells = 100;
aa = rand(50,100); 
bb = rand(100, 100);

% test original timing
tic; for i = 1:ticReps, aa * bb; end
fprintf('original: %3.3f\n', toc);

% make some matrices inside a large number of cells
q = cell(nCells, nCells);
for i = 1:nCells * nCells
    q{i} = sprand(10000,10000, 0.0001);
end

% the timing again
tic; for i = 1:ticReps, aa * bb; end
fprintf('after large q cell: %3.3f\n', toc);

% make q into a matrix
q = cat(2, q{:});

% the timing again
tic; for i = 1:ticReps, aa * bb; end
fprintf('after large q matrix: %3.3f\n', toc);

clear q
% the timing again
tic; for i = 1:ticReps, aa * bb; end
fprintf('after clear q: %3.3f\n', toc);

In both staged, q takes up about 2Gb. Result:

original: 0.183
after large q cell: 0.320
after large q matrix: 0.175
after clear q: 0.184

[Walter Roberson]

How much memory do you have? If you are using MS Windows then what is reported by the command

memory

?

[Adrian]

I have 64 Gb of memory, and the variables mentioned above don't get close to filling it up. Also note that if the variable is a matrix of the same bytesize as the cell, the slow-down dissapears. Would it have something to do with how matlab maintains large cells (I assume by keeping many pointers around?).

[Philip Borghesani]

There is something going on here but I am not sure what it is.

• The problem reproduces in a script and function, Even moving the multiply loop into a local function does not seem to make any difference.
• I am having trouble reproducing on Linux but have not yet ruled it out.
• It does seem to reproduce on Win7 and Win10.

[Adrian]

Thanks for checking on your systems.

Yeah, this is perplexing me quite a bit. I guess we need some help from someone who deeply understands how cells are stored, pointed to, and why that would affect other MATLAB variables.

[Philip Borghesani]

In theroy I understand exactly how cells work. My wroking threory is that it has something to do with how the system memory manager is handling the many small allocations used to create the sparse matrices. I experimented with Changing the cell array to hold a normal matrix of approximately the same size and the performance problem went away.

[Adrian]

This is my intuition as well. Unfortunately, each of my small sparse matrices are slightly different sizes.

Of course, I can figure out how to keep them in one long vector by keeping indices around, and that's what I'm doing, but this is rather cumbersome and has its own slow-downs.

Answer 1

[Jan]

When you run the code in the command window, Matlab's JIT acceleration cannot or does not optimize the execution time, or perhaps only partially. The JIT is subject to changes between versions, so I stopped to check this. The JIT identifies variables processed in loops and if they do not change their type, they are addressed faster - at least it looks like, because the JIT is not fully documented. When you have many variables in the workspace and Matlab has to access one, it must search in the lookup table for symbols, to find out, if a symbol is a variable, function, java class, etc. This lookup is time-consuming and a huge workspace can slow this down.

An evil example code:

tic
r = 1;
a = 0;
for i = 1:1000
  a = a + r * rand;
  if rand < 0.0001
    r = @myFunctionWhichReplies_31415
  end
end
toc

Now Matlab has to lookup the symbol "r" in each iteration. Even if this code is included in a function, the JIT cannot avoid this. But without this evil change, the loop is accelerated by recognizing that "r" is always the same array.

As soon as an eval or assignin('caller') modifies the lookup table for symbols, the JIT cannot optimize the code anymore and the speed of loops can degrade substantially. Changing the type of a variable anywhere in the code can impede the acceleration also.

So, this answer does not match the question, but it explains, why running code in the command window with a large base workspace can slowdown the execution such that the observed differences can happen.

[EDITED] As Philip Borghesani has mentioned in the comments: The JIT is developping and not documented. Some of the statements of this answer might concern certain Matlab releases only. It is questionable, if code should be optimized for a specific JIT version, but it is a good practice to try at least not to impede this tool.

[Adrian]

Thanks for your answer!

It seems like I can get it down to the minimum example I added in my update -- basically just one more variable in the workspace -- a large cell array with many small matrices -- is enough to create the slow down in the matrix multiplication. I'm not sure this jives with your explanation since there aren't many variables for MATLAB to look at. Does a similar slowdown make sense given a large cell?

Also, this slowdown happens inside functions as well, not just in the workspace.

[Jan]

Note that the JIT can work only in lines, which contain a single command. In you testr code, the type of q is changed from cell to double. Even if the variable is not used in the loop, the JIT documentation (shipped in older Matlab versions) states, that this will degrade the performance.

[Adrian]

Sorry, I don't really understand that first sentence. Any chance you could expand?

[Philip Borghesani]

Jan, older (pre R2015b) information on the jit most likely does not apply to recent MATLAB versions based on the new execution engine. It is much less sensitive to things like variables that change type and does not fall off a cliff like the previous jit tended to.