Can anyone explain why Matlab gets slower and slower until restart if large cell or struct arrays are allocated and cleared repeatedly, but only on Windows, not Linux?

I am experiencing a serious performance problem with some matlab code that I have simplified with the attached example. I would appreciate any help in explaining how to avoid or workaround this issue, and also anyone who can run my example and confirm that they see the same result. I am very surprised at how badly this affects performance and how simple it is to reproduce (How many people are suffering from this unknowingly?). Here are some properties of this issue I've noticed:

1. execution time increases fairly linearly with each reinitialization of a large cell array or struct array.
2. execution time remains slow until Matlab is restarted.
3. execution time of other unrelated code with different variables that also meet the criteria is affected until restart.
4. Only occurs if both the cell or struct array containers are large enough (around 2000 elements or more)
5. Only occurs if each cell element or struct array element contains a large matrix (around 200 x 200 or more)
6. Only occurs on Windows (Linux runs the same example code without issues). I am using Windows 7 64 bit (16GB ram)
7. Occurs on all recent versions of Matlab that I have tried (R2015b through R2017a)
8. Occurs in a script (See SlowingExecutionIssueSimple.m or the code pasted below)
9. Occurs in a function, but with slightly different conditions. Does not occur if the variable is persistent for certain initialization methods. Occurs if the variable is not persistent regardless of initialization method. See SlowingExecutionIssue.m for easy testing of all these cases.
10. After many iterations of the outer loop, the growth in execution time eventually seems to level off, but at a completely unusable level of performance compared to the first iteration.
11. Occurs even with fully preallocated arrays (in some cases, it occurs especially if fully preallocated - see struct array example in SlowingExecutionIssue.m for case where incomplete preallocation avoids this problem)
12. "clear all" and "clear classes" have no effect.

Thanks in advance for any help with this. So far I have only been able to work around it in my application code by making variables persistent inside a function and avoiding reinitialization (i.e. reinitializing only one element at a time inside the innermost loop). It is not always possible to work around it and requires constant use of the memory that could otherwise be freed. Is this a bug in how Matlab manages memory?, or an unavoidable side effect of windows memory management? If it doesn't get fixed soon, I may have to switch permanently to Linux to avoid this issue.

iter = 10000;
for i = 1:10
    tic;
    a0 = ones(221,241);
    a = a0;
%     c=cell(iter,1);%Cell array example. The problem only occurs if c is reinitialized each time
    f = repmat(struct('a',a),1,iter);%Struct array example. Struct array with all elements populated with "a"
    for j=1:iter
        %a has to change each iteration or the issue doesn't show up
        a=a+1;%Change the variable
        a=a-1;%Change the variable back to original value
%         c{j}=a;%This causes serious slowdown with each run
        f(j).a = a;%This causes serious slowdown with each run
%         c{j}=a0;%This runs fast even though a0 is identical in size, type, and value to a
%         f(j).a = a0;%This runs fast
    end
    toc
end

Here is the output I get from this script:

>> SlowingExecutionIssueSimple
Elapsed time is 1.227035 seconds.
Elapsed time is 1.336831 seconds.
Elapsed time is 1.349026 seconds.
Elapsed time is 1.426942 seconds.
Elapsed time is 1.568531 seconds.
Elapsed time is 1.779247 seconds.
Elapsed time is 2.051785 seconds.
Elapsed time is 2.412232 seconds.
Elapsed time is 2.857880 seconds.
Elapsed time is 3.500180 seconds.
>> clear all
>> clear classes
>> SlowingExecutionIssueSimple
Elapsed time is 2.254901 seconds.
Elapsed time is 4.609098 seconds.
Elapsed time is 5.811552 seconds.
Elapsed time is 6.322061 seconds.
Elapsed time is 6.974427 seconds.
Elapsed time is 7.242437 seconds.
Elapsed time is 7.527272 seconds.
Elapsed time is 7.704636 seconds.
Elapsed time is 8.079658 seconds.
Elapsed time is 8.315676 seconds.
>>

Answer 1

[Jan]

With 20 iteration I get (Matlab R2016b/64, Win7, Core2Duo, ):

 Elapsed time is 12.796962 seconds.
 Elapsed time is 5.915845 seconds.
 Elapsed time is 4.910906 seconds.
 Elapsed time is 4.819912 seconds.
 Elapsed time is 5.078799 seconds.
 Elapsed time is 5.410653 seconds.
 Elapsed time is 5.353264 seconds.
 Elapsed time is 5.862806 seconds.
 Elapsed time is 6.867665 seconds.
 Elapsed time is 7.050129 seconds.
 Elapsed time is 7.989765 seconds.
 Elapsed time is 9.024225 seconds.
 Elapsed time is 10.223250 seconds.
 Elapsed time is 11.062545 seconds.
 Elapsed time is 11.918006 seconds.
 Elapsed time is 12.276263 seconds.
 Elapsed time is 12.650565 seconds.
 Elapsed time is 12.974336 seconds.
 Elapsed time is 13.291335 seconds.
 Elapsed time is 13.585811 seconds.

