Analysis and Prediction of Optimal Array Size of Pre-allocation.

Hello,

I am studying the optimization of dynamic growth arrays in Matlab. While I have learnt that pre-allocation(which is the best option) is not possible everytime, I was wondering if there is some way to systematically analyse and detect (or make best guess of) dynamic array growth and estimate the optimal array size for pre-allocation even when the maximum possible size of the array is unknown?

Thank you.

Answer 1

[Cedric]

Depending the nature of your computation, you can get an "analytical estimate", e.g. " memory usage grows like n^2" for a given algorithm.

If you don't have this information, you can try to guess the nature of the relationship between memory usage and dimension or time resolution/range, or both. One way to achieve this is to run the code iteratively increasing the dimension (and/or any other relevant parameters) and plot/fit the memory usage.

When both fail, you can either overshoot the prealloc if possible and cut the extra at the end of the computation (which is generally fine for short-lived computations), and/or prealloc by block (in theory).

To illustrate the first situation, if you know that a vector resulting from an iterative computation should be filled with, say between 1e7 and 1e8 elements, you can prealloc for 1e8 or even 2e8 elements (to be sure) and reduce the vector to the actual number of elements after the computation (instead of iteratively increasing its size).

To illustrate the second situation, if you cannot overshoot the prealloc, you can perform an initial prealloc of e.g. 1e6 elements, and then extend it by 1e6 elements each time it is needed (or increase the size by a given factor, e.g 1.25, 1.5, 2, etc; see note 2). Doing so, you have n(extensions) << n(elements), which increases the efficiency in theory (see note 1).

Note 1: the extension by block is quite slow in MATLAB in practice, even slower than not preallocating (which is not what I get in other languages/contexts). I would be interested to have an explanation about that.

Note 2: I don't know what was the depth of your question, but if you were thinking about how the JIT optimizes memory management internally (e.g. 1.25 to 2 growth factor for realloc() operations, and not how to manage "preallocation" at a user level), you might want to contact Mathworks. I found some information about other languages here (and references therein):

• http://stackoverflow.com/questions/1100311/what-is-the-ideal-growth-rate-for-a-dynamically-allocated-array
• http://en.wikipedia.org/wiki/Dynamic_array

but nothing about how it is done internally in MATLAB and whether it is worth caring about optimal growth factors (for reuse) at a user level.

[Sridipta]

Hey Cedric,

   Thanks for you response. It was helpful but I am not sure it that answers the problem that I have at hand. I need to,

1. Develop an analysis to detect dynamic array growths; 2. Estimate the optimal size of a growing array;

So I guess I need to delve a little deeper and investigate how exactly the compiler does the detection of a growing array and estimation of optimal size. Could you help me in this direction?

Thanks.

[Cedric]

Hi Sridipta,

Ok, so you need the more in-depth version of what I wrote. Actually, what I know is essentially described on Undocumented Matlab (by Yair Altman) in the following pages (it is even there that I got all the information that I have on the topic, because I could find it absolutely nowhere else):

• http://undocumentedmatlab.com/blog/preallocation-performance/
• http://undocumentedmatlab.com/blog/array-resizing-performance/
• http://undocumentedmatlab.com/blog/internal-matlab-memory-optimizations/
• http://undocumentedmatlab.com/blog/matlabs-internal-memory-representation/
• http://undocumentedmatlab.com/blog/profiling-matlab-memory-usage/
• http://undocumentedmatlab.com/blog/undocumented-profiler-options/

If you look at what Yair is doing, he is testing very thoroughly and thoughtfully the system's behavior/response time/etc. As I wrote in my previous answer though, if you need answers about what JIT comp. and any other internal feature do effectively (and not benchmarking methods/results), I guess that you'll have to contact Mathworks. I also occasionally see people from Mathworks on this forum, who seem to be working on MATLAB internals; who knows, they might see this thread as well!

[Sridipta]

Hey Cedric,

Thanks a ton. Will get back to you if I need any more assistace! :)