Inconsistent assignment time for matrix inside a class

Hi,

My previous question maybe not clear enough. Hopefully this is clearer.

Suppose I have a handle class o with a property o.x, which is a n by n double matrix.

Does matlab gurantee that "o.x(1,1) = 1;" take O(1) time? Or it can take O(n^2) time?

Somehow in my program, sometimes that sentences take O(n^2) time.

Our of many runs of my program, it happens only sometimes and I am not able to produce the example consistently.

See below for more details.

=== Old Version ====

I have a handle class looks like the following:

classdef SlowClass < handle
   properties
      x = zeros(1000,0);
   end
   
   methods
      function append(o)
         o.x(:,end+1) = 1;
      end
   end
end

Sometimes, after enough o.append(), the program becomes very slow. (even when I still have >40GB unused ram.)

When it is slow, I pause the program and run the following in debug mode

tic;
for i = 1:1000
    o.x(1,1)=1;
end
toc;

Elapsed time is 9.414806 seconds. (When the program is fast, in debug mode, this takes microseconds instead.)

However, if I restart the matlab, it becomes normal again (until a long while).

I tried profiling the for loop "tic;for i = 1:1000, o.x(1,1)=1;end; toc;" when it is slow and I get the following as the bottleneck (4 seconds spent on this). I am not sure what is being copying.

% in vcruntime140.dll, it looks like memcpy to me
push rdi
push rsi
mov rax, r11
mov rdi, rcx
mov rcx, r8
mov rsi, r10
rep movsb byte ptr [rdi], byte ptr [rsi]
pop rsi
pop rdi
ret

In my full program, this slowdown happens more consistently. I am still coding my program. Within 1 hour of development and testing, this slowdown usually happens. It disappears when I restart the matlab.

In the toy program above, I am only able to trigger this once for now.

My main question is why?

Observations:

• When the program is slow, the cost of "o.x(1,1)=1;" seems linear to the size of o.x.
• When the program is slow, recreating the object by "o = SlowClass()" does not help.
• If I have two identical class file, one class is slow doesn't imply another class is slow.
• After clear all, the program is fast again.

[Matt J]

I can't reproduce it. What is the size of o.x when the code is "slow"? Also, what version of Matlab?

[Yin Tat Lee]

I am using R2020b. The size is within 3000 x 3000. The trouble is that somehow for the toy code above, it happens only once. In my main program, it happens more, but still very infrequent. If I had a reproducible example, I would just submit a bug report.

I am just hopping to see if someone on internet faces similar issue before.

[Matt J]

How is it possible for o.x to be 3000 x 3000? Your append function only adds columns, not rows.

[Yin Tat Lee]

In my full program, the 1000 in "zeros(1000,0);" is some number depends on the dataset. I try many ways to mechanically reproduce the mistake, but not sucessful. The only sucessful way I know is to continue writing my program and testing.

My workflow is like this:

Finish some modification of the program.

Test it on some script.

Usually the script finishes instantly. It have been a while that it does not finishes instantly with some small probability. But I haven't pay attention until now. Then I play around and realize when I pause the program and run "o.x(1,1)=1;", it is very slow.

I am now suspecting maybe the problem only happens when I am actively changing the code and rerunning the program (i.e. some JIT issue?)

Do you have any idea if I catch this mistake next time and pause the program, how can I debug it?

I tried to save the state and open a new matlab and continue from there. The bug doesn't reproduce.

Answer 1

[Matt J]

When the program is slow, the cost of "o.x(1,1)=1;" seems linear to the size of o.x.

Naturally. Every time you append to x, the original copy of x is destroyed and rebuilt, which involves a number of operations proportional to the size of x. It doesn't matter that you have >40GB. It only matters how long it takes for the original x to be copied.

[Yin Tat Lee]

I am talking about the speed of "o.x(1,1)=1;", not the cost of append.

o.x(1,1)=1; should take O(1) time, and usually it takes O(1) time.

But somehow with very low probability, it takes linear time for some reason.

When that happens, it always take linear time in subsequent run of o.x(1,1)=1;

So, my main question is where is this unpredictability comes from. And the unpredicitability is with very low probability like running the same function millions of time and it suddenly happens, then happens consistently afterward.

Unrelated to my question, but still worth to mention. Appends does not desotry the matrix every time when you append in the last dimension. Matlab will preallocate the matrix like the std::vector in C++.

you can try the following code:

tic;
x = zeros(1000,0);
for i = 1:10000
x(:,end+1) = zeros(1000,1);
end;
toc;

Elapsed time is 0.126009 seconds.

tic;
x = zeros(0,1000);
for i = 1:10000
x(end+1,:) = zeros(1000,1);
end;
toc;

(This takes forever.)

[Yin Tat Lee]

I have changed my question. Hopefully it is more clear.