After

clear all
pack

th results are:

 Elapsed time is 7.361198 seconds.
 Elapsed time is 14.111978 seconds.
 Elapsed time is 14.360832 seconds.
 Elapsed time is 14.552819 seconds.
 ...  stable timings

This looks like a problem of the memory manager of the OS.

[EDITED] 10 iteration in R2009a:

 Elapsed time is 3.651902 seconds.
 Elapsed time is 4.155962 seconds.
 Elapsed time is 4.235177 seconds.
 Elapsed time is 4.178624 seconds.
 Elapsed time is 4.218829 seconds.
 Elapsed time is 4.560025 seconds.
 Elapsed time is 4.319851 seconds.
 Elapsed time is 4.316553 seconds.
 Elapsed time is 4.300376 seconds.
 Elapsed time is 4.294655 seconds.

Well, I admint: Not a problem of the OS, but of Matlab's memory manager.

[Philip Borghesani]

It does appear to be the Windows memory manager. It reproduces for me on all MATLAB versions including R2009a and R2008a and on Windows 7 and 10. Linux seems to be fine. When profiled almost all time is in Windows heap functions including ntdll.dll:RtlpAllocateHeapInternal and RtlFreeHeap.

This stack overflow conversation suggest others similar results and has more experiments and comments: stack overflow link

[RR]

Thanks Philip and Jan for taking time to reproduce it. Good to know it's not just me. I was hoping it might be avoided by going to windows 10, but apparently not based on your response, Philip. I submitted a support request also and am waiting for any workaround. So far they have also reproduced the issue. How has this not been brought up before? the Stack overflow link does seem to be the same sort of issue. According to that, it may be partly avoidable with different compiler toolchain and/or different memory allocation and freeing procedures. I suppose for Matlab that would mean Mathworks developers rewriting some code deep in the core of how matlab manages memory, or building core matlab engine components with a different compiler? That doesn't seem like a quick fix that will be coming anytime soon. I wonder if there are any workarounds that can help avoid it other than using persistent variables. I wonder if matlab coder generates code that behaves any differently.

[Philip Borghesani]

The only likely solution for you is going to be to change how your code uses memory or stop using Windows. Using smaller or larger blocks of memory should make the problem go away. Is there any chance chunks of your data can be stored in (m,n,count) 3d arrays?. Changing the order of operations or minimizing allocation operations may reduce the problem. Our spending time optimizing your example probably won't be helpful to you. If you post more information about your actual code/problem you are trying to solve and information about what operations are slow then we may be able to give suggestions on how to re-architect things for better performance.

I find it likely that the comments on changing compilers in the stack overflow posting are incorrect. The MATLAB versions I tested were built with many different versions of Visual Studio including VS2015. The profiling I did showed the time to be in the NT kernel not the c run time library. One other option would be to post a bug report to Microsoft with example code similer to that in the Stack Overflow posting but I would not expect a resolution from them any sooner then MATLAB can fix the problem.

As an example I believe the following code does the essentially the same operations as your original code but has no slowdown. A cell array or object implementation could hide the gory details.

iter = 10000;
blocks=10;
numblocks=iter/blocks;
for i = 1:10
    tic;
    a0 = ones(221,241);
    a = a0;
    clear f
    f(1,1:numblocks)=struct('a',repmat(a,1,1,blocks));
    for j=1:iter
        %a has to change each iteration or the issue doesn't show up
        blocknum=floor(iter/blocks)+1;
        blockidx=mod(iter,blocks)+1;
        a=a+1;%Change the variable
        a=a-1;%Change the variable back to original value
        f(blocknum).a(:,:,blockidx) = a;
    end
    toc
end

[RR]

Thanks for taking the time to post that example. My actual application is really very similar to my example script. I have both 2D and 3D versions of it, the 3D being the more important final product. Either way, I have a 2D or 3D grid (this is the 221 x 241 matrix in the example) of data that is updated once per time step. Each time step's result is the starting point for the next time step's grid, and it must be stored at each time step for later analysis. (the loop of 10000 iterations of j represents the time steps). The outer loop represents each time I need to run my application, which will be in a continuous loop running as close to real time as possible. I could implement it as in your example, except that I think you meant the "iter" argument in the floor and mod calls should be j so that those are changing through the whole range of memory that f spans. With that change, it still avoids the slowdown issue, but it takes about 3 times longer than the best workaround I've found so far, which is the persistent variable case in the SlowingExecutionIssue.m script I originally posted. In my real code this is also a function, which is why I have to make f persistent in order to avoid clearing and reallocating it every call. I'm not really sure why your workaround is slower, except possibly the additional indexing that must happen in the a(:,:,blockidx) = a syntax? The whole point of my application is to accelerate processing vs. other slower implementations of the algorithm, so the slowdown that comes from the higher dimensional indexing is a huge deal. That's why a struct array (or have tried cell array with similar results) is being used in the first place, because it was the fastest vs. a large 3D matrix for 2D + time, or 4D matrix, for 3D + time. I tried a variation on your blocks idea using a struct array of struct arrays, with the outer array holding blocks and inner array the elements of each block. That didn't work (same slowdown issue). I guess because it is still one large object holding everything. Maybe if I use completely different variable names to hold each block? That would sure be a mess to keep track of, though. Any ideas for applying your concept without the indexing overhead?

[RR]

I am attaching another script and output file that explore variations in the array size that is being stored in the each struct array element. It seems that that array size is the driving factor. original example used a 221 x 241 array with about 53000 elements. If I store the same amount of data, but arranged in smaller chunks with a longer struct array, or the other way around, there is no problem, even though the total data size is the same, and even though is is still all stored in a single struct array. if the underlying array has 10000 elements, not only does it not have the problem, but if run first before changing back to the problematic 50000 element size, it actually prevents the problem. The exact same two sizes run in the opposite order from a fresh matlab start immediately show the slowdown issue. larger sized arrays are also fine, like 500000 elements. That is why your example of breaking the data into blocks worked. But it wasn't breaking it up into blocks that was the key, instead it was that the array was 10 times larger due to the 3rd dimension being used as the block index. I tried the exact same idea but using separate variables for the blocks and the same array size and it made no difference (Had exactly the same slowdown behavior as if it were all in one larger struct array). The only thing that really matters is the underlying array size. The part that is really weird is how running with one size first can prevent the issue when run with the problematic size afterwards. Any explanation for that? (and it has to be a certain size to have that effect - very small (2000) or very large (500000) have no slowdown, but also no prevention effect. 10000 prevents the issue for 50000. Feel free to take a look at the attached script and output to see what I mean.

[Philip Borghesani]

Yes, it is the underlying block size and number of blocks that makes a difference sorry I did not make that clear enough in my other postings. The number of elements in a cell array or structure will have little impact unless it is huge, no need for multiple variables. Performance of structures and cells should be nearly identical they have essentially the same underlying implementation.

The large size cut off seems to be one megabyte and things get worse as your data size approaches a megabyte. Your observations on the effect of the order of operations is interesting, that was something I wanted to explore but had not yet. I would like to investigate this further and think that by putting your processing code and the data into a handle class object or by just passing around your data store (f) as input and output to the processing function you can avoid the persistent variable. Unfortunately I won't have time to investigate further for a few days.

I think there are a couple of mistakes in your original test code that might have given you misleading ideas: f was never persistent due to repmat line, the array would have been much faster as d(:,:,j) then d(j,:,:) due to memory layout issues.

[Philip Borghesani]

Here is an example that runs fast and does not show the performance problem. Note that both functions must be functions, scripts disable the in place optimization. Using a 3d array for buffer is not bad ether. There are a couple of tricks in the code to allow assignment in place with no allocations for the line t=t*0+a;

 function faster2
 iter = 10000;
 buffer{iter}=[];
 for i = 1:20
    tic;
    a0 = ones(221,241);
    buffer=doit(iter,a0,buffer);
    toc
 end
 end
 function c=doit(iter,a,c)
    for j=1:iter
        %a has to change each iteration or the issue doesn't show up
        a=a+1;%Change the variable
        a=a-1;%Change the variable back to original value
        t=c{j};c{j}=[];  
        if isempty(t)
            t=a;
        else
            t=t*0+a;
        end
        c{j}=t;
        %c{j}=a;%Not too bad but could be better
%         if isempty(c{j})  %is also ok
%             c{j}=a;
%         else
%             c{j}(:)=a(:);
%         end

    end
 end

[RR]

Wow, I see that it works, but I have no idea why. I can see that the buffer is created once and left in place, but can you explain why the tricks work? Is there any hidden documentation that explains this black magic? I see that t=a; does not work like t=t*0+a;, which is quite unintuitive. I also see that without the c{j} = []; and the intermediate storage in t it doesn't work either. What is going on here? Also is it implicit pass by reference of the buffer into doit?

[Philip Borghesani]

If you search around for MATLAB hints and tricks you can find details on most of them.

Basic concepts to get you started.

• MATLAB always passes everything by reference and does copy on write.
• When the same variable is assigned by a function or operation and passed into it from a function then modifications can be done in place and no copy on write is needed. Loren's Blog on in place operations
• The trick with t is because the in-place optimization does not currently work for a cell in a cell array. Clearing the cell is needed to release the second reference to the array that was "moved" to t.
• The multiplication by zero is to allow t to be passed into the scalar operation allowing its buffer to be reused. Actual multiplication is so fast compared to memory access and allocation that its cost is irrelevant.

[James Tursa]

"... MATLAB always passes everything by reference and does copy on write. ..."

Almost always. There are some circumstances (which escape me at the moment) where MATLAB will pass a deep copy of scalar arguments